On QVarLengthArray and Uninitialized Storage in C++

10.01.2023 Giuseppe D'Angelo No comments

If you’re following our Youtube channel you might have heard me talking about QVarLengthArray.

If you’re not… you should follow us! But let me give you a quick recap.

QVarLengthArray is a Qt container that acts like a vector; its elements are stored contiguously in memory and it has a dynamic size. At any time we can add or remove elements from it.

Unlike std::vector or QVector, QVarLengthArray has a small buffer pre-allocated inside itself. The idea is pretty simple: if in the “common case” it only needs to store a relatively small number of elements, one can avoid paying for a heap allocation. (To say it in other terms: it’s a “vector with small object optimization”.)

This is realized by storing elements directly inside the QVarLengthArray‘s internal buffer, in case they fit.

If the QVarLengthArray grows too much and the number of elements exceeds the internal buffer’s size, then a heap allocation is used and QVarLengthArray becomes pretty much like an “ordinary” vector.

Of course, whether this “common case” is realistic depends on the particular context. In Qt this class is used when indeed there’s statistical/profiling data indicating that we could spare the heap allocation.

In code, QVarLengthArray‘s class layout looks something like this (note, this is hugely simplified):

template <typename T, qsizetype Prealloc = 256>
class QVarLengthArray
{
  // Points to either the internal storage (if capacity <= Prealloc),
  // or to a heap-allocated array otherwise. Since it points to the first
  // element, it's begin().
  T *ptr; 

  // Current size and capacity
  qsizetype size;
  qsizetype capacity;

  // The internal buffer
  alignas(T) std::byte internal_storage[Prealloc * sizeof(T)];
};

QVarLengthArray is supposed to be used a drop-in replacement for something like vector. Typically you’ll see it used inside a function as a temporary storage for some algorithm:

void doWork() {
  // number of elements is usually "small"
  QVector<Element> v;
    v.reserve(...);

  while (...) {
    // gather the elements to process
    v.push_back(element);
  }

  for (const Element &e : v) {
    // process them
    process(e);
  }

  // elements are contiguous
  some_c_api(v.data(), v.size()); 
}

Here we could very easily switch to QVarLengthArray:

void doWork() {
  // Estimate: max 16 elements "most of the time"
  QVarLengthArray<Element, 16> v;
  v.reserve(...);

  while (...) {
    // gather the elements to process
    v.push_back(element);
  }

  for (const Element &e : v) {
    // process them
    process(e);
  }

  // elements are contiguous
  some_c_api(v.data(), v.size()); 
}

The Tradeoff

What is happening here is that we are trading a certain heap allocation (with std::vector) for some extra stack usage (the QVarLengthArray object itself is big) and a heap allocation that happens only in the “unlikely” case where we have too many elements to fit in the internal buffer. The key is guessing the preallocated size correctly to make this trade-off worthwhile.

So that’s it? Just go and use QVarLengthArray?

Well, not so quick! There is one very important API difference between and vector classes. It’s so important that I’ll write in big:

QVarLengthArray<T>::resize(N) does not necessarily initialize its elements.

The Quest For Uninitialized Storage

What do I mean by that? Consider this simple example:

QVector<int> vec;
vec.resize(10);   // all zeros -- guaranteed

QVarLengthArray<int> qvla;
qvla.resize(10);  // indeterminate values!

When you use QVarLengthArray<T>::resize on a trivially constructible type T, or similarly when you use the corresponding resizing constructor (e.g. QVarLengthArray<int> tenInts(10);), the elements in the container are not value-initialized. Instead, they are left in an indeterminate state. Needless to say, attempting to read or manipulate an element of our container will likely trigger undefined behavior.

Bear in mind, this is by design, and documented, and auto-tested:

If the value type is a primitive type (e.g., char, int, float) or a pointer type (e.g., QWidget *), new elements are not initialized. For other types, the elements are initialized with a default-constructed value.

(The wording is a bit inaccurate, but the gist is there.)

The idea here is pretty simple: avoiding paying for the initialization of elements if the following code is going to overwrite them anyway. In other words, use QVarLengthArray as some sort of managed “uninitialized storage”.

This is a very sought-after feature from standard containers and allocation facilities: in a lot of “low level” code we need to allocate storage, and we want to manage it properly (in a container, using smart pointers, etc.). Yet, the same facilities also needlessly initialize the storage — which is a waste if we are going to overwrite the content:

auto readDataFromSocket() {
  std::vector<std::byte> buffer;
  buffer.resize(socket->availableBytes());    // resizes AND initializes
  socket->read(buffer.data(), buffer.size()); // overwrites the contents.
  return buffer;
}

