multithreading - 安全地更新大型数据矩阵线程: now using millions of mutexes?

Question

我正在修改很久以前写的一些代码，并决定重写它以更好地利用线程(并更好地利用编程。)。

它位于:https://github.com/buddhabrot/buddhabrot/blob/master/basic.c:

这是一个渲染佛陀分形的应用程序。出于超出此问题范围的原因，很难使用备忘录来优化此问题，并且基本上，如果您对此进行概要分析，则超过99％的时间将花费在最终执行的最内层循环中:

buddhabrot[col][row]++;

多个线程将执行此代码。由于递增不是线程安全的，因此在内存的这一部分周围使用了特定的互斥锁。因此，佛陀存储器中的每个可寻址位置都有一个单独的互斥体。

现在，这比使用一个锁更有效(当然这肯定会使所有线程都互相等待)，但是内存效率较低；似乎互斥体也需要一些数据。我还想知道带有数百万个互斥量的pthreads实现中的其他影响吗？

我现在要考虑另外两种策略:

对于 map 中的每个“区域”，使用一组不太密集的互斥锁。因此，例如[col/16] [row/16]的锁只有在访问与另一个像素相同的16像素区域时才会锁定线程。锁的密度可以动态调整。
但是，当我对此建模时，我想知道我是否没有解决甚至可能由内核实现的现有问题，而且我也真的找不到不降低速度的方法。我也考虑过“互斥树”，但在此循环中，所有这些都太慢了(为说明起见，在优化​​了编译器背后的一些数学运算的顺序之后，我可以挤出大约30％的处理器时间) 。有没有关于这个的话题，我该如何寻找有关“互斥密度计划”的信息。

复制每个线程的内存，这样我什至不必在其周围互斥。但是，这甚至使内存效率更低。它将解决具有数百万个互斥锁而又不知道其后果的问题。

那么，还有什么我能做的更好的事情吗？

Answer 1

您可以在Windows平台上使用intrin.h中的原子增量函数，例如InterlockedIncrement。

#include <intrin.h>

#pragma intrinsic(_InterlockedExchangeAdd, _InterlockedIncrement, _InterlockedDecrement, _InterlockedCompareExchange, _InterlockedExchange)
#define InterlockedExchangeAdd _InterlockedExchangeAdd
#define InterlockedIncrement _InterlockedIncrement
#define InterlockedDecrement _InterlockedDecrement
#define InterlockedCompareExchange _InterlockedCompareExchange
#define InterlockedExchange _InterlockedExchange

#pragma intrinsic(abs, fabs, labs, memcmp, memcpy, memset, strcat, strcmp, strcpy, strlen)
#pragma intrinsic(acos, cosh, pow, tanh, asin, fmod, sinh)
#pragma intrinsic(atan, exp, log10, sqrt, atan2, log, sin, tan, cos) 

此增量是原子的，不需要在矩阵上具有数百万个互斥量或全局锁。