Home

Safe Garbage Collection = Regions + Intensional Type Analysis

Safe Garbage Collection = Regions + Intensional Type Analysis, by Daniel C. Wang and Andrew W. Appel:

We present a technique to implement type-safe garbage collectors by combining existing type systems used for compiling type-safe languages. We adapt the type systems used in region inference [16] and intensional type analysis [8] to construct a safe stop-and-copy garbage collector for higher-order polymorphic languages. Rather than using region inference as the primary method of storage management, we show how it can be used to implement a garbage collector which is provably safe. We also introduce a new region calculus with non-nested object lifetimes which is significantly simpler than previous calculi. Our approach also formalizes more of the interface between garbage collectors and code generators. The efficiency of our safe collectors are algorithmically competitive with unsafe collectors.

I'm surprised this region calculus hasn't received more attention or follow-up discussion in subsequent papers. It seems eminently practical, as it replaces the more complicated alias analyses required in other region calculi, with garbage collection of region handles; seems like a huge improvement over general GC, assuming region inference is sufficiently precise.

By naasking at 2009-10-11 20:47 | Implementation | Software Engineering | Teaching & Learning | other blogs | 10713 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

See Fluet & Want's follow-on

You may be interested in some follow-on work by Matthew Fluet and Dan Wang where they implemented a Scheme system, including a GC, in Cyclone (a type-safe dialect of C).
See here for more details.

By Greg Morrisett at Tue, 2009-10-13 19:04 | login or register to post comments

Indeed, an interesting paper

Indeed, an interesting paper that I read at one point. Great to see an application of these compelling ideas in language research.

I haven't found any other systems that garbage collect region handles as Appel's paper suggests though. It would seem to be a decent compromise on the full static analysis for full region safety for a practical language, and such a GC is considerably simpler than that required for tracing arbitrary language structures.

The only other similar papers that suggest dynamic checks deal with explicit memory management with regions, and ref-counting region handles to identify when they are safe to delete.

By naasking at Tue, 2009-10-13 19:56 | login or register to post comments

Benefits?

I read the introduction to the paper, but as far as I can tell the only advertised benefit of this [set of] techniques is that it reduces the likelyhood of the garbage collector being buggy.

I have never heard of a production system crashing due to a faulty garbage collector. I presume this is a rare class of bugs.

Given the complexity of the approach, I wonder if there are any other benefits - for instance can any of these ideas be used to increase the efficiency of garbage collection? I have heard of (and seen) LOTS of production systems experiencing problems due to excessive GC load.

By Mike Hearn at Wed, 2009-10-14 17:22 | login or register to post comments

Improving GC is exactly what

Improving GC is exactly what I had in mind. Unless I missed something, such a region design means that all data structures need not be traced at runtime, only the live region headers are traced, which consists of those regions specified in the "only" term of the region calculus. The rest can be freed in bulk. This is a significant reduction in data, and much friendlier to virtual memory in particular. The complexity is the addition of a region type system, and region inference.

By naasking at Wed, 2009-10-14 18:11 | login or register to post comments

OK, that sounds good.

The paper didn't talk about playing better with virtual memory or shortening pause times, but it makes sense that these would improve. I wonder why .... perhaps the authors are just being conservative, or perhaps they haven't been able to measure it on a realistic workload. I'll read the full paper when I get a chance, thanks for the link.

By Mike Hearn at Wed, 2009-10-14 18:42 | login or register to post comments

It didn't discuss those

It didn't discuss those advantages because they are advantages of all region-based memory management. Most other such systems are more complicated because they attempt to prove static safety in the presence of aliasing, where this one resorts runtime checks.

By naasking at Wed, 2009-10-14 19:29 | login or register to post comments

Statically proving safety is

Statically proving safety is basically impossible in any pluggable architecture... especially with these AOP DI containers.

By Z-Bo at Thu, 2009-10-15 15:30 | login or register to post comments

Statically proving safety is

Statically proving safety is basically impossible in any pluggable architecture... especially with these AOP DI containers.

I wouldn't say that necessarily. As long as it supports separate compilation, safety becomes tractable. See the ML Kit for instance, where they managed to integrate regions with ML modules.

By naasking at Thu, 2009-10-15 16:12 | login or register to post comments

One of my favorite talks was

One of my favorite talks was from Emery Berger about work he did with some MSR folks (I'm guessing Ben Zorn -- DieHard?) on dealing with faulty memory: run the program with multiple instances of a call using random allocators and then vote (also a technique against buffer overflows and I think some other basic use cases).

The funny part was when they dropped their new collector into various apps for performance testing -- some broke. Perplexingly, their code was fine. If I remember right, I think they found cases where programs became dependent upon these bugs: it would not be backwards compatible to fix the GC!

By lmeyerov at Thu, 2009-10-15 11:13 | login or register to post comments

understanding non-deterministic acquisition/release of resources

I think they found cases where programs became dependent upon these bugs: it would not be backwards compatible to fix the GC!

I am guessing these are RAII failures associated with not understanding these VMs all use non-deterministic finalization...?

By Z-Bo at Thu, 2009-10-15 15:25 | login or register to post comments

I don't think so, but really

I don't think so, but really don't remember. I think they found more cases where the GC had an invariant in practice (memory not moving, or at least up to a certain point) that legacy programs relied upon.

Anyways, while scouring the net for bug reports of CSS layout not terminating (!!!), I came across another GC bug report: http://izumi.plan99.net/blog/index.php/2009/04/10/hunting-down-obscure-gc-bugs/

OTOH, I've got to wonder -- would directed random testing be a heck of a lot more effective? E.g., David Molnar's whitebox fuzz testing. Clearly not in some domains, but for many cases (e.g., Java)...

By lmeyerov at Sun, 2009-10-18 08:04 | login or register to post comments

Buggy GC

I have never heard of a production system crashing due to a faulty garbage collector. I presume this is a rare class of bugs.

It's rare because people put a lot of work into making their garbage collectors trustworthy. Research on provably correct GC is meant to make it possible to produce more trustworthy collectors with less work.

By John Stracke at Thu, 2009-10-15 15:38 | login or register to post comments

YMMV

> I have never heard of a production system crashing due to a faulty garbage collector. I presume this is a rare class of bugs.

Rare?
Not so much: Java's GC (a long time ago) had a bug which removed objects held only by static references.
And any imprecise GC (such as the Boehm GC which is widely used) can become ineffective for some programs which have lots of data (failing to deallocate most of the unused memory)..

So it's only rare because one tend to test a program before using it in production and if the GC doesn't work well then you workaround the issue..

By renox at Fri, 2009-10-16 15:35 | login or register to post comments