更快 test_and_clear_bit

Question

我运行在 x86_64 上的 Linux 内核模块中使用下面的代码。基本上，我迭代了 256 位，对于设置为 1 的每一位，我将其清除并执行特定操作。但是，下面的代码需要几千个周期才能运行（瓶颈不是在 if 语句主体内执行的代码）。

unsigned long *data = ...;
for (int i = 0; i < 256; i++) {
    //test_and_clear_bit is a function defined in the Linux kernel
    if (test_and_clear_bit(i, data)) {
        //bit i was set, so do something
    }
}

瓶颈似乎是 test_and_clear_bit 函数。我正在迭代的数据是一个 硬件定义的数据结构 ，我只能用读-修改-写指令来改变它（根据英特尔手册）。这是因为处理器可能会同时尝试改变数据结构。因此，我不能退回到简单的解决方案，例如使用单个自旋锁保护数据结构，然后仅使用非原子指令读取和清除位。

有更快的方法吗？

Answer 1

这是一个很难回答的问题，因为我们不知道这个数据到底是什么，而且因为这个声明：

The data I'm iterating over is a hardware-defined data structure that I may only mutate with read-modify-write instructions (according to the Intel manual).

也就是说，我们能做的最好是笼统 ideas/recommendations，这可能适用于也可能不适用于您的具体情况。您可以尝试以下方法：

将 data 复制到本地缓冲区 并迭代这些位，只有在本地缓冲区中设置了该位时才调用 test_and_clear_bit。这将避免在尚未在本地缓冲区上设置的位上调用 test_and_clear_bit。显然，未在本地缓冲区中设置的位可能已在结构复制和执行之间设置，但如果这是可以接受的损失，这可能会显着加快循环.
如果可能，一次测试多个位。正如@immibis 在评论中提到的那样，如果您可以一次检查 8、16、32 或 64 位，那么只有在您从 multi-bit 集获得响应时才测试单个位。如果很可能每 8 个或更多个中至少有一个位被设置，那么这将不起作用并且实际上会减慢循环，因为它会添加一个额外的不必要的调用。
尝试使用 volatile 实现您自己的 test_and_clear_bit，正如@IlyaBursov 在评论中提到的那样。这 not 保证有效，并且在一个平台或编译器上可能有效的可能在另一个平台或编译器上无效。但是，如果您使用的是 hardware-defined 内存结构，则 platform-specific 解决方案可能适合您。请注意，volatile 不太可能防止此处理器修改位，但在某些平台（如果幸运的话，您的平台）上它很可能会。作为 mentioned here：

As a result, most implementations do not insert sufficient memory fences to guarantee that other threads, or even hardware devices, see volatile operations in the order in which they were issued

On some platforms, some limited ordering guarantees are provided, either because they are automatically enforced by the underlying hardware or, as on Itanium, because different instructions are generated for volatile references. But the specific rules are highly platform dependent. And even when they are specified for a specific platform, they may be inconsistently implemented.

Answer 2

通过使用原子交换（或原子获取和与 0 的与）复制并清除本地缓冲区中的所有数据；然后继续努力。这应该和您的代码一样有效，因为您清除的每一位 都将被处理 而不会冒忽略和覆盖正在设置的位 "in the meanwhile".

的风险

我不知道 Linux 内核原语，但是 gcc atomic builtins 会是这样的：

const int bpl = 8*sizeof(unsigned long);
const int len = (256+bpl-1)/bpl;
unsigned long ldata[len];
for(int i = 0; i < len; ++i) {
    ldata[i] = __atomic_exchange_n(&data[i], 0, __ATOMIC_ACQ_REL);
}
for(unsigned i = 0; i < 256; ++i) {
    if(ldata[i/bpl] & (1<<(i%bpl))) {
        // do your stuff
    } 
}

更快 test_and_clear_bit

Faster test_and_clear_bit

c

linux

x86

atomic

linux-kernel