如何在每次迭代中交替扫描 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 创建位掩码的后续行动）

更新

我想知道是否有潜在的解决方案可以通过将两个比特流的块加载到寄存器（在我的例子中是 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]|...| 并单独处理连接

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

Answer 1

这个循环很难优化。主要问题是循环的每次迭代都依赖于前一次循环，甚至循环中的指令也是依赖的。这创建了一个长的几乎顺序的指令链来执行。结果，处理器无法有效地执行此操作。此外，此链中的某些指令具有相当高的延迟：tzcnt 在 Intel 处理器上具有 3 个周期的延迟，L1 load/store 具有 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 并且分支预测可以假设循环将继续，所以它只是miss-predict 最后一个条件跳转。在 Intel 处理器上，关键路径由 1 个周期延迟 inc、1 个周期延迟 shr、3 个周期延迟 tzcnt 组成，每轮 5 个周期（1 轮 = 初始循环的 1 次迭代）。在 AMD Zen-like 处理器上，它是 1+1+2=4 个周期，这非常好。进一步优化这一点似乎非常具有挑战性。

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

Answer 2

这是另一种方式，未经测试。互联网上的人们都建议不要使用 goto，但有时，例如您的用例，该功能确实有帮助。

// Grab 2 more of these masks, or if you don't have any, return false
bool loadMasks( uint32_t& mask1, uint32_t& mask2 );
// Consume the found value
void consumeIndex( size_t index );

void processMasks()
{
    size_t sourceOffset = 0;
    uint32_t mask0, mask1;
    // Skip initial zeros
    while( true )
    {
        if( !loadMasks( mask0, mask1 ) )
            return;
        if( 0 != ( mask0 | mask1 ) )
            break;
        sourceOffset += 32;
    }

    constexpr uint32_t minusOne = ~(uint32_t)0;
    uint32_t idx;

    // Figure out the initial state, and jump
    if( _tzcnt_u32( mask0 ) > _tzcnt_u32( mask1 ) )
        goto testMask1;

    // Main loop below
testMask0:
    idx = _tzcnt_u32( mask0 );
    if( idx >= 32 )
    {
        sourceOffset += 32;
        if( !loadMasks( mask0, mask1 ) )
            return;
        goto testMask0;
    }
    consumeIndex( sourceOffset + idx );
    mask1 &= minusOne << ( idx + 1 );

testMask1:
    idx = _tzcnt_u32( mask1 );
    if( idx >= 32 )
    {
        sourceOffset += 32;
        if( !loadMasks( mask0, mask1 ) )
            return;
        goto testMask1;
    }
    consumeIndex( sourceOffset + idx );
    mask0 &= minusOne << ( idx + 1 );
    goto testMask0;
}

如何在每次迭代中交替扫描 2 位掩码

How to efficiently scan 2 bit masks alternating each iteration

c++

performance

optimization

bit-manipulation

x86-64