Why did we bother with initializing the vector’s contents if we are going to overwrite them anyways? Can’t we do better?

Allocating Uninitialized Data in Modern C++

Luckily, C++20 and C++23 bring us a bunch of improvements in the area.

Smart Pointers

In C++20 we have make_unique_for_overwrite and make_shared_for_overwrite. They complement make_unique and make_shared by allowing “uninitialized” allocations. Suppose that you want to dynamically allocate 100k integers and not initialize them. You know the drill and you use make_unique:

std::unique_ptr<int[]> p1 = std::make_unique<int[]>(100'000);

This allocates, but also initializes the array. That’s a huge waste of time if the data is meant to be overwritten (from a file, database, socket, …).

The reason why the integers are initialized has to do with the specification of make_unique. In the case above, it is defined to do this:

// std::make_unique<int[]>(100'000) returns this:

return std::unique_ptr<int[]>(new int[100'000]())
                                           // ^^ look here

The inner parenthesis perform value-initialization. For integers, that means zero-initialization, i.e.: set them to 0.

But we don’t want zero initialization. How do we achieve that in C++? We use default initialization, which leaves the values in an indeterminate state. The integers in the array are initialized, in the sense that they exist as far as the abstract machine is concerned; but no initialization code is emitted for them, which is what we want here.

(That’s why I was using the word “initialized” between double quotes — to distinguish from the Language Lawyer notion of initialization.)

This means, however, that we cannot use make_unique because it will always value-initialize. We need to explicitly spell out the allocation, for instance like this:

std::unique_ptr<int[]> p2(new int[100'000]); // no ()

But ew, that’s a raw new in my code. Go away!

Thankfully, C++20 has packaged this feature for us. It’s called make_unique_for_overwrite:

// C++20: allocates 100k integers, but does not initialize them
std::unique_ptr<int[]> p3 = std::make_unique_for_overwrite<int[]>(100'000);

Strings

Similarly, C++23 allows us to resize a string without value-initializing its data. Quite some care went into the design to try to avoid accidentally creating strings with indeterminate values inside (since string is such a widely used vocabulary type).

In the final version, you’re supposed to pass a function that will initialize the new string data right away, effectively closing any “window of opportunity” for an uninitialized string to accidentally exist and maybe get passed around. Here it is, resize_and_overwrite:

// C++23
std::string s = ~~~;

auto oldSize = s.size();

s.resize_and_overwrite(100'000, [oldSize](char *buf, std::size_t count) {

  // For starters, s will *reserve* enough space, without initializing it.
  //
  // - buf points to the string's storage (i.e. s.data()) *after* the reserve;
  // - count is the 1st argument to resize_and_overwrite (100k), so
  //   we can re-use this function with different `count`s.


  // Populate the range [buf, buf+count]. We can mutate the entirety of
  // the string's buffer. But let's say we're just interested in populating
  // the new contents -- from position oldSize up to count.
  for (size_it i = oldSize; i < count; ++i)
    buf[i] = generateData(i);

  // Notes:
  // - If we're growing, the newly created storage is *uninitialized*.
  //   Don't read from it!
  //
  // - The old contents are still there, and we can access them freely.
  //   If needed, carry `oldSize` manually, to identify where to start 
  //   writing (and leave the old contents alone).
  //
  // - It is legal to write into buf[count],
  //   but it will be overwritten with \0 when we're done.
    
  // We don't need to populate the *entire* buffer -- we may stop short!
  // The returned value will be the new size of the string.

  return actual_new_size;
});

While tempting, note that you cannot leave uninitialized data in a string (by doing nothing in your function).

Honestly, I find this solution quite awkward. I understand what the goal is, but this approach feels not ergonomic at all, hard to compose, and so on.

In any case, we can spot a common theme here:

In all the adopted solutions, the overwrite wording makes it very clear that we are dealing with uninitialized data, which is supposed to be overwritten.

I’ll come back to this later.

std::vector

What about std::vector? Well, there has been a separate proposal to solve the problem there. But at the time of this writing, it has not made any progress. The proposal indeed notices that a lot of 3rd party implementations of vector-like containers offer such a facility.

In the meanwhile, users can use a custom allocator that has a no-op construct. You can find a suitable implementation here on StackOverflow, which is nicely linked from the cppreference page about std::vector::resize.

I am not a big fan of this sort of solution. Allocators are invasive; they change the type of your vector, effectively reducing its usefulness as an interface type or vocabulary type. In C++17, polymorphic allocators have been introduced to mitigate this issue — and guess what? The above solution doesn’t work with pmr::allocator, as construction isn’t delegated to a memory resource.

The proposal points out that a lot of 3rd party vector implementations do have a non-initializing resize (for instance: Boost.Vector); it would be great™ if we also had one in the Standard.

Qt

What about Qt containers? In Qt, we do not have a non-initializing resize for QString (or QByteArray), but we have non-initializing construction, by using a tag type:

QString s(100'000, Qt::Uninitialized);
QByteArray ba(100'000, Qt::Uninitialized);

Note: this particular constructor is still undocumented. It’s unknown if it will be published in this form; in Qt we don’t like tag types. We strongly prefer “named constructors”, that is, factory functions, because they’re easier to discover and way less error-prone.

And QVector? QVector is missing such functionality, just like std::vector. A patch for adding the same functionality was proposed but abandoned a long time ago.

Back to Square One

But anyway, wasn’t this supposed to be a blog post about QVarLengthArray?

Yes, and specifically to bash on the horrible decision of making it not initialize contents, when using a vocabulary (the “container vocabulary”) that is always meant to initialize contents.

Why do I call it horrible? Because it goes against any established practice of any other container class, carving yet another “special case to remember” in the already-super-complicated world of C++:

std::vector<int>     c1(size);  // initializes
std::deque<int>      c2(size);  // initializes
std::list<int>       c3(size);  // initializes
QVector<int>         c4(size);  // initializes
QVarLengthArray<int> c5(size);  // DOES NOT INITIALIZE
   
 
cont.resize(newSize);  // initializes the new elements... UNLESS IT'S A QVLA

This isn’t just an itch — it’s a very strong impedance mismatch.

Remember where we started: you had a QVector, maybe in a hot path, and realized that it only stores a few elements (most of the time). Can you spare some memory allocation?

The solution cannot be to “simply” replace it with QVarLengthArray. You also need to review the code and make sure that it’s not relying on initializing resize. A 1-liner fix becomes a code refactoring exercise.

Would you now be comfortable with doing that 1-liner change, if it happens to be in some convoluted algorithmic code that you know that works today? Not so sure anymore, right?

Not to mention, this makes QVarLengthArray bad to use in generic code. Many people complain about the poor usability of things like std::vector<bool>, (also) because they’re awkward to use in generic code:

template <typename Container, typename T>
void fill(Container &container, const T &amp;t)
{
  for (auto &e : container)
    e = t;
}

std::vector<int> v;
fill(v, 42);  // OK

std::vector<bool> v2;
fill(v2, true); // ERROR! Cannot create a (language) reference into a vector<bool>

Raise your hand if you like the usability of this.

Similarly, QVarLengthArray becomes dangerous to use if generic code makes assumptions regarding resizing a generic Container.

Suppose that you want to count the frequencies of elements in a given collection (e.g., counting frequencies of individual characters into a std::string); you could concoct this code:

template <typename <template ...> Storage, typename T> // let users choose the containers they want
auto countFrequencies(T &&collection)
{
  Storage<size_t> c(domain_size);  // for char, that's 256

  for (const auto &e : collection)
    c[e]++;

  return c;
}

… which does not work with QVarLengthArray’s uninitialized resize, because its sized constructor does not initialize. You need to remember to fill the contents. Ew!

I’ve also stressed how important it is that the Standard Library finds common wording for the uninitialized resizing. That wording is for making users aware of the danger of uninitialized data, which must be written into before use.

Clearly, QVarLengthArray predates any such wording, and we don’t have a crystal ball. But it would’ve been infinitely better for it to simply use any other name but resize() for the purpose! Let’s call it resizeUninitialized() and move on. No one would complain.

Unfortunately, now it is way too late to fix it, as it’s documented behavior. User code is relying on it. While making resize() always initialize would never change a correct program’s behavior, it would affect the performances of sensitive code. So, we cannot do that.

The Moral Lesson

Building a common vocabulary of common behaviors is essential for end-users to be able to use a language effectively. C++ is already riddled with traps at every corner. Hiding non-obvious behaviors in what’s otherwise a common vocabulary should be avoided at all costs.

On the other hand, adding “hidden” or non-standard features also means that users will start relying on them (this is Hyrum’s Law). So one will never be able to remove them again without breaking something.

My suggestion here is:

• always follow the pre-existing nomenclature and behaviors, to minimize surprises for end-users;
• if you can’t or don’t want to (for very good reasons, like the performance benefits of uninitialized resizes), then use a different vocabulary! This will make it very obvious that one is dealing with non-common behaviors.

Thank you for reading.