如何加快位测试

Question

我正在考虑如何在以下例程中加速位测试:

void histSubtractFromBits(uint64* cursor, uint16* hist){
    //traverse each bit of the 256-bit-long bitstring by splitting up into 4 bitsets
    std::bitset<64> a(*cursor);
    std::bitset<64> b(*(cursor+1));
    std::bitset<64> c(*(cursor+2));
    std::bitset<64> d(*(cursor+3));
    for(int bit = 0; bit < 64; bit++){
        hist[bit] -= a.test(bit);
    }
    for(int bit = 0; bit < 64; bit++){
        hist[bit+64] -= b.test(bit);
    }
    for(int bit = 0; bit < 64; bit++){
        hist[bit+128] -= c.test(bit);
    }
    for(int bit = 0; bit < 64; bit++){
        hist[bit+192] -= d.test(bit);
    }
}

实际的gcc实现对bit参数进行范围检查,然后使用位掩码对-s进行范围检查.我可以在没有位集和我自己的位移/屏蔽的情况下完成它,但我相当肯定不会产生任何显着的加速(告诉我,如果我错了,为什么).

我对x86-64程序集并不是很熟悉,但我知道有一点测试指令,而且我知道理论上可以用gcc进行内联汇编.

1)您认为为上述代码编写内联汇编模拟是否值得？

2)如果是,那么我将如何去做,即你能告诉我一些基本的入门代码/样本,指出我正确的方向吗？

Answer 1

据我所知,你基本上遍历每一位.因此,我想象每次只需提供良好的性能,只需移动和屏蔽LSB.就像是:

uint64_t a = *cursor;
for(int bit = 0; a != 0; bit++, a >>= 1) {
    hist[bit] -= (a & 1);
}

或者,如果您只希望设置很少的位并且对gcc特定的东西感到满意,那么您可以使用 __builtin_ffsll

uint64_t a = *cursor;
int next;
for(int bit = 0; (next = __builtin_ffsll(a)) != 0; ) {
    bit += next;
    hist[bit - 1] -= 1;
    a >>= next;
}

这个想法应该没问题,但对实际代码没有保证:)

更新:使用矢量扩展的代码:

typedef short v8hi __attribute__ ((vector_size (16)));

static v8hi table[256];

void histSubtractFromBits(uint64_t* cursor, uint16_t* hist)
{
    uint8_t* cursor_tmp = (uint8_t*)cursor;
    v8hi* hist_tmp = (v8hi*)hist;
    for(int i = 0; i < 32; i++, cursor_tmp++, hist_tmp++)
    {
        *hist_tmp -= table[*cursor_tmp];
    }
}

void setup_table()
{
    for(int i = 0; i < 256; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            table[i][j] = (i >> j) & 1;
        }
    }
}

如果可用,这将被编译为SSE指令,例如我得到:

        leaq    32(%rdi), %rdx
        .p2align 4,,10
        .p2align 3
.L2:
        movzbl  (%rdi), %eax
        addq    $1, %rdi
        movdqa  (%rsi), %xmm0
        salq    $4, %rax
        psubw   table(%rax), %xmm0
        movdqa  %xmm0, (%rsi)
        addq    $16, %rsi
        cmpq    %rdx, %rdi
        jne     .L2

当然,这种方法依赖于缓存中的表.