Lib.rs

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.11"

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.

The experiment was performed on 30-04-2023. There were 10000 repetition cycles. The entire benchmark took 486s.

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.