#map #set #immutable #persistent #functional

immutable-chunkmap

A fast immutable map and set with batch insert and update methods, COW operations, and big O efficient implementations of set and merge operations

20 releases (2 stable)

1.0.1 Sep 24, 2021
0.5.9 Oct 30, 2020
0.5.8 Nov 3, 2019
0.5.4 Feb 13, 2019
0.1.2 Dec 26, 2017

#132 in Data structures

Download history 648/week @ 2022-03-15 500/week @ 2022-03-22 628/week @ 2022-03-29 581/week @ 2022-04-05 447/week @ 2022-04-12 501/week @ 2022-04-19 501/week @ 2022-04-26 427/week @ 2022-05-03 679/week @ 2022-05-10 423/week @ 2022-05-17 571/week @ 2022-05-24 973/week @ 2022-05-31 945/week @ 2022-06-07 910/week @ 2022-06-14 723/week @ 2022-06-21 492/week @ 2022-06-28

3,235 downloads per month
Used in 8 crates (2 directly)

MIT/Apache

765KB
3.5K SLoC

Rust 3K SLoC // 0.0% comments JavaScript 328 SLoC // 0.1% comments OCaml 80 SLoC Shell 1 SLoC

immutable chunk map

A cache efficient immutable map, written using only safe rust, 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

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

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

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.

Dependencies