c++ - C++ map of maps 上的细粒度锁

Question

我有一个 C++17 应用程序，它有多个线程并发写入 map 的 map :

// global shared variable across threads
std::map<int, std::map<int, int>> the_map;

// many threads inserting different values for varying i and j
auto val = somewhat_expensive_f()
the_map[i][j] = val;

对于此应用程序，完成后 the_map 中有数万个唯一 (i,j) 对和大约 2,000 个 map 。我正在尝试运行多个线程来运行昂贵的计算，这些计算会插入到这张 map 中。现在我正在使用 std::map不允许并发插入。

我用 std::lock_guard<std::mutex> 包装了插入内容作为第一次削减，当然这确实减慢了应用程序并阻碍了并发性。我的直觉是我可以使用一些并发映射映射或细粒度锁定。

对于第二种方法，我的直觉是使用 (i,j) 元组的散列来创建某种锁数组，这些锁被编入索引。例如，lock_guard<mutex>(array_of_locks[hash((i<<32)|j) % array_sz])可以允许在数千个子 map 之间共享多个锁。

问题 1:我走在正确的轨道上吗？对此方法有任何反馈吗？

问题 2:使用这种方法时，我担心的一个问题是数组中相邻互斥锁的错误共享。我可以填充它们以填充整个缓存行。有更好的方法吗？

我可以考虑的另一种方法是在线程本地映射中进行某种插入，然后稍后将它们组合到主线程中。

Answer 1

将您的 map 分成多张 map ，每张 map 都可以独立锁定，是一种很好且实用的方法。高效执行此操作的关键是记住，虽然您的 map 中可能有成千上万个条目，但您可能没有那么多线程或那么多内核。

如果您的机器有 8 个核心，然后将您的 key 散列到 64 个不同的桶中，每个桶都有自己的映射和互斥锁，将确保不太可能发生争用，并且不会显着降低应用程序的速度。

最多 8 个核心可以同时尝试插入，即使它们一直这样做，也只有 12% 的时间被阻止。不过，您的线程可能还有很多其他事情要做，因此真正的争用远不止于此。

正如@Eric 指出的那样，Google 的神奇词是“锁 strip 化”。

关于相邻互斥锁的错误共享:std::map 插入速度不够快，这不是一个真正的问题。

您可能需要担心的一件事是用于分配 map 节点的内存分配器中的争用。毕竟，它们都来自同一个堆。