45 lines
2.0 KiB
Markdown
45 lines
2.0 KiB
Markdown
# immutable chunk map
|
|
|
|
A cache efficient immutable map with lookup performance close to
|
|
BTreeMap and reasonably good insertion performance. Optional copy on
|
|
write mutable operations bring modification performance within 2x of
|
|
BTreeMap in the best case while still offering snapshotting, and big O
|
|
efficient set operations of a persistant data structure.
|
|
|
|
A graph of lookup performance of various data structures using usize
|
|
keys. Full test data in the bench/charts directory. Tests performed on
|
|
an Intel Core i7 8550U under Linux with a locked frequency of 1.8 GHz.
|
|
|
|
* OCaml: core map (from the Jane Street core library), an AVL tree
|
|
with distinct leaf nodes and a relaxed balance constraint.
|
|
* Chunkmap: this library
|
|
* Chunkmap COW: this library using only COW operations
|
|
* BTreeMap: from the Rust standard library
|
|
* HashMap: from the Rust standard library
|
|
|
|
|
|
|
|
Chunkmap is very close to BTreeMap for random accesses using keys
|
|
without hashing. Obviously if you don't need ordered data use a
|
|
HashMap.
|
|
|
|
|
|
|
|
Insertion performance, while not as good as most mutable data
|
|
structures, is not awful when using COW mode exclusively. In the case
|
|
where you have many updates to do at once you can go even faster by
|
|
using insert_many. In some cases, e.g. building a map from scratch
|
|
using sorted inputs this can be faster than even a HashMap. The below
|
|
case is more typical, adding 10% of a data set to the map.
|
|
|
|
|
|
|
|
A note about the COW bar on this graph. It represents using only
|
|
mutable COW operations on the map, it is perfectly possible to use an
|
|
actual insert_many call instead of mutable COW operations if it's
|
|
faster in your application, which as you can see, depends on the size
|
|
of the map.
|
|
|
|
# License
|
|
This project is dual licensed under the MIT or the Apache 2 at your discretion.
|