使用Core 2 CPU（SSSE3）计算大缓冲区的比特流行计数

Question

使用Core 2 CPU（SSSE3）计算大缓冲区的比特流行计数

13

我正在寻找在512字节或更多字节的大缓冲区上进行popcount的最快方法。我可以保证任何所需的对齐方式，并且缓冲区大小始终是2的幂。缓冲区对应于块分配，因此通常位要么全部设置，要么不设置，或者大部分设置偏向于缓冲区的“左侧”，偶尔有空洞。

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

- GCC的__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:

- Matt Joiner

1

@Matt，你可以在这里找到它的提及 https://secure.wikimedia.org/wikipedia/en/wiki/SSE4 - Jens Gustedt

@Jens Gustedt：我知道这个指令（尽管我的CPU不支持它），但不知道在GCC上的使用方法。 - Matt Joiner

@Matt：如果你使用gcc，我不会担心用汇编实现这个功能的问题。我信任这些人，使用__builtin_popcountll并使用-march=native进行编译即可。但是我在我的机器上也没有该指令，因此我无法确认这是否做到了正确的事情：在我的机器上，这仍然导致函数调用。 - Jens Gustedt

1

为什么？“popcount”的第一个谷歌搜索结果似乎是由Bart Massey（XCB的作者）最近发布的一个页面，记录了他寻找最佳popcount算法的过程，其中包括他尝试的算法、基准测试代码和结果。 - llasram

@llasram：一些例子：24words链接我的问题能够在96字节块上操作而不需要单个分支。加速单词操作很好，但对于大数组，仍然存在隐式边界检查等O(n)成本。另一个是展开，针对大缓冲区优化的算法可以以巨大的效果使用它。通常，组合非平凡指令序列可以比单独操作单词更快地执行popcount（或其他任务）。我发现的另一个算法设法使用MULT指令来削减周期。 - Matt Joiner

显示剩余8条评论

4个回答

2

我总结了最好的C/汇编函数，用于对大缓冲区进行种群计数/海明权重。最快的汇编函数是ssse3_popcount3，在这里有描述。它需要SSSE3，可在Intel Core 2及更高版本和2011年后到达的AMD芯片组上使用。它使用SIMD指令以16字节块进行popcount，并一次展开4个循环迭代。

最快的 C 函数是 popcount_24words，其使用了位切片算法，具体描述请参见这里。值得注意的是，我发现 clang 实际上可以生成适当的向量汇编指令，从而使性能显著提高。除此之外，该算法仍然非常快速。

- Matt Joiner

1

请注意，SSE4具有POPCNT指令。 - Paul R

@Paul R：是的，这已经被提到了。我在问题中限制了解决方案为SSSE3或更低版本，同时也发现POPCNT虽然非常快速和方便，但并不比一些矢量化解决方案更快。 - Matt Joiner

3

这是错误的。POPCNT是最快的方法。此处有基准测试和详细解释。 - dan

2

这个答案可以通过展示实际的代码来大大改进，而不是依赖外部网站。因为现在的情况是，答案可能会因为您无法掌控的资源变化而失效。 - Toby Speight

1

@dan：在现代英特尔（Haswell及更高版本）上，AVX2比标量popcnt更快。但只有256位向量：AVX1 / SSSE3不会更快，如果我没记错的话。Ryzen很有趣；它每个时钟周期有4个64位的popcnt，所以它可能在标量方面表现最佳。AVX512 vpternlogd可以实现更多优化：使用按位AND和popcount而不是实际int或float乘法的大型（0,1）矩阵乘法？，具体来说，https://github.com/WojciechMula/sse-popcount/blob/master/popcnt-avx512-harley-seal.cpp对于16x ZMM向量（16x 512位），执行30x vpternlogd + 1个向量popcnt。 - Peter Cordes

2

如果您有 popcnt：

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

http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011/compiler_c/intref_cls/common/intref_sse42_ATA.htm

- Anycorn

1

我建议您实现Hacker's Delight中优化的32位popcnt例程之一，但要针对SSE向量中的4个32位整数元素进行操作。然后，您可以每次迭代处理128位，这应该比优化的32位标量例程快4倍左右。

- Paul R

我不知道你所提到的例程中它是如何实现的，但是可以确定的是SSE4.1 POPCNT指令只能在通用寄存器上运行，而不能在XMM寄存器上运行。 - PhiS

@PhiS：确实 - 我不建议使用SSE 4.1 POPCNT - 在Hacker's Delight中有一些高效的C语言32位popcnt例程，可以作为SSE 4 x 32位popcnt实现的基础。然后，您可以迭代处理您的数据块，每次128位，生成4个32位部分人口统计数据，最后将它们相加以获得总人口统计数据。 - Paul R

实际上，我发现一些最好的解决方案使用向量操作来进行128位计数。 - Matt Joiner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

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

请参阅斯坦福位操作技巧的变体。在我看来，斯坦福版本似乎是最好的选择。它看起来非常容易作为x86汇编代码编写。

这两个版本都没有使用分支指令。

这些可以推广到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位值相加在最后。