原子、可扩展、带边界的单调计数器

Question

我有一个关键的代码路径，线程在其中使用整数的原子增量来计算全局发生的事件数。这相当快，但仍然需要保存整数的缓存线在内核之间跳跃。在NUMA系统中，这会产生大量的MESI流量。

热拍的伪代码是所有线程都这样做：

const int CHECK_VALUE = 42;
int counterNew = counter++;
if (counterNew == CHECK_VALUE) {
Do Final work
}

计数器是单调递增的，它必须达到的值是预先知道的。

在递增counter之后，至少有一个线程必须得出全局计数器已达到CHECK_VALUE的结论。多个线程得出这样的结论是可以接受的(我总是可以在这一点上同步它们——因为这不再是热门路径)。

如果我知道counter的值是单调的，并且最终值是已知的，那么有可能比使用原子增量来跟踪它做得更好吗？

Answer 1

您可以使用原子CAS操作(比较ans交换)来完成此操作。在i386体系结构上，这是指令CMPXCHG。如果需要，您可以使用小型组装功能，在您的平台上实现CAS，或者在这里询问我关于英特尔的实施。您的代码必须如下：

int local_cnt;
// Atomic increment counter 
do {
local_cnt = counter;
} while(cas(&counter, local_cnt, local_cnt + 1) != local_cnt);
// check old counter value
if(local_cnt == CHECK_VALUE) { 
// do something
}

Answer 2

如果没有同步，计数器可能会停留在0。事实上，它不会经常出现这种比赛情况，所以计数器会大致准确。我认为您可以证明计数器序列中不会跳过任何值：如果计数器以前不是1，则不可能将其更改为2，这适用于计数器可能持有的每个值。因此，如果可以忽略一些事件，则使用++而不是原子增量的全局计数器将起作用。然而，即使不同步，这仍然会导致您想要避免的一些内存问题(跨CPU重新同步缓存线)。

另一种方法是投票。每个线程都可以在自己的私有数据中统计其事件。另一个线程可以每分钟轮询一次，查看事件数是否大于阈值。

另一种方法是在线程数据中增加一个内部计数器，当达到10时，增加全局计数器。这将使全局增量的数量减少10。

另一种方法是在线程中碰撞内部计数器。只要单个线程达到cEvents/threadcount，就执行同步。

另一种方法是在线程中碰撞内部计数器。每当单个线程达到某个限制时，请检查其他线程数，看看它们是否一起>线程数。这与使用轮询线程大致相同，但不使用其他线程。

有很多方法可以用私人柜台做这样的事情。这完全取决于你需要的准确性。