如何在Sandy Bridge的一系列整数中快速将位数计入单独的箱中？

Question

更新:请阅读代码,它不是关于计算一个int中的位

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

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
}

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

加载和存储和添加的数量减少了4倍,但这将由LUT负载和其他内务处理稍微抵消.你可能仍然看到加速2倍.如果您决定尝试,我有兴趣知道结果.

Answer 2

也许你可以一次做8个,将8位间隔8个并保持8个uint64的计数.但是,每个单独的计数器只有1个字节,因此count在你必须解压缩那些uint64之前,你只能累积255个调用.

Answer 3

看看位摆弄黑客

• 计数位设置
  • 计算位数，天真的方式
  • 计算查找表设置的位数
  • 计算位设置，Brian Kernighan 的方式
  • 使用 64 位指令对 12、24 或 32 位字中设置的位进行计数
  • 并行计算位集
  • 计算从最高有效位到给定位置的位集（排名）
  • 选择具有给定计数（排名）的位位置（从最高有效位开始）

编辑至于“位位置桶积累”（bit_counter[]），我有一种感觉，这可能是 valarrays + 掩码的一个好例子。不过，这需要相当多的编码+测试+分析。如果您真的感兴趣，请告诉我。

如今，您可以使用绑定元组（TR1、boost 或 C++11）非常接近 valarray 行为；我有一种感觉，它会变得更容易阅读和更慢的编译。