Judy Arrays

http://judy.sourceforge.net

by ColinWright • 14 years ago

47 9 14 years ago

judy.sourceforge.net

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.

erichocean• 14 years ago

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

seclorum• 14 years ago

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

sovande• 14 years ago

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.

marshray• 14 years ago

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.

FreeFull• 14 years ago

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

julian37• 14 years ago

Two articles benchmarking Judy arrays compared to hash tables:

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

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

tptacek• 14 years ago

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.

sashametro• 14 years ago

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.

Judy Arrays

Related Stories