Judy, a datastructure taylored for modern CPUs

Marc Ernst Eddy van Woerkom <>
Sat Mar 8 21:59:36 CET 2003


reading about functional datastructures, below is 
something that is opposite in spirit. :)
A datastructure that is designed to take advantage of 
the architecture of modern CPUs.

BTW are associative arrays are used deep within
the Erlang implementation? :)


------- Start of forwarded message -------

Judy is an implementation of a sorted associative array in C.  All
reasonable associative array implementations have O(log N) insert and
lookup complexity, but the constant factor for Judy is very much
smaller than other widely used implementations (several times faster
than STL's "map" and twice as fast as SGI's "hash_map", in my trivial
benchmarks).  The designer explains why here
<http://judy.sourceforge.net/downloads/10minutes.htm>; most of the 
improvement comes from awareness of the characteristics of modern 
memory architectures.
sweetcode mailing list
------- End of forwarded message -------

More information about the erlang-questions mailing list