Branden wrote:
> I actually don't understand how traversing a graph can be faster than
> incrementing/decrementing/testing for zero on a refcount.
There are two main reasons advanced garbage collectors are fast:
1. Cheap allocations. Most fast collectors have a one or two
instruction malloc. In C it looks like this:
void *malloc(size) { void *obj = heap; heap += size; return obj; }
It's easier to do alignments in a macro layer above the allocator
so the allocator doesn't have to constantly re-align to address
boundaries. There is basically no difference between the performance
of heap and stack allocations with a good collector.
2. Work proportional to live data, not total data. This is hard to
believe for a C programmer, but good garbage collectors don't have
to "free" every allocation -- they just have to preserve the live,
or reachable, data. Some researchers have estimated that 90% or
more of all allocated data dies (becomes unreachable) before the
next collection. A ref count system has to work on every object,
but smarter collectors only work on 10% of the objects.
- Ken
