[gclist] ref-counting performance cost

[Boehm, Hans]

> -----Original Message-----
> From: Simon Peyton-Jones [mailto:simonpj@microsoft.com]

> Finally, there's the locality issue.  Contiguous allocation improves
> locality.
> Compaction improves locality.  On the other hand, reference counting 
> re-uses hot addresses.  So it's entirely unclear to me what 
> the tradeoff
> in cache effects is.
> 
I agree that contiguous allocation improves locality.  But nonmoving
mark-sweep collectors also often allocate contiguously in this sense.  And
even reference counters may.  Many applications seem to have sufficiently
regular allocation behavior that large regions get deallocated and reused at
once, causing free lists to often contain contiguous objects.  I'd love to
know to what extent this is true for large real applications.

It's also unclear whether fully contiguous allocation is better or worse
than segregating allocation requests by size.

I'm sure we agree that the compaction process itself has terrible temporal
locality, and may easily dominate the cache misses/page faults generated by
a program.  (It is likely to have good spatial locality, but that doesn't
help much, you still need to suck two copies of the whole generation/heap
through the cache.)  I believe that many JVM implementors have discovered
this the hard way, and modern JVMs tend to be much more careful about
minimizing the amount of compaction they do.  (This isn't much of an issue
if you're scavenging a mostly empty nursery.  It is a big issue if you
compact the entire heap, or if the client doesn't allocate enough
short-lived objects.)  The trick is to balance this cost against compaction
benefits.

Whether compaction helps mutator locality (aside from wiping out its working
set to do the compaction, if it wasn't already gone), probably depends on
how the compaction is done.  I would guess that a breadth-first Cheney copy
is usually worse than not compacting, though I don't recall any
measurements.  Breadth-first traversals by the mutator are not very common.
Sliding compaction should always be a win, assuming you do no damage to
object alignment.

Hans