micromap

Crates.io	micromap
lib.rs	micromap
version	0.0.15
source	src
created_at	2023-04-16 16:46:58.338612
updated_at	2024-01-01 05:46:10.451559
description	The fastest alternative to HashMap, for maps smaller than 20 keys
homepage	https://github.com/yegor256/micromap
repository	https://github.com/yegor256/micromap
max_upload_size
id	840688
size	100,874

Yegor Bugayenko (yegor256)

documentation

README

A much faster alternative of HashMap, for very small maps. It is also faster than FxHashMap, hashbrown, ArrayMap, IndexMap, and all others. The smaller the map, the higher the performance. It was observed that when a map contains more than 20 keys, it may be better to use the standard HashMap, since the performance of micromap::Map may start to degrade. See the benchmarking results below.

WELCOME: Not all functions that you might expect to have in a map are implemented. I will appreciate if you contribute by implementing these missing functions.

First, add this to Cargo.toml:

[dependencies]
micromap = "0.0.14"

Then, use it like a standard hash map... well, almost:

use micromap::Map;
let mut m : Map<u64, &str, 10> = Map::new(); // allocation on stack
m.insert(1, "foo");
m.insert(2, "bar");
assert_eq!(2, m.len());

Pay attention, here the map is created with an extra generic argument 10. This is the total size of the map, which is allocated on stack when ::new() is called. Unlike HashMap, the Map doesn't use heap at all. If more than ten keys will be added to the map, it will panic.

Read the API documentation. The struct micromap::Map is designed as closely similar to std::collections::HashMap as possible.

Benchmark

There is a summary of a simple benchmark, where we compared micromap::Map with a few other Rust maps, changing the total capacity of the map (horizontal axis). We applied the same interactions (benchmark.rs) to them and measured how fast they performed. In the following table, the numbers over 1.0 indicate performance gain, while the numbers below 1.0 demonstrate performance loss.

	2	4	8	16	32	64	128
`hashbrown::HashMap`	21.49	11.70	6.48	3.64	1.66	0.60	0.31
`heapless::LinearMap`	1.00	1.59	1.18	1.27	1.34	1.20	0.98
`indexmap::IndexMap`	12.81	12.48	7.53	4.62	2.41	0.97	0.49
`linear_map::LinearMap`	2.27	1.62	1.16	1.09	1.04	1.15	1.15
`linked_hash_map::LinkedHashMap`	28.55	21.61	12.49	7.42	3.83	1.57	0.78
`litemap::LiteMap`	3.76	2.89	2.04	1.86	1.32	0.59	0.48
`micromap::Map` 👍	1.00	1.00	1.00	1.00	1.00	1.00	1.00
`nohash_hasher::BuildNoHashHasher`	21.08	12.04	7.62	3.31	1.65	0.64	0.34
`rustc_hash::FxHashMap`	20.51	11.79	6.66	3.94	1.44	0.55	0.30
`std::collections::BTreeMap`	21.16	10.37	8.66	6.60	3.83	1.20	0.73
`std::collections::HashMap`	22.02	14.87	8.98	5.29	2.84	1.05	0.58
`tinymap::array_map::ArrayMap`	2.00	4.71	4.56	4.90	5.58	4.57	4.70

The experiment was performed on 31-12-2023. There were 1000000 repetition cycles. The entire benchmark took 194s.

As you see, the highest performance gain was achieved for the maps that were smaller than ten keys. For the maps of just a few keys, the gain was enormous.

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.

Commit count: 360