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?
