std.allocator: primitives for helping GC

[via Digitalmars-d]

On Thursday, 1 May 2014 at 04:06:02 UTC, Andrei Alexandrescu 
wrote:
> So far allocators have been quite GC-agnostic; deallocation 
> would be needed for each allocation, and there was little 
> structure to help tracing.
>
> The primitive resolveInternalPointer has made a step toward 
> more precise structuring of heaps, and now it's time to look at 
> some real GC helpers.
>
> These are markAllAsUnused, markAsUsed, and doneMarking. Find 
> their description here:
>
> http://erdani.com/d/phobos-prerelease/std_allocator.html
>
> There are a few proof of concept implementations here:
>
> https://github.com/andralex/phobos/blob/allocator/std/allocator.d
>
> The basic idea is that the GC would initiate a collection by 
> calling markAllAsUnused. That would cause the underlying 
> untyped allocator to softly mark all memory as free, but 
> without actually messing it up. (Many allocators are capable of 
> implementing such a primitive cheaply.)
>
> Then, the GC would trace objects starting from roots. Whenever 
> it finds a used pointer, it would mark the corresponding memory 
> as allocated by using markAsUsed, effectively undoing the soft 
> freeing for it.
>
> At the end of the process, what's left is the memory 
> effectively in use. Everything else got free by construction.
>
> It seems to me that these three primitives (together with 
> resolveInternalPointer) are sufficient for conservative 
> tracing. I plan to make tracing more precise by adding more 
> structure, but the scanning logic will stay the same.
>
> Now is the time to destroy. I might be missing something by a 
> mile.

This marking will usually be implemented by setting a flag near 
the memory in question, which is not COW and cache friendly, 
because it tends to write all over the place.

For this reason, some GCs use a temporary bitmap for marking, and 
leave the marked memory untouched. By pushing the marking to the 
specific allocators, this can no longer be implemented globally.

But I guess a GC is not required to use these helper functions, 
so I guess it's fine...

And just to be sure: doneMarking is _not_ supposed to actually 
free the memory (and call the destructors), is it? That's still 
the GC's job, right?