Use Bit-Vector for Initialized Flags

[ibraheemdev]

Right now each entry has an AtomicBool, which can waste a lot of memory depending on the alignment of T.

[clarfonthey]

I agree that would be nice, although it'd require using unstable APIs to make it efficient. You'd have to leverage the existing pointer to prefix the entry array with a bit-vector of sufficient length, and there's really no easy way to make this work on stable.

Additionally, I'm not sure how this would affect cache locality, since each entry's flag is no longer right next to it, and larger buckets could exceed the size to fit an entry's flag and its value in cache.

Also, if you're using this crate, you should know that it's not memory-efficient. You sacrifice memory efficiency and the ability to keep everything in one place with concurrency.

[ibraheemdev]

You'd have to leverage the existing pointer to prefix the entry array with a bit-vector of sufficient length, and there's really no easy way to make this work on stable.

You can do this using alloc directly with a custom layout.

Additionally, I'm not sure how this would affect cache locality, since each entry's flag is no longer right next to it, and larger buckets could exceed the size to fit an entry's flag and its value in cache.

It's true that the flag and value would no longer be in the same cache line. One thing we could do to improve this is to have a true marker length that's lazily updated based on updates to the bitvector, such that everything up to the marker length is initialized. This would reduce contention for readers.

Also, if you're using this crate, you should know that it's not memory-efficient. You sacrifice memory efficiency and the ability to keep everything in one place with concurrency.

Using a bitvec can cut the memory overhead almost in half in many cases, so I think it's worth doing.

[clarfonthey]

Oh huh, I guess I never realised that even though Allocator isn't stable, alloc is, so, never mind. You definitely could do this with a custom layout:

#[repr(C)]
struct Entry<T, const N: usize> {
    active: BitArr![for N, in AtomicU8],
    data: [T; N],
}

While you can't actually make an unsized version of this work properly, you could just make the pointer point to Entry<T, 1> and then cast appropriately.