On 07/19/2010 12:23 PM, Steven Schveighoffer wrote:
On Mon, 19 Jul 2010 12:21:36 -0400, Andrei Alexandrescu
<[email protected]> 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
