Why does llvm::SmallVector split its storage?

Question

The implementation of llvm::SmallVector<T,N> is split amongst many types:

• llvm::SmallVectorBase holds 3 void*s for begin, end, and capacity.
• llvm::SmallVectorTemplateCommon<T> holds the first element of the small storage, as an appropriately aligned and sized char array.
• llvm::SmallVector<T,N> holds the next N-1 elements of the small storage, as an array of appropriately aligned and sized chararrays.

Why is the storage split between the two class templates, as opposed to having the most derived class (SmallVector<T,N>) simply store all N elements and pass in pointers to this storage down to the base class? That is, where currently the default constructor does:

SmallVector() : SmallVectorImpl<T>(N) { }

A hypothetical different implementation could do:

SmallVector() : SmallVectorImpl<T>(&Storage, T * sizeof(N)) { }

and SmallVectorTemplateCommon would not have the FirstEl member. What is the advantage of the implementation as it stands?

Answer 1

Splitting the storage avoids storing the inline capacity (or an "is small" bit) in the "size-erased" type SmallVectorImpl.

SmallVectorImpl<T> can be used to reference any SmallVector<T, N> and supports all vector operations on it. When the the underlying storage grows the pointer cannot be passed to free if it's using the inline capacity. Comparing the current storage's address to the first element of the inline capacity is convenient and saves a bit of memory in SmallVector.