[ruby-core:27543] Re: better GC?

Free beer wouldn't be bad, either ;-)

I agree that the overhead would be unacceptable, based on the points you raised. For true production-level code, performance would be unacceptable.

However, maybe another thing to consider is to work up a simple method for GC experimentation so that anyone who wanted to try out a new GC approach could do so without having to get into the guts of everything; if such a GC ended up being useful it could then be incorporated with the 'native' build that did not use the 'experimentation hooks'.

In other words, what I am suggesting is a 'pluggable' GC architecture for the purposes of accelerating development of proposed changes/additions to the language in a more 'agile' manner. Then if a particular GC were accepted it would be mind-melded into the production-level code without the hooks so performance is as good as it can get.

This kind of approach might serve well with other aspects of language development, but the GC issue is by far the biggest in terms of performance considerations. GC issues killed java credibility for years, for example, so the faster the growing pains are gotten out of the way, the better, I would offer.

e

On Jan 11, 2010, at 10:22 AM, Rick DeNatale wrote:

> On Mon, Jan 11, 2010 at 9:42 AM, Erik Scheirer <[e-mail]> wrote:
>> I think a pluggable/loadable GC scheme, as long as its really simple to use, is perfect.
> 
> So would be a lasting world peace!
> 
>> There would be some overhead created by making it pluggable, though, but in the scheme of things it would be well worth the small amount of cpu cycles lost.
> 
> I just can't see the feasibility of this.  Any good GC involves
> careful interaction between the parts of the system which mutate
> memory and those which manage it.  Getting a highly performant GC
> almost always involves careful coordinated design of things like:
> 
> The low-level layout of objects.
> The division of memory into various collections of objects (e.g. in a
> GC scheme the old objects and the new object live in different spaces,
> sometimes the new space moves each time a minor GC happens.
> Efficient detection of whether an object is old or new.
> For a GC requiring a 'write-barrier', efficient implementation of that
> write barrier.
> ...
> 
> And to really get the most out of a GC, some of the low level
> decisions can be platform and processor specific.
> 
> There are cascading design decisions to be be made.  For example, lets
> say we're making a generation scavenging GC.  We need to capture
> enough information as the mutator (the program) runs so that we can
> find any new objects which are referenced by an old object. This is
> the reason for the write barrier.  So there are several issues:
> 
>   How do we detect a store of a reference to a new object  into an
> old object with the lowest overhead.
>   How do we remember a store into an old object with the lowest overhead.
>   ...
> 
> There are several strategies for detecting old vs new objects, each
> with it's own tradeoffs, for example:
>   A flag bit in the object header
>   Address range checking to see which space it's in, or not in.
>   On some platforms and processors, one might make use of the virtual
> memory hardware and access privileges to detect such stores, but this
> is highly non-portable and may or may not outperform other approaches.
> 
> Flag bits need to be maintained properly, and are expensive, see below.
> Address range checking is more common, and goes back to the
> interactions with the overall design of the "VM".
> 
> And what about how to remember the old objects which need to be
> considered during a new object GC.
> 
> We could perhaps make a linked or set of "remembered" objects, but
> this is expensive both in terms of space and speed.
> 
> Most GCs use some form of "card marking" where old space is broken up
> in to 'cards' containing a range of memory.  Cards are similar to
> pages in a virtual memory system, and may or may not be the same in a
> particular GC implementation. In such a scheme when a new object
> reference is stored in an old object, the fact that has happened is
> stored as a change to the card in which the old object resides.  The
> most obvious way to do this is to have a data structure somewhere
> which has a bit for each card.
> 
> But on most processors setting individual bits is expensive involving
> fetching, masking, and re-storing a larger datatype.
> 
> The Self guys recognized this and found that for the processors they
> were working on using a byte rather than a bit for the mark, was much
> better overall despite requiring eight times the space for the marks.
> 
> http://www.cs.ucsb.edu/~urs/oocsb/papers/write-barrier.pdf
> 
> And these are just some of the variations once one has chosen a
> particular GC algorithm or perhaps one of a family of GC algorithms.
> 
> Now I know that LLVM attempts to do something like this,
> 
> http://llvm.org/docs/GarbageCollection.html
> 
> but it apparently hasn't been all that successful:
> 
> http://lhc-compiler.blogspot.com/2009/01/why-llvm-probably-wont-replace-c.html
> 
> 
> The problem is that LLVM defines the interface between the mutator and
> the GC "framework" in terms of C functions and function callbacks,
> e.g. for the write-barrier, whereas a really efficient GC implements
> the write barrier(and other GC bookkeeping tasks) in a few machine
> instructions.
> 
> 
> I fear that a pluggable GC would only let you play around with pretty
> poorly performing GC alternatives.
> 
> -- 
> Rick DeNatale
> 
> Blog: http://talklikeaduck.denhaven2.com/
> Twitter: http://twitter.com/RickDeNatale
> WWR: http://www.workingwithrails.com/person/9021-rick-denatale
> LinkedIn: http://www.linkedin.com/in/rickdenatale
> 
>