GC performance - was Re: [gclist] GC topics

[boehm.PARC@xerox.com]

"[Darius:]
> - While it can be a pragmatic issue, I don't believe that the ability
>   to plug a GC in an existing system tells much about how easy it
>   can be to implement one.
[David:]
As it happens, it is also easy to write a conservative GC."

Though I agree with David in spirit, I would have stated it a bit differently.
It's easy to write a simple fully conservative garbage collector.  I've never
seen Doug McIlroy's collector built on top of malloc, but I think it was only a
few hundred lines.  It's also easy to write a simple precise copying GC,
assuming you ignore interactions with the runtime system and the outside world.
Based on what I've seen neither one will perform all that well.  They both will
exhibit unacceptable pause times for large amounts of live data.  In addition,

The copying one will:
- use too much memory, since it will touch twice as much VM as there are live
objects at every collection.  It will need considerably more physical memory
than that to avoid paging and to keep GC frequency down.

The conservative one will:
- be limited to one platform.
- accidentally retain too much memory with unpleasantly high probability.
- incur unnecessarily high allocation and collection overheads, especially for
small objects.
- touch too much VM during collections, though it won't be as bad as the
copying one.

Getting good performance out of either requires work.  To really take advantage
of the extra information, your precise collector probably should have both a
copying collector for young objects and a (primarily) nonmoving collector for
old objects.  Your conservative collector should have its own allocator, keep
track of known false references, etc.  Both need to operate incrementally for
full collections, etc.

All of this also greatly complicates performance comparisons between
algorithmic approaches.  It's not hard to get a factor of 2 or more performance
difference depending on how much bit-twiddling has gone into the collector
implementation.

Hans
Standard disclaimer ...