GC, the simple solution

[Daniel Keep]

Just a few comments, since you invoked my name :P

Frank Benoit wrote:
> Let's think about the scenario of having reference counting (RC) and
> mark&sweep (MS) in parallel. Like Daniel Keep said, it is used in
> Python. If Python uses this, the idea cannot be so crazy.

Just wanted to point out that if I remember correctly (and I *could* be
wrong), the cycle checking is only done on decrefs, since that's the
only time that cycles become a problem.

>> 3) in a multithreaded app, the incs and decs must be synchronized
> 
> Isn't a atomic inc/dec enough? (Don't know anything about the
> performance of the asm "lock" instruction)

They definitely have to be synched: because in decref you've got to:

1. ref--;
2. if( ref == 0 ) free(ptr);
3. if( obj.canHaveCycles ) registerForCycleCheck(obj);

If not more.  You then also need the incs synched with that, otherwise
you could end up "ref++"ing in the middle of "free(ptr)".

>> 7) Fixing the compiler to hide all this stuff from the programmer will
>> make it difficult to interface cleanly with C.
> 
> hm, ok. Here is some more manual work necessary.
> If you give the last reference to a C lib, isn't this a problem for the
> MS GC also?

MS' GC doesn't use refcounting (I assume you're talking about .NET,
btw).  In fact, to solve this problem, it uses pinning:

"""
When the runtime marshaler sees that your code is passing to native code
a reference to a managed reference object, it automatically pins the
object. What this means is that the object is put in a special state
where the garbage collector will neither move the object in memory nor
remove the object from memory. ...

When the native function returns, the marshaled object is automatically
unpinned. Automatic pinning is very convenient, but it raises another
question. What happens if the native function caches the pointer for use
later on? When the function returns, won't the collector be free to move
the object? The answer is yes, and the solution for your code in such a
situation is to manually pin the object using the
System.Runtime.InteropServices.GCHandle type.
"""

 -- http://msdn.microsoft.com/msdnmag/issues/04/10/NET/

>> 8) Ref counting can fragment the heap thereby consuming more memory just
>> like the gc can, though the gc typically will consume more memory overall.
> 
> Isn't the actual GC implementation also fragmenting the heap?
> But I don't have any idea to this issue.

Not as badly.  The current GC is pretty good at keeping fragmentation to
a minimum.  Fragmentation happens when you allocate lots of little
objects, then free some but not all, and end up with teeny-tiny "holes"
in memory that are hard to fill.

I think Walter said this because of his comment on using "wrapper"
objects to implement the references: you'd end up with lots of "holes"
in memory.

>> 9) Ref counting does not eliminated latency problems, it just reduces them.
> 
> Where do you mean is the latency with RC? The collecting work is done in
> the smallest pieces all the time. Only the allocation of new memory
> needs an unbound time to complete. But it does not need to stop all
> other threads. e.g. hardware interrupts don't need to be disabled.

I think he means that it doesn't make latency just disappear; it spreads
it over time.  It's the old "drop a frog into hot water and it'll jump
out, drop it in cold water and then boil it and it won't notice" anecdote.

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