The Little Things: The Missing Performance in std::vector

std::vector is often said to be the default container. This is because it provides a simple abstraction over a growable contiguous chunk of memory, thus providing good baseline performance for common operations, such as adding more elements or iterating over them.

However, many non-standard reimplementations of std::vector have emerged over time. These are usually driven by performance consideration, e.g. avoiding allocations for small vectors^[1], having static capacity^[2], tightly integrating with the OS for faster reallocations^[3], or optimizing moving elements with bitwise copying^[4].

Most of these cannot be merged into std::vector without changing it significantly, e.g. small vector optimization completely changes the expected complexity of moving the vector^[5]. Other can require other library and language changes, such as support for bitwise moves. But recently, I ran into a simple API change that can improve the performance of a common usage pattern by 10+ %.

Let's consider a simple function that takes one vector and returns a transformation of the input.

std::vector<size_t> convert_to_indices(std::vector<Key> const& keys) {
    std::vector<size_t> indices;
    for (Key k : keys) {
        indices.push_back(to_index(k));
    }
    return indices;
}

As I mentioned in a previous article, this implementation leaves a bunch of performance on the table. We can easily make it faster by reserving enough memory for indices ahead of time, like so

std::vector<size_t> convert_to_indices(std::vector<Key> const& keys) {
    std::vector<size_t> indices;
    indices.reserve(keys.size());
    for (Key k : keys) {
        indices.push_back(to_index(k));
    }
    return indices;
}

But this code still leaves some performance on the table, depending on the compiler^[6] and stdlib implementation. So, how can we fix this?

We cannot, not without changing std::vector. The lost performance comes from the fact that vector::push_back has to check whether it needs to grow the vector, even though it will never happen in the convert_to_indices function. A sufficiently smart compiler could optimize this out, but neither GCC nor Clang do (and MSVC makes a complete hash of things).

What we need is a function that inserts a new element into the vector, but does not check for capacity^[7]. I like the name push_back_unchecked for this functionality, so I will use it in the rest of this post.

Benchmarks

How much of a difference does using push_back_unchecked make? To figure this out, we would need a reimplementation of std::vector, which also includes push_back_unchecked. So I made a very simple one. It only supports push_back and push_back_unchecked and a few miscellaneous functions like size, or reserve.

Let's run 3 different benchmarks, all following the basic structure from the snippet earlier, that is, create an output vector, reserve enough space for all elements, and then add the elements to the output vector.

The transformation operation is going to be

1. The Key -> index conversion snippet from earlier
2. Multiplying every element by 2

For each of these, we will compare the performance of std::vector::push_back, nonstd::vector::push_back, and nonstd::vector::push_back_unchecked^[8].

You can check the benchmark implementation in the GitHub repository.

I ended up collecting results for the three main compilers, specifically MSVC 19.29.30151^[9], GCC 10.5, and Clang 15.0.7 (using libc++-15)^[10]. GCC and Clang were run under WSL2 and MSVC on Windows 10 directly.

Results

I collated the results for all benchmarks into one table per compiler.

• std column is the result of using std::vector::push_back
• nonstd is the result of using nonstd::vector::push_back
• unchecked is the result of using nonstd::vector::push_back_unchecked
• \(\frac{\textbf{std}}{\textbf{nonstd}}\) is the speedup from using nonstd::vector::push_back instead of std::vector::push_back
• \(\frac{\textbf{nonstd}}{\textbf{unchecked}}\) is the speedup from using nonstd::vector::push_back_unchecked instead of nonstd::vector::push_back

Generally we want to see that the \(\frac{\textbf{std}}{\textbf{nonstd}}\) is around 1, and \(\frac{\textbf{nonstd}}{\textbf{unchecked}}\) is more than 1.

Clang

The results from Clang+libc++ are about what we want to see. The performance of using plain push_back is roughly the same between nonstd::vector and libc++'s std::vector, and push_back_unchecked provides improvements ranging from significant for N == 10'000'000 to massive for smaller inputs.

GCC

The results from GCC+libstdc++ are very similar to those from Clang+libc++. Compared to Clang's results, there is a slightly greater difference between using std::vector and nonstd::vector, but the differences are still minor. GCC does seem to be worse at taking advantage of push_back_unchecked, in the copy + mult benchmark, providing significantly worse performance for small input sizes.

MSVC

The results for MSVC are, in a way, the most interesting ones. This is because nonstd::vector already significantly outperforms MS' std::vector. MSVC also does not take advantage of push_back_unchecked to generate massively faster code for small inputs the way GCC and Clang do.

Conclusion

From the benchmarks, push_back_unchecked provides a nice (10+%) improvement for a common usage pattern. The improvement could even be called "massive" for specific compiler and input size combinations. Obviously, it is not a panacea; the improvement comes from simplifying the code the compiler has to reason about when adding a new element to the vector. As adding the new element (or computing the new element) becomes more expensive, the total improvement trends to zero.

The trade-off for the increased performance is a whole new way to trigger UB when using a vector. Is this trade-off worth it? I think it certainly is, and we should add something like this to the actual std::vector. There is even a precedent for this in the standard library, std::basic_string::resize_and_overwrite^[11], which also allows the user to bypass the capacity checks when operating on a basic_string instance.

