GC, the simple solution

Frank Benoit keinfarbton at nospam.xyz
Sun Jun 4 06:43:10 PDT 2006


In nearly every other GC implementation you will need also a read or
write barrier. With reference counting you have a write barriere.

Yes, the unprecise, non-incremental, "Stop-the-world", non-concurrent,
non-generational, conservative Phobos GC implementation is an exception.

But a write barrier alone doesn't make ref counting ridiculous. Well you
are right, it is not the solution for all and everything, but I think a
big step in the right direction. And mark&sweep GC should be the option.

> * because references are on the object, you can't have array slices

Don't understand that point.

> * it's also incompatible with pointers: if the pointer is to a member of
> an object, how on earth do you update the refcount then?

In the actual implememtation of the gc, every object's memory range is
registered by the gc. With that you can get the objects refcounter address.

> * slower in the immediate sense (incref & decref calls, plus it'll mean
> less code in L1 and L2 CPU cache, which can kill performance in some
> architectures)

Performance has two sides. Throughput is one thing, worst latency the
other. We can think about techniques to optimize unecessary
increments/decrements.
BTW all incremental GCs will also need read and/or write barriers, which
will have the same perfomance issues.

> * requires all objects to have destructors to decref child objects
> (implicit or otherwise)

Yes, all objects having child objects. But if you think, that destructor
calls are a performance issue, you will get problems with the mark&sweep
also.

> * without auto, makes it impossible to ensure an object's destruction
> when you leave scope: you can leak references

How can that happen, if we have them native? Well ok, e.g. if you store
the reference to a static variable, then it is not freed. But this is
really a programmers bug. But I think that is something an advanced look
at it will find solutions. First we have to decide to go for ref counting :)

> * inability to free cycles
> * inability to even *run* destructors where cycles are involved, because
> there is no order in which they can logically be executed and still be valid

Right, here a manual ref=null is needed. And perhaps a mark&sweep
algorithm to detect such cycles in the debug version, called on request.
So if you know you program, you can avoid cycles, or you can break them
before releasing the last reference.

Doing a realtime GC seems to be not possible. The existing "realtime GC"
seems to me, incremental ones, which stop the world for a short limited
time. And that time goes into your worst latency. So if I want to do
things with a latency less 100us, there is no chance to implement a GC.
Ref counting whould be a solution, but this can only work if the whole
program does not depend on "Stop-the-world".


> As it stands, you can implement reference counting yourself: you just
> need to write an allocator, and call the incref and decref functions
> manually.  However, I do think that having built-in *support* for
> Reference counting would be fantastic.  The less that stuff like this is
> left in the hands of the programmer, the better.
No, i can't.
* The dereference operator cannot be overwritten.
* Existing classes, native arrays etc. does not work like this.
I do not need a few classes managed with ref counting. I want to avoid
the "Stop the world". And phobos needs it.

Where is the proof that ref counting is so slow? In mark&sweep you have
to run over the whole memory. If the memory is low, you have to do that
often. This is really slow than.



More information about the Digitalmars-d mailing list