What Is Better: Reserve Vector Capacity, Preallocate to Size or Push Back in Loop

What is better: reserve vector capacity, preallocate to size or push back in loop?

Better performance will be reached when avoiding dynamic reallocation, so try to have the vector memory be big enough to receive all elements.

Your first solution will be more efficient because if nSize is bigger than default vector capacity, the second one will need a reallocation to be able to store all elements.

As commented by Melkon, reserve is even better:

void myfnc_1(void *a_src, uint32_t a_segment) {
    size_t nSize = GetSize();
    std::vector<std::string> values;
    values.reserve( nSize );
    char* v = a_src;

    for (size_t i = 0; i < nSize; ++i) {
        values.push_back( std::string( v, a_segment ) );
        v += a_segment;
    }
}

Does declaring a vector with size offer any improvements over using push_back in C++

With

vector<int> Array(n);

you create a vector that contains n elements, all memory needed for those elements is allocated immediately.

When you use e.g.

Array.push_back(value);

then the vector needs to be resized, which could mean the memory have to be reallocated and all the contents have to be copied to the new memory.

---

Instead of creating an array with a set size, you could instead preallocate (or reserve) memory:

vector<int> Array;  // An empty vector
Array.reserve(n);   // Reserve memory, but keep the size as zero (it's still empty)
Array.push_back(value);  // No reallocation needed, size is now one

This is useful when you have a vector of objects that can't be default-constructed.

Important concepts to learn: The vector size and its capacity and what the difference between them is.

The capacity is the number of elements the vector have allocated memory for.

The size is the current number of elements in the vector.

It's quite common for the capacity to be different from the size. And it must always be true that capacity >= size.

Is there a downside to a significant overestimation in a reserve()?

Summary

There is likely to be some downside to using a too-large reserve, but how much is depends both on the size and context of your reserve() as well as your specific allocator, operating system and their configuration.

As you are probably aware, on platforms like Windows and Linux, large allocations are generally not allocating any physical memory or page table entries until it is first accessed, so you might imagine large, unused allocations to be "free". Sometimes this is called "reserving" memory without "committing" it, and I'll use those terms here.

Here are some reasons this might not be as free as you'd imagine:

Page Granularity

The lazy commit described above only happens at a page granularity. If you are using (typical) 4096 byte pages, it means that if you usually reserve 4,000 bytes for a vector that will usually contains elements taking up 100 bytes, the lazy commit buys you nothing! At least the whole page of 4096 bytes has to be committed and you don't save physical memory. So it isn't just the ratio between the expected and reserved size that matters, but the absolute size of the reserved size that determines how much waste you'll see.

Keep in mind that many systems are now using "huge pages" transparently, so in some cases the granularity will be on the order of 2 MB or more. In that case you need allocations on the order of 10s or 100s of MB to really take advantage of the lazy allocation strategy.

Worse Allocation Performance

Memory allocators for C++ generally try to allocate large chunks of memory (e.g., via sbrk or mmap on Unix-like platforms) and then efficiently carve that up into the small chunks the application is requesting. Getting these large chunks of memory via say a system call like mmap may be several orders of magnitude slower than the fast path allocation within the allocator which is often only a dozen instructions or so. When you ask for large chunks that you mostly won't use, you defeat that optimization and you'll often be going down the slow path.

As a concrete example, let's say your allocator asks mmap for chunks of 128 KB which it carves up to satisfy allocations. You are allocating about 2K of stuff in a typical vector, but reserve 64K. You'll now pay a mmap call for every other reserve call, but if you just asked for the 2K you ultimately needed, you'd have about 32 times fewer mmap calls.

Dependence on Overcommit Handling

When you ask for a lot of memory and don't use it, you can get into the situation where you've asked for more memory than your system supports (e.g., more than your RAM + swap). Whether this is even allowed depends on your OS and how it is configured, and no matter what you are up for some interesting behavior if you subsequently commit more memory simply by writing it. I means that arbitrary processes may be killed, or you might get unexpected errors on any memory write. What works on one system may fail on another due to different overcommit tunables.

