如何在并发情况下填充std::unordered_map?

Question

我需要填充一个包含大约100个条目的std::unordered_map<int,T>。这些条目构造成本高昂，我希望使用OpenMP并行地执行此操作：

unordered_map<int, T> mapWithTs;

#pragma omp parallel for schedule(dynamic) // dynamic because T constructs in some unpredictable time.
for(int i=0; i<100; ++i)
{
  mapWithTs.emplace(i, {i}) // calls the constructor T(i)
}

我读到地图将重新哈希，迭代器将不再有效。我该怎么做才能使其正常工作？

此外，标准库的并发解决方案会是什么样子？

- dani

---

昂贵的建造是否意味着它们易于搬迁？每个线程能否创建自己的完整向量，然后一个线程将这些向量对象移动到映射中？ - Galik

你需要创建多个线程，每个线程填充自己的映射表，然后将这些映射表合并（在单个线程中）。 - n. m.

你只需要同步（互斥）对地图的访问。我不知道如何使用OpenMP进行同步，但是你可能知道。如果不知道，请查阅文档。 - Cheers and hth. - Alf

@ Galik，你提到了我的第一个计划，但我在想是否有直接做的方法。例如，禁止再散列或类似的东西。现在我认为最好的方法是默认构造一个“空的”T，然后重写它或者使用一些T::doTheExpensivePart()方法。 - dani

为什么不使用已经为并行设计的数据结构，例如TBB的concurrent unordered map https://software.intel.com/en-us/node/506171？您可以将其与OpenMP一起使用，尽管您可能还想查看TBB以满足所有并行需求。 （顺便说一句，我在英特尔工作，但不是在TBB上，而且无论如何，TBB都是BSD风格许可证：-））。 - Jim Cownie

Answer 1

如果这些昂贵的构造实例是通过引用（例如shared_ptr、裸指针等）来帮助的，我建议让每个线程创建自己的本地映射，即堆栈局部映射，在一个被经典地称为“映射”的步骤中，然后在一个经典的被称为“减少”的步骤中将它们组合起来。

这就是所谓的“Map-Reduce”算法。

“map”是一个函数的通常名称，该函数将一个函数应用于集合中的所有元素。

“reduce”是一个函数的通常名称，通过调用当前中间结果和每个元素的函数，将集合中的所有元素组合成单个值。

因此有了这个名字 :)

- yeoman

---

需要注意的一件事是使用“map”操作时隐式地通过new、malloc或类似方式使用堆内存。大多数实现为所有线程提供单个堆，因此使用堆内存可能会导致争用和锁定，类似于显式使用带锁的共享映射。 - Andrew Henle

你的意思是当它运行低时吗？或者是JVM、GNU libc++、BSD libc++的堆在并发分配方面出奇地低效吗？ - yeoman

你是指它运行低时吗？还是JVM、GNU libc++、BSD libc++的堆在并发分配方面出奇地低效？两者都有可能。这取决于堆实现和内存使用模式。根据我的经验，多线程感知堆通常表现得非常好 - 大多数情况下。但我见过一些使用模式，会将这种堆实现降为有效地单线程应用程序。如果你进行基准测试，期望从运行8个线程中获得6倍加速，并且看不到任何加速，那么这只是需要注意的事情。 - Andrew Henle

非常感谢您指出这一点，这可能会成为非常有价值的知识，就像监控Unix或Linux机器的系统负载一样，我最近才发现这是一个大问题:D - yeoman

Answer 2

正如Galik和yeoman所指出的那样，使对象移动成为廉价操作是至关重要的。如果已经是这样（构造很重，但移动很便宜），那么你就没问题了。否则，你应该将对象放入uniq_ptr中。之后，重新哈希也将成为一项廉价操作（是的，重新哈希需要线性时间，但它是0（1）摊销复杂度）。因此，你不需要担心重新哈希。

接下来是填充映射。你从几个线程中使用它，因此必须确保不超过一个线程同时使用它。你需要像#pragma omp critical或std::mutex这样的东西。这里有一个重要的部分：如果你像现在这样使用emplace，那么重型T构造函数将在关键部分执行，这将破坏并行化的整个思想。因此，在这种特殊情况下，你更喜欢事先创建对象T，然后进入关键部分，并将对象移动到哈希映射中。

如果构建T是一个非常耗时的操作（比将值插入unordered_map要花费更长时间），那么就这样吧。通过创建每个线程列表并将它们插入到map中，您不会获得性能提升。否则，yeoman的答案可以为您带来额外的好处，但代价是增加代码的复杂性。

- Alexey Guseynov