This crate provides a Map
and Set
container that can make use of a
pre-calculated backing storage. This enables the Rust compiler to heavily
optimize operations over them and avoid allocating.
See documentation for information on how to use this crate.
Add fixed-map
to your Cargo.toml
:
[dependencies]
fixed-map = "0.8.0"
Anything used as a key in either a Map
or a Set
needs to implement
the Key
trait. This should be derived:
use fixed_map::{Key, Map};
#[derive(Clone, Copy, Key)]
enum Key {
North,
South,
East,
West,
}
After this you can use one of our containers:
use fixed_map::{Map, Set};
let mut map = Map::new();
map.insert(Key::North, 200);
map.insert(Key::South, 100);
assert_eq!(map.get(Key::North), Some(&200));
assert_eq!(map.get(Key::East), None);
let mut set = Set::new();
set.insert(Key::North);
set.insert(Key::South);
assert!(set.contains(Key::South));
assert!(!set.contains(Key::East));
The following features are available:
std
- Disabling this feature causes this crate to be no-std. This means that dynamic types cannot be used in keys, like ones enabled by themap
feature (default).hashbrown
- CausesStorage
to be implemented by dynamic types such as&'static str
oru32
. These are backed by ahashbrown
(default).entry
- Enables anentry
API similar to that found onHashMap
.serde
- CausesMap
andSet
to implementSerialize
andDeserialize
if it's implemented by the key and value.
Specialized storage through the Key
trait
The Key
derive is provided to instruct our containers on how to build
optimized storage for a given Key
. We also require any key to be Copy
.
use fixed_map::Key;
#[derive(Clone, Copy, Key)]
enum Key {
North,
South,
East,
West,
}
What happens behind the scenes is that a proc macro is used to build a struct optimized for storing and indexing exactly 4 values - one for each variant.
Something exactly like this:
struct Storage<V> {
data: [Option<V>; 4],
}
It becomes a bit more complicated once we start considering composite
keys. See the Key
documentation for more information.
There are many cases where you want associate a value with a small, fixed number of elements identified by an enum.
Let's say you have a game where each room has something in four directions. We can model this relationship between the direction and the item using two enums.
#[repr(usize)]
pub enum Dir {
North,
East,
South,
West,
}
pub enum Item {
Bow,
Sword,
Axe,
}
The goal is for the performance of fixed map to be identical to storing the
data linearly in memory like you could through an array like [Option<Item>; N]
where each index corresponds to a variant in Dir
.
Doing this manually could look like this:
let mut map: [Option<Item>; 4] = [None, None, None, None];
map[Dir::North as usize] = Some(Item::Bow);
if let Some(item) = &map[Dir::North as usize] {
println!("found item: {:?}", item);
}
But with a fixed Map
you can do it idiomatically like this, without
incurring a drop in performance:
use fixed_map::{Key, Map};
#[derive(Clone, Copy, Key)]
pub enum Dir {
North,
East,
South,
West,
}
#[derive(Debug)]
pub enum Item {
Bow,
Sword,
Axe,
}
let mut map = Map::new();
map.insert(Dir::North, Item::Bow);
if let Some(item) = map.get(Dir::North) {
println!("found item: {:?}", item);
}
The Entry API uses unwrap_unchecked
to obtain mutable references to the
inner value of Some
s, and to skip drop
when overwriting None
s.
We include benchmarks to ensure that we abide by the expectation that a fixed map or set should perform roughly the same as an array with the same number of elements.
In the following benchmarks fixed-map is compared to:
fixed
- AMap
with a derivedKey
withN
variants.hashbrown
- A high performance hash map. This is only included for reference.- Note: Maps are created with
HashMap::with_capacity(N)
.
- Note: Maps are created with
array
- A simple[Option<Key>; N]
array.
Note: for all insert
benchmarks the underlying storage is cloned in each
iteration.
get/fixed/4 time: [208.96 ps 209.57 ps 210.17 ps]
get/fixed/8 time: [211.12 ps 211.86 ps 212.55 ps]
get/fixed/16 time: [211.50 ps 211.84 ps 212.23 ps]
get/fixed/32 time: [211.02 ps 211.40 ps 211.79 ps]
get/array/4 time: [215.76 ps 216.56 ps 217.68 ps]
get/array/8 time: [216.80 ps 217.28 ps 217.83 ps]
get/array/16 time: [215.88 ps 216.21 ps 216.58 ps]
get/array/32 time: [216.39 ps 216.82 ps 217.33 ps]
get/hashbrown/4 time: [2.9134 ns 2.9168 ns 2.9210 ns]
get/hashbrown/8 time: [2.9143 ns 2.9175 ns 2.9212 ns]
get/hashbrown/16 time: [2.9258 ns 2.9293 ns 2.9328 ns]
get/hashbrown/32 time: [2.9387 ns 2.9428 ns 2.9466 ns]
insert/fixed/4 time: [421.82 ps 422.47 ps 423.22 ps]
insert/fixed/8 time: [635.46 ps 636.91 ps 638.55 ps]
insert/fixed/16 time: [1.0579 ns 1.0599 ns 1.0621 ns]
insert/fixed/32 time: [1.6991 ns 1.7016 ns 1.7043 ns]
insert/array/4 time: [419.26 ps 419.76 ps 420.30 ps]
insert/array/8 time: [624.30 ps 626.27 ps 628.33 ps]
insert/array/16 time: [1.0444 ns 1.0467 ns 1.0490 ns]
insert/array/32 time: [1.6828 ns 1.6904 ns 1.6990 ns]
insert/hashbrown/4 time: [87.002 ns 87.233 ns 87.475 ns]
insert/hashbrown/8 time: [96.995 ns 97.287 ns 97.589 ns]
insert/hashbrown/16 time: [517.89 ns 518.66 ns 519.57 ns]
insert/hashbrown/32 time: [156.10 ns 156.67 ns 157.30 ns]
values/fixed/4 time: [209.09 ps 209.51 ps 209.91 ps]
values/fixed/8 time: [213.99 ps 215.34 ps 217.08 ps]
values/fixed/16 time: [213.24 ps 213.94 ps 214.72 ps]
values/fixed/32 time: [212.71 ps 213.82 ps 215.15 ps]
values/array/4 time: [211.07 ps 211.78 ps 212.59 ps]
values/array/8 time: [211.48 ps 212.03 ps 212.65 ps]
values/array/16 time: [213.04 ps 213.49 ps 213.99 ps]
values/array/32 time: [213.18 ps 213.78 ps 214.60 ps]
values/hashbrown/4 time: [3.3965 ns 3.4007 ns 3.4056 ns]
values/hashbrown/8 time: [3.8443 ns 3.8627 ns 3.8895 ns]
values/hashbrown/16 time: [5.6312 ns 5.6666 ns 5.7029 ns]
values/hashbrown/32 time: [8.7221 ns 8.7674 ns 8.8117 ns]
array/sum_values time: [3.0394 ns 3.0463 ns 3.0534 ns]
fixed/sum_values time: [3.0503 ns 3.0559 ns 3.0619 ns]
Most examples are in place to test what kind of assembler they compile to.
To do this, run:
RUSTFLAGS="--emit asm" cargo build --release --example <example>
You should be able to find the assembler generated in the target folder:
ls target/release/examples/