Re: copying vs. mark-sweep gc's; more gc biblio; funny

wilson@cs.utexas.edu (Paul Wilson) writes:
...


>I think Zorn makes a very important point that mark-sweep gc's needn't be
>much less efficient than copying gc's. As Appel has pointed out, copying
>collectors don't have to expend any CPU cycles dealing with
>garbage---garbage is reclaimed implicitly by moving the LIVE data
>somewhere else. So as memory gets bigger, it gets more efficient... in
>theory.


>Even though copying is asymptotically more efficient, the actual constants
>involved may dominate. The cost of maintaining the "free list" of
>available space can actually be quite small for a non-copying gc. (Keep
>in mind that if you use a bitmap instead of an actual free list, you can
>put 32 words "on the list" by storing a single zero into a 32-bit word of
>the bitmap.)


...


I agree with almost all of Paul's posting, but I'll pick on this part
anyway. The argument about mark-sweep collectors being asymptotically
less efficient then copying collectors has been repeated in the literature
many more times than I can remember. Unless you define "mark-sweep"
collection to be limited to particularly stupid algorithms, I believe the
argument is just plain wrong.


The argument is obviously wrong if you include allocation and
initialization overhead in the garbage collection time. Even a copying
collector will touch garbage objects in the heap - for example, the next
time they're allocated.


So let's assume that we're including only garbage collection time. (It's
not clear to me that this makes any sense, especially since it seems
easier to build good concurrent mark/sweep collectors than copying
collectors, and it's not clear what this means in the presence of
concurrency, but no matter ...) Now let's assume, as Paul suggests, that
the free list is represented as a bit map. Let me further assume that I
keep the mark bits contiguously in a separate region of memory. (This is
practically desirable for VM reasons in any case.) I then mark all
accessible objects. This takes time proportional to the amount of LIVE
memory. The sweep phase then takes ZERO additional time; the mark bits
ARE my free list. (There are various data structures tricks that I can
use to avoid clearing the mark bits. In practice that doesn't matter
anyway.)


Even with a traditional free list data structure, it's easy to perform a
little bit of the sweep phase at each allocation, since the sweep phase
doesn't have to worry about mutator interaction.


One might object that allocation can theoretically take a long time with
either of these schemes. This is again a data structure problem that can
be overcome. Henry Baker has a solution that avoids this problem by
keeping all objects on one of several doubly linked lists. It can be used
to get O(LIVE) marking time and O(1) allocation time (assuming separate
pools of fixed size objects). (Henry Baker uses this to get a real-time
nonmoving collector. I'm not sure whether the algorithm has been
published yet.)


Granted, copying collectors do have some performance advantages. But as
Paul said, the constants are what matters. I don't believe that a M/S
allocator could keep up very well with SML of NJ allocation rates. But
I'm also completely unconvinced that copying very old objects makes sense.
I don't think the trade-offs are obvious.


Hans
(boehm@parc.xerox.com)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.