[Lvlug] mai-tree Continues to r0x0rz yu0r m0m

[jhigdon at linuxfools.org]

On Thu, Apr 14, 2005 at 08:15:41AM -0400, Nachiketa Kalam wrote:
> 
> Nachiketa Kalam said:
> >> Ok...I am completely rearranging mai-tree. I thought it would be fun to
> >> aim for speed. So I am rewriting vector.c to realloc a single array when
> >> the vector must expand instead of allocating new blocks (see the
> >> infinite array example in O'Reilly Practical C Programming)
> 
> <snip rest of improvements and statistics>
> 
> This has all been good. However, I have more! I was sitting around in math
> class yesterday, and I figured that removing the nary data type and
> replacing it with a tree of vectors would easily save me 11 bytes per
> index at least. Important design changes made this possible.
> 
> Even more importantly, I figured out a way to make the tree less
> top-heavy. Since most of the factors distilled from a key are two's, I
> reasoned that dividing the two's count by...two (foo << 1) and commuting
> whether the two's count is odd or even to the end would more equally
> distribute the weight of the tree and have tremendous consequences for
> memory use, while preserving the low collision rates the algorithm enjoys.
> And since vector_Get is so fast, it just doesn't matter that much.
> 
> So:
> 
> 21 6 8 7 9 1 becomes:
> 10 6 8 7 9 1 1 (the nary is now seven nodes deep)
> 
> and 20 6 8 7 9 1 becomes:
> 10 6 8 7 9 1 0
> 
> Should I go a step further? Possibly: do the same thing to the three's?
> 
> Or is anyone still reading this stuff?
> 

Nope!