What is the most memory-efficient array of nullable vectors when most of the second dimension will be empty?

Question

I have a large fixed-size array of variable-sized arrays of u32. Most of the second dimension arrays will be empty (i.e. the first array will be sparsely populated). I think Vec is the most suitable type for both dimensions (Vec<Vec<u32>>). Because my first array might be quite large, I want to find the most space-efficient way to represent this.

I see two options:

1. I could use a Vec<Option<Vec<u32>>>. I'm guessing that as Option is a tagged union, this would result each cell being sizeof(Vec<u32>) rounded up to the next word boundary for the tag.

2. I could directly use Vec::with_capacity(0) for all cells. Does an empty Vec allocate zero heap until it's used?

Which is the most space-efficient method?

Answer 1

Actually, both Vec<Vec<T>> and Vec<Option<Vec<T>>> have the same space efficiency.

A Vec contains a pointer that will never be null, so the compiler is smart enough to recognize that in the case of Option<Vec<T>>, it can represent None by putting 0 in the pointer field. What is the overhead of Rust's Option type? contains more information.

What about the backing storage the pointer points to? A Vec doesn't allocate (same link as the first) when you create it with Vec::new or Vec::with_capacity(0); in that case, it uses a special, non-null "empty pointer". Vec only allocates space on the heap when you push something or otherwise force it to allocate. Therefore, the space used both for the Vec itself and for its backing storage are the same.

Answer 2

Vec<Vec<T>> is a decent starting point. Each entry costs 3 pointers, even if it is empty, and for filled entries there can be additional per-allocation overhead. But depending on which trade-offs you're willing to make, there might be a better solution.

• Vec<Box<[T]>> This reduces the size of an entry from 3 pointers to 2 pointers. The downside is that changing the number of elements in a box is both inconvenient (convert to and from Vec<T>) and more expensive (reallocation).
• HashMap<usize, Vec<T>> This saves a lot of memory if the outer collection is sufficiently sparse. The downsides are higher access cost (hashing, scanning) and a higher per element memory overhead.

• If the collection is only filled once and you never resize the inner collections you could use a split data structure:

  This not only reduces the per-entry size to 1 pointer, it also eliminates the per-allocation overhead.

  struct Nested<T> {
     data: Vec<T>,
     indices: Vec<usize>,// points after the last element of the i-th slice
  }
  
  impl<T> Nested<T> {
      fn get_range(&self, i: usize) -> std::ops::Range<usize> {
         assert!(i < self.indices.len());
         if i > 0 {
             self.indices[i-1]..self.indices[i]
          } else {
             0..self.indices[i]
          }
      }
  
      pub fn get(&self, i:usize) -> &[T] {
          let range = self.get_range(i);
          &self.data[range]
      }
  
      pub fn get_mut(&mut self, i:usize) -> &mut [T] {
          let range = self.get_range(i);
          &mut self.data[range]
      }
  }
  

  For additional memory savings you can reduce the indices to u32 limiting you to 4 billion elements per collection.