Change the size of C++ vector without initializing added elements

Question

In my program there is some frequently used data type with trivial fields

struct Element {
  Element() noexcept : x( 0 ), y( 0 ), z( 0 ) {}
  float x, y, z;
};

and also there are many pieces of code taking vectors of Elements, e.g.

void foo( std::vector<Element> & es );

So it would be very complicated to introduce radical changes in Element (like changing its default constructor) or rewriting all these pieces to replace std::vector with something else.

And I have some performance-critical place where a vector of Elements must be created, filled and passed to foo:

std::vector<Element> es;
// resize is necessary only to allocate the storage, all values will be rewritten in the parallel region later
es.resize( N );
// perform computation of all values in the vector in parallel for best performance
tbb::parallel_for( tbb::blocked_range<size_t>( 0, es.size() ), 
    [&]( const tbb::blocked_range<size_t> & range ) {
        for ( size_t i = range.begin(); i < range.end(); ++i ) {
           ...
           es[i] = ...
        }
    }
…
foo( es );

What I observe is that es.resize takes considerable time for huge N because it not only allocates the memory, but also default initializes every element, which is not necessary in my case.

Is there a way to increase the size of the vector without initializing its elements, which will be all initialized later? Something like std::make_unique_for_overwrite available for unique_ptrs.

Taegu

You want reserve, but to use that you have to add elements into the vector using push_back or similar functions. – Bedrail

It's a rare case, when it's better to use a raw array in std::unique_ptr<Element[]>. FYI std::string in C++23 gets std::string::resize_and_overwrite() for such purposes. IDK why std::vector<T> does not. – Robomb

You could potentially add a tag c'tor that is a no-op. Then reserve + emplace_back in a loop, hoping an optimising compiler sees the whole thing as discardable. Might be a long shot, though. – Cynical

@Bedrail emplace_back() would be the preferred choice – Guajardo

Another option is to just get rid of the vector. Since you know exactly how many elements you need memory for, allocate a byte array of that size, and then use placement-new or std::construct_at() to construct the actual elements in it where needed. – Guajardo

@RemyLebeau You can't use emplace_back with the OP's type as is: coliru.stacked-crooked.com/a/1aec8b768427b696. If you use emplace_back({1, 2, 3}) instead it will work but push_back will do the same thing. – Bedrail

@Bedrail you can if a suitable constructor is added to the struct. – Guajardo

Answer 1

Thanks to the comment by StoryTeller, the following solution worked for me.

I added no-op constructor in Element:

struct NoInit {};
inline constexpr NoInit noInit;

struct Element {
  Element() noexcept : x( 0 ), y( 0 ), z( 0 ) {}
  Element( NoInit ) noexcept { }
  float x, y, z;
};

Then replaced es.resize( N ); with the call to new function:

template<class V>
void resizeNoInit( V & v, size_t targetSize )
{
    // allocate enough memory
    v.reserve( targetSize );
    // resize without memory access
    while ( v.size() < targetSize )
        v.emplace_back( noInit );
    // in case initial size was larger
    v.resize( targetSize );
}

making initial reserve and then adding elements in the vector one by one using emplace_back without actual access to the element's memory.

It works many times faster than standard vector::resize, and Clang is especially good in optimizing it:

resizeNoInit: 0.0011801
std. resize:  0.0184119

Online demo: https://godbolt.org/z/n6Tc7dj88

Taegu

The timings change if you repeat the test and take the average time (rather than running each only once). Then Clang is pretty similar and GCC's resize is faster than resizeNoInit. Also, in your test, you should use the same constructor, so call resize(N, noInit). See godbolt.org/z/Yn7G1nz9M – Niccolo

@flipchart, thanks. Please note that es.resize(N, noInit) creates one element using noInit constructor and then copies it to initialize all other elements in the vector. Surprisingly, compilers can optimize it well. – Taegu

Answer 2

I guess that a custom allocator can help you. The 2nd template parameter of the std::vector can be used for this purpose.

And that allows you to implement the best fitting solution for you.

If you want that the values are not initialized, then you could derive your custom allocator from std::allocator and overwrite/add a new construct function. The explanation for construct can be read here.

If we copy and paste the functions prototype from the above link, but implement it as an "empty" function, then we can maybe get what you want.

And, please use the std::vectors reserve function (omitted in below example).

Please see a very simple example below:

#include <iostream>
#include <vector>

struct Element {
    Element() noexcept : x(0), y(0), z(0) {}
    double x, y, z;
};

template <class T>
struct MyAllocator : public std::allocator<T> {
    template <class U, class... Args> void construct(U*, Args&&...) {}
};
using ElementAllocator = MyAllocator<Element>;

int main() {
    std::vector<Element, ElementAllocator> data(5, Element{});

    for (const Element& e : data) std::cout << e.x << '\t' << e.y << '\t' << e.z << '\n';
    data.resize(10);
    for (const Element& e : data) std::cout << e.x << '\t' << e.y << '\t' << e.z << '\n';
}

Most probably you would need to write an allocator function that will exactly fit your needs. I do not have enough information here for more support . . .

Aurum

Thanks. As far as I understand, this will require to change std::vector<Element> to std::vector<Element, ElementAllocator> both in the place of construction and in all functions receiving and passing that data type, which is a lot of work in big codebase. Also it will require more changes since now all resizes stop initializing elements and not only the necessary one. – Taegu

It isn't the allocator that does the default-construction but the container itself. – Doggoned

Answer 3

I've developed a C++20-capable union called ndi_t<> for types without a destructor to omit their default-construction:

#pragma once
#include <type_traits>
#include <new>
#include <utility>

template<typename T>
#if defined(__cpp_concepts)
    requires std::is_trivially_destructible_v<T>
#endif
union ndi_t
{
    ndi_t();
    template<typename ... Args>
        requires std::is_constructible_v<T, Args &&...>
    ndi_t( Args &&... args );
    ndi_t &operator =( T const &assign );
    template<typename ... Args>
        requires std::is_constructible_v<T, Args &&...>
    T &construct( Args &&... args );
    operator T &();
    T *operator &();
    T *operator ->();
private:
    T m_value;
};

template<typename T>
#if defined(__cpp_concepts)
    requires std::is_trivially_destructible_v<T>
#endif
inline ndi_t<T>::ndi_t()
{
}

template<typename T>
#if defined(__cpp_concepts)
    requires std::is_trivially_destructible_v<T>
#endif
template<typename ... Args>
#if defined(__cpp_concepts)
    requires std::is_constructible_v<T, Args &&...>
#endif
inline ndi_t<T>::ndi_t( Args &&... args ) :
    m_value( std::forward<Args>( args ) ... )
{
}

template<typename T>
#if defined(__cpp_concepts)
    requires std::is_trivially_destructible_v<T>
#endif
inline ndi_t<T> & ndi_t<T>::operator =( T const &assign )
{
    m_value = assign;
    return *this;
}

template<typename T>
#if defined(__cpp_concepts)
    requires std::is_trivially_destructible_v<T>
#endif
template<typename ... Args>
#if defined(__cpp_concepts)
    requires std::is_constructible_v<T, Args &&...>
#endif
inline T &ndi_t<T>::construct( Args &&... args )
{
    new( (void *)&m_value ) T( std::forward<Args>( args ) ... );
    return m_value;
}

template<typename T>
#if defined(__cpp_concepts)
    requires std::is_trivially_destructible_v<T>
#endif
inline ndi_t<T>::operator T &()
{
    return m_value;
}

template<typename T>
#if defined(__cpp_concepts)
    requires std::is_trivially_destructible_v<T>
#endif
inline T *ndi_t<T>::operator &()
{
    return &m_value;
}

template<typename T>
#if defined(__cpp_concepts)
    requires std::is_trivially_destructible_v<T>
#endif
inline T *ndi_t<T>::operator ->()
{
    return &m_value;
}

With that you could f.e. do a vector<ndi_t<int>>::resize( N ) without the appended items to be default-initialized.
The objects mostly behave like their native-counterparts., i.e. you can assign values of the type encapuslated in ndi_t inside them and you could read their native values. If you want to get the address of the encapsulated object just apply & to the ndi_t<>-object and you'll get the address of the encapsulated data. And you can access members with the ->-operator if the encapsulated type is a class-type.
The only drawaback so far I've seen is that if you have a container and you want to get the address an iterator points to with to_address( it ) you get the address of the ndi_t<>-object and not the encapsulated object; so you have to apply &* to the address returned by to_address().

Doggoned