Space/time usage to construct Vec<T> vs Option<Vec<T>>

#1

I have a struct representing the inner node of a tree (and will be constructed millions of times).

This struct has a field storing Vec<T>. 99% of the time this field will be empty.

I am trying to understand the cost of:

pub struct A {
  pub data: Vec<T>,
}

pub fn new() A {
  A { data: vec![]; }
}

vs

pub struct B {
  pub data: Option<Vec<T>>
}
pub fn new() B {
  B { data: None; }
}

Can someone explain the space usage of A vs B as well as the time cost of A::new() vs B::new().

Thanks!

EDIT: In particular, the key point is that 99% of the time, the Vec will be empty.

1 Like
#2

Vec<T> and Option<Vec<T>> have the same size (3 words, you can easily check that using size_of). That's because Vec has a non-null field internally that allows Option to use the null value as None.

Runtime-wise both should be similar too, both None and Vec::new() are constants.

If you really want to save memory in the empty case, you can use eg. Option<Box<Vec<T>> (1 word, but additional indirection) or Option<Box<[T]>> (2 words, with no additional indirection (Box<[T]> is like Vec, but not growable)).

5 Likes
#3

It is important to keep in mind that an empty Vec does not allocate heap memory. Thus, Vec::new() is always a cheap operation.

2 Likes
#4

Does the semantics of what you are trying to do differentiate between "empty vector" and "nonexistent vector"? If so, go for Option. If not, go for the plain Vec. There is no point in wrapping a collection into an Option just for the sake of it. It only makes code more complex, and introduces additional conditional jumps when you need to access the contents.

3 Likes
#5

The core of the problem is that I incorrectly assumed that Vec::new() does heap allocation for elements. Clearly I am wrong. Is there a easy way to verify this from source?

#6

Sure, e.g. you can see that Vec::new() is const. Furthermore, if you go to its source, you can see that the underlying RawVec buffer is initialized using a constant, RawVec::NEW. Transitively, its construction only calls Unique::empty(), which only returns a dangling non-null pointer made up out of thin air.

1 Like
#7

Thanks. For anyone else that's never seen a const fn -- What is `const fn`?

#8

Also from the documentation:

The vector will not allocate until elements are pushed onto it.

3 Likes