c++ - 为什么对一个 vector 进行多线程操作的速度很慢？

Question

我有很多键(C字符串)，我想预先计算它们的哈希值。我制作了一个包含关键数据及其哈希值的结构。我将这些结构插入 vector 并将 vector 分为几组。每组 key 将被一个线程散列。

最小示例:

struct Key
{
    char* data;    // mostly 10 character strings
    uint64_t hash; // init with 0 and compute later
};

// hash group of keys
static void hash_keys(size_t idx_start, size_t const& length)
{
    size_t idx_end = idx_start + length;
    for (size_t i = idx_start; i < idx_end; i++)
    {
        Key* k = keys[i];
        // hash key by murmurhash2 or djb2 hash function
        k->hash = external_hash_key(k->data);
    }
}

vector<Key*> keys;

// push all keys into keys vector
external_fill_keys();
size_t num_of_keys = keys.size();

// start threads
vector<thread> workers;

size_t length = num_of_keys / NUM_OF_WORKERS;
size_t remainder = num_of_keys % NUM_OF_WORKERS;

for (size_t i = 0; i < NUM_OF_WORKERS; i++)
    workers.push_back(
        thread(
            hash_keys,
            i * length, length
        )
    );

hash_keys(NUM_OF_WORKERS * length, remainder);

// join threads
for (auto& worker : workers)
    worker.join();

我大约有300万把 key 。如果我使用单线程运行代码-仅调用hash_keys(0, keys.size())-我将获得4.0秒的估计时间。如果我用4个工作线程运行代码，我将得到5.5秒。

问题是为什么这要慢一些？不建议从多个线程读取相同的 vector 吗？以及如何利用这些线程并在更短的时间内完成呢？

Answer 1

原来我的代码有两个问题:

错误共享，当一个线程更新了一个键的哈希值时，它试图与相邻线程写入同一缓存行，从而显着降低了执行速度

每个键都是通过单个new调用创建的，而不是一次创建更多的键(在示例中不可见，此问题发生在external_fill_keys函数中)。

解决方案是为每个线程创建独立的键数组，并在加入线程后将数组串联成一个大数组。