如何避免大量锁？

Question

让arr声明如下。

std::vector<std::vector<int>> arr(10,000,000);

我的串行代码是这样的

for (const auto [x, y] : XY) {
  arr[x].push_back(y);
}

我使用openmp，定义了一个锁数组如下。

std::vector<omp_lock_t> locks(10,000,000);

用locks，我用

#pragma omp parallel for schedule(dynamic)
for (const auto [x, y] : XY) {
  omp_set_lock(&locks[x]);
  arr[x].push_back(y);
  omp_unset_lock(&locks[x]);
}

这种方法适用于我的机器（windows linux 子系统）。但后来我发现以下 post

c/c++ maximum number of mutexes allowed in Linux

这让人担心我是否使用了太多的锁，我的程序可能不适用于其他平台（那些对允许的锁数量有限制的平台）。

请问有没有其他方法可以让我的控制粒度和上面一样，而且没有上限。我可以使用比较和交换之类的东西吗？

Answer 1

根据 OpenMP documentation，omp_lock_t 代表 “一个简单的锁”。我想它是某种 自旋锁 。因此，您不需要关心互斥量的限制。（互斥量需要与内核/调度程序进行一些交互，这可能是限制它们数量的原因。）

omp_lock_t 使用单个内存位置，这对于自旋锁来说很好。例如，这个现场演示显示 omp_lock_t 只需要 4 个字节，而 std::mutex 需要 40 个字节：https://godbolt.org/z/sr845h8hx.

请注意，自旋锁可以用单个字节实现，甚至可以用单个位实现（BTS on x86_64）。因此，您可以在内存中更多地压缩锁。但是，我会小心使用这种方法，因为它会带来严重的 虚假共享 问题。

我认为您的解决方案非常好。由于临界区中的操作应该非常快，并且多个线程同时访问同一元素的可能性很低，我认为自旋锁是一个合适的解决方案。

编辑

正如评论中所指出的，术语简单锁可能并不意味着该锁实际上是自旋锁。由 OpenMP 实现决定它将使用哪种类型的锁。然后，如果您想确保您使用的是真正的自旋锁（我仍然认为它是合适的），您可以自己编写或使用某个提供自旋锁的库。（请注意，高效的自旋锁实现并不那么简单。例如，它需要在 load/read 操作而不是 exchange/test-and-set 操作上自旋，这通常是天真的实现。）

Answer 2

几个可能的解决方案

如果您使用的是支持事务同步扩展 (TSX) 的现代英特尔处理器，则可以使用单个推测锁。（请参阅 [您可能错过的两个小型 OpenMP 功能][1]）。这显示了一个非常相似的用例。

您可以使用较小的锁数组并使用散列从数组索引映射到锁集。像这样的东西（未经测试和编译！）

// Allocate and initialise the lock array, wherever you have that!
    enum { ln2NumLocks = 10,
           NumLocks = 1<<ln2NumLocks }
    omp_lock_t locks[NumLocks];
    for (int i=0; i<NumLocks; i++)
        omp_init_lock(&locks[i]);

// Hash from array index to lock index. What you have here
// probably doesn't matter too much. It doesn't need to be
// a crypto-hash!
int mapToLockIdx(int arrayIdx) {
    return ((arrayIdx >> ln2NumLocks) ^ arrayIdx) & (numLocks-1);
}

// Your loop is then something like this
#pragma omp parallel for schedule(dynamic)
for (const auto [x, y] : XY) {
    auto lock = &locks[mapToLock(x)]; 
    omp_set_lock(lock);
    arr[x].push_back(y);
    omp_unset_lock(lock);
}



  [1]: https://www.openmp.org/wp-content/uploads/SC18-BoothTalks-Cownie.pdf

如何避免大量锁？

How do I avoid large number of locks?

c++

parallel-processing

multithreading

mutex

openmp