immutable-chunkmap 2.0.6

A fast immutable map and set with batch insert and update methods, COW operations, and big O efficient implementations of set and merge operations
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 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

![alt text](bench/charts/intel_corei7-8550U_arrayvec_compact/usize_get.png "average lookup time")

Chunkmap is very close to BTreeMap for random accesses using keys
without hashing. Obviously if you don't need ordered data use a
HashMap.

![alt text](bench/charts/intel_corei7-8550U_arrayvec_compact/usize_insert.png "average insert time")

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.

![alt text](bench/charts/intel_corei7-8550U_arrayvec_compact/usize_insert_many.png "insert many")

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.