Re: Fast allocation vs lightweight collection

On Mon, Aug 25, 2003 at 12:33:48PM -0400, Michel Dagenais wrote:
> One very important point that did not come out in the discussion is the
> interaction between garbage collection and multi-threading. 

This is a good point. Multi-threaded applications make the GC pause
problem much more important. In a single threaded application, there
are sometimes reasonable moments to manually pause. However, in a
multithreaded app there is seldom a time where all of the threads
simultaneously reach a state where they will accept a pause. For
example, in a single threaded webserver, you can garbage collect after
you have finished rendering a page to the user, before you accept the
next one. However, in a multi-threaded webserver under load
(i.e. tomcat), all threads will never finish rendering page at the
same time, making any pause disruptive.

This is why I like the old architecture of mod_mono better than the
new single-process model. The single process model is going to pause
all threads to GC, while the multi-process mod_mono could hide it
inside the dead time after serving a request.

> Reference counting, for instance, needs some form of locking when
> updating the reference counts, unless you rely on the application to
> do its own locking and not modify a pointer from two threads.

Because objects are never moved, the only "unsafe" thing to do is
prematurely deallocate an object. This means that locking is only
required only if many mutators are doing the deallocation and
finalization.

This is a probem in a "pure" reference counting algorithm.

One modern ref-counting optimization is to use a hybrid scheme which
sweeps the stack and registers as part of a "root set". This avoids
the need to ref-count very common activities such as local variable
manipulation and function argument passing. When using this scheme, a
refcount of zero only puts the object in the "to be checked"
state. The gc process has to quickly scan the root-set to determine
additional (uncounted) pointers and find out if the object is alive or
dead. This algorithm's synchronization primitive is a "stop the world"
event which involves scanning the stacks of all active threads and
refcount=0 objects. (much faster than the full heap scanning of most
heap gc). 

In this algorithm, only the gc process handles deallocation, so the
mutators don't need to lock. I'm sure there is some research about
this which would be more thorough than my paragraph above.

I wonder if it is possible to do a cycle-finding algorithm which can
run fully concurrently -- locking againt the only 'unsafe' thing out
there, the gc thread which could decallocate objects. The only output
of the cycle-finding algorithm is a list of new objects "to be
checked" for dead and the cycle-information which proves that their
refcounts are too high. Intuitively it seems to me like this should be
doable as a background operation, because if threaded mutators made it
wrong, the real gc thread would find out during it's world stop.

-- 
David Jeske (N9LCA) + http://www.chat.net/~jeske/ + [email protected]
_______________________________________________
Mono-gc-list maillist  -  [email protected]
http://lists.ximian.com/mailman/listinfo/mono-gc-list