2 个版本
0.1.9 | 2022年9月12日 |
---|---|
0.1.8 | 2022年9月8日 |
190 在 压缩
每月 29 次下载
38KB
556 行
Peapod
Peapod
是一个类似 Vec
的数据结构,用于以超级紧凑的方式存储枚举集合,就像豆荚里的豌豆一样 :) 它可以与实现了
Phenotype
特性的任何枚举一起使用,该特性捕捉每个变体的行为。
内容
使用方法
首先,将 peapod == 0.1.6
添加到您的 Cargo.toml
中。
您几乎可以使用 Peapod
像一个普通的 Vec
。并非所有功能都是可能的,特别是将 Peapod
作为切片处理。这是由于内部数据表示的原因。
为了使枚举适合 Peapod 存储,请在该枚举上添加 #[derive(Phenotype)]
。
use peapod::{Phenotype, Peapod};
fn main() {
// The Peapod representation is a lot smaller!
// These numbers are in bytes
assert_eq!(ILovePeas::PEAPOD_SIZE.unwrap(), 9);
assert_eq!(std::mem::size_of::<ILovePeas>(), 16);
let mut pp = Peapod::new();
pp.push(ILovePeas::SnowPea);
pp.push(ILovePeas::Edamame(0x9EA90D));
pp.push(ILovePeas::GeneticPea {
wrinkled: true,
yellow: true,
});
for pea in pp {
// do something with pea!
}
}
#[derive(Phenotype)] // <- this is where the magic happens
enum ILovePeas {
Edamame(usize),
SnowPea,
GeneticPea { wrinkled: bool, yellow: bool },
}
动机
我们只有这么多内存可以工作。特别是在空间受限的系统中,我们希望特别高效。Peapod 提供了一种存储枚举的方法,可以显着减少空间使用。您可以在技术部分深入了解动机。
简单来说:Peapod 为枚举提供超紧凑的存储!
技术
枚举(也称为标签联合)在内存中通过标签(整数)和联合来表示。标签指定如何解释联合的位。例如,标签0可能表示“将联合读作Result::Ok(_)
”,而标签1可能表示“将联合读作Result::Err(_)
”。
由于对齐原因,编译器必须将枚举布局得使标签占据比所需更多的空间。如果只有两种变体,我们只需要一个位来跟踪某个变体。看这个相当极端的例子
enum Two {
First(usize),
Second(usize)
}
// mem::size_of::<Two> == 16
由于每个变体的尺寸是8字节,枚举的大小是16字节,所以使用了8字节来存储标签!浪费了63位!我们可以做得更好。
Peapod
通过“分割”枚举为标签和联合来工作。标签存储在bitvec
类型中,以避免由于对齐而浪费空间。所有枚举数据(以联合形式)也一起存储。
这张图说明了前面的例子
Scale: 1 - == 1 byte
Standard:
+--------+--------+
| tag | data |
+--------+--------+
^ Only this byte is actually needed to store the tag
Standard array:
+--------+--------+--------+--------+--------+--------+
| tag | data | tag | data | tag | data | . . .
+--------+--------+--------+--------+--------+--------+
Peapod:
+-+--------+
| | data |
+-+--------+
^ tag
Peapod array:
+-+ +--------+--------+--------+
| | + | data | data | data | . . .
+-+ +--------+--------+--------+
^ many tags can be packed into one byte, we could hold 5 more tags in this byte
它是如何做到的?
前言:编译器人士,请原谅我。
魔法在于Phenotype
特征,它有两个非常重要的方法:cleave
和reknit
。
type Value;
fn cleave(self) -> (usize, Self::Value)
fn reknit(tag: usize, value: Self::Value) -> Self
类型Value
是某种可以保存每个枚举变体所有数据的类型。它应该是一个联合。
cleave
接受一个枚举的具体实例,并将其分割为标签(此标签是Phenotype
内部的,与编译器无关)和Self::Value
。 reknit
做相反的事情,接受一个标签和一个Self::Value
,并将其重新组合成枚举变体。
所有实现都通过proc-macros的魔法来完成。#[derive(Phenotype)]
是这个项目的核心。
#[derive(Phenotype)]
首先查看您的枚举,然后生成一些“辅助”类型,如下所示
enum ThreeTypes<T> {
NamedFields {
one: T,
two: usize
},
Tuple(usize, usize),
Empty
}
// Represents the `NamedFields` variant
#[repr(packed)]
struct __PhenotypeInternalThreeTypesNamedFieldsData<T> {
one: T,
two: usize,
}
// Represents the `Tuple` variant
#[repr(packed)]
struct __PhenotypeInternalThreeTypesTupleData(usize, usize);
#[allow(non_snake_case)]
union __PhenotypeInternalThreeTypesData<T> {
NamedFields: ManuallyDrop<__PhenotypeInternalThreeTypesNamedFieldsData<T>>,
Tuple: ManuallyDrop<__PhenotypeInternalThreeTypesTupleData>,
Empty: (),
}
然后,它生成cleave
方法。此示例的生成代码如下所示
fn cleave(self) -> (usize, Self::Value) {
match &*ManuallyDrop::new(self) {
ThreeTypes::Empty => (2usize, __PhenotypeInternalThreeTypesData { Empty: () }),
ThreeTypes::Tuple(_0, _1) => (
1usize,
__PhenotypeInternalThreeTypesData {
Tuple: ManuallyDrop::new(__PhenotypeInternalThreeTypesTupleData(
unsafe { ::core::ptr::read(_0) },
unsafe { ::core::ptr::read(_1) },
)),
},
),
ThreeTypes::NamedFields { one, two } => (
0usize,
__PhenotypeInternalThreeTypesData {
NamedFields: ManuallyDrop::new(__PhenotypeInternalThreeTypesNamedFieldsData::<
T,
> {
one: unsafe { ::core::ptr::read(one) },
two: unsafe { ::core::ptr::read(two) },
}),
},
),
}
}
我们只是在match
枚举变体并将每个字段读取到正确的辅助结构体中。
cleave
做相反的事情。根据标签,它读取联合并根据辅助struct
中的数据生成枚举变体。
fn reknit(tag: usize, value: Self::Value) -> ThreeTypes<T> {
match tag {
2usize => ThreeTypes::Empty,
1usize => {
let data =
ManuallyDrop::<__PhenotypeInternalThreeTypesTupleData>::into_inner(unsafe {
value.Tuple
});
ThreeTypes::Tuple(data.0, data.1)
}
0usize => {
let data =
ManuallyDrop::<__PhenotypeInternalThreeTypesNamedFieldsData<T>>::into_inner(
unsafe { value.NamedFields },
);
ThreeTypes::NamedFields {
one: data.one,
two: data.two,
}
}
_ => unreachable!(),
}
}
何时不使用 Peapod
- 有时,
枚举
会进行特殊优化,这意味着编译器找到了一种巧妙的方法来省略标签。一个典型的例子是Option<NonNull<T>>
:由于NonNull<T>
不能为空,编译器可以使用空指针来表示None
变体。这是可以接受的,因为None
变体实际上不包含NonNull<T>
。总的来说,有效的指针位模式表示Some
变体,而空指针表示None
变体,因此不需要存储标签。 - 有时
Peapod
不会生成更小的表示。您可以使用提供的IS_MORE_COMPACT
常量进行检查。 - 您没有分配器。我正在开发一个固定大小的
Peapod
,但它似乎在const
泛型不完整的情况下会很难。
许可证
在以下任一许可证下获得许可:
- Apache许可证,版本2.0 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
- MIT许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)
任您选择。
贡献
除非您明确声明,否则任何有意提交并由您包含在作品中的贡献,根据Apache-2.0许可证的定义,应按上述方式双许可,不附加任何额外的条款或条件。
依赖关系
~2.5MB
~59K SLoC