c++ - 如何在 Sandy Bridge 上的一系列整数中快速将位计数到单独的 bin 中？

Question

这个问题在这里已经有了答案:

Count each bit-position separately over many 64-bit bitmasks, with AVX but not AVX2 (5 个回答)

关闭 3年前.

更新:请阅读代码，这不是计算一个整数中的位数

是否可以通过一些聪明的汇编程序来提高以下代码的性能？

uint bit_counter[64];

void Count(uint64 bits) {
  bit_counter[0] += (bits >> 0) & 1;
  bit_counter[1] += (bits >> 1) & 1;
  // ..
  bit_counter[63] += (bits >> 63) & 1;
}

Count 在我算法的最内层循环中。

更新:架构:x86-64、Sandy Bridge，因此可以使用 SSE4.2、AVX1 和旧技术，但不能使用 AVX2 或 BMI1/2。

bits 变量具有几乎随机的位(接近半零和半一)

Answer 1

您可以尝试使用 SSE，每次迭代增加 4 个元素。

警告:后面有未经测试的代码...

#include <stdint.h>
#include <emmintrin.h>

uint32_t bit_counter[64] __attribute__ ((aligned(16)));
                     // make sure bit_counter array is 16 byte aligned for SSE

void Count_SSE(uint64 bits)
{
    const __m128i inc_table[16] = {
        _mm_set_epi32(0, 0, 0, 0),
        _mm_set_epi32(0, 0, 0, 1),
        _mm_set_epi32(0, 0, 1, 0),
        _mm_set_epi32(0, 0, 1, 1),
        _mm_set_epi32(0, 1, 0, 0),
        _mm_set_epi32(0, 1, 0, 1),
        _mm_set_epi32(0, 1, 1, 0),
        _mm_set_epi32(0, 1, 1, 1),
        _mm_set_epi32(1, 0, 0, 0),
        _mm_set_epi32(1, 0, 0, 1),
        _mm_set_epi32(1, 0, 1, 0),
        _mm_set_epi32(1, 0, 1, 1),
        _mm_set_epi32(1, 1, 0, 0),
        _mm_set_epi32(1, 1, 0, 1),
        _mm_set_epi32(1, 1, 1, 0),
        _mm_set_epi32(1, 1, 1, 1)
    };

    for (int i = 0; i < 64; i += 4)
    {
        __m128i vbit_counter = _mm_load_si128(&bit_counter[i]);
                                          // load 4 ints from bit_counter
        int index = (bits >> i) & 15;     // get next 4 bits
        __m128i vinc = inc_table[index];  // look up 4 increments from LUT
        vbit_counter = _mm_add_epi32(vbit_counter, vinc);
                                          // increment 4 elements of bit_counter
        _mm_store_si128(&bit_counter[i], vbit_counter);
    }                                     // store 4 updated ints
}

它是如何工作的:基本上我们在这里所做的只是对原始循环进行矢量化处理，以便每次循环迭代处理 4 位而不是 1。所以我们现在有 16 次循环迭代而不是 64 次。对于每次迭代，我们从bits，然后将它们用作 LUT 的索引，其中包含当前 4 位的 4 个增量的所有可能组合。然后我们将这 4 个增量添加到 bit_counter 的当前 4 个元素中。

加载、存储和添加的数量减少了 4 倍，但这将在某种程度上被 LUT 加载和其他内务处理所抵消。不过，您可能仍会看到 2 倍的速度提升。如果您决定尝试一下，我很想知道结果。