c++ - 多线程安全插入 vector 的最快方法是什么？

Question

我有一个程序，其中多个线程共享相同的数据结构，该数据结构基本上是一个二维 vector 数组，有时两个或多个线程可能必须插入相同的位置，即 vector ，如果不采取预防措施可能会导致崩溃.为这个问题实现安全解决方案的最快和最有效的方法是什么？由于这个问题不会经常发生(没有高争用)，我有一个 2D 互斥数组，其中每个互斥映射到一个 vector ，然后每个线程锁定然后在完成更新相应 vector 后解锁互斥。如果这是一个好的解决方案，我想知道是否有比 mutex 更快的东西可以使用。

请注意，我正在使用 OpenMP 进行多线程处理。

Answer 1

解决方案在很大程度上取决于问题的性质。例如:

• 如果 vector 大小可能超出其容量(即需要重新分配)。
• 是否只读取 vector 、插入元素或元素既可以插入也可以删除。

在第一种情况下，除了使用锁你别无选择，因为你总是需要检查 vector 是否正在重新分配，并在必要时等待重新分配完成。

另一方面，如果您完全确定 vector 仅由单个线程初始化一次(这不是您的情况)，您可能不需要任何同步机制来执行对 vector 元素(内部元素)的访问不过，可能仍需要访问同步)。

如果仅在 vector 的后面插入和删除元素(队列样式)，则使用 atomic compare and swap就足够了(自动增加 vector 的大小，并在交换成功时插入位置 size-1。

如果元素可以在 vector 的任何点被删除，它的内容可能需要移动以删除空洞。这种情况类似于重新分配。您可以使用自定义堆来管理 vector 中的空位置，尽管这会增加复杂性。

最终，您可能需要开发自己的并行数据结构或依赖库，例如 TBB或 Boost .