[gclist] Garbage collection and XML

Boehm, Hans hans_boehm@hp.com
Thu, 8 Mar 2001 14:31:41 -0800

> In a multi-threaded world, mutability also has
> the annoying overhead of synchronization (for a competently
> designed memory allocator, synchronization on a multiprocessor
> can be 10-20 times as expensive as allocation (*)).  Sure,
> mutable data structures are great for programming in the
> small, but build something big, and they become a major
> pain, and given the overheads they're not necessarily any
> faster.
I agree with the general conclusion, but you need to be careful about the
costs.  Reallocating objects along a path in a large applicative data
structure tends to involve allocating and dropping relatively long-lived
objects.  I suspect the garbage collection costs will outweigh the
allocation costs by a fair margin, no matter what garbage collector you use.
(This might not hold if you can keep the heap very sparsely occupied.  But
even then the allocation cost wil be dominated by the cache miss to first
write to the object.)

But sharing can still be a huge advantage of the applicative data structure.

> (*) non-recursive synchronization costs two bus locks,
> or (my machine, with cpu clocked 6x memory bus) 120 cycles.
> Heap memory allocation is load, add, compare, conditional
> branch (predicted not taken), store, store, followed by
> field initialization.
Is that an X86 machine?  I just timed a Pentium III/500/100 machine at
something near 25 cycles per
"lock; cmpxchgl".  I'm interested because I've sometimes heard the claim
that X86 is particularly bad at this, but that hasn't really been consistent
with my experience.  Is this chipset dependent, perhaps?