Re:Judy arrays are patented
by zrail on Friday January 11, 2013 @01:45PM
(#5044238)
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.
[ Parent
| on HN ]
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).
Re:Judy arrays are patented
by snogglethorpe on Friday January 11, 2013 @06:09PM
(#5045586)
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).