Re: Ruby and Judy

> > I need to study Judy more, but it seems like it used a trie where I use
> > B-tree keys. I'm worried the Judy may consume too much memory on some
cases
>
> This is the major reason people do not use digital trees (tries) however,
> Judy was able to solve this problem.  In fact Judy is normally consumes
less
> memory than other methods.  The reason is because Judy takes advantage
that
> a digital tree decodes a portion of the key at each level, therefore the
> whole key need not be stored in the tree.

I admit that B-Trees probably are more memory expensive than Judy trees. I
imagine the wasted space can improve insertion times.

The static trie I've been working with was based on ideas from the article
"Fast IP Routing with LC-Tries" article in Dr. Dobbs Journal (search their
archives). I modified it in several ways including adding a substring
compare node to avoid subsequent comparison to see if a match was truly a
match. The datastructure uses a fillfactor to decide the size of the
jumptable at a given bit-offset in the index. The fillfactor is the
percentage of empty slots in a jumptable. The index bit-length of a given
node is decided by the longest sequence that does not violate the fillfactor
and which does not cross a machine word boundary in the index. The bitstring
is shifted into place and is used to jump to the next node.

I have considered having a combined static trie and a dynamic B-Tree
(B-Trie) where new data is added to the B-Tree and the static trie is
recompiled occasionally much like garbage collection.

> Judy does not use "path compression" (per Steffin) because that
opportunity
> is only available high in the tree.  This part of the tree is normally in
> the data cache therefore the very wide branch does not help performance.
> Very wide branches make a very dynamic tree slow to add and delete.
> Judy will use wider that 256 branches when 1TB machines are commonplace.

I agree that you should limit the maximum fanout - as I also did in my
static trie - because you want to keep the jumptable within cache boundaries
and because you want to not waste too much memory. I do not agree that you
only get a wide fanout close to the root. That depends on the datasource.
For example "comp.lang." could be a common prefix where you get the
diversity closer to the leaf.

> Judy did not use a b-tree internally because of the number of cache-line
> fills necessary to search a node. However we came close. B-trees have a
> lot of good properties if done well.  I think there is some b-tree code
> in the apps/benchmark section of the Judy source download.

I found that having between 7-14 entries in the B-Tree proved to be quite
efficient. A linear tight loop search of a small node should be running
within data and instruction cache. It is not a problem that the node is
small - you are simply trading tree height against local node search
performance. You trim the node size until you get maximum performance. For
this to work optimally, related nodes should preferable be stored close to
each other. The benefit of small nodes is also the you need to move less
entries during insertion and removal.

The latest concept I have been working on is allocating small B-Tree nodes
from larger pages: try allocate next node from same page. From a disk-cache
point of view the page works like a large B-Tree node which in turn is
divided into smaller CPU-cache smaller nodes. I expect this to work well
with memory mapped files as well as large indices where some nodes
eventually gets paged out. You also get a good tradeoff between avoiding CPU
expensive intranode binary search and still have good logarithmic behavior.

> Have you got some code to compare?  SLcompare.c benchmark at
> <www.sourcejudy.com> compares JudySL with the best 3 methods I have
> been able to get code. I do not write code for known methods because
> I am too tainted.

I have some fast 32 bit indexing datastructures including a fairly fast
B-Tree.
The B-Trie for variable length keys is very recently implemented and use
code that is not yet optimized (needs inlining). I am curious about the
performance though - so we might set something up - but it would take some
amount of work (mail me if interested, remove "-anti-spam" from mail
address).

You could also take a look at ternary search trie by Sedgewick:
http://www.ddj.com/documents/s=921/ddj9804a/9804a.htm

It uses too much memory and does not have sufficient data locality but the
code is very small and simple. It executes in a tight loop. It could be
enhanced with a sub-string compare node as I did with the B-Trie to avoid an
excessive number of nodes with only one branch.

Mikkel