# immutable chunk map
A cache efficient immutable map with lookup performance equivalent to
BTreeMap written using only safe rust (and std), and reasonably good
insertion performance, in line with other persistent map libraries.
A graph of lookup performance of various data structures using i64
keys. Full test data in the results.gnumeric spreadsheet. Tests
performed on an Intel Core i7 6700HQ under Linux, cpu frequency
governor 'performance'.
* OCaml: core map (from the Jane Street core library), an AVL tree
with distinct leaf nodes and a relaxed balance constraint.
* Std Avl: a classical AVL tree map from the 'immutable-map' cargo
package
* Chunkmap: this library
* BTreeMap: from the Rust standard library
* Binary Search: binary search in a sorted array of keys
* HashMap: from the Rust standard library
* Array: random access to a Vec
Chunkmap is very close to BTreeMap, and binary search, which is
probably optimal for random accesses using keys without
hashing. Obviously if you don't need ordered data use a HashMap or
even a Vec.
Single insertion is slightly more expensive than a classical AVL tree,
however multi insertion modes can significantly reduce this
overhead. Anyway, if you care a lot about insertion performance you
really shouldn't use a persistent data structure, as you pay a heavy
price compared to a mutable one.
However in one very specific case, inserting into a chunkmap can be
faster than even a HashMap. If you have a lot of data to add at once
(at least 10% of what's already in the map), then you can sort it
first, and use insert_many, which is much faster than add. The graph
below shows building maps from scratch using sorted data, which is the
best possible case.
