Been sitting on this email a while, and as one of the creators of libJudy I want to kibbitz, though I might not have much to offer.
> Sean Barrett made some good points regarding the lack of benchmark > tests vs other algorithms... Yeah, we did what we could, in the time we had. I'm sure Doug Baskins ran a lot of comparisons, but most were not formalized/delivered. > ...as well as the impact of Judy's use of double the Pentium > cache-line size. We focused on "modern CPUs" in HP workstations first. Later decided that while Judy could be tuned a little for a (surprisingly few) parameters like cache line size, it didn't matter enough to bother. We had enough trouble as it was, getting people to use it at all, especially in existing applications where the data set size was small enough and/or the current method was "good enough" that it wouldn't help much. > However, the comparison is between a traditional Hash table and JudyL > (an optimised form of tree if I understood the documentation > correctly). Writing patent apps, I studied ~20 academic papers and ~5 textbook sections, and no one had anything like Judy, or was even in the same space. All the researchers were fine-tuning or focusing on aspects of what we called "by-population" trees. Came to realize that Judy is a radix tree (more or less = digital tree) and no one had put much thought into how to do the radix approach while keeping data size and insert/delete transitions small, so as to then get wide, shallow, fast trees. So Judy's optimization is essentially "careful compression of the nodes in a radix tree." Note that an array-of-array... of Judy arrays, essentially for handling long and/or variable length keys, is a radix tree of radix trees... Judy scales infinitely, unlike almost anything else I've heard of. > I was wondering if anyone has done similar tests (speed and space) > with JudyHS vs a mainstream STL hash table implementation on a decent > optimising compiler... Sorry I don't know much about JudyHS(), Doug added it later. In general, a tuned hash table beats Judy, but tuned requires you have a well-specified data set size and shape ahead of time, and even then it behooves you to keep your hash algorithm CPU-non-intensive, and hope not to need random access in a way that basically destroys the value of CPU caching. Whereas a radix approach like Judy naturally sorts data (at least in some form, which might or might not be useful to the problem space) for good cache locality for sequential operations. You can think of Judy as an array of array of hash tables, where each hash table has 256 buckets, and the hash operation is "index through the next byte of the key". In other words, nearly zero time hash operation, ordering/locality, and the magic is in the handling of "synonyms", or what we called subexpanses. > In addition, a big research area of the past few years has been in > concurrent algorithms. Has anyone tried to apply such > wait-free/lock-free techniques or even tried to make an offset-based > structure that can be shared (shared "sections" a.k.a "memory mapped > files" under Windows) between processes (or persisted to disk as-is)? Dunno about the big question, but I did work on a thread-test program for libJudy, that I think was released too, and we found that the overhead for thread lock/unlock, especially on HPUX, but even on Linux, swamped typical Judy operation times. So you were better off treating Judy arrays as atomic (one overall thread lock per array) if you had to lock at all, than to crave some way to lock subtrees. Performance code is a tricky business. For example, if you really care, you don't use libJudy.sl/so, you use libJudy.a, which is fortunately small enough that who cares it's replicated in each program? Using shlibs, again, swamps the raw speed of libJudy itself. > The main advantage of hash tables over tree-based structures is their > transparency of implementation: this leads to the ability to very > quickly work out what the lowest granularity of mutual exclusion is, > where to apply it, and how to replace pointers with offsets. Transparency? I guess, if you say so! But what I found, hunting for applications where we could insert Judy, was that they were so non-encapsulated that you couldn't easily substitute some other algorithm. I came away unimpressed, especially seeing one app where 10-year-old hash tables simply needed to be quadrupled in size for 10x improvement -- but no one ever had time/reason to go look. > However, this does not mean that hash tables are better in terms of > speed/space, just that they are easier to apply such transformations > to unless you are the original author of the source code. Possibly, depending on the level of complexity in the hash table implementation, such as trick table size auto-increase/decrease, synonym handling, etc. Cheers, Alan Silverstein ------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys - and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV _______________________________________________ Judy-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/judy-devel
