4 ms·
Judy Arrays (2004)
- throwaway81523 4y agoFrom 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.
- 314 4y agoThe 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.
- lifthrasiir 4y agoEven 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/ https://nothings.org/computer/judy/ (2003)
- vanderZwan 4y agoOn 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 https://en.wikipedia.org/wiki/Judy_array [1] https://code.google.com/archive/p/judyarray/ https://code.google.com/archive/p/judyarray/ [2] https://github.com/JanX2/judy-arrays https://github.com/JanX2/judy-arrays (github export of previous)
- throwaway313313 4y agoUse 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.
- morelisp 4y agoNo, use an LSM.
- pxeger1 4y agoLSM: https://en.wikipedia.org/wiki/Log-structured_merge-tree https://en.wikipedia.org/wiki/Log-structured_merge-tree
- lelanthran 4y ago> No, use an LSM. What is an LSM?
- pclmulqdq 4y agoLSM 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).
- deleted 4y ago[deleted]
- ww520 4y agoJudy Arrays would be faster than LSM.
- TacticalCoder 4y agoWhat'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?
- JonChesterfield 4y agoI 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.
- sethev 4y agoRoaring 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.
- nullc 4y ago> 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.
- dang 4y agoRelated: How Judy arrays work and why they are so fast (2002) - https://news.ycombinator.com/item?id=20820795 https://news.ycombinator.com/item?id=20820795 - Aug 2019 (13 comments) Performance Improvements Using Judy Arrays - https://news.ycombinator.com/item?id=5639013 https://news.ycombinator.com/item?id=5639013 - May 2013 (51 comments) Judy arrays are patented - https://news.ycombinator.com/item?id=5043667 https://news.ycombinator.com/item?id=5043667 - Jan 2013 (56 comments) Judy Arrays - https://news.ycombinator.com/item?id=3675759 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 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 https://news.ycombinator.com/item?id=859336 - Oct 2009 (4 comments)
- B1FF_PSUVM 4y agoThis was probably prompted by https://news.ycombinator.com/item?id=32704977 https://news.ycombinator.com/item?id=32704977 ("Those who do not know judy1 are doomed to reinvent it." apropos Roaring Bitmaps)
- apavlo 4y agoI taught Judy Arrays in our Advanced DB course in 2020: https://youtu.be/N6rhECUjdaI?t=3043 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.
- B1FF_PSUVM 4y ago"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).
- cmrdporcupine 4y agohttps://github.com/topics/adaptive-radix-tree https://github.com/topics/adaptive-radix-tree
- cmrdporcupine 4y agoThank you so much for these lectures on YouTube BTW. They've been highly enjoyable for me.
- ww520 4y agoThe Advanced DB course is great. It's a great survey of the modern DB technologies. Thanks for putting it up in Youtube.
- megous 4y agoI built slackware package manager replacement based on Judy Arrays, 17 years ago. :) https://spkg.megous.com/ https://spkg.megous.com/ It was quite fast even on 50 MHz 486-DX2.
- keepquestioning 4y agoWhy was I not taught this in a data structures cause?