Thin `Vec` representation

[marcianx]

I was thinking about minimizing the size of enums containing Vecs, and it just occurred to me: what's the disadvantage of storing the size and capacity fields of the standard library's Vec in the heap-allocated part? Specifically, Vec could be defined as (ignoring NonNull for simplicity):

struct Vec<T> {
  ptr: *const (),
  PhantomData<T>,
}

with the ptr being allocated with

• an alignment of max(align_of<usize>(), align_of<T>()), and
• an initial padding that is max(2*size_of<usize>(), align_of<T>()) bytes to be used to store size and cap.

Then, Vec would be the same size as Box. This would reduce the struct size of Vec and String 3x and allow them to be passed as a single register.

The slight disadvantages that come to mind are:

• The pointer would always require an alignment of at least align_of<usize>().
• len() would require a branch:

  if self.is_empty() { // self.ptr == 0x1
      0
  } else {
      unsafe { ptr::read(self.ptr as *const usize) }
  }
  

Given that this is not how Vecs are typically implemented in system languages, is there some major disadvantage that alludes me?

[Hyeonu]

Cache miss and branching are the main targets of the performance micro-optimization. One thing to note is that with this approach every .len() may triggers cache miss.

[marcianx]

Thanks for the reply.

I can imagine that would only really be an issue when accessing length without intending to access the vec itself?
Still, if len is the major thing to optimize for, one could compromise by storing the size inline and the cap on the heap-allocated part, reducing Vec from 3 words to 2. Is there still a major disadvantage of this approach?

[cuviper]

There's a ThinVec like that in thincollections.

[mbrubeck]

https://crates.io/crates/smallbitvec Is a specialized container that also uses this layout. It's used in Firefox and Servo.

[kornel]

BTW, if you don't need the Vec to grow, then Box<[T]> is a bit thinner: only ptr + size.