4 ms·
Judy Arrays
- ColinWright 15y agoIt looks like this was discussed a few years ago: http://news.ycombinator.com/item?id=859336 http://news.ycombinator.com/item?id=859336 That discussion is worth reading, but any new insights will have to go here, because that submission is old enough to have the discussion closed.
- erichocean 15y agoI use these extensively, love them. (The API is really hard at first though.)
- seclorum 15y agoI've used them too, for years .. its my 'go-to' for sparse arrays on any internal/utility projects I'm using. I'm a bit hesitant to ship anything using them to end-users, though, due to the HP patent issue .. but thats just a gut feeling. Technically, there's not much out there that gives me the ease-of-use and performance of the Judy API for large, sparse or dense, datasets. I didn't find the API too challenging .. well, the fact is that once you get Judy integrated into your own datatype classes, its a dead cinch. Sure would be nice to see Judy in modern architectures like Android/iOS, though ..
- sovande 15y agoJudy arrays are implemented as a trie and one of the cool things is that arrays can be sparse or dense. As a sparse array it is (almost) as fast as a hash table. As a dense array it basically works as a bit map which is one of, if not, the fastest data structure around.
- marshray 15y agoIntrigued, I looked into them a few months ago. My conclusions: 1. They're patented by HP. 2. They're highly tuned for a specific cache line size. 3. They bring in a lot of code competing for space in the instruction cache. It may be optimal in benchmarks, but I suspect it could contribute to that general bloat miasma feeling your code gets when it's just too darn large. I didn't run benchmarks myself, but overall I decided that (for me anyway) Judy arrays were probably not worth it over simpler alternatives.
- FreeFull 15y agoAccording to Wikipedia there is a patent that concerns these. http://www.google.com/patents/US6735595 http://www.google.com/patents/US6735595
- julian37 15y agoTwo articles benchmarking Judy arrays compared to hash tables: http://rusty.ozlabs.org/?p=153 http://rusty.ozlabs.org/?p=153 http://www.nothings.org/computer/judy/ http://www.nothings.org/computer/judy/
- tptacek 15y agoI really like that nothings.org article, for what it's worth: worth reading. It is unfortunately not improved by the new update tacked to the beginning of the article. You're probably better off skipping that.
- sashametro 15y agoI wonder, if somebody took the same optimization approach (cache-line size optimization) to the tree/hash/etc. data-structures and applied them to matrices, would they be inspired to call them Bobby Tables? http://xkcd.com/327/ http://xkcd.com/327/ in case you don't get the reference.