如何有效地扫描每次迭代交替的 2 位掩码

Question

给定 2 个位掩码，应交替访问（0,1,0,1...）。我尝试获得运行时高效的解决方案，但找不到比以下示例更好的方法。

uint32_t mask[2] { ... };
uint8_t mask_index = 0;
uint32_t f = _tzcnt_u32(mask[mask_index]);
while (f < 32) {
    // element adding to result vector removed, since not relevant for question itself
    mask[0] >>= f + 1;
    mask[1] >>= f + 1;
    mask_index ^= 1;
    f = _tzcnt_u32(mask[mask_index]);
}

ASM 输出（MSVC、x64）似乎被放大了很多。

inc         r9  
add         r9,rcx  
mov         eax,esi  
mov         qword ptr [rdi+rax*8],r9  
inc         esi  
lea         rax,[rcx+1]  
shrx        r11d,r11d,eax  
mov         dword ptr [rbp],r11d  
shrx        r8d,r8d,eax  
mov         dword ptr [rbp+4],r8d  
xor         r10b,1  
movsx       rax,r10b  
tzcnt       ecx,dword ptr [rbp+rax*4]  
mov         ecx,ecx  
cmp         rcx,20h  
jb          main+240h (07FF632862FD0h)  
cmp         r9,20h  
jb          main+230h (07FF632862FC0h) 

有人有建议吗？

（这是 使用 SIMD 解决循环数据依赖性的后续内容 - 使用 SIMD 在 sgn 值的 int8_t 数组中查找 -1 和 +1 之间的转换来创建位掩码）

更新

我想知道是否有一个潜在的解决方案可以通过将两个位流的块加载到寄存器（在我的例子中是 AVX2）来利用 SIMD，如下所示：

|m0[0]|m1[0]|m0[1]|m1[1]|m0[2]|m1[2]|m0[n+1]|m1[n+1]|

或者

1 每个流注册一个块

|m0[0]|m0[1]|m0[2]|m0[n+1]|

|m1[0]|m1[1]|m1[2]|m1[n+1]|

或者将流分割成相同大小的块，并同时处理寄存器中容纳的尽可能多的通道。假设我们有 256*10 个元素，最终可能会进行 10 次迭代，如下所示： |m0[0]|m0[256]|m0[512]|...| |m1[0]|m1[256]|m1[512]|...| 并单独处理连接

不确定这是否是一种在每个周期实现更多迭代并限制水平位扫描、移位/清除操作和避免分支的需要的方法。

Answer 1

优化这个循环是相当困难的。主要问题是循环的每次迭代都依赖于前一次迭代，甚至循环中的指令也是依赖的。这会创建一个要执行的长的、几乎连续的指令链。结果，处理器无法有效地执行此操作。此外，该链中的某些指令具有相当高的延迟：tzcnt在 Intel 处理器上有 3 个周期的延迟，L1 加载/存储有 3 个周期的延迟。

一种解决方案是直接使用寄存器而不是具有间接访问的数组，以减少链的长度，尤其是具有最高延迟的指令。这可以通过展开循环两次并将问题分成两个不同的问题来完成：

uint32_t m0 = mask[0];
uint32_t m1 = mask[1];
uint8_t mask_index = 0;

if(mask_index == 0) {
    uint32_t f = _tzcnt_u32(m0);

    while (f < 32) {
        m1 >>= f + 1;
        m0 >>= f + 1;
        f = _tzcnt_u32(m1);

        if(f >= 32)
            break;

        m0 >>= f + 1;
        m1 >>= f + 1;
        f = _tzcnt_u32(m0);
    }
}
else {
    uint32_t f = _tzcnt_u32(m1);

    while (f < 32) {
        m0 >>= f + 1;
        m1 >>= f + 1;
        f = _tzcnt_u32(m1);

        if(f >= 32)
            break;

        m0 >>= f + 1;
        m1 >>= f + 1;
        f = _tzcnt_u32(m0);
    }
}

// If mask is needed, m0 and m1 need to be stored back in mask.

这应该会快一点，特别是因为关键路径更小，而且还因为两个班次可以并行执行。这是生成的汇编代码：

$loop:
        inc     ecx
        shr     edx, cl
        shr     eax, cl
        tzcnt   ecx, edx

        cmp     ecx, 32
        jae     SHORT $end_loop

        inc     ecx
        shr     eax, cl
        shr     edx, cl
        tzcnt   ecx, eax

        cmp     ecx, 32
        jb      SHORT $loop

请注意，现代 x86 处理器可以融合指令cmp+jae和cmp+ jb，并且分支预测可以假设循环将继续，因此它只是错过了最后一个条件跳转。在 Intel 处理器上，关键路径由 1 周期延迟inc、 1 周期延迟shr、 3 周期延迟组成tzcnt，导致每轮 5 个周期（1 轮 = 初始循环的 1 次迭代）。在AMD Zen-like处理器上，它是1+1+2=4个周期，这非常好。进一步优化这一点似乎非常具有挑战性。

一种可能的优化是使用查找表，以便以更大的步长计算m0和的较低位m1。然而，查找表获取具有 3 个周期的延迟，在实践中可能会导致昂贵的缓存未命中，占用更多内存，并使代码明显更加复杂，因为尾随 0 位的数量可能相当大（例如 28 位）。因此，我不确定这是一个好主意，尽管它确实值得尝试。