On Mon, 19 Jul 2010 13:47:38 -0400, Andrei Alexandrescu
<[email protected]> wrote:
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.
I don't pretend to know what ominous problems Walter knows about regarding
the compiler's view, but here is what I'm thinking:
If a pointer points to the beginning of a node, and a node has at least
one pointer in it (which it must, since it's a tree), then pointing one
byte into the node means you're still pointing at the same block, making
sure the GC doesn't collect.
Really, the generated code will be exactly the same as your solution, but
it's less of a misuse of the type system IMO (believe it or not). I'd
rather use casts when you are trying to use something that's typed as one
thing as something else. When using unions, I usually expect only one
member of the union to be valid at any one time.
And wouldn't a union be more egregious with the upcoming mostly-precise
scanner?
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!
Not quite :) There is one byte for padding because (insert gasp-inspiring
music accent) all struct heap allocations are allocated through newArray
with a size of 1. I discovered this when working on the array append
patch.
So even a 16-byte struct requires a 32-byte block.
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%.
Most of this is mitigated if you have a custom allocator that allocates an
array of nodes at once (what I do in dcollections). As a simple
implementation, you could allocate enough nodes to be under a certain
threshold of wasted space.
I wonder what things look like (alignment, granularity) for the 64-bit
implementation.
They must be 8-byte aligned, and have 3 8-byte pointers, so that means at
least 24 bytes. If you store an int, then it will still fit in the
32-byte block. I don't know what's planned as the minimum size for 64-bit
GC.
-Steve
