GC, the simple solution

Daniel Keep daniel.keep.lists at gmail.com
Sun Jun 4 18:15:51 PDT 2006



Frank Benoit wrote:
> 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.

I guess we'll just have to disagree, then :)

Like I said before, I think the current GC should be the default since,
even if it's not the best in terms of latency, it's the *safest*.
There's no need for someone coding under it to worry about things like
cycles, etc.  By having refcounting an option, we can say to
programmers: "turn this on if you like, but watch your back for cycles!"

<joking>Plus, the current system gives us bitchin' benchmarks with wc!
;)</joking>

>> * because references are on the object, you can't have array slices
> 
> Don't understand that point.

An array slice is a pointer and a length.  The problem is the "pointer"
part:

>> * 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.

Aaah, ok: you're putting the refcount somewhere in the allocated chunk.
   Sorry, I thought you meant hide it as a member on objects.

However, I imagine that this is still going to do horrible things to
pointer operations in terms of speed.  Every time you move or copy a
pointer, you'd have to ask the GC "ok, find which pool this pointer is
located in, then inc/dec the refcount."

>> * 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.

I concede that, as well as that the current GC has (probably) the worst
all-at-once latency you can get.

>> * 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.

Well, I don't *need* destructors in most general objects under
mark&sweep.  It's only when they're holding some external resource, and
that's when I usually manage them with auto or scoped destruction.

... which would admittedly be easier with refcounting, if a little bit
slower :)

>> * 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 :)

What I mean is that if I say "auto Foo x = ..." then I know that come
hell or high water, D is going to destroy that object at the end of
scope.  Plus, because of auto rules, I *cannot* leak a reference to that
object: D simply won't let me.

As for the static variable case, it's no different to the current
implementation: you save a reference to something in a global or static
variable, and it's never going to die :)

>> * 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.

The problem I have is that even if I *do* "know" my program, I don't
want to have to worry about this.  I just want to write my damn code!
This is one of the great advantages of D: if you don't give a rat's
about memory management, you don't have to.

That said, D *does* have one advantage: at compile time, the compiler
can determine if it's possible for an object to indirectly refer to
itself.  Using this, it can insert something like this into the decref:

# static if( typeof(ptr).canPointToItself )
#     registerForCycleChecking(ptr);

That way, you know that cycles will get checked for *eventually*.

> Doing a realtime GC seems to be not possible.

Oh, you'll get no argument from me THERE. :)

> 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".

I saw an interesting paper once that was talking about using a
tri-colour mark&sweep collector that was fully concurrent: sounded
heinously complicated to write, but could run a full collect in the
background of your app.

Buggered if I can find the damn thing again, though...

>> 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.

MyRef.value

Yeah, it's not that great, but at least it's *possible* :)

> * Existing classes, native arrays etc. does not work like this.

Fair enough.

> I do not need a few classes managed with ref counting. I want to avoid
> the "Stop the world". And phobos needs it.

I don't think phobos "needs" it.  What I think would help immensely was
if phobos was easier to rebuild with different compiler flags,
collector, etc.

Would you be happy if it was trivial to recompile phobos using
refcounting instead of the current GC, and then use that?

# build -phobos -collector=refcount -version=SomethingElse
# build MyProggy -collector=refcount -- uses phobos_refcount.lib

> 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.

I don't have any proof on me, although knowing the internet I'm sure I
could find some "proof" without too much trouble :P

And yes; if memory is low, m&s will probably take a long time.
Actually, I should find out how long that is.  Would be interesting to
know exactly how long it takes to collect 512 meg of garbage :P

Personally, I don't mind how D's default collector is implemented, so
long as it is efficient in the general case, and I don't have to know
anything about the way it works in order to write code.

That said, I'd still like to see D support collectors other than the
base GC.  Ideally, I think D should support at least:

# -collector=simple        -- current style: no special support needed
# -collector=writebarrier  -- calls std.gc.writeBarrier(ptr) on writes
# -collector=refcount      -- calls std.gc.writeBarrier(ptr), as well as
#                             std.gc.incref and std.gc.decref as
#                             appropriate.

That way, we can all have our cake, be it chocolate cake, fruit cake or
cheesecake.  Plus, we even get to *eat* it :)

	-- Daniel

-- 
Unlike Knuth, I have neither proven or tried the above; it may not even
make sense.

v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D
i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP  http://hackerkey.com/



More information about the Digitalmars-d mailing list