为什么 bitops in linux 内核性能比我的慢？

Question

我正在寻找用 c 语言编写的最佳 bitops 库或函数，因此我认为 linux 内核在这种情况下是最好的。
所以我从 arch/x86/include/asm/bitops.h 复制 Linux 内核 set_bit 函数并与我的进行比较，结果很奇怪！！！

kernel_bitops.c

#define ADDR                   BITOP_ADDR(addr)
#define __ASM_FORM(x)          #x 
#define BITOP_ADDR(x)          "m" (*(volatile long *) (x))
#define __ASM_SEL(a,b)          __ASM_FORM(b)
#define __ASM_SIZE(inst, ...)   __ASM_SEL(inst##l##__VA_ARGS__, inst##q##__VA_ARGS__)

__always_inline void linux_set_bit(long nr, volatile unsigned long *addr)
{
  asm volatile(__ASM_SIZE(bts) " %1,%0" : : ADDR, "Ir" (nr) : "memory");
}

my_bitops.c

#define SETBIT(_value, _bitIndex)   _value |= (1ul<<(_bitIndex))
__always_inline void mine_set_bit(long nr, volatile unsigned long *addr)
{
    SETBIT(*addr,nr)
}

main.c

#define ARRAY_SIZE  10000000
static unsigned long num_array[ARRAY_SIZE];
unsigned long int num = 0x0F00000F00000000;
for (int i = 0; i < ARRAY_SIZE; i++)
    num_array[i] = num;

clock_t start = clock();
for (unsigned long int i = 0 ; i < ARRAY_SIZE; i++)
    for (unsigned long int j = 0; j < sizeof(unsigned long int) * 8; j++)
         // linux_set_bit(j, &num_array[i]);
         // mine_set_bit(j, &num_array[i]);
clock_t end = clock();

Linux 耗时：1375991 us
我的时间：912256 us
CPU：英特尔（R）酷睿（TM）i7-7700K CPU @ 4.20GHz

用-O2生成的汇编代码是：

            26 [1]                 linux_set_bit(j, &num_array[i]);
    0x4005c0  <+   90>        48 8b 45 d0                    mov    -0x30(%rbp),%rax
    0x4005c4  <+   94>        48 c1 e0 03                    shl    [=14=]x3,%rax
    0x4005c8  <+   98>        48 8d 90 60 10 60 00           lea    0x601060(%rax),%rdx
    0x4005cf  <+  105>        48 8b 45 d8                    mov    -0x28(%rbp),%rax
    0x4005d3  <+  109>        48 89 d6                       mov    %rdx,%rsi
    0x4005d6  <+  112>        48 89 c7                       mov    %rax,%rdi
    0x4005d9  <+  115>        e8 69 00 00 00                 callq  0x400647 <linux_set_bit>

        71 [1]    asm volatile(__ASM_SIZE(bts) " %1,%0" : : ADDR, "Ir" (nr) : "memory");
0x400653  <+   12>        48 8b 45 f0  mov    -0x10(%rbp),%rax
0x400657  <+   16>        48 8b 55 f8  mov    -0x8(%rbp),%rdx
0x40065b  <+   20>        48 0f ab 10  bts    %rdx,(%rax)

        19 [1]      SETBIT(*addr,nr);
0x400653  <+   12>        48 8b 45 f0     mov    -0x10(%rbp),%rax
0x400657  <+   16>        48 8b 00        mov    (%rax),%rax
0x40065a  <+   19>        48 8b 55 f8     mov    -0x8(%rbp),%rdx
0x40065e  <+   23>        be 01 00 00 00  mov    [=14=]x1,%esi
0x400663  <+   28>        89 d1           mov    %edx,%ecx
0x400665  <+   30>        d3 e6           shl    %cl,%esi
0x400667  <+   32>        89 f2           mov    %esi,%edx
0x400669  <+   34>        89 d2           mov    %edx,%edx
0x40066b  <+   36>        48 09 c2        or     %rax,%rdx
0x40066e  <+   39>        48 8b 45 f0     mov    -0x10(%rbp),%rax
0x400672  <+   43>        48 89 10        mov    %rdx,(%rax)

我哪里错了？或者Linux运行缓慢？

Answer 1

主要区别在于您的代码无法处理大于 unsigned long 中的位数的“位数”，而 Linux 的版本可以。由于这种差异，您已经编写了一个适用于您的版本限制的循环，当这些限制不存在时，这并不理想，并且对于 Linux 的版本也不理想。

具体；对于 Linux 的版本，你 could/should 这样做：

for (unsigned long int i = 0 ; i < ARRAY_SIZE * sizeof(unsigned long int) * 8; i++) {
    linux_set_bit(i, num_array);
}

通过删除整个内部循环开销，加上找到指向数组元素的指针所需的计算（&num_array[i] 部分），它会明显更快（并且可能比你的更快).

Answer 2

是的，bts %reg, (mem)很慢（https://uops.info）； IDK 为什么 Linux 强制形成而不使用 lock 前缀。可能操作需要是原子的。在同一个内核上中断，用一条指令完成。

如果不是，用多条指令模拟它来计算包含你想要的位的字节或双字的地址会更快：How can memory destination BTS be significantly slower than load / BTS reg,reg / store?

（不过，bts imm, (mem) 还不错，所以你可以使用 __builtin_constant_p(bitpos) 并使用 memory-destination bts。）

正如@Brendan 指出的那样，您的版本仅适用于 bitpos < sizeof(unsigned long) * CHAR_BIT，即在第一个 qword 内。

我不知道为什么 Linux 使用 volatile 指针强制内存目标 bts。据推测，除了性能之外还有某种原因。否则，是的，这是一个错过的优化。

为什么 bitops in linux 内核性能比我的慢？

Why bitops in linux kernel performance in slower than mine?

c

linux

performance

assembly

x86-64