2个版本
使用旧的Rust 2015
| 0.1.1 | 2018年9月24日 |
|---|---|
| 0.1.0 | 2018年9月24日 |
#15 in #索引
37KB
771 行
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>，并且可以为任何类型实现。实现可以使用enum_like_derive crate自动进行，它提供了一个#[derive(EnumLike)]过程宏。
示例
将此添加到你的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，你可以将其用作位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。
| n | Vec | EnumVec8 | EnumVec16 | EnumVec32 | EnumVec64 | EnumVec128 |
|---|---|---|---|---|---|---|
| 1 | 0.125 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0.25 | 1 | 1 | 1 | 1 | 1 |
| 3 | 0.375 | 0.75 | 0.9375 | 0.9375 | 0.984375 | 0.984375 |
| 4 | 0.5 | 1 | 1 | 1 | 1 | 1 |
| 5 | 0.625 | 0.625 | 0.9375 | 0.9375 | 0.9375 | 0.9765625 |
| 6 | 0.75 | 0.75 | 0.75 | 0.9375 | 0.9375 | 0.984375 |
| 7 | 0.875 | 0.875 | 0.875 | 0.875 | 0.984375 | 0.984375 |
| 8 | 1 | 1 | 1 | 1 | 1 | 1 |
| 9 | 0.5625 | 0 | 0.5625 | 0.84375 | 0.984375 | 0.984375 |
| 10 | 0.625 | 0 | 0.625 | 0.9375 | 0.9375 | 0.9375 |
| 11 | 0.6875 | 0 | 0.6875 | 0.6875 | 0.859375 | 0.9453125 |
完整的表格可以作为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》存储库中，为可以放入一个《usize》中的位数。具有128位存储的《EnumVec》是目前最内存高效的选项，但在典型的64位机器上，大多数操作比其他实现慢2倍。8、16、32和64位版本具有相似的性能。
每个《EnumVecN》的“效率限制”，即它比《Vec》更好的最大项位数如下
| 存储大小 | 效率限制 |
|---|---|
| EnumVec8 | 4 |
| EnumVec16 | 4 |
| EnumVec32 | 11 |
| EnumVec64 | 22 |
| EnumVec128 | 42 |
定制
要更改默认存储，只需从内部模块导入《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 crate。
缺点
- 由于
EnumVec无法返回引用，因此没有索引语法。请使用get和set代替。 - 您不能使用slice方法，如split()、get(range)、reverse()、chunk和window迭代器、sort()、dedup()等。因为没有实现deref（与
&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，它们利用打包一次处理多个元素。一些其他基准测试似乎更快，因为重新分配：当达到1、2、4、8等元素时，Vec将重新分配，但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:
用于枚举变体的集合
该功能实现为一个包装在 bit-set 集合库之上，提供整数值的集合。我们使用了 enum_like 集合库中的 EnumLike 特性，该特性允许枚举变体与整数值之间的转换。
由于 EnumSet 是 BitSet 的包装，而 BitSet 是 BitVec 的包装，因此查看此集合库生成的汇编代码应该很有趣。
依赖项
~150KB