c - 内存操作 : set every n-th bit (C/C++) in modern CPUs/GPUs

Question

据我所知，“现代”CPU 有相当令人印象深刻的例程来处理二进制数据，例如通过相同的操作流式传输许多数据。

临时我找不到一个库来使用那些 CPU 或 GPU 硬件制作简单的指令(在 GB 内存中设置每 5 位)，只是经典的 | << &技巧。

但是设置每第 5 位或第 721 位必须与在宽度为 5 或宽度 721 的黑白图片中绘制垂直黑线相同，我希望有一种快速的方法。

所以我的问题是:是否有任何提示如何在主流 x86_64 Intel/AMD CPU 或 GPU 上以快速有效的方式玩位？开源将是一个附加条件。

Answer 1

首先，对大块内存执行此操作会因缓存未命中而成为瓶颈。当前的 CPU 每次加载/存储可以执行相当多的指令，并且仍然会最大化内存带宽。如果我们谈论的是已经在 L1 缓存中的几 k 内存，这个问题就更有趣了。

如果您每隔 721 位设置一次， vector 的东西就帮不了您了。您的步幅为 90.125 字节，甚至比 AVX512 vector 还大。所以最佳解决方案是在适当的地址做单字节OR。编写循环以跟踪字节内的位位置和字节位置非常重要。如果它是一个编译时常量步幅，按 8 展开会很容易。 (每第 8 个 OR 额外增加一个字节。)

; pointer in rdi
; loop counter in ecx
.loop:
    or byte ptr [rdi+90*0],  1<<0
    or byte ptr [rdi+90*1],  1<<1
    or byte ptr [rdi+90*2],  1<<2
    or byte ptr [rdi+90*3],  1<<3
    or byte ptr [rdi+90*4],  1<<4
    or byte ptr [rdi+90*5],  1<<5
    or byte ptr [rdi+90*6],  1<<6
    or byte ptr [rdi+90*7],  1<<7
    add rdi, 90*8 + 1
    sub ecx, 8
    jg .loop
    ; handle the last up to 7 iterations

对于不是编译时常量的步长，您可以在执行 ptr += stride/8 + carry 时将 8 位寄存器循环 stride % 8 >。实际上，通过寄存器计数循环比通常的 ALU 操作(在最近的 Intel 上)慢一点，但可变计数移位也是如此。

; ecx = unsigned int stride.  rdi=char *dest
mov  ebx, ecx
and  ecx, 7    ; ecx = stride%8
shr  ebx, 3    ; ebx = stride/8

mov  al, 1
.loop:
    or    byte ptr [rdi], al
    rol   al, cl
    add   rdi, rbx
    ;  efficiently figure out when we need to add an extra 1 to rdi
    ; lost interest at this point, feel free to edit or post another answer finishing this code.
    dec   edx
    jg   .loop

我正在想办法增加字节内位的位置，它在回绕时设置进位标志，这样你就可以 adc 来做 ptr+= stride +携带。或者只是得到一个 0 或 1 来添加。

较短的步幅

如果您的位步幅等于 128b，那么事情就微不足道了。只需读取/修改并使用常量掩码存储到 POR。

如果您的步幅较小，那么事情就会变得有趣。 vector 寄存器没有按位循环指令。在 xmm 寄存器中移动多个设置位可能有一些聪明的方法。