More radical ideas about gc and reference counting

[Rainer Schuetze via Digitalmars-d]

On 11.05.2014 21:16, John Colvin wrote:
> On Sunday, 11 May 2014 at 18:18:41 UTC, Rainer Schuetze wrote:
>>
>> 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?

If we don't want to make a copy with memcpy, we have to rely on the OS 
paging. I don't know linux too well, but on Windows the idea would be to 
use VirtualProtect with PAGE_WRITECOPY. This could allow control on page 
size granularity over what would be mapped to another process.

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

Preciseness has little impact because copy-on-write protection works on 
page level. You will also pay for the page fault if you only write 
non-pointer data into the page.

It would help to sort memory chunks without pointers (they have 
attribute NO_SCAN) into separate pages that don't need page protection.

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

You'll need more memory, but given enough idle-time for a lower priority 
collector thread, a higher priority thread could run almost undisturbed. 
IIRC this meant about 40ms, as all threads need to be stopped for the 
time the fork is running.

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

Sure, but it is also not easy ;-) I guess we would need some inspiration 
from existing implementation in other languages how to do it efficiently.