Avoid std::vector::reserve

Overview

The reserve method of std::vector might seem like a no-brainer optimization. It is supposed to preallocate memory for the vector so that it doesn’t have to reallocate memory as new elements are added. This should make it faster, right? Well, not quite. In this post, I’ll explain why you should avoid using reserve in most cases. I’ll also discuss specific scenarios where reserve is commonly used and why it might not be a good idea.

I’ve included the benchmark code on Godbolt, so you can check it out yourself. Unfortunately, it fails to run there (likely due to memory usage), but you can copy the code and run it locally. Godbolt link.

1. Vector length is known at compile time

std::vector is a dynamic array, designed for cases where the array size is unknown at compile time. If the size is known at compile time, you should use std::array. Unlike std::vector, std::array stores its elements inline, avoiding allocations altogether.

struct ChairWithFourLegs {
    std::array<Leg, 4> legs;
};

2. Vector length is known at a runtime but not at the compile time

Often, the number of elements is known when the vector is created. A common pattern is to create an empty vector and immediately call reserve to preallocate memory. This requires adding elements using push_back or emplace_back. However, even though we know there’s sufficient memory, each addition will still perform the checks.

In such cases, a better approach is to create a vector with default-initialized elements and assign values using the subscript operator:

template <size_t Count>
void BM_CreateWithReserve(benchmark::State& state) {
  for (auto _ : state) {
    std::vector<int> a;
    a.reserve(Count);
    for (size_t i = 0; i < Count; ++i) {
      a.emplace_back(i);
    }
    benchmark::DoNotOptimize(a[20]);
  }
}

template <size_t Count>
void BM_CreateWithSize(benchmark::State& state) {
  for (auto _ : state) {
    std::vector<int> a(Count);
    for (size_t i = 0; i < Count; ++i) {
      a[i] = i;
    }
    benchmark::DoNotOptimize(a[20]);
  }
}

On my machine, reserve is 30–50% slower:

3. Adding elements to existing vector

Another common use case is adding multiple elements to an existing vector. For instance, when receiving data in batches on a server, you may want to append the data to a vector. The intuitive solution might be to reserve memory for the elements before appending them.

However, this is surprisingly slower than appending elements without reserving memory. By default, vectors allocate extra memory as elements are added, reducing the need for frequent reallocations. This gives vector operations an amortized complexity of O(1). When you call reserve, the complexity becomes O(n), even though it saves a small amount of memory.

template <size_t BatchSize>
void BM_Add1MBatchNoReserve(benchmark::State& state) {
  for (auto _ : state) {
    std::vector<int> a;
    for (size_t i = 0; i < 1'000'000; i += BatchSize) {
      for (size_t j = 0; j < BatchSize; ++j) {
        a.emplace_back(i + j);
      }
    }
    benchmark::DoNotOptimize(a[20]);
  }
}

template <size_t BatchSize>
void BM_Add1MBatchReserve(benchmark::State& state) {
  for (auto _ : state) {
    std::vector<int> a;
    for (size_t i = 0; i < 1'000'000; i += BatchSize) {
      a.reserve(i + BatchSize);
      for (size_t j = 0; j < BatchSize; ++j) {
        a.emplace_back(i + j);
      }
    }
    benchmark::DoNotOptimize(a[20]);
  }
}

The negative impact of reserve is especially noticeable with smaller batch sizes:

Conclusion

The simple advice: don’t use reserve. The nuanced advice: measure performance for your specific use case, then decide.