2 个版本

0.1.9 2022年9月12日
0.1.8 2022年9月8日

190压缩

每月 29 次下载

MIT/Apache

38KB
556

Peapod

Peapod 是一个类似 Vec 的数据结构,用于以超级紧凑的方式存储枚举集合,就像豆荚里的豌豆一样 :) 它可以与实现了 Phenotype 特性的任何枚举一起使用,该特性捕捉每个变体的行为。

内容

  1. 使用方法
  2. 动机
  3. 技术
  4. Peapod 的工作原理
  5. 何时不使用 Peapod

使用方法

首先,将 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特征,它有两个非常重要的方法:cleavereknit

type Value;
fn cleave(self) -> (usize, Self::Value)
fn reknit(tag: usize, value: Self::Value) -> Self

类型Value是某种可以保存每个枚举变体所有数据的类型。它应该是一个联合。

cleave接受一个枚举的具体实例,并将其分割为标签(此标签是Phenotype内部的,与编译器无关)和Self::Valuereknit做相反的事情,接受一个标签和一个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许可证的定义,应按上述方式双许可,不附加任何额外的条款或条件。

依赖关系

~2.5MB
~59K SLoC