Thanks for reading through it!
bearophile wrote:
Robert Fraser:
Attached, if you don't mind NO comments.
This is your code, I can see you have not used the union trick to reduce the
memory used by each node that I suggested you:
private static struct TreeNode
{
TreeNode* left;
TreeNode* right;
TreeNode* mid;
K split;
K[] key;
V value;
}
How does the union trick work exactly?
And it seems all nodes contain a value, not just the leaves.
I'm assuming that V.sizeof == (void*).sizeof. There's actually 12 bytes
that are unused on all but nodes containing values, since the key is
also cached in there. This could eliminated by keeping track of the
current stack in the opApply methods, but that slows down iteration.
Non-leaf nodes can also have values. For example, if you have "var" = 5
and "var2" = 10, "r" will have a value and a mid.
the compiler wasn't unrolling the tail call<
I think still DMD isn't able to unroll tail calls.
Regarding the memory.d, in my implementation I have used a:
T[(MAX_BLOCK_BYTES / T.sizeof)] items;
you have used:
private void[BLOCK_SIZE] data = void;
memset(blk.data.ptr, 0, BLOCK_SIZE);
Not setting that void array (of uint? ubyte?) to void the compiler sets it to
zero with a memset, so I don't understand what you have gained.
void[SIZE]; fails with an obscure error message... you need to
initialize it to void.
And allocating an array of nodes offers a GC a chance to know what's inside the
block of memory, so it's more compatible with better future GCs (it may be
better even now).
It also allows for safer initializations of the struct fields, for example on
some CPUs null can be != 0
I agree, but I wanted a generic construct that could also be used for
allocating class instances.
Later I'll try to adapt your code to Phobos1.
Thanks!
