C++: Allocate memory for an std::vector then initialize its elements in parallel

Question

I have a use case for creating an std::vector with many elements, each of which is of a simple, but non-primitive, type (POD struct). The vector and type are sufficiently large/complex that in the following,

std::vector<U> v;
v.resize(1000000000);
for(size_t i=0;i<v.size();++i){/* initialize v[i] */}

the resize call is noticeably slow. And it's wasteful because resize is default-initializing all those entries, then I'm going through in a loop and setting them all to their correct/useful values.

What I would like to do is to allocate all the memory for the vector, but not initialize any of the entries, then go through in parallel and initialize all the entries, e.g. with OpenMP

std::vector<U> v;
v.reserve(1000000000);
#pragma omp parallel for
for(size_t i=0;i<v.size();++i){/* initialize v[i] */}

However, reserve doesn't actually change the size of v, so I'd have to keep doing push_back in my loop, which won't maintain the proper ordering of the elements (which matters in my use case); I really want to write something like v[i] = ... in my loop body.

Is there a way to allocate/"initialize" a vector without initializing any of its elements, and to then fill in / initialize all the elements in parallel?

Answer 1

Your options are:

• Replace std::vector with an alternative (e.g. uvector)
• Use some sort of library to resize without initialization, such as UninitializedMemoryHacks from Facebook.

After you've performed the resize, you can use OpenMP in the usual ways.

Answer 2

It depends on the default constructor for your type U. If the default constructor is cheap, it is very unlikely that you will gain anything parallelizing it.

struct U {
   int a, b, c;
   U():a(0), b(1), c(2) {}
};

If your default constructor is expensive, it would make more sense to split it in two parts: One for default initialization and a function for the actual initialization.

struct U {
   vector<int> a;
   U() {}
   void init(int n) { a.resize(n); }
};

In both alternatives, the regular resize or assign call to the vector would be very hard to beat.

If you really are set in doing things this way, you could use a reinterpret_cast to an array. This way, the default constructor won't be called.

U * u_array = reinterpret_cast<U*>(malloc(100*sizeof(U)));

I strongly advise against this last option.