More radical ideas about gc and reference counting

[John Colvin via Digitalmars-d]

On Sunday, 11 May 2014 at 18:18:41 UTC, Rainer Schuetze wrote:
>
>
> 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:
>Coventry
> 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.

a) Can't we do our own specialised alternative, instead of doing 
something as heavyweight as fork?

b) Surely that worst case is a very unlikely case, given a 
precise, concurrent garbage collector.

c) Does this actually help in the 99% cpu, 99% memory, 16ms per 
frame setting that Manu talks about?

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


Adding optional write-barriers would be great. It would allow us 
to do real experiments and stop the discussion being so 
hypothetical. It doesn't do any harm to add the capability, 
surely?


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