Стенд многопоточного подхода для построения набора всех элементов в массиве?

Question

У меня есть массив элементов, которые я хочу использовать hash (это шаблонный массив или вектор, если хотите) и пустую таблицу хэша. У меня есть процессор с несколькими ядрами (и гиперпотоком), и я хочу использовать его как можно лучше, чтобы вставить все элементы массива в набор. Есть ли код в STL (или в Boost или какой-либо другой бесплатной библиотеке), который это делает?

Я понимаю, что некоторые тривиальные решения:

1. Используйте параллельный/поточно-набор (например, хэш-поддержку), и просто каждая нить вставить секцию массива.
2. Имейте каждый поток, создавая свой собственный набор, а затем повторно вычисляйте объединенные множества.

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

Примечания:

• Излишне говорить, что вставка набор не вставляет дубликаты.
• Массив может иметь дубликаты (на самом деле, я ожидаю, что количество элементов набора будет меньше 1% длины массива, но не может предполагать, что это всегда так).
• В комплект не нужно поддерживать удаление элемента, или он может быть медленным и т.д.

Answer 1

Посмотрите на компании Intel Threading Building Blocks (tbb) библиотеки в http://www.threadingbuildingblocks.org. В частности, для упрощения написания параллельного кода есть concurrent_unordered_set и другие контейнеры, совместимые с параллелизмом, а также функциональные шаблоны (например, parallel_for и parallel_for_each). И TBB является открытым и кросс-платформенным.

Та же функциональность существует и в библиотеке параллельных шаблонов Microsoft (ppl).

Несколько эскизов кода для вставки векторных элементов в concurrent_unordered_set. Код тестируется с последней версией TBB, но некоторые части для краткости опущены.

#include <tbb/tbb.h> 
#include <tbb/concurrent_unordered_set.h> // missing in tbb.h 

int main() { 
    std::vector<MyDataType> v; 
    tbb::concurrent_unordered_set<MyDataType> s; 

    /* (1) */ 
    tbb::parallel_for_each(v.begin(), v.end(), [&](const MyDataType& item){ 
     s.insert(item); 
    }); 

    /* (2) */ 
    tbb::parallel_for(size_t(0), size_t(v.size()), [&](size_t i){ 
     s.insert(v[i]); 
    }); 

    /* (3) */ 
    tbb::parallel_for(
     tbb::blocked_range<std::vector<MyDataType>::iterator>(v.begin(), v.end()), 
     [&](const tbb::blocked_range<std::vector<MyDataType>::iterator>& range){ 
      s.insert(range.begin(), range.end()); // inserts a sequence 
     } 
); 

    return 0; 
} // main 

Вариант (1) является самым простым, но и самым медленным, так как в настоящее время parallel_for_each не агрегирует обработку итераций цикла. В этом коде объем работы в одной итерации слишком мал, чтобы оправдывать накладные расходы для создания и выполнения задачи.

В варианте (2) используется parallel_for, который объединяет несколько итераций в одной задаче и, следовательно, намного быстрее, хотя и довольно прост.

Вариант (3) является самым быстрым, но также самым подробным. Он явно использует blocked_range, тем самым подвергая агрегацию коду пользователя. Преимущество заключается в том, что все векторные элементы в заданном диапазоне могут быть вставлены в набор с помощью одного вызова. Он добавляет еще несколько процентов производительности, и некоторую многословность можно скрыть, например. Определения типов.

Отказ от ответственности: Я разработчик TBB.