Very fast, mutable associative data types based on Judy arrays.
A good imperative, mutable replacement for IntMap.
Judy arrays are both speed- and memory-efficient, with no tuning or configuration required, across a wide range of index set types (sequential, periodic, clustered, random). Judy's speed and memory usage are typically better than other data storage models such as skiplists, linked lists, binary, ternary, b-trees, or even hashing, and improves with very large data sets.
The memory used by a Judy array is nearly proportional to the population (number of elements).
For further references to the implementation, see:
Building a simple word-index table. About 4x faster than using an
import Control.Monad import qualified Data.Judy as J main = do j <- J.new :: IO (J.JudyL Int) forM_ [1..10000000] $ \n -> J.insert n (fromIntegral n :: Int) j v <- J.lookup 100 j print v
$ ghc -O2 --make A.hs [1 of 1] Compiling Main ( A.hs, A.o ) Linking A ...
$ time ./A Just 100 ./A 1.95s user 0.08s system 99% cpu 2.028 total
A JudyL array is a finite map from Word to Word values. A value is addressed by a key (Key). The array may be sparse, and the key may be any word-sized value. There are no duplicate keys.
Allocate a new empty JudyL array. A finalizer is associated with the JudyL array, that will free it automatically once the last reference has been dropped.
Insert a key and value pair into the JudyL array. *If the key is already present in the map, the value is not modified*
Lookup a value associated with a key in the JudyL array.
Class of things that can be stored in the JudyL array. You need to be able to convert the structure to a Word value, or a word-sized pointer.