Skip to content

Comment on Judy arrays are patented

Comments

This has been true for quite a long time, and IIRC is why they're not more widely used. That and they're pretty complicated to implement properly.

They are only better for some workloads and not others. e.g., they are excellent for accessing data in-order, but are worse than a very simple hash table for random access:

http://preshing.com/20130107/this-hash-table-is-faster-than-...

(yes, this hash table is vulnerable to timing attacks; point is, for many workloads Judy brings in considerable complexity but is actually inferior to other solutions).

Just an aside, but man, that's a refreshingly readable and pleasant article...

That, and because they need to be tuned for each individual cache line size.

See http://nothings.org/computer/judy/ for a more thorough analysis of Judy arrays (at 20 kLoC) versus straightforward hash tables (at 0.2 kLoC).

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.