使用Core2CPU (SSSE3)的大缓冲区的位波普数

Question

我正在寻找最快的方法来计算512或更多字节的大缓冲区。我可以保证任何必需的对齐，缓冲区大小总是2的幂。缓冲区对应于块分配，所以通常比特要么全部设置，没有设置，或者大部分设置更倾向于缓冲区的“左”，偶尔有洞。

我考虑过的一些解决方案是：

• GCC的__builtin_popcount
• popcount_24words
• 数位集合，的方式

我对最快的解决方案感兴趣，它必须工作在32位x86芯片组属于core2或更新的。SSE和SIMD是非常有趣的。我将在以下四核CPU上进行测试：

matt@stanley:~/anacrolix/public/stackoverflow$ cat /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz
stepping        : 11
cpu MHz         : 1600.000
cache size      : 4096 KB
physical id     : 0
siblings        : 4
core id         : 0
cpu cores       : 4
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 10
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm tpr_shadow vnmi flexpriority
bogomips        : 4800.21
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Answer 1

下面我概述了我为大型缓冲区的种群数/汉明体重找到的最好的C/汇编函数。

最快的组装函数是ssse3_popcount3，描述为这里。它需要SSSE3，可在英特尔核心2和更高版本，和AMD芯片组在2011年到达。它使用SIMD指令以16字节块进行波普计数，并一次取消4次循环迭代。

最快的C函数是popcount_24words，描述为这里。它采用了位切片算法。注意，我发现嘎吱声实际上可以生成适当的矢量组装指令，这给性能带来了令人印象深刻的提高。撇开这一点不说，算法仍然非常快。

Answer 2

请参阅AMD软件优化指南中的32位版本，第195页为一个实现。这将直接为x86提供程序集代码。

看看斯坦福比特绕行黑客的变体，斯坦福版本对我来说是最好的版本。作为x86 asm的代码看起来非常容易。

这两种方法都不使用分支指令。

这些可以概括为64位版本。

对于32或64位版本，您可以考虑执行SIMD版本。SSE2将同时执行4个双字或两个四字(任意一种方式，128位).您要做的是在每个可用的2或4个寄存器中实现32位或64位的波普计数。当您完成时，您将在XMM寄存器中得到2到4组popcounts；最后一步是存储并将这些popcounts添加到一起，以获得最终答案。我猜，我希望你做的稍微好一些，做4个并行32位波普计数，而不是2个并行64位波普计数，因为后者可能在每次迭代中需要1到2个额外的指令，而且很容易将4，32位值相加到一起。

Answer 3

如果你有爸爸：

http://kent-vandervelden.blogspot.com/2009/10/counting-bits-population-count-and.html

ATA.htm