1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242
//! This crate provides a map implementation that can make use of a fixed-size //! backing storage. It enables the compiler to heavily optimize map lookups by //! translating them into pattern matching over strictly defined enums. //! Potentially allowing for interesting performance characteristics. //! //! For more information on how to use, see the [documentation]. //! //! ## Features //! //! The following features are available: //! //! * `serde` - Causes [Map] and [Set] to implement [Serialize] and //! [Deserialize] if it's implements by their keys and/or values. //! //! ## Deriving `Key` //! //! The [Key derive] is provided to instruct the `fixed-map` containers on how //! to build optimized storage for a given Key. We also require the key to //! implement [Copy] for it to implement `Key`. //! //! ```rust //! 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)); //! ``` //! //! ## 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 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 by storing the data as an array like //! `[Option<Item>; N]` where each index correspondings to each variant in //! `Dir`. //! //! Doing this yourself could look like this: //! //! ``` //! #[repr(usize)] //! pub enum Dir { //! North, //! East, //! South, //! West, //! } //! //! #[derive(Debug)] //! pub enum Item { //! Bow, //! Sword, //! Axe, //! } //! //! 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 `fixed-map` you can do it like this without (hopefully) incurring //! any drop in performance: //! //! ```rust //! 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); //! } //! ``` //! //! ## Unsafe use //! //! This crate uses unsafe for its iterators. This is needed because there is no //! proper way to associate generic lifetimes to associated types. //! //! Instead, we associate the lifetime to the container (`Map` or `Set`) which //! wraps a set of unsafe derefs over raw pointers. //! //! ## Benchmarks //! //! 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. //! //! ```text //! 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] //! ``` //! //! [`hashbrown`]: https://github.com/Amanieu/hashbrown //! //! ## Examples //! //! 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/ //! ``` //! //! [Map]: https://docs.rs/fixed-map/*/fixed_map/map/struct.Map.html //! [Set]: https://docs.rs/fixed-map/*/fixed_map/map/struct.Set.html //! [Copy]: https://doc.rust-lang.org/std/marker/trait.Copy.html //! [documentation]: https://docs.rs/fixed-map //! [Key derive]: https://docs.rs/fixed-map/*/fixed_map/derive.Key.html #![deny(missing_docs)] pub mod key; pub mod map; pub mod set; pub mod storage; pub use self::map::Map; pub use self::set::Set; pub use fixed_map_derive::Key;