[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.
>=20
> So would be a lasting world peace!
>=20
>> 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.
>=20
> 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:
>=20
> 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.
> ...
>=20
> And to really get the most out of a GC, some of the low level
> decisions can be platform and processor specific.
>=20
> 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:
>=20
>   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.
>   ...
>=20
> 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.
>=20
> 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".
>=20
> And what about how to remember the old objects which need to be
> considered during a new object GC.
>=20
> We could perhaps make a linked or set of "remembered" objects, but
> this is expensive both in terms of space and speed.
>=20
> 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.
>=20
> But on most processors setting individual bits is expensive involving
> fetching, masking, and re-storing a larger datatype.
>=20
> 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.
>=20
> http://www.cs.ucsb.edu/~urs/oocsb/papers/write-barrier.pdf
>=20
> 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.
>=20
> Now I know that LLVM attempts to do something like this,
>=20
> http://llvm.org/docs/GarbageCollection.html
>=20
> but it apparently hasn't been all that successful:
>=20
> =
http://lhc-compiler.blogspot.com/2009/01/why-llvm-probably-wont-replace-c.=
html
>=20
>=20
> 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.
>=20
>=20
> I fear that a pluggable GC would only let you play around with pretty
> poorly performing GC alternatives.
>=20
> --=20
> Rick DeNatale
>=20
> 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
>=20
>=20