std :: unordered_map: многопоточность вставок? - PullRequest
Новая
       27

std :: unordered_map: многопоточность вставок?

0 голосов
/ 16 декабря 2018

У меня есть куча данных (огромный список целых чисел от 0 до ULLONG_MAX), и я хочу извлечь все уникальные значения.Мой подход заключается в создании unordered_map, используя значения целочисленного списка в качестве ключей и одноразовый бул для значений карты.Я повторяю список и вставляю одноразовые значения для каждого ключа.В конце я повторяю карту, чтобы получить все уникальные ключи.Довольно прямо вперед.

Однако мой список настолько велик (сотни миллионов), что я бы хотел многопоточность этого процесса.Я знаю, что наивный подход к многопоточности не сработает, потому что вставки unordered_map влияют на базовую структуру данных и поэтому не безопасны для потоков.А добавление блокировок вокруг каждой вставки будет медленным и, возможно, сведет на нет любое ускорение потоков.

Однако, предположительно, не каждая вставка изменяет структуру данных (только те, которые не помещаются в существующие выделенные сегменты?).Есть ли способ проверить, потребуется ли перераспределение unordered_map для конкретной вставки, перед вставкой?Таким образом, я мог блокировать потоки только тогда, когда карта меняется, вместо блокировки во время каждой вставки.Затем перед каждой вставкой потоки просто проверяют, существует ли блокировка ... вместо того, чтобы делать полную блокировку / разблокировку.Это возможно?

1 Ответ

0 голосов
/ 16 декабря 2018

Фундаментальное правило распараллеливания разбивает работу на части, работает на части, а затем объединяет части

Хеширование / поиск элементов - самая дорогая часть всего шебанга, поэтому мы сосредоточимся на распараллеливании.

Если вам абсолютно необходим результат в виде хеш-таблицы, у меня для вас плохие новости: вам придется написать свой собственный.Как говорится, давайте начнем.

Во-первых, давайте решим проблему в серийном режиме.это простоПриведенная ниже функция принимает вектор и обратный вызов.Мы собираемся взять вектор, преобразовать его в unordered_set и передать unordered_set для обратного вызова.Просто?Да.

Теперь, поскольку мы собираемся делать это в потоке, мы не можем сделать это сразу.Вместо этого мы вернем лямбду, которая не принимает аргументов.Когда эта лямбда вызывается, именно тогда она создаст unordered_set и передаст ее обратному вызову.Таким образом, мы можем передать каждую лямбду своему собственному потоку, и каждый поток запустит задание, вызвав лямбду.

template<class Vector, class Callback>
auto lazyGetUnique(Vector& vector, Callback callback) {
    using Iterator = decltype(vector.begin());
    auto begin = vector.begin();
    auto end = vector.end();
    using elem_t = typename std::iterator_traits<Iterator>::value_type;

    //We capture begin, end, and callback
    return [begin, end, callback]() {
        callback(std::unordered_set<elem_t>(begin, end));
    };
}

Теперь - что должен делать этот обратный вызов?Ответ прост: обратный вызов должен назначить содержимое unordered_set на вектор.Зачем?Потому что мы собираемся объединить результаты, и объединить векторы намного быстрее, чем объединить unordered_set.

Давайте напишем функцию, которая даст нам обратный вызов: 

template<class Vector>
auto assignTo(Vector& v) {
    return [&](auto&& contents) {
        v.assign(contents.begin(), contents.end());
    };
}

Предположим, мы хотим получить уникальные элементы вектора и присвоить их обратно этому вектору.Теперь это действительно просто сделать: 

std::vector<int> v = /* stuff */;
auto new_thread = std::thread( lazyGetUnique(v, assignTo(v)) );

В этом примере, когда new_thread завершит выполнение, v будет содержать только уникальные элементы.

Давайте посмотрим на полную функцию, чтобы сделать все.

template<class Iterator>
auto getUnique(Iterator begin, Iterator end) {
    using elem_t = typename std::iterator_traits<Iterator>::value_type;

    std::vector<elem_t> blocks[4];

    //Split things up into blocks based on the last 4 bits
    //Of the number. This allows us to guarantee that no two blocks
    //share numbers. 
    for(; begin != end; ++begin) {
        auto val = *begin; 
        blocks[val & 0x3].push_back(val); 
    }

    //Each thread will run their portion of the problem.
    //Once it's found all unique elements, it'll stick the result in the block used as input
    auto thread_0 = std::thread( lazyGetUnique(blocks[0], assignTo(blocks[0])) );
    auto thread_1 = std::thread( lazyGetUnique(blocks[1], assignTo(blocks[1])) );
    auto thread_2 = std::thread( lazyGetUnique(blocks[2], assignTo(blocks[2])) );

    //We are thread_3, so we can just invoke it directly
    lazyGetUnique(blocks[3], assignTo(blocks[3]))(); //Here, we invoke it immediately

    //Join the other threads
    thread_0.join();
    thread_1.join();
    thread_2.join(); 

    std::vector<elem_t> result;
    result.reserve(blocks[0].size() + blocks[1].size() + blocks[2].size() + blocks[3].size());

    for(int i = 0; i < 4; ++i) {
        result.insert(result.end(), blocks[i].begin(), blocks[i].end());
    }

    return result;
}

Эта функция разбивает вещи на 4 блока, каждый из которых не пересекается.Он находит уникальные элементы в каждом из 4 блоков, а затем объединяет результат.На выходе получается вектор.

...