TinyVec 如何与 Vec 大小相同？

Question

TinyVec定义为：

pub enum TinyVec<A: Array> {
  #[allow(missing_docs)]
  Inline(ArrayVec<A>),
  #[allow(missing_docs)]
  Heap(Vec<A::Item>),
}

然而，如果你运行这段代码，你会得到有趣的结果（playground）：

use tinyvec::*;

fn main() {
    dbg!(std::mem::size_of::<Vec<u8>>());
    
    dbg!(std::mem::size_of::<TinyVec<[u8; 13]>>());
    dbg!(std::mem::size_of::<TinyVec<[u8; 14]>>());
    dbg!(std::mem::size_of::<TinyVec<[u8; 15]>>());
    dbg!(std::mem::size_of::<TinyVec<[u8; 16]>>());
}

输出：

[src/main.rs:4] std::mem::size_of::<Vec<u8>>() = 24
[src/main.rs:6] std::mem::size_of::<TinyVec<[u8; 13]>>() = 24
[src/main.rs:7] std::mem::size_of::<TinyVec<[u8; 14]>>() = 24
[src/main.rs:8] std::mem::size_of::<TinyVec<[u8; 15]>>() = 32
[src/main.rs:9] std::mem::size_of::<TinyVec<[u8; 16]>>() = 32

我知道 Rust 可以使用“利基”来优化枚举大小 - 基本上它将判别式放在一些未使用的空间中，甚至是变体的未使用的值中。但我真的不明白它是如何做到这一点的Vec<>。

肯定有一些配置Vec<>是无效的，因此可以用于判别式，例如大小 > 容量、空数据指针 && 大小 > 0 等。但是 Rust 是否真的足够聪明来解决这个问题，或者它是手工编码的利基？

Answer 1

秘密在于它ArrayVec<[u8; 14]>小于Vec<u8>并占用 16 个字节：

pub struct ArrayVec<A> {
  len: u16,
  pub(crate) data: A, // A = [u8; 14]
}

与Vec24 个字节相比，还剩下 8 个字节TinyVec<[u8; 14]>未使用。这些字节为零可以代表Inline变体，它们非零可以代表Heap变体。换句话说，编译器足够聪明，可以使用 的数据指针部分Vec，即NonNull<T>, 作为利基。

因此TinyVec是：

struct TinyVec<A> {
    // ArrayVec (first 8 bytes are zero):
    this_is_null: *mut [u8; 14],
    len: u16,
    data: [u8; 14],
}

或者：

struct TinyVec<A> {
    // Vec (first 8 bytes are non-zero and point to data):
    data: *mut [u8; 14],
    len: usize,
    capacity: usize,
}

第一个字段的值充当两种可能性之间的鉴别器。

可以通过以下不安全代码观察到这一点：

type TinyVec = tinyvec::TinyVec<[u8; 14]>;

fn main() {
    assert_eq!(std::mem::size_of::<TinyVec>(), 24);
    let a: TinyVec = (0..10).collect();
    let b: TinyVec = (0..20).collect();
    unsafe {
        // XXX this makes assumptions about the layout of TinyVec and Vec
        // not guaranteed by rustc
        println!("{:?}", std::mem::transmute::<_, &(usize, u16, [u8; 14])>(&a));
        println!("{:?}", std::mem::transmute::<_, &(usize, usize, usize)>(&b));
    }
}

操场

它打印如下内容：

(0, 10, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0])
(94630321433040, 20, 20)

第一行显示内联表示：空利基、长度 10 和值数组。第二行显示堆表示：非空利基（指向堆的数据指针），后跟长度和容量。