enum-vec

高效存储枚举变体的向量

文档

假设你有一个有4个变体的枚举 Direction。存储判别符只需要2位，但Rust会使用至少1字节（8位）。因此，当使用一个包含16个元素的 Vec<Direction> 时，它将使用16字节内存。然而，这个crate提供了一个 EnumVec 类型，它只使用所需的位数。因此，一个包含16个元素的 EnumVec<Direction> 只会使用4字节内存。

实现

由于Rust没有提供计数类型变体的方式，enum_like crate定义了一个具有关联常量NUM_VARIANTS的trait EnumLike，以及从usize到T的辅助方法。此trait为一些常见类型实现，如bool和Option<T>，并且可以为任何类型实现。实现可以通过使用提供#[derive(EnumLike)]过程宏的enum_like_derive crate来自动化。

示例

将以下内容添加到你的 Cargo.toml

[dependencies]
enum_vec = "0.3"
enum_like = "0.2"
enum_like_derive = "0.1"

然后在 src/main.rs

#[macro_use]
extern crate enum_like_derive;
extern crate enum_like;
extern crate enum_vec;

use enum_vec::EnumVec;

#[derive(Copy, Clone, Debug, EnumLike)]
enum Direction {
    Left, Right, Up, Down,
}

fn main() {
    let mut v = EnumVec::new();
    v.push(Direction::Left);
    v.push(Direction::Right);
    v.push(Direction::Left);
    v.push(Direction::Right);

    for d in v {
        println!("{:?}", d);
    }
}

有关更多使用示例，请参阅 examples/src/main.rs

BitVec

由于EnumVec本质上是一个n位vec，你可以将其用作这样的。

type BitVec = EnumVec<bool>;
type TwoBitVec = EnumVec<[bool; 2]>;
type TwoBitVec = EnumVec<(bool, bool)>;
type FourBitVec = EnumVec<[bool; 4]>;

推导 EnumLike

只要枚举的所有字段都是 EnumLike，就可以自动为几乎所有类型推导 EnumLike。

struct BitField {
    opt_0: bool,
    opt_1: bool,
    opt_2: bool,
    opt_3: bool,
}
enum BitsOrRaw {
    Bits(BitField),
    Raw { opt_01: (bool, bool), opt_23: (bool, bool), },
}

impl EnumLike

您可以编写自定义的 EnumLike 实现：以下代码允许创建一个 EnumVec<Digit>，其中每个元素是 4 位，而不是由 u8 需要的 8 位。

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
struct Digit {
    x: u8, // x >= 0 && x <= 9
}

unsafe impl EnumLike for Digit {
    const NUM_VARIANTS: usize = 10;
    fn to_discr(self) -> usize {
        self.x as usize
    }
    fn from_discr(x: usize) -> Self {
        let x = x as u8;
        Self { x }
    }
}

这个特质是不安全的，因为其他代码假设 to_discr() 从不返回大于 NUM_VARIANTS 的值。

内存效率

由于默认情况下每个块是 32 位，所以当每个元素长度为 1、2、4、8、16 或 32 位时，EnumVec 才是 100% 内存高效的。这是因为元素永远不会跨越两个块：存储在 32 位块内的 15 位元素将始终使用 30 位，并浪费剩余的 2 位。一般来说，效率可以通过 1 - (32 % n) / 32 来计算，但它始终与正常的 Vec 相当或更好。然而，当 n >= 11 时，它们相等，所以如果您有一个具有 2048 个变体的类型，您应考虑使用 Vec。

完整的表格可以作为 Python 单行脚本提供

x = [(n, n/8 if n <= 8 else n/16 if n <= 16 else n/32 if n <= 32 else n/64, 1-(8%n)/8, 1-(16%n)/16, 1-(32%n)/32, 1-(64%n)/64, 1-(128%n)/128) for n in range(1, 64+1)]

一个使用 8 位存储块的 EnumVec8 不能用来存储超过 8 位的项。同样，对于存储超过 32 位的元素，默认的 EnumVec32 是不够的。一个项的最大位大小在 EnumLike crate 中定义为可以放入一个 usize 中的位数。目前，具有 128 位存储的 EnumVec 是最内存高效的选项，但大多数操作在典型的 64 位机器上比其他实现慢 2 倍。8 位、16 位、32 位和 64 位的版本具有类似性能。

每个 EnumVecN 的 "效率限制"，即它比 Vec 更好的最大项大小（以位为单位）如下

自定义

要更改默认存储，请从内部模块导入 EnumVec

use enum_vec::vec_u64::EnumVec;
use enum_vec::vec_u8::EnumVec as EnumVec8;

这将使 EnumVec 使用 64 位块，提高内存效率，并添加使用 8 位块的 EnumVec8 的选项。请注意，enum_vec![] 宏始终创建一个 EnumVec，所以以下代码将无法编译：

let a: EnumVec8 = enum_vec![];

将无法编译。

选择哪种存储大小？

• 使用 EnumVec8 以最小化小型向量的开销，实际上可以考虑使用 SmallEnumVec。
• 对于非常大的向量，尤其是当元素位大小不是 2 的幂时，使用 EnumVec64，因为它在某些情况下更内存高效。
• 只有在内存效率比性能更重要时，才使用 EnumVec128。
• 如果性能比内存效率更重要，则使用 Vec。
• 当您大多数时间需要存储少量元素（最多128位）时，请使用SmallEnumVec。

