From: MikkelFJ Date: 2002-09-01T05:37:36+09:00 Subject: 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 > 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