From 2004. I've always felt suspicious towards this package. It's a huge amount of code to squeeze a little bit of extra performance out of an otherwise simple operation. I don't know if it used much any more. I figure if the standard modules aren't fast enough, maybe it's better to tailor something to the application, than use a heavily optimized but very complicated general purpose library.
The key claim is that it has been specialized against the target architecture to tune each parameter optimally. But, yeah that was done 20 years ago and it is not clear how much the costs have shifted on modern architectures.
Even at that time the claim was heavily challenged [1], and I agree to Sean's conclusion: Judy array might be slightly faster for some applications but an added complexity is not worth it.
On that note, it's interesting to me that the wiki page for Judy arrays mentions that the "smallest implementations are thousands of lines of code", but then also links to a 1250 LOC implementation in the references.
The latter might be a more interesting jump-off point for experimentation than this massive library.
Use this as a key value store in memory if you are working in C for speed. I've used this to handle multiple 200+ million entry tables in memory, that were not able to be handled as effectively using SQL.
Consider using this if you need to intersect very large data sets that otherwise would take a prohibitive amount of time to even insert into an SQL database (with or without an index) or otherwise even handle in a script language.
LSM trees are mostly for persistent storage. You can do a lot better in memory with a btree or a different data structure. LSM trees have a lot of operations that need multiple scans or are O(n) instead of O(log n).
What's the data structure you'd use when Judy arrays would be a good fit but the implementation doesn't exist for your language of choice? I mean: what's the closest to Judy arrays that's ubiquitous? Roaring bitmaps maybe?
I like hashed tries a lot. That's essentially a sparse array indexed by strings. Works well as a persistent data structure. Popularised by clojure and scala.
Roaring bitmaps are integer sets with optimized set-wise operations, like intersecting two sets to find out which integers are contained by both. Judy is an associate array (so it's interface is similar to a hash table). There's a specialized case for word->bit, but no set-wise operations and no way to match the performance of roaring for those.
This doesn't quite answer your question, but if Roaring fits your case you should use it instead of Judy1 even if have Judy1 available.
> but if Roaring fits your case you should use it instead of Judy1 even if have Judy1 available.
Why? Assuming you have no need for the specialized whole set union and intersection operations. At least the C roaring library only supports 32-bit keys which is a hard blocker vs judy1 for some applications.
24 comments
[ 5.3 ms ] story [ 58.6 ms ] thread[1] https://nothings.org/computer/judy/ (2003)
The latter might be a more interesting jump-off point for experimentation than this massive library.
[0] https://en.wikipedia.org/wiki/Judy_array
[1] https://code.google.com/archive/p/judyarray/
[2] https://github.com/JanX2/judy-arrays (github export of previous)
Consider using this if you need to intersect very large data sets that otherwise would take a prohibitive amount of time to even insert into an SQL database (with or without an index) or otherwise even handle in a script language.
What is an LSM?
This doesn't quite answer your question, but if Roaring fits your case you should use it instead of Judy1 even if have Judy1 available.
Why? Assuming you have no need for the specialized whole set union and intersection operations. At least the C roaring library only supports 32-bit keys which is a hard blocker vs judy1 for some applications.
How Judy arrays work and why they are so fast (2002) - https://news.ycombinator.com/item?id=20820795 - Aug 2019 (13 comments)
Performance Improvements Using Judy Arrays - https://news.ycombinator.com/item?id=5639013 - May 2013 (51 comments)
Judy arrays are patented - https://news.ycombinator.com/item?id=5043667 - Jan 2013 (56 comments)
Judy Arrays - https://news.ycombinator.com/item?id=3675759 - March 2012 (9 comments)
A 10-minute description of how Judy arrays work and why they are so fast - https://news.ycombinator.com/item?id=1419526 - June 2010 (13 comments)
Judy, an efficient sparse dynamic array implementation - https://news.ycombinator.com/item?id=859336 - Oct 2009 (4 comments)
("Those who do not know judy1 are doomed to reinvent it." apropos Roaring Bitmaps)
https://youtu.be/N6rhECUjdaI?t=3043
AFAIK nobody uses them because of the (unfounded) patent fears.
ART indexes are a modern implementation of radix trees / tries that is better.
"ART index software radix tree" works (the A stands for adaptive).
https://spkg.megous.com/
It was quite fast even on 50 MHz 486-DX2.