Почему многопоточная работа на одном векторе медленная? - PullRequest
Новая
       4

Почему многопоточная работа на одном векторе медленная?

2 голосов
/ 19 февраля 2020

У меня много ключей (c -строк), и я хочу пересчитать их хэши. Я сделал структуру, которая содержит ключевые данные и их ха sh. Я поместил эти структуры в вектор и разделил вектор на группы. Каждая группа ключей будет хешироваться одним потоком.

Минимальный пример: 

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();

У меня около 3 000 000 ключей. Если я запускаю код с одним потоком - просто вызываю hash_keys(0, keys.size()) - я получаю 4,0 секунды предполагаемого времени. Если я запускаю код с 4 рабочими потоками, я получаю 5,5 секунды.

Вопрос в том, почему это медленнее? Чтение одного вектора из нескольких потоков не рекомендуется? И как я могу использовать эти темы и сделать это в более короткие сроки?

1 Ответ

0 голосов
/ 02 марта 2020

Оказалось, что с моим кодом возникли две проблемы:

  • Ложное совместное использование, когда один поток обновил га sh одного ключа, он попытался записать в ту же строку кэша, что и соседний поток, который значительно замедлилось выполнение
  • Каждый ключ был создан с помощью одного вызова new вместо одновременного создания нескольких ключей (в примере не видно, эта проблема возникла в функции external_fill_keys).

Решением будет создание независимого массива ключей для каждого потока, и после объединения потоков массивы будут объединены в один большой массив.

...