std.allocator: false pointers

[Andrei Alexandrescu via Digitalmars-d]

Hello,


I'm currently doing a nice optimization in the tracing code: I use the 
same bit (per block) to indicate "this memory is allocated" and "this 
memory is marked as used during tracing".

The way the trick works is, at the beginning of a collection the GC 
marks all of its memory as deallocated (sic!). Then, it traces through 
pointers and marks BACK as allocated the memory that's actually used. At 
the end of tracing, there's no need to do anything - what's used stays 
used, the rest is free by default.

This is unlike more traditional GCs, which use a SEPARATE bit to mean 
"mark during tracing". At the beginning of the collection, these "mark" 
bits are set to 0. Then collection proceeds and marks with 1 all blocks 
that are actually used. As the last step, collection deallocates all 
blocks that were marked with 0 and were previously allocated.

So the optimization consumes less memory and saves one pass. It does 
have a disadvantage, however.

Consider a false pointer. It will claim that a block that's free is 
actually occupied, and the implementation can't distinguish because it 
conflates the "mark" and the "allocated" bit together. So it's possible 
that at the end of collection there are blocks allocated that previously 
weren't. The optimization is therefore sensitive to false pointers.

Thoughts? How bad are false pointers (assuming we fix globals, which 
only leaves the stack and registers)?


Andrei