Finally, it makes managing your process a bit harder since the "VM size" metric as reported by monitoring tools won't have much relationship to what your process may ultimately commit.

Worse Locality

Allocating more memory than you need makes it likely that your working set will be more sparsely spread out in the virtual address space. The overall effect is a reduction in locality of reference. For very small allocations (e.g., a few dozen bytes) this may reduce the within-same-cache-line locality, but for larger sizes the main effect is likely to be to spread your data onto more physical pages, increasing TLB pressure. The exact thresholds will depend a lot on details like whether hugepages are enabled.

clang tidy complains about push_back into vector in a loop

"pre-allocate" here does not mean to resize the vector to the final size, which is what vector<string> result(tmp.size()); does, but to reserve memory for the final size:

vector<string> result;
result.reserve(tmp.size());

As mentioned in the comments that is purely meant as performance optimization. It doesn't change the behavior of the code. The reserve call will cause allocation of a memory block large enough to hold the final vector size, but doesn't construct any of the elements yet, which would still be done with push_back.

This is a performance optimization because otherwise the final size is not known to the vector and so it may need to reallocate memory blocks multiple times during the loop, which will (asymptotically for large sizes) increase the time that the loop takes by a constant factor, assuming the length of the strings is bounded and the call to mph->getValue() is O(1), otherwise the effect will be less significant.

Is initializing a vector of empty values more efficient than just calling `push_back()`?

In short, push_back causes re-allocation only when size exceeds capacity.

If your concern is preallocation "might" impact performace, then using vector::reserve would let vector preallocate capacity if you know how much you want. Then push_back won't cause allocation when it doesn't exceed capacity.

However if you don't know the length of your data, reserve is not suitable. So use it judiciously.

Ref: https://en.cppreference.com/w/cpp/container/vector/reserve

The example in cppreference: https://godbolt.org/z/PcYjWj

---

Between setting size in ctor or reserve, it depends on whether you need default-initialized value or not.

Benefits of using reserve() in a vector - C++

It's useful if you have an idea how many elements the vector will ultimately hold - it can help the vector avoid repeatedly allocating memory (and having to move the data to the new memory).

In general it's probably a potential optimization that you shouldn't need to worry about, but it's not harmful either (at worst you end up wasting memory if you over estimate).

One area where it can be more than an optimization is when you want to ensure that existing iterators do not get invalidated by adding new elements.

For example, a push_back() call may invalidate existing iterators to the vector (if a reallocation occurs). However if you've reserved enough elements you can ensure that the reallocation will not occur. This is a technique that doesn't need to be used very often though.

Why push_back is slower than operator[] for a previously allocated vector

push_back does a bounds check. operator[] does not. So even if you've reserved the space, push_back is going to have an extra conditional check that operator[] will not have. Additionally, it will increase the size value (reserve only sets the capacity), so it will update that every time.

In short, push_back is doing more than what operator[] is doing - which is why it is slower (and more accurate).

std::vector reserve() and push_back() is faster than resize() and array index, why?

Does resize initialize the newly allocated vector where reserve just allocates but does not construct?

Yes.

Vector: initialization or reserve?

Both variants have different semantics, i.e. you are comparing apples and oranges.

The first gives you a vector of n default-initialized values, the second variant reserves the memory, but does not initialize them.

Choose what better fits your needs, i.e. what is "better" in a certain situation.

allocating memory using push_back vs constructing vectors of specific size

I think the author is comparing the following two cases:

int n = ...;
std::vector<...> v(n);
for (auto& x : v) x = some_value_known_at_runtime;

and

int n = ...;
std::vector<...> v;
for (int i = 0; i < n; i++) v.push_back(some_value_known_at_runtime);

The 1st case would construct the vector with n default-constructed elements, then assign them later; which might result in poorer performance.

Of cource, you can use reserve in 2nd case, which could avoid reallocation and make it more effcient; if the count of elements could be known in advance.

int n = ...;
std::vector<...> v;
v.reserve(n);
for (int i = 0; i < n; i++) v.push_back(some_value_known_at_runtime);

---

Related Topics