From: "(Doug Baskins)" (Doug Baskins) Date: 2002-08-30T01:33:05+09:00 Subject: Re: Ruby and Judy "MikkelFJ" wrote in message news:<3d68f556$0$166$edfadb0f@dspool01.news.tele.dk>... > > This (Judy in general) is a very interesting concept to > > me, partly because I find it hard to imagine this kind > > of thing coded with the kind of efficiency we seem to > > talking about, and yet presumably in a platform-independent > > manner. > > > > I'm not knocking it, I'm just surprised that Judy exists. > > [Mikkel] > I have been working with some similar concept using B-Trees: > Having an efficient in-memory tree with a reduced level of branching > compared to typically page sized trees does work quite efficiently. However, > you have to have very large hash tables before the B-tree it outperforms a > hashed 32 bit key. > > I implented a variant called I-Tree (I later learned they are also know as > ordered B-Trees or OB-trees). An I-Tree uses the size of the sub-tree for > indexing. At leaf level there is no key. Hence a space efficient dynamic > array. > > I was actually considering making Ruby running on this indexing principle, > but also realize it is a lot of work. > > 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. > (especially smaller trees) which is why I chose B-Tree keys instead of using > a trie lookup. If Judy does handle this efficiently it's interesting. I > noticed the use of "widening" also know as path compression. I've also been > working with this in relation to statically indexed trees, but it is not > good for dynamic behavior. Jucy seem to have abanded the use of key > widening. The cost for not widening the key is more levels in the tree. 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. > > The I-Tree is very space efficient. The B-Tree requires a key for each entry > which effectively becomes 64 bit per entry and the inherent space overhead > in B-Trees for not fully using all nodes. > > The downside of in-memory B-Trees is that entries must be moved during > insertion into node. It is generally faster to do linear scan than using > binary search of node up to a certain size (which is too large due to cache > considerations). 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. > > Ordinary Red-black trees (STL map) are not very space efficient. But for > small collections they are fast and has little additional overhead. > > Also note the 3-Trie posted in DDJ a few years back. I implemented a variant > using multi-level B-Trees. It branches on 32bit (or 64) bits instead of > Judy's 8 bit. I haven't measured it but I expect it to be a very efficient > suffix tree string indexing method. I store runs of strings to avoid > excessive number of sub-trees. > > Mikkel 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. doug@sourcejudy.com