It is an alternative on-heap implementation of a map with keys of type usize and a fixed capacity. It works much faster than a standard HashMap because it allocates memory for all keys at once and then the cost of get() is O(1). Obviously, with this design, the cost of iter() increases because the iterator has to jump through empty keys. However, there is a supplementary function next_key(), which returns the next available key in the map. It is recommended to use it in order to ensure sequential order of the keys, which will guarantee O(1) cost of next() in iterators.
If usize keys are placed sequentially, the only true competitor of ours is std::vec::Vec. We beat it too, see the benchmarking results below.
First, add this to Cargo.toml:
[dependencies]
emap = "0.0.13"
Then, use it like a standard hash map... well, almost:
use emap::Map;
let mut m : Map<&str> = Map::with_capacity_init(100); // allocation on heap
m.insert(m.next_key(), "foo");
m.insert(m.next_key(), "bar");
assert_eq!(2, m.len());
If more than 100 keys will be added to the map, it will panic. The map doesn't increase its size automatically, like Vec does (this is one of the reasons why we are faster).
Read the API documentation. The struct emap::Map is designed as closely similar to std::collections::HashMap as possible.
Benchmark
There is a summary of a simple benchmark, where we compared emap::Map with Vec, changing the total capacity CAP of them (horizontal axis). We applied the same interactions (benchmark.rs) to them both and measured how fast they performed. In the following table, the numbers over 1.0 indicate performance gain of Map against Vec, while the numbers below 1.0 demonstrate performance loss.
| 4 | 16 | 256 | 4096 | |
|---|---|---|---|---|
i ∈ 0..CAP {M.insert(i, &"Hello, world!")} |
1.08 | 1.91 | 2.26 | 2.21 |
i ∈ 0..CAP {M.insert(i, &"大家好"); s ∈ M.values() {sum += s.len()}} |
1.04 | 0.56 | 0.50 | 0.35 |
i ∈ 0..CAP {M.insert(i, &42); s ∈ M.into_values() {sum += s}} |
1.02 | 0.76 | 0.35 | 0.35 |
i ∈ 0..CAP {M.insert(i, &42); s ∈ M.keys() {sum += s}} |
1.05 | 0.65 | 0.34 | 0.35 |
i ∈ 0..CAP {M.insert(i, &42); s ∈ M.values() {sum += s}} |
1.14 | 0.61 | 0.50 | 0.52 |
i ∈ 0..CAP {M.insert(i, &42)}; M.clear(); M.len(); |
1.14 | 2.20 | 6.37 | 7.85 |
i ∈ 0..CAP {M.insert(i, &42)}; i ∈ CAP-1..0 {M.remove(&i)} |
1.21 | 1.90 | 2.23 | 2.31 |
The experiment was performed on 30-04-2023. There were 10000 repetition cycles. The entire benchmark took 509s.
How to Contribute
First, install Rust and then:
$ cargo test -vv
If everything goes well, fork repository, make changes, send us a pull request. We will review your changes and apply them to the master branch shortly, provided they don't violate our quality standards. To avoid frustration, before sending us your pull request please run cargo test again. Also, run cargo fmt and cargo clippy.
Also, before you start making changes, run benchmarks:
$ rustup run nightly cargo bench
Then, after the changes you make, run it again. Compare the results. If your changes degrade performance, think twice before submitting a pull request.
3 Nov 5, 2023
3 Sep 15, 2022
9 Feb 28, 2023
27 Jun 26, 2023
1 Oct 26, 2021
5 Nov 5, 2022
98 Jun 21, 2023
2 Oct 24, 2021
43 Nov 25, 2022
9 Sep 8, 2023
4 Mar 30, 2024
8 Aug 23, 2022
1 Jun 17, 2022
15 Mar 23, 2023
12 Apr 19, 2023
48 Jun 14, 2023
19 Jul 12, 2023
67 Jan 1, 2023
3 Dec 6, 2022