fixed-map

Note: this crate is still in heavy development. Please be careful!

This crate provides a map implementation that can make use of a fixed-size backing storage.

For more information on how to use fixed-map, see the documentation.

The `Key` derive

The Key derive is provided to construct optimized storage for a given Key.

For example:

use fixed_map::{Key, Map};

#[derive(Clone, Copy, Key)]
enum Part {
    One,
    Two,
}

#[derive(Clone, Copy, Key)]
enum Key {
    Simple,
    Composite(Part),
    String(&'static str),
    Number(u32),
    Singleton(()),
}

let mut map = Map::new();

map.insert(Key::Simple, 1);
map.insert(Key::Composite(Part::One), 2);
map.insert(Key::String("foo"), 3);
map.insert(Key::Number(1), 4);
map.insert(Key::Singleton(()), 5);

assert_eq!(map.get(Key::Simple), Some(&1));
assert_eq!(map.get(Key::Composite(Part::One)), Some(&2));
assert_eq!(map.get(Key::Composite(Part::Two)), None);
assert_eq!(map.get(Key::String("foo")), Some(&3));
assert_eq!(map.get(Key::String("bar")), None);
assert_eq!(map.get(Key::Number(1)), Some(&4));
assert_eq!(map.get(Key::Number(2)), None);
assert_eq!(map.get(Key::Singleton(())), Some(&5));

Missing APIs

The API of this project is incomplete since it is experimental. You can help by adding more!

Why does this crate exist?

There are many cases where you want associate a value with a small, fixed number of elements identified by an enum.

For example, let's say you have a game where each room has something in for directions:

#[derive(Key)]
pub enum Dir {
    North,
    East,
    South,
    West,
}

Now we can use this map to associate an item with each direction.

let mut map = fixed_map::Map::new();
map.insert(Dir::North, Item::Bow);

Performance

The goal is for the performance of fixed-map to be identical to storing the data linearly in memory like when using [Option<Key>; N].

In the following benchmarks, fixed-map is compared to:

fixed - A fixed_map::Map with a derived Key with N variants.
hashbrown - A high performance hash map. This is only included for reference.
- Note: Maps are created with HashMap::with_capacity(N).
array - A simple [Option<Key>; N] array.

Note: for all insert benchmarks the underlying map is cloned in each iteration.

fixed/get4              time:   [253.97 ps 255.78 ps 257.75 ps]
fixed/get8              time:   [257.56 ps 259.70 ps 261.82 ps]
fixed/get16             time:   [253.47 ps 255.78 ps 258.44 ps]
fixed/get32             time:   [245.90 ps 246.58 ps 247.35 ps]

array/get4              time:   [490.51 ps 491.72 ps 493.00 ps]
array/get8              time:   [514.83 ps 519.88 ps 525.49 ps]
array/get16             time:   [520.87 ps 528.57 ps 538.60 ps]
array/get32             time:   [515.18 ps 525.02 ps 537.46 ps]

hashbrown/get4          time:   [3.4101 ns 3.4419 ns 3.4792 ns]
hashbrown/get8          time:   [3.3051 ns 3.3220 ns 3.3437 ns]
hashbrown/get16         time:   [3.2872 ns 3.2961 ns 3.3058 ns]
hashbrown/get32         time:   [3.2700 ns 3.2783 ns 3.2869 ns]

fixed/insert4           time:   [494.04 ps 495.74 ps 497.61 ps]
fixed/insert8           time:   [752.24 ps 755.71 ps 760.33 ps]
fixed/insert16          time:   [1.3142 ns 1.3196 ns 1.3252 ns]
fixed/insert32          time:   [2.1143 ns 2.1203 ns 2.1259 ns]

array/insert4           time:   [500.43 ps 504.79 ps 509.23 ps]
array/insert8           time:   [767.07 ps 769.24 ps 771.50 ps]
array/insert16          time:   [1.3343 ns 1.3386 ns 1.3431 ns]
array/insert32          time:   [2.1609 ns 2.1668 ns 2.1730 ns]

hashbrown/insert4       time:   [85.362 ns 86.288 ns 87.712 ns]
hashbrown/insert8       time:   [96.778 ns 97.102 ns 97.482 ns]
hashbrown/insert16      time:   [122.12 ns 122.56 ns 123.05 ns]
hashbrown/insert32      time:   [166.31 ns 167.78 ns 169.47 ns]

fixed/iter4             time:   [2.0091 ns 2.0141 ns 2.0191 ns]
fixed/iter8             time:   [6.4643 ns 6.4953 ns 6.5312 ns]
fixed/iter16            time:   [46.684 ns 46.839 ns 47.006 ns]
fixed/iter32            time:   [99.789 ns 100.03 ns 100.28 ns]

array/iter4             time:   [6.5876 ns 6.6116 ns 6.6361 ns]
array/iter8             time:   [6.4052 ns 6.4235 ns 6.4438 ns]
array/iter16            time:   [7.5715 ns 7.6424 ns 7.7706 ns]
array/iter32            time:   [10.104 ns 10.174 ns 10.281 ns]

hashbrown/iter4         time:   [3.7405 ns 3.7538 ns 3.7672 ns]
hashbrown/iter8         time:   [4.5252 ns 4.5433 ns 4.5692 ns]
hashbrown/iter16        time:   [8.5868 ns 8.6118 ns 8.6375 ns]
hashbrown/iter32        time:   [12.868 ns 12.898 ns 12.928 ns]

Examples

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/

LICENSE

This project is distributed under the terms of both the MIT license and the Apache License (Version 2.0).

This project contains code derived from HashMap (Rust stdlib).

fixed-map 0.6.1