enforce()?

[Andrei Alexandrescu]

On 07/19/2010 12:23 PM, Steven Schveighoffer wrote:
> On Mon, 19 Jul 2010 12:21:36 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>> By the way, I'm still eagerly waiting for your red-black tree
>> implementation.
>
> Sorry for the delay, I've been very busy at work, and I wanted to slip
> in a couple druntime fixes for array appending.
>
> All that is left really is the unit testing, and making the docs more
> phobos-ish.
>
>> I think it would be pure awesomeness if you massaged the red/black bit
>> inside one of the pointers. I figured out a way of doing that without
>> throwing off the garbage collector:
>
> Yes, that works (BTW, you don't need the union, I hate unions :), just
> substitute _bits for _left everywhere, I think it would even work with a
> moving GC).

Walter told me that union is instrumental to keeping the compiler in the 
know about such shenanigans. What does your idea look like? You mean 
keeping a possibly misaligned RBTreeNode pointer and manipulating that? 
I think that's a bit worse than unions because it transforms a sure 
thing into a maybe works thing.

> But I don't know how important it is to save that extra 4 bytes/node. A
> redblack node already has 3 pointers in it, the flag puts it to 16 bytes
> instead of overhead instead of 12. It certainly can be an implementation
> choice.
>
> I can look at left-leaning trees (I've had it on my todo list for
> dcollections too).

Sounds great. If the payload is one word, on a 32-bit system we'd have 
20 bytes per node. I seem to recall the current GC can allocate 16 bytes 
and then 32 bytes and then 48 bytes, so with the embedded bit we're 
looking at halving the total allocated size. Not too shoddy! Then the 
relative overhead of that extra word is not felt up until a payload of 
20 bytes, at which point again it jumps to 33%.

I wonder what things look like (alignment, granularity) for the 64-bit 
implementation.


Andrei