How to avoid default initialization of objects in std::vector?

286 views Asked by At

When I allocate large space with std::vector it takes significant time because std::vector default-initializes the objects in it.

I see that a long time ago people discussed the topic in the How can I avoid std::vector<> to initialize all its elements?, but most of the recommendations were to write own memory allocator (which is quite risky, hacky and expensive) or inherit to std::vector, which is not very good solution, as well.

Have something changes since that times? Do we have any reasonable way to avoid initialization? I create some 13 Gb vectors and each takes about 2 seconds to initialize to default values which will be rewritten by the next command. I can’t believe developers didn’t provide a flexible way to avoid this initialization.

I can’t use std::vector::reserve here, since parallel execution policies (more precisely, non-ranges algorithms) require forward iterators or stronger and I can’t use std::back_inserter to fill the container. See the Update section below.

With the long discussion in comments if 'std::vector' is suitable for my needs and what are the requirements for underlying elements, I want to sum up with a very simple requirement here:

I am totally fine with std::vector and it works in most of the cases. What I need is the ability to change its size without initializing the underlying elements, just an option to make std::vector::size = std::vector::capacity not causing _Uninitialized_fill_n in std::vector which could be done with my own allocator and which one I still want to avoid.

To show in code:

#include <chrono>
#include <vector>
#include <iostream>

int main()
{
    std::chrono::high_resolution_clock::time_point start;
    std::chrono::high_resolution_clock::time_point end;
       
    const std::size_t size = 13'000'000'000 / sizeof(int);

    start = std::chrono::high_resolution_clock::now();
    int *arr = new int[size];
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Allocation with new took: " << std::chrono::duration<double>(end - start) << "\n";
    
    start = std::chrono::high_resolution_clock::now();
    std::vector<int> v(size);
    end = std::chrono::high_resolution_clock::now();
   
    std::cout << "Allocation with std::vector took: " << std::chrono::duration<double>(end - start) << "\n";

    // Prevent "over" optimization
    for (std::size_t i = 1; i < size; ++i) {
        v[i]+=v[i-1];
        arr[i]+=arr[i-1];
    }

    std::cout << v[size-1] << arr[size-1];
}

Less memory allocated on live demo to make it runnable.

On my PC (Winx64, MSVC++ 2022 latest, Release, Fully Optimized) it shows:

Allocation with new took: 0.50399s
Allocation with std::vector took: 2.04084s

And these 1.5 seconds of difference for every vector I don’t want to pay for.

Update

Since this caused misunderstanding in comments, here is why std::vector::reserve doesn't work for me. The code

#include <execution>
#include <vector>

int main()
{
    std::vector source_data = { 1,2,3,4,5 }; // Gigabytes of real data

    std::vector<int> v;
    v.reserve(source_data.size());

    std::transform(std::execution::par_unseq, 
        source_data.begin(), source_data.end(), std::back_inserter(v),
        [](auto in) {
            return in+1; // Some transformation
        });
}

won't compile with the error code like

Error C2338 static_assert failed: 'Non-ranges algorithms require that mutable iterators be Cpp17ForwardIterators or stronger.

which is highly reasonable, since std::back_inserter is output (sequential) iterator.

Update 2

In the discussion Change the size of C++ vector without initializing added elements people consider the same task, but solutions focused on two topics. The latter them is implementing own allocator, which, as I already stated above is expensive and risky.

The former solution to provide the underlying type without default initialization is more interesting, but in my circumstances (Winx64, MSVC++ 2022 latest, Release, Fully Optimized) this live demo leads only to three hundred times increase of execution time for vector allocation (to 600 seconds from 2 seconds above). Of course, the cause is this loop with emplace_back which works fine when your goal is to avoid initialization at any cost, by fails when it comes to performance which is the key in my question. The key Please correct me, if I implemented the test in a wrong way.

The same goes to the question C++ vector that doesn't initialize its members?, where similar solutions works just fine to avoid initialization but with high cost when it comes to performance. So, the formally solve the task of initialization avoidance, but the root problem of performance is not solved; the performance results in most cases worse.

Update 3

Since I don't need to change the content (add/remove elements) on the later stages, most likely, the interface I need is std::span which mostly mimics the std::vector interface except ownership and modifications. Any thoughts?

0

There are 0 answers