slab icon indicating copy to clipboard operation
slab copied to clipboard

Optimize the layout of Entry for ZSTs

Open udoprog opened this issue 5 years ago • 1 comments

This PR optimizes the layout of Entry to allow the discriminator to be embedded in the Vacant field. This makes Slab better to use for ZSTs.

ZSTs permits using Slab as a recyclable ID allocator without wasting the extra space for the discriminator:

let mut slab = Slab::<()>::new();

let id1 = slab.insert(());
let id2 = slab.insert(());
slab.remove(id1);
let id3 = slab.insert(()); // re-use of `id1`

This also means that the size of Entry<T> should always be optimizable mem::size_of::<T>() + mem::size_of::<usize>() with alignment.

Note that this does strictly speaking break public API, since it only allows for inserting std::usize::MAX - 1 entries instead of std::usize::MAX.

udoprog avatar Feb 18 '20 12:02 udoprog

Note that this does strictly speaking break public API, since it only allows for inserting std::usize::MAX - 1 entries instead of std::usize::MAX.

I think this is fine, because the length of Vec will not be larger than isize::MAX / size_of::<T>. (size_of::<T> will never zero in our case.)

https://doc.rust-lang.org/nightly/alloc/vec/index.html

Vectors ensure they never allocate more than isize::MAX bytes.

taiki-e avatar Mar 23 '22 10:03 taiki-e