您可以尝试使用 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 次。对于每次迭代,我们从 加载 4 位bits
,然后使用它们作为 LUT 的索引,其中包含当前 4 位的 4 个增量的所有可能组合。然后我们将这 4 个增量添加到 bit_counter 的当前 4 个元素中。
加载、存储和添加的数量减少了 4 倍,但这将在某种程度上被 LUT 加载和其他内务处理所抵消。不过,您可能仍会看到 2 倍的速度提升。如果您决定尝试一下,我很想知道结果。