Judy Arrays | Hacker News Reader

Judy Arrays

judy.sourceforge.net

47 pointsColinWright9 comments

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.

According to Wikipedia there is a patent that concerns these. http://www.google.com/patents/US6735595

Two articles benchmarking Judy arrays compared to hash tables:

http://rusty.ozlabs.org/?p=153

http://www.nothings.org/computer/judy/

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

It looks like this was discussed a few years ago:

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.

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.

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?

http://xkcd.com/327/ in case you don't get the reference.

I use these extensively, love them. (The API is really hard at first though.)

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

Reply on news.ycombinator.com