And finally, push_back is not the only member function on std::vector we could apply this treatment to. emplace_back is an obvious candidate here, as it also operates on individual elements and is often used in cases where we know the required capacity ahead of time. To me, the question mark is over things like assign and other range-based functions. On the one hand, doing one capacity check per the whole range should be cheap enough not to matter. On the other, if we add push_back_unchecked, adding, e.g. assign_unchecked would be symmetrical, and there is no doubt that it would help someone out.

Other lessons learned

Having learned my lesson from trying to improve the performance of Catch2, I always benchmarked my own vector implementation against std's. These baseline benchmarks have paid off almost immediately because in the first implementation, my vector's push_back was almost twice as slow as libstdc++'s std::vector's.

The code below is the first implementation of push_back I had, see if you can spot the issue:

    void push_back(T&& elem) {
        if (m_next != m_end) {
            Detail::construct_at(m_next, std::move(elem));
            ++m_next;
            return;
        }
        const auto current_size = size();
        const auto new_cap = calculate_new_cap(current_size + 1);
        auto* new_memory = Detail::allocate_uninit<T>(new_cap);
        // Constructing new element has to happen before we move
        // old elements, in case someone is doing `v.push_back(v[0])`
        try {
            Detail::construct_at(new_memory + current_size, std::move(elem));
        }
        catch (...) {
            Detail::deallocate_no_destroy(new_memory, new_cap);
            throw;
        }
        m_next = std::uninitialized_move(m_first, m_next, new_memory);
        // Account for the inserted element
        ++m_next;
        Detail::deallocate_no_destroy(m_first, current_size);
        m_first = new_memory;
        m_end = m_first + new_cap;
    }

There is no real issue if you define real issue as code that is inefficient on its own. However, when I benchmarked this implementation against libstdc++'s std::vector, I found that its performance was up to 4x worse than the actual std::vector.

Why? Because inlining is the most important optimization in the world of modern C++, the GCC's inliner did not like how big the function is. When I instead outlined the last few lines into its own helper function, adopt_new_memory, I got performance on par with std::vector.

This is the "fixed" version:

    void push_back(T&& elem) {
        if (m_next != m_end) {
            Detail::construct_at(m_next, std::move(elem));
            ++m_next;
            return;
        }
        const auto current_size = size();
        const auto new_cap = calculate_new_cap(current_size + 1);
        auto* new_memory = Detail::allocate_uninit<T>(new_cap);
        // Constructing new element has to happen before we move
        // old elements, in case someone is doing `v.push_back(v[0])`
        try {
            Detail::construct_at(new_memory + current_size, std::move(elem));
        }
        catch (...) {
            Detail::deallocate_no_destroy(new_memory, new_cap);
            throw;
        }
        adopt_new_memory(new_memory, new_cap);
        // Account for the element inserted ahead of time
        ++m_next;
    }

Next up was benchmarking against MSVC's stdlib. Compared to MSVC's std::vector, the implementation above was significantly slower, up to 3x. Because both std::vector and nonstd::vector were significantly slower when compiled with MSVC than when compiled with GCC, I had to look for some pattern that broke MSVC's optimizer badly.

After some thinking, I noticed that I could completely remove the try-catch block because in nonstd::vector, I static_assert that the elements in it are no-throw move-constructible.

This meant that the implementation of push_back(T&&)^[12] could be simplified down to just

    void push_back(T&& elem) {
        if (m_next != m_end) {
            Detail::construct_at(m_next, std::move(elem));
            ++m_next;
            return;
        }
        const auto current_size = size();
        const auto new_cap = calculate_new_cap(current_size + 1);
        auto* new_memory = Detail::allocate_uninit<T>(new_cap);
        // Constructing new element has to happen before we move
        // old elements, in case someone is doing `v.push_back(v[0])`
        Detail::construct_at(new_memory + current_size, std::move(elem));
        adopt_new_memory(new_memory, new_cap);
        // Account for the element inserted ahead of time
        ++m_next;
    }

This change made no difference in the performance with GCC (or, as I later checked, Clang), but this version of push_back(T&&) now beats MS's std::vector easily. Why? Because the MSVC version I have is bad at handling try-catch blocks where no exceptions can be thrown.

Let's take a look at an example where two functions should compile into the same ASM if the compiler properly optimizes try-catch blocks:

#include <cstdio>

void f1(int* ptr, int i) {
    *ptr = i;
}

void f2(int* ptr, int i) {
    try {
        *ptr = i;
    } catch (...) {
        puts("RIP\n");
        throw;
    }
}

godbolt

Notice that GCC is smart enough to compile both f1 and f2 into the same ASM. MSVC 19.29 instead makes a hash of f2, compiling in the whole exception handler. MSVC 19.37 performs a lot better; the two functions still aren't identical, but now the difference is only that f2 allocates 40 bytes of stack space for no reason.

And that's all for this article. Reimplementing a tiny subset of std::vector in a way to keep the comparison fair was an interesting exercise, and figuring out why it optimizes differently was quite fun.

Standardizing std::vector::push_back_unchecked would be nice, but I am not touching wg21 unless I am well-compensated for doing so.