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:
toml
[dependencies]
fixed-map = "0.9.0"
Anything used as a key in either a [Map] or a [Set] needs to implement
the [Key] trait. This should be derived:
```rust use fixed_map::{Key, Map};
enum MyKey { North, South, East, West, } ```
After this you can use one of our containers:
```rust use fixed_map::{Map, Set};
let mut map = Map::new(); map.insert(MyKey::North, 200); map.insert(MyKey::South, 100);
asserteq!(map.get(MyKey::North), Some(&200)); asserteq!(map.get(MyKey::East), None);
let mut set = Set::new(); set.insert(MyKey::North); set.insert(MyKey::South);
assert!(set.contains(MyKey::South)); assert!(!set.contains(MyKey::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 the map
feature (default).hashbrown - Causes [Storage] to be implemented by dynamic types such
as &'static str or u32. These are backed by a hashbrown (default).entry - Enables an [entry] API similar to that found on [HashMap].serde - Causes [Map] and [Set] to implement [Serialize] and
[Deserialize] if it's implemented by the key and value.Key] traitThe [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].
```rust use fixed_map::Key;
enum MyKey { 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:
rust
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.
```rust
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:
```rust
let mut map: [Option
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:
```rust use fixed_map::{Key, Map};
pub enum Dir { North, East, South, West, }
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 Somes, and to skip drop when overwriting Nones.
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 - A [Map] with a derived [Key] with N variants.hashbrown] - A high performance hash map. This is only included for
reference.
HashMap::with_capacity(N).array - A simple [Option<Key>; N] array.Note: for all insert benchmarks the underlying storage is cloned in each
iteration.
```text 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/sumvalues time: [3.0394 ns 3.0463 ns 3.0534 ns] fixed/sumvalues 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:
sh
RUSTFLAGS="--emit asm" cargo build --release --example <example>
You should be able to find the assembler generated in the target folder:
sh
ls target/release/examples/