On 11.05.2014 10:22, Benjamin Thaut wrote:
Am 10.05.2014 19:54, schrieb Andrei Alexandrescu:
The next sentence goes on to list the advantages of RC (issues we have
wrestled with, like destructors), and then goes on to say the recent
awesome RC is within 10% of "the fastest tracing collectors".
Are you suggesting that D's GC is among 'the fastest tracing
collectors'? Is such a GC possible in D?
I believe it is.
While it might be possible to implement a good GC in D it would require
major changes in the language and its librariers. In my opinion it would
be way more work to implement a propper GC than to implement ARC.
Every state of the art GC requires percise knowdelge of _all_ pointers.
And thats exactly what we currently don't have in D.
I think most garbage collectors can work with a number of false
pointers. The referenced memory area has to be treated as pinned and
cannot be moved. Limiting the false pointers to stack and registers
seems like a compromise, though most of the stack could even be
annotated. Code for this does already exist in the debug info
generation, though I suspect stack tracing could be unreliable.
Here's my current stance on the GC discussions:
I agree that the current GC is pretty lame, even if it were precise.
"Stop-the-World" with complete tracing does not work for any interactive
application that uses more than a few hundred MB of garbage collected
memory (with or without soft-realtime requirements). Other applications
with larger allocation requirements are easily dominated by collection
time. Proposing to use manual memory management instead is admitting
failure to me.
For a reasonable GC I currently see 2 possible directions:
1. Use a scheme that takes a snapshot of the heap, stack and registers
at the moment of collection and do the actual collection in another
thread/process while the application can continue to run. This is the
way Leandro Lucarellas concurrent GC works
(http://dconf.org/2013/talks/lucarella.html), but it relies on "fork"
that doesn't exist on every OS/architecture. A manual copy of the memory
won't scale to very large memory, though it might be compressed to
possible pointers. Worst case it will need twice as much memory as the
current heap.
It would be very interesting how far we can push this model on the
supported platforms.
2. Change the compiler to emit (library defined) write barriers for
modifications of (possible) pointers. This will allow to experiment with
more sophisticated GC algorithms (if the write barrier is written in D,
we might also need pointers without barriers to implement it). I know
Walter is against this, and I am also not sure if this adds acceptable
overhead, but we don't have proof of the opposite, too.
As we all know, the usual eager reference counting with atomic
operations is not memory-safe, so my current favorite is "concurrent
buffered reference counting" (see chapter 18.2/3 "The garbage collection
handbook" by Richard Jones et al): reference count modifications are not
performed directly by the write barrier, but it just logs the operation
into a thread local buffer. This is then processed by a collector thread
which also detects cycles (only on candidates which had their reference
count decreased during the last cycle). Except for very large reference
chains this scales with the number of executed pointer modifications and
not with the heap size.
