Lib.rs

› 数据结构
#map #container #proc-macro #key-value #no-std

no-std fixed-map

使用过程宏计算存储布局的固定映射

作者： John-John Tedro， Peter Jaszkowiak

26个版本

0.9.5 2024年4月19日
0.9.3 2023年10月21日
0.9.2 2023年4月26日
0.8.2 2023年3月22日
0.5.0 2018年12月23日

#138 在 数据结构 中

Download history 75/week @ 2024-04-26 29/week @ 2024-05-03 46/week @ 2024-05-10 45/week @ 2024-05-17 65/week @ 2024-05-24 32/week @ 2024-05-31 37/week @ 2024-06-07 30/week @ 2024-06-14 35/week @ 2024-06-21 23/week @ 2024-06-28 82/week @ 2024-07-05 34/week @ 2024-07-12 62/week @ 2024-07-19 43/week @ 2024-07-26 50/week @ 2024-08-02 18/week @ 2024-08-09

每月179 次下载
用于 3 crate

MIT/Apache

180KB
2.5K SLoC

fixed-map

github crates.io docs.rs build status

此crate提供了一个Map和Set容器，可以利用预先计算的底层存储。这使得Rust编译器可以对这些操作进行大量优化并避免分配。

有关如何使用此crate的更多信息，请参阅文档。


用法

将fixed-map添加到您的Cargo.toml

[dependencies]
fixed-map = "0.9.5"

用作Map或Set中的键的任何内容都需要实现Key特质。这应该被派生

use fixed_map::{Key, Map};

#[derive(Clone, Copy, Key)]
enum MyKey {
    North,
    South,
    East,
    West,
}

之后，您可以使用我们的容器之一

use fixed_map::{Map, Set};

let mut map = Map::new();
map.insert(MyKey::North, 200);
map.insert(MyKey::South, 100);

assert_eq!(map.get(MyKey::North), Some(&200));
assert_eq!(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));

功能

以下功能可用

  • std - 禁用此功能会导致此crate为no-std。这意味着无法在键中使用动态类型，如通过map功能启用的那样（默认）。
  • hashbrown - 导致Storage通过动态类型（如&'static str或u32）实现。这些由hashbrown支持（默认）。
  • entry - 启用类似于在HashMap中找到的entry API。
  • serde - 如果键和值实现了，则使Map和Set实现Serialize和Deserialize。

通过Key特性实现专业存储

通过Key派生来实现，指导我们的容器如何为给定的Key构建优化的存储。我们还要求任何键必须是Copy。

use fixed_map::Key;

#[derive(Clone, Copy, Key)]
enum MyKey {
    North,
    South,
    East,
    West,
}

幕后发生的事情是使用进程宏构建一个结构体，该结构体针对存储和索引恰好4个值进行了优化——每个变体一个。

就是这样的东西

struct Storage<V> {
    data: [Option<V>; 4],
}

一旦我们开始考虑复合键，事情就会变得复杂起来。有关更多信息，请参阅Key文档。


为什么这个crate存在？

有很多情况，你想将一个值与通过枚举识别的小型固定数量的元素关联起来。

比如说，你有一个游戏，每个房间在四个方向上都有东西。我们可以使用两个枚举来模拟方向和物品之间的关系。

#[repr(usize)]
pub enum Dir {
    North,
    East,
    South,
    West,
}

pub enum Item {
    Bow,
    Sword,
    Axe,
}

目标是使固定映射的性能与像通过数组（如[Option<Item>; N]）那样线性存储数据一样，其中每个索引对应于Dir中的一个变体。

手动实现可能看起来像这样

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);
}

但是，使用固定的Map，你可以像这样习惯性地做，而不会降低性能

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);
}

不安全使用

Entry API使用unwrap_unchecked来获取Some的内部值的可变引用，并且在覆盖None时跳过drop。


基准测试

我们包括基准测试以确保我们遵守固定映射或集合的性能应大致与具有相同元素数量的数组相同的预期。

以下基准测试将fixed-map与以下内容进行比较：

  • fixed - 一个具有派生Key（具有N个变体）的Map。
  • hashbrown - 一个高性能哈希表。这仅包括作为参考。
    • 注意：映射使用HashMap::with_capacity(N)创建。
  • array - 一个简单的[Option<Key>; N]数组。

注意：对于所有insert基准测试，底层存储在每个迭代中都会进行克隆。

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]

示例

大多数示例都是用来测试它们编译成什么样的汇编代码。

要这样做，请运行

RUSTFLAGS="--emit asm" cargo build --release --example <example>

你应该能在目标文件夹中找到生成的汇编器

ls target/release/examples/

依赖项

~1.6–2.3MB
~39K SLoC