Regarding SmallVec implementation


#1

I’m finding SmallVecs ( https://crates.io/crates/smallvec ) useful in my code.

This stores nine u64 locally:

type SV = SmallVec<[u64; 9]>;

size_of::<SV>() is 104 bytes, coming from 8 * 4 + 8 * 9.

But can’t SmallVec be implemented like this (instead of [T; 9] there’s the Array that’s used by SmallVec)?

enum SmallVec2<T> {
    Inline { len: u32, array: [T; 9] },
    Heap { vec: Vec<T> }
}

fn main() {
    println!("{}", std::mem::size_of::<SmallVec2<u64>>());
}

That takes 4 + 4 + 9 * 8 = 8 + 72 = 80 bytes, saving 24 bytes.

For SmallVec2::Inline.len 32 bits suffice. The capacity of the inline arrays is always 9.

(There are ways to further improve the packing, but such optimizations come later, and are better implemented using the future untagged enum feature).


#2

Here’s an explanation of why SmallVec needs two drop flags. The drop flags and the enum tag all add up to quite a lot since they are enlarged to pack the layout correctly (field alignment).