[gclist] why malloc/free instead of GC?

Boehm, Hans hans_boehm@hp.com
Tue, 18 Feb 2003 10:45:13 -0800

> From: Charles Fiterman [mailto:cef@geodesic.com]
> If you have mark and sweep or moving collection at some point your 
> application will become so large that collection time causes 
> you to violate 
> it no matter how many CPU's you add. You must have a way to 
> distribute free 
> operations and not run them all at once.
Why?  All evidence I've seen suggests that

a) Heap sizes grow roughly with memory access speed.  The amount of time it takes to touch or trace a "large" heap on a "fast" seems to stay roughly constant over the years, even though the meaning of "large" and "fast" changes.

b) Tracing collection scales quite well with processor count.  I haven't done the measurement, but I strongly suspect that you can buy a machine that will collect a 10GB heap with 50% pointer-full-object-occupancy in under a second.  (It won't be a cheap machine, but ...)

> Reference counting also has the advantage that the 
> destruction of objects 
> can have rational finalizers. Finalizers must be safe, general, sure, 
> prompt and ordered. Safe means they don't violate the type 
> system. General 
> means finalizers can run any code in the language and have that code 
> produce normal results, for example exceptions can't just get 
> discarded. 
> Sure means if you build an object it gets to destroy itself. 
> Prompt means 
> finalizers aren't indefinitely postponed. Ordered means 
> finalizers run in a 
> determined order, if you ship the application you don't 
> change the order 
> creating portability bugs.

I don't know how to get "prompt"ness and "sure"ness guarantees without running finalizers synchronously in the thread dropping the reference.  That's "safe" in your sense, but it's unsafe in that it can result in spurious deadlocks and/or similar problems.  Hence it's highly undesirable.  For details, see my 2003 POPL paper (http://portal.acm.org/citation.cfm?doid=604131.604153 or http://www.hpl.hp.com/techreports/2002/HPL-2002-335.html ).