具有Core 2 CPU(SSSE3)的大缓冲区的位popcount

我正在寻找在512或更多字节的大缓冲区上popcount的最快方法。 我可以保证任何所需的对齐,缓冲区大小始终是2的幂。缓冲区对应于块分配,因此通常位是全部设置,没有设置,或者大多数设置有利于缓冲区的“左”,偶尔出洞。

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

  • 海湾合作委员会的__builtin_popcount
  • Bitslice popcount_24words
  • 计算位数,Brian Kernighan的方式

我对最快的解决方案感兴趣,它必须适用于属于core2或更新版本的32位x86芯片组。 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: 

有关一种实现,请参阅AMD软件优化指南中的32位版本,第195页。 这为您直接提供了x86的汇编代码。

查看斯坦福大学的一个变种,让我看起来最好的一个版本。 它看起来很容易编码为x86 asm。

这些都不使用分支指令。

这些可以推广到64位版本。

对于32位或64位版本,您可以考虑使用SIMD版本。 SSE2将同时执行4个双字或两个四字(两路128位)。 您要做的是在可用的2个或4个寄存器中的每个寄存器中实现32或64位的popcount。 完成后,您将在XMM寄存器中最终获得2或4组popcounts; 最后一步是将这些popcounts存储并添加到一起以获得最终答案。 猜测,我希望你做4个并行32位popcounts而不是2个并行64位popcounts,因为后者可能在每次迭代中需要1或2个附加指令,并且它很容易添加4,32位价值观一起结束。

我概述了我发现的最佳C /汇编函数,用于下面的大缓冲区的人口数/汉明重量 。

最快的汇编函数是ssse3_popcount3 ,如下所述。 它需要SSSE3 (可在Intel Core 2及更高版本上使用)和AMD芯片组在2011年到货。它使用SIMD指令以16字节块的forms弹出,并一次展开4次循环迭代。

最快的C函数是popcount_24words ,如下所述。 它使用位切片算法。 值得注意的是,我发现clang实际上可以生成适当的向量汇编指令,从而使性能提升了不少。 除此之外,该算法仍然非常快。

我建议实现Hacker’s Delight中优化的32位popcnt例程之一,但是对于SSE向量中的4 x 32位整数元素。 然后,您可以每次迭代处理128位,与优化的32位标量例程相比,这可以提供大约4倍的吞吐量。