c++ - 支持多线程方法来构建数组中所有元素的集合吗？

Question

我有一个要散列的元素数组(它是一个模板化数组；如果您愿意，也可以是一个 vector )和一个空的散列表。我有一个具有多个核心(和超线程)的 CPU，并且希望尽可能地利用它来将所有数组元素插入到集合中。 STL(或Boost或其他一些免费库)中是否有代码可以执行此操作？

我意识到一些简单的解决方案是:

1. 使用并发/线程安全集(例如哈希支持)，并且只需让每个线程插入数组的一部分。
2. 让每个线程创建自己的集合，然后重复计算集合并集。

但重点是我宁愿不编写自己的代码，而是选择常用的代码。 编辑另外，我想要一个不需要我使用某些特定线程管理/池系统的解决方案，但我可以将其与我的任意线程一起使用。

注释:

• 不用说，集合插入不会插入重复的拷贝。
• 数组可能有重复项(事实上，我希望集合元素的数量小于数组长度的 1% - 但不能假设情况总是如此)。
• 集合不需要支持元素删除，否则可能会很慢等。

Answer 1

查看英特尔的线程构建模块 (tbb) 库，地址:http://www.threadingbuildingblocks.org 。特别是，有 concurrent_unordered_set 和其他并发友好的容器，以及函数模板(例如 parallel_for 和 parallel_for_each)来简化编写并行代码。而且 TBB 是开源且跨平台的。

Microsoft 的并行模式库 ( ppl ) 中也存在相同的功能。

一些用于将 vector 元素插入到并发无序集合中的代码草图。该代码已使用最新版本的 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，从而将聚合暴露给用户的代码。这样做的好处是，给定范围内的所有 vector 元素都可以通过一次调用插入到集合中。它增加了几个百分点的性能，并且可以使用例如隐藏一些冗长的内容。类型定义。

免责声明:我是一名 TBB 开发人员。