c++ - 检查 uint8_t[8] 是否包含任何非 0 并使用一次内存负载访问非零插槽

Question

基本上我有一个带有定义的结构

#define BATCH_SIZE 8
#define BATCH_SIZE_LOG 3
//#define BATCH_MASK 0x7070707070707070

// for the sake of understanding the ASM turn this into a no-op
#define BATCH_MASK (~(0UL))
struct batcher {
    uint8_t indexes[8];
    uint64_t vals[8 * BATCH_SIZE];

    uint32_t __attribute__((noinline))
    push(const uint64_t i, const uint64_t v) {
        if(__builtin_expect(indexes[i] < (BATCH_SIZE - 1), 1)) {
            vals[8 * i + indexes[i]++] = v; 
            return 0;  
        }
        return 1;
    }

    uint32_t __attribute__((noinline))
    claim(const uint64_t i) {
        if(__builtin_expect(indexes[i] == (BATCH_SIZE - 1), 1)) {
            indexes[i] = 8;
            return 0;
        }
        return 1;
    }

    uint32_t 
    can_pop() const {
        if(*((uint64_t *)(&indexes[0])) & BATCH_MASK) {
            return 1;
        }
        return 0;
    }

    uint64_t __attribute__((noinline))
    pop() {
        if(__builtin_expect(can_pop(), 1)) {
            const uint32_t idx = _tzcnt_u64(*((uint64_t *)(&indexes[0])) & BATCH_MASK) >> BATCH_SIZE;
            return vals[8 * idx + --indexes[idx]]; 
        }
        return 0;
    }
};

我很好奇的是 pop 是否可以仅通过 indexes 的 1 次内存加载来实现(所以总共 2 个，1 个来自 indexes和 1 来自 vals)

第一个内存加载是将所有索引解释为uint64_t，以便我可以检查它是否为非0，如果是，则使用其中一个索引。

我一直在查看汇编输出here

其中实现了 pop

batcher::pop():
        movq    (%rdi), %rax  // first load from indexes
        testq   %rax, %rax
        jne     .L11
        ret
.L11:
        xorl    %edx, %edx
        movzbl  (%rdi,%rdx), %eax // second load from indexes
        decl    %eax
        movb    %al, (%rdi,%rdx)
        movzbl  %al, %eax
        movq    8(%rdi,%rax,8), %rax
        ret

编译器实现这一点的方式是从 %(rdi) 到 %rax 来解释为 uint64_t (测试是否存在任何非 0 索引)，如果条件通过加载计算出的 uint8_t 索引，则进行第二次加载。

我想知道是否有一种方法可以在程序集中实现 pop (我将要做的事情)而无需两次加载。我知道我可以通过对第一次加载的结果进行移位/屏蔽来完成相同的逻辑。我特别想知道的是，是否有一种方法可以对第一次加载产生的 uint64_t 进行索引，就好像它在 uint8_t[8] 数组中一样。

我的猜测是，这不可能是因为寄存器没有内存地址，所以能够做到这一点并不完全有意义，但我可能会丢失一些专门用于隔离中的字节的指令>uint64_t 或通过某种方式重构 pop 的程序集实现来实现此功能。

注意:我仅限于 Intel Skylake 上可用的指令集。

如果有人有任何想法，我将不胜感激。谢谢!

Answer 1

可能是 tzcnt，将计数向下舍入为 8 位的倍数，然后右移(使用 BMI2 shr​​x，因此它是单个 uop)。然后非零字节位于寄存器的底部，您可以在其中 movzbl 将其零扩展到任何其他寄存器 ( not the same one, that would defeat mov-elimination )

    tzcnt  %rax, %rcx          # input in RAX
    and    $-8, %ecx           # 0xff...f8
    shrx   %rcx, %rax, %rdx    # rdx = rax >> cl
    movzbl %dl,  %eax          # zero latency between separate registers

(如果可以全零，如果您需要检测这种情况，请test/jz，或者只是让移位发生。qword 移位 64 会使值保持不变，因此结果将是0。)

您可以使用_tzcnt_u64等内在函数来做到这一点；为此使用内联汇编没有明显的好处。您可以使用 GNU C 执行未对齐的严格别名安全 qword 加载
typedef uint64_t aliasing_u64 __attribute__((aligned(1), may_alias))。

---

只有 8 个字节，对 movemask 结果上的 pcmpeqb/pmovmskb/tzcnt 的常用 SIMD 进行查找就显得有些过分了字节位置。 (然后整数 movzbl 使用字节偏移量从内存加载该字节)。