PackedU8

当项目大小为8或16位时，使用Vec始终是一个更好的选择。但这并不总是容易，因为一个Vec<[bool; 8]>将占用每个元素8字节而不是8位。要强制它使用8位，请将其包装为Vec<PackedU8<[bool; 8]>>

use enum_like::PackedU8;

let a = vec![PackedU8::new([true; 8]); 10];

for x in a {
    let x = x.value();
}

SmallEnumVec

可以在以下位置找到实验性的SmallEnumVec：

use enum_vec::smallvec_u32::EnumVec as SmallEnumVec;

当使用具有smallvec功能的编译器编译时，此功能在Cargo.toml中启用

enum_vec = { version = "0.3", features = ["smallvec"] }

SmallEnumVec将使用堆栈来存储项目，并且只有当它变得太大时才会分配。当前的默认值是使用4x32位的内联存储。这将允许存储128个1位项，64个2位项，32个4位项等。

有关更多信息，请参阅smallvec存储库。

缺点

• 由于EnumVec无法返回引用，因此没有索引语法。请使用get和set代替。
• 您不能使用切片方法，如split()，get(range)，reverse()，chunk和window迭代器，sort()，dedup()等。因为没有实现解引用（与可以用作&Vec的&[T]不同）。
• 大多数操作（push，pop，insert，remove）的速度比Vec等效操作慢2或3倍。像extend，from_slice或vec![None; 1000];这样的操作甚至更糟。

基准测试

以下是当T需要2位存储时，Vec<T>与EnumVec<T>的比较。

(提交 e8db9c883b82e472e9aefb6087be55dafd76b6a0)

 name                           normal_vec2 ns/iter  enum_vec32_2 ns/iter  diff ns/iter    diff %  speedup 
 ::bench_all                    3                    5                                2    66.67%   x 0.60 
 ::bench_all_small              3                    5                                2    66.67%   x 0.60 
 ::bench_all_worst_case         1,308                41                          -1,267   -96.87%  x 31.90 
 ::bench_all_worst_case_small   19                   5                              -14   -73.68%   x 3.80 
 ::bench_any                    8                    12                               4    50.00%   x 0.67 
 ::bench_any_small              8                    12                               4    50.00%   x 0.67 
 ::bench_any_worst_case         447                  59                            -388   -86.80%   x 7.58 
 ::bench_any_worst_case_small   11                   6                               -5   -45.45%   x 1.83 
 ::bench_extend                 419                  3,793                        3,374   805.25%   x 0.11 
 ::bench_extend_small           48                   108                             60   125.00%   x 0.44 
 ::bench_from_slice             180                  3,237                        3,057  1698.33%   x 0.06 
 ::bench_from_slice_small       27                   79                              52   192.59%   x 0.34 
 ::bench_insert                 8,059                13,154                       5,095    63.22%   x 0.61 
 ::bench_insert_at_zero         16,898               38,729                      21,831   129.19%   x 0.44 
 ::bench_insert_at_zero_small   218                  190                            -28   -12.84%   x 1.15 
 ::bench_insert_small           275                  258                            -17    -6.18%   x 1.07 
 ::bench_iter_all               2,327                4,948                        2,621   112.63%   x 0.47 
 ::bench_macro_from_elem        602                  2,435                        1,833   304.49%   x 0.25 
 ::bench_macro_from_elem_small  28                   80                              52   185.71%   x 0.35 
 ::bench_push                   4,914                7,097                        2,183    44.42%   x 0.69 
 ::bench_push_small             181                  130                            -51   -28.18%   x 1.39 
 ::bench_pushpop                4,390                12,107                       7,717   175.79%   x 0.36 
 ::bench_remove                 5,261                10,823                       5,562   105.72%   x 0.49 
 ::bench_remove_at_zero         15,880               68,593                      52,713   331.95%   x 0.23 
 ::bench_remove_at_zero_small   101                  443                            342   338.61%   x 0.23 
 ::bench_remove_small           103                  207                            104   100.97%   x 0.50 

唯一肯定比Vec等效操作更快的方法是all和any，它们利用打包来一次性处理许多元素。某些其他基准测试看起来更快是因为重新分配：当Vec达到1，2，4，8，...元素时将重新分配，但EnumVec将每32/n，64/n，...重新分配，并且由于基准测试中的n=2，而"_small"基准测试中的插入数默认为16，因此Vec将重新分配4次，而EnumVec将重新分配1次。

要运行基准测试，请下载源代码并运行

cargo +nightly bench --features smallvec > bench_log
cargo benchcmp normal_vec2 enum_vec32_2 bench_log

您需要安装cargo-benchcmp才能轻松比较基准测试。例如，要比较默认的32位EnumVec与8位EnumVec，在处理4位元素时运行

cargo benchcmp enum_vec32_4 enum_vec8_4 bench bench_log

另请参阅

枚举集

枚举映射

枚举类型

位向量

小型位向量

小型向量

lib.rs:

实现 #[derive(EnumLike)] 的过程宏