Filling a vector with multiple threads
<p>I need to fill a huge (7734500 elements) <code>std::vector&lt;unsigned int&gt;</code> with random values, and I am trying to do it in parallel with multiple threads to achieve a higher efficiency. Here is the code that I have so far:</p>

<pre><code>std::random_device rd; // seed generator

std::mt19937_64 generator{rd()}; // generator initialized with seed from rd

static const unsigned int NUM_THREADS = 4;


std::uniform_int_distribution&lt;&gt; initialize(unsigned long long int modulus)
{
    std::uniform_int_distribution&lt;&gt; unifDist{0, (int)(modulus-1)};
    return unifDist;
}


void unifRandVectorThreadRoutine
    (std::vector&lt;unsigned int&gt;&amp; vector, unsigned int start,
    unsigned int end, std::uniform_int_distribution&lt;&gt;&amp; dist)
{
    for(unsigned int i = start ; i &lt; end ; ++i)
    {
        vector[i] = dist(generator);
    }
}


std::vector&lt;unsigned int&gt; uniformRandomVector
    (unsigned int rows, unsigned int columns, unsigned long long int modulus)
{
    std::uniform_int_distribution&lt;&gt; dist = initialize(modulus);

    std::thread threads[NUM_THREADS];

    std::vector&lt;unsigned int&gt; v;
    v.resize(rows*columns);

    // number of entries each thread will take care of
    unsigned int positionsEachThread = rows*columns/NUM_THREADS;

    // all but the last thread
    for(unsigned int i = 0 ; i &lt; NUM_THREADS - 1 ; ++i)
    {
        threads[i] = std::thread(unifRandVectorThreadRoutine, v, i*positionsEachThread,
            (i+1)*positionsEachThread, dist);
        // threads[i].join();
    }

    // last thread
    threads[NUM_THREADS - 1] = std::thread(unifRandVectorThreadRoutine, v,
        (NUM_THREADS-1)*positionsEachThread, rows*columns, dist);
    // threads[NUM_THREADS - 1].join();

    for(unsigned int i = 0 ; i &lt; NUM_THREADS ; ++i)
    {
        threads[i].join();
    }

    return v;
}
</code></pre>

<p>At the moment, it takes approximately 0.3 seconds: do you think there is a way to make it more efficient?</p>

<hr>

<p><strong>Edit:</strong> Giving each thread its own generator</p>

<p>I have modified the routine as follows</p>

<pre><code>void unifRandVectorThreadRoutine
    (std::vector&lt;unsigned int&gt;&amp; vector, unsigned int start,
    unsigned int end, std::uniform_int_distribution&lt;&gt;&amp; dist)
{
    std::mt19937_64 generator{rd()};
    for(unsigned int i = start ; i &lt; end ; ++i)
    {
        vector[i] = dist(generator);
    }
}
</code></pre>

<p>and the running time dropped by one half. So I am still sharing the <code>std::random_device</code> but each thread has its own <code>std::mt19937_64</code>.</p>

<hr>

<p><strong>Edit:</strong> Giving each thread its own vector and then concatenating  </p>

<p>I changed the code as follows:</p>

<pre><code>void unifRandVectorThreadRoutine
    (std::vector&lt;unsigned int&gt;&amp; vector, unsigned int length,
    std::uniform_int_distribution&lt;&gt;&amp; dist)
{
    vector.reserve(length);
    std::mt19937_64 generator{rd()};
    for(unsigned int i = 0 ; i &lt; length ; ++i)
    {
        vector.push_back(dist(generator));
    }
}
</code></pre>

<p>and</p>

<pre><code>std::vector&lt;unsigned int&gt; uniformRandomVector
    (unsigned int rows, unsigned int columns, unsigned long long int modulus)
{
    std::uniform_int_distribution&lt;&gt; dist = initialize(modulus);

    std::thread threads[NUM_THREADS];

    std::vector&lt;unsigned int&gt; v[NUM_THREADS];

    unsigned int positionsEachThread = rows*columns/NUM_THREADS;

    // all but the last thread
    for(unsigned int i = 0 ; i &lt; NUM_THREADS - 1 ; ++i)
    {
        threads[i] = std::thread(unifRandVectorThreadRoutine, std::ref(v[i]), positionsEachThread, dist);
    }

    // last thread
    threads[NUM_THREADS - 1] = std::thread(unifRandVectorThreadRoutine, std::ref(v[NUM_THREADS-1]),
        rows*columns - (NUM_THREADS-1)*positionsEachThread, dist);

    for(unsigned int i = 0 ; i &lt; NUM_THREADS ; ++i)
    {
        threads[i].join();
    }

    std::vector&lt;unsigned int&gt; finalVector;
    finalVector.reserve(rows*columns);

    for(unsigned int i = 0 ; i &lt; NUM_THREADS ; ++i)
    {
        finalVector.insert(finalVector.end(), v[i].begin(), v[i].end());
    }

    return finalVector;
}
</code></pre>

<p>The execution time is slightly worse than before, when I was using just one vector shared between all the threads. Am I missing something or can it just happen?</p>

<hr>

<p><strong>Edit:</strong> using a different PRNG + benchmarks  </p>

<p>Using a different PRNG (as suggested in some comments/answers) helps a lot: I tried with the <code>xorshift+</code> and here is the implementation I am using:</p>

<pre><code>class xorShift128PlusGenerator
{
public:
    xorShift128PlusGenerator()
    {
        state[0] = rd();
        state[1] = rd();
    };


    unsigned long int next()
    {
        unsigned long int x = state[0];
        unsigned long int const y = state[1];
        state[0] = y;
        x ^= x &lt;&lt; 23; // a
        state[1] = x ^ y ^ (x &gt;&gt; 17) ^ (y &gt;&gt; 26); // b, c
        return state[1] + y;
    }


private:
    std::random_device rd; // seed generator
    unsigned long int state[2];

};
</code></pre>

<p>Then the routine is as follows</p>

<pre><code>void unifRandVectorThreadRoutine
    (std::vector&lt;unsigned int&gt;&amp; vector, unsigned int start,
    unsigned int end)
{
    xorShift128PlusGenerator prng;
    for(unsigned int i = start ; i &lt; end ; ++i)
    {
        vector[i] = prng.next();
    }
}
</code></pre>

<p>Since I am now home and I am using a different (and more powerful) machine, I redid the tests to compare the results. Here is what I obtain:</p>

<ul>
<li>Mersenne Twister with one generator per thread: 0.075 seconds</li>
<li>xorshift128+ shared between all threads: 0.023 seconds</li>
<li>xorshift128+ with one generator per thread: 0.023 seconds</li>
</ul>

<p>Note: the execution time varies at each repetition. These are just typical values.</p>

<p>So there seems to be no difference if the xorshift generator is shared or not, but with all these improvements the execution time has dropped significantly.</p>