用多个线程填充矢量

Question

我需要std::vector<unsigned int>用随机值填充一个巨大的(7734500元素),我试图与多个线程并行地实现它以实现更高的效率.这是我到目前为止的代码:

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<> initialize(unsigned long long int modulus)
{
    std::uniform_int_distribution<> unifDist{0, (int)(modulus-1)};
    return unifDist;
}


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


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

    std::thread threads[NUM_THREADS];

    std::vector<unsigned int> 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 < 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 < NUM_THREADS ; ++i)
    {
        threads[i].join();
    }

    return v;
}

目前,大约需要0.3秒:您认为有一种方法可以提高效率吗？

---

编辑:为每个线程提供自己的生成器

我修改了例程如下

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

并且运行时间减少了一半.所以我仍在分享,std::random_device但每个线程都有自己的std::mt19937_64.

---

编辑:给每个线程自己的向量,然后连接

我更改了代码如下:

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

和

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

    std::thread threads[NUM_THREADS];

    std::vector<unsigned int> v[NUM_THREADS];

    unsigned int positionsEachThread = rows*columns/NUM_THREADS;

    // all but the last thread
    for(unsigned int i = 0 ; i < 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 < NUM_THREADS ; ++i)
    {
        threads[i].join();
    }

    std::vector<unsigned int> finalVector;
    finalVector.reserve(rows*columns);

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

    return finalVector;
}

当我在所有线程之间只使用一个向量共享时,执行时间比以前略差.我错过了什么或者它会发生吗？

---

编辑:使用不同的PRNG +基准测试

使用不同的PRNG(如某些评论/答案中所建议的)有很多帮助:我尝试过xorshift+,这是我正在使用的实现:

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 << 23; // a
        state[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
        return state[1] + y;
    }


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

};

然后例程如下

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

由于我现在在家,而且我正在使用不同(且功能更强大)的机器,我重新测试以比较结果.这是我获得的:

• Mersenne Twister每个线程有一个发生器:0.075秒
• xorshift128 +在所有线程之间共享:0.023秒
• xorshift128 +每个线程有一个生成器:0.023秒

注意:执行时间在每次重复时都会有所不同.这些只是典型值.

因此,如果共享xorshift生成器似乎没有区别,但是通过所有这些改进,执行时间显着下降.

Answer 1

生成器std::mt19937_64 generator{rd()};在线程之间共享.将存在一些需要更新的共享状态,因此存在争用; 有数据竞争.您还应该考虑允许每个线程使用自己的生成器 - 您只需要确保它们生成单独的序列.

您可能有一个缓存争用问题std::vector<unsigned int> v;,它在线程外部声明,然后在每个线程中的for循环的每次迭代中命中.让每个线程都有自己的向量来填充,一旦完成所有线程,就将它们的结果整理到向量中v.可能通过一个std::future将是最快的.争用的确切大小取决于缓存行大小和正在使用的向量(和分段)的大小.

在这种情况下,您使用相对较少的线程(4)填充大量元素(7734500),该比率可能会导致较少的争用.

对于您可能正在使用的数字线程,您应该考虑将其绑定NUM_THREADS到目标上可用的硬件并发性; 即std::thread::hardware_concurrency().

当处理这么大的元素时,你也可以避免不必要的初始化和移动结果(尽管给出了int类型,这里的移动不太明显).容器本身也是值得注意的; vector需要连续的内存,因此任何其他元素(在联盟阶段)都可能导致内存分配和复制.

随机数生成器的速度也可能具有影响,其他实现和/或算法可能显着地影响最终执行时间以供考虑.

与所有基于性能的问题一样 - 最终解决方案需要测量.实施可能的解决方案,测量目标处理器和环境并进行调整,直到找到合适的性能.