I'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 ..
Judy 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.
Intrigued, 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.
I 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?
9 comments
[ 3.1 ms ] story [ 35.9 ms ] threadhttp://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.
Sure would be nice to see Judy in modern architectures like Android/iOS, though ..
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.
http://rusty.ozlabs.org/?p=153
http://www.nothings.org/computer/judy/
It is unfortunately not improved by the new update tacked to the beginning of the article. You're probably better off skipping that.
http://xkcd.com/327/ in case you don't get the reference.