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

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.

2 Likes

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)).

6 Likes

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

4 Likes

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.

4 Likes

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?

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.

2 Likes

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

Also from the documentation:

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

5 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.