Search code examples
rustmemory-managementcontainers

A Vec-like containers of different types that can share the same block of memory on the heap

I'm trying to write a SparseSet implementation that in my case consists of 3 Vecs:

pub struct SparseSet<T> {
    dense_values: Vec<T>,
    dense_keys: Vec<Key>,
    sparse: Vec<SparseEntry>,
    next_free_sparse_entry: usize,
}

I noticed that when the amount of the elements needs to increase, all 3 Vecs have the same size, which means that when they need to increase the memory they allocated, they would likely do that at the same time.

I assume the best-case scenario to reduce allocations would be for them to share the same heap memory block. Then, when they need to grow, allocate a new block of x2 size and let them move their elements to the appropriate parts of this new block, then deallocate the previous block.

enter image description here

However, I'm not sure how I can achieve this in Rust.

Can I do it without using "unsafe"? Are there solutions for this in the standard library?

And if not, what features of unsafe Rust should I look into?

Solution

  • This seems like a bad idea, but fun to build. The mismatch in size between the 3 structs will probably cause alignment issues that will wipe out any performance gains. Please don't do this in production, especially not without benchmarking.

    If you want to continue down this path, you will have to use unsafe. Here's a relevant quote from the Nomicon:

    You wanted advanced. We're gonna go advanced.

    You can create a wrapper around a Vec<MaybeUninit<uXXX>> (where uXXX is an unsigned integer of the right alignment) that checks and unsafely transmutes an array/slice of [uXXX] into your desired T on access. Check out the source code of array_assume_init() and the Nomicon's Implementing Vec for inspiration.