高效的按位求和计算

Question

有没有一种有效的方法来计算 uint8_t 个缓冲区的按位总和（假设缓冲区的数量 <= 255，这样我们就可以求和 uint8）？基本上我想知道在每个缓冲区的第 i 个位置设置了多少位。

例如：对于 2 个缓冲区

uint8 buf1[k] -> 0011 0001 ...
uint8 buf2[k] -> 0101 1000 ...
uint8 sum[k*8]-> 0 1 1 2 1 0 0 1...

是否有针对此类要求的任何 BLAS 或增强例程？

IMO 这是一个高度向量化的操作。

更新：以下是要求

for (auto&& buf: buffers){
  for (int i = 0; i < buf_len; i++){
    for (int b = 0; b < 8; ++b) {
      sum[i*8 + b] += (buf[i] >> b) & 1;
    }
  }
}

Answer 1

OP 原始代码的替代方法：

一次执行 8 次加法。使用查找 table 将 8 位扩展为 8 个字节，每个位对应一个字节 - 参见 ones[].

void sumit(uint8_t number_of_buf, uint8_t k, const uint8_t buf[number_of_buf][k]) {
  static const uint64_t ones[256] = { 0, 0x1, 0x100, 0x101, 0x10000, 0x10001, 
      /* 249 more pre-computed constants */ 0x0101010101010101};

  uint64_t sum[k];
  memset(sum, 0, sizeof sum):

  for (size_t buf_index = 0; buf_index < number_of_buf;  buf_index++) {
    for (size_t int i = 0; i < k; i++) {
      sum[i] += ones(buf[buf_index][i]);
    }
  }

  for (size_t int i = 0; i < k; i++) {
    for (size_t bit = 0; bit < 8;  bit++) {
      printf("%llu ", 0xFF & (sum[i] >> (8*bit)));
    }
  }
}

另见。

Answer 2

作为 chux 方法的修改，查找 table 可以替换为矢量移位和掩码。这是一个使用 GCC's vector extensions.

的示例

#include <stdint.h>
#include <stddef.h>

typedef uint8_t vec8x8 __attribute__((vector_size(8)));

void sumit(uint8_t number_of_buf,
           uint8_t k,
           const uint8_t buf[number_of_buf][k],
           vec8x8 * restrict sums) {
    static const vec8x8 shift = {0,1,2,3,4,5,6,7};

    for (size_t i = 0; i < k; i++) {
        sums[i] = (vec8x8){0};
        for (size_t buf_index = 0; buf_index < number_of_buf;  buf_index++) {
            sums[i] += (buf[buf_index][i] >> shift) & 1;
        }
    }
}

Try it on godbolt.

我交换了 chux 的回答中的循环，因为一次为一个缓冲区索引累加总和似乎更自然（然后总和可以在整个内部循环中缓存在寄存器中）。缓存性能可能会有所折衷，因为我们现在必须按列优先顺序读取二维 buf 的元素。

以ARM64为例，GCC 11.1编译内循环如下

// v1 = sums[i]
// v2 = {0,-1,-2,...,-7} (right shift is done as left shift with negative count)
// v3 = {1,1,1,1,1,1,1,1}
.L4:
        ld1r    {v0.8b}, [x1]         // replicate buf[buf_index][i] to all elements of v0
        add     x0, x0, 1             
        add     x1, x1, x20
        ushl    v0.8b, v0.8b, v2.8b   // shift
        and     v0.8b, v0.8b, v3.8b   // mask
        add     v1.8b, v1.8b, v0.8b   // accumulate
        cmp     x0, x19
        bne     .L4

我认为一次执行两个字节（因此将 i 上的循环展开 2 倍）并使用 128 位向量运算会更有效率。我把它留作练习 :)

我不是很清楚这最终会比查找 table 快还是慢。您可能必须在感兴趣的目标机器上对两者进行分析。

高效的按位求和计算

efficient bitwise sum calculation

c

c++

algorithm

blas

bitset