Judy Arrays (2004) | Hacker News Reader

Judy Arrays (2004)

judy.sourceforge.net

61 pointsmpweiher23 comments

Open articleView on HN

I taught Judy Arrays in our Advanced DB course in 2020:

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" or "ART index software", "ART index database" etc is a singularly unproductive search ...

"ART index software radix tree" works (the A stands for adaptive).

https://github.com/topics/adaptive-radix-tree

Thank you so much for these lectures on YouTube BTW. They've been highly enjoyable for me.

The Advanced DB course is great. It's a great survey of the modern DB technologies. Thanks for putting it up in Youtube.

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.

No, use an LSM.

LSM: https://en.wikipedia.org/wiki/Log-structured_merge-tree

> No, use an LSM.

What is an LSM?

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).

Judy Arrays would be faster than LSM.

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)

This was probably prompted by https://news.ycombinator.com/item?id=32704977

("Those who do not know judy1 are doomed to reinvent it." apropos Roaring Bitmaps)

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.

[1] https://nothings.org/computer/judy/ (2003)

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.

[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)

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.

I built slackware package manager replacement based on Judy Arrays, 17 years ago. :)

https://spkg.megous.com/

It was quite fast even on 50 MHz 486-DX2.

Why was I not taught this in a data structures cause?

Reply on news.ycombinator.com