Re: Fast allocation vs lightweight collection

On 08/26/03 David Jeske wrote:
> On Tue, Aug 26, 2003 at 08:59:02AM +0100, Torstensson, Patrik wrote:
> > Not really true. The cmpxchg (and other) will lock the CPU cache (or
> > cause a cache invalid signal to happen) on a x86. This causes serious
> > performance problems 
> 
> > (it's better than a kernel lock but still..)
> 
> That is quite an understatement. I don't have a manual handy to look
> up the numbers, but my gut ballparks that the kernel context switch,
> probable TLB flush, plus the cache invalidation which is required for
> the kernel locks anyhow will come in at over 10x of the cost of L1/L2
> cache invalidation alone in overall performance cost.

There is no need to go with kernel-based locks, a spinlock would be
sufficient if there are no suitable atomic instructions or sequences
available for a platform. Still, even if there isn't a function call
with 'lock' in the name, the atomic instructions are expensive
and they add up to the speed overhead that thread-unsafe reference
counting already has.
There is also branch prediction trashing before each inc/dec, since you
need to make sure the reference is not NULL.

> I think we have a disagreement about what it means to be "very
> expensive". The 1 second worst case pause time of most "modern" GC
> systems is very expensive to me. It usually means I can't write
> software with them and have to resort to C, C++, or a ref-counted
> system like Python. I don't mind a 10%, 20% or sometimes even 30%
> performance hit, as long as it is spread evenly throughout the
> program.

Many disagree with you on the price people is willing to pay, but fear
not: this is free software and proving your point is just a SMOP:-)
You can start adding an integer counter to the MonoObject struct in
metadata/object.h and adding the proper atomic inc/dec instructions
whenever a reference is written or read.

> For me, ANY pausing scheme is "very expensive", and ANY incremental
> scheme with bounded worst-case pauses is acceptable.

I guess you mean unbounded? Reference counting can have unbounded delays
when deallocating, too, though I agree they can be more 'unlikely'.

> Compared to other incremental schemes, reference counting adds some
> cost to the mutator in exchange for greater throughput when memory is
> being turned over quickly.
> 
> The write-barrier of a tri-color scheme is possibly less costly, but
> yeilds more work for the incremental collector to do.

I think the first steps to do if we want to improve or experiment with
the GC in mono are these:
*) make sure we can identify precisely all and only the managed
pointers, in the heap, the stack and the registers. This alone is a big
task. A tweaked libgc that moves the objects around randomly at each 
collection can help to shake out the bugs.
*) define an interface for pluggable GCs, so that anyone can get to
experiment with thier preferred GC model.

As I see it, implementing the actual GC algorithm is the easy part
and can only be done after the first step is accomplished.

lupus

-- 
-----------------------------------------------------------------
[email protected]                                     debian/rules
[email protected]                             Monkeys do it better
_______________________________________________
Mono-gc-list maillist  -  [email protected]
http://lists.ximian.com/mailman/listinfo/mono-gc-list