std.allocator: false pointers

[Orvid King via Digitalmars-d]

Well, in a 64-bit address space, the false pointer issue is almost
mute, the issue comes in when you try to apply this design to 32-bit,
where the false pointer issue is more prevelent. Is the volume of
memory saved by this really worth it?

Another thing to consider is that this makes it impossible to
pre-allocate blocks of varying sizes for absurdly fast allocations via
atomic linked lists, in most cases literally a single `lock cmpxchg`.

On 5/2/14, Andrei Alexandrescu via Digitalmars-d
<digitalmars-d at puremagic.com> wrote:
> 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
>