Mat*_*ner 12 c optimization x86 assembly hammingweight
我正在寻找在512或更多字节的大缓冲区上popcount的最快方法.我可以保证任何所需的对齐,缓冲区大小总是2的幂.缓冲区对应于块分配,因此通常位是全部设置,没有设置,或者大多数设置有利于缓冲区的"左",偶尔出洞.
我考虑过的一些解决方案是:
我对最快的解决方案感兴趣,它必须适用于属于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 软件优化指南，第 195 页中的 32 位版本。这直接为您提供了 x86 的汇编代码。
查看斯坦福 bit-twiddling hacks 的一个变体斯坦福版本对我来说是最好的。编码为 x86 asm 看起来很容易。
这些都不使用分支指令。
这些可以推广到 64 位版本。
对于 32 位或 64 位版本，您可能会考虑制作 SIMD 版本。SSE2 将一次执行 4 个双字或两个四字（128 位）。您想要做的是在可用的 2 或 4 个寄存器中的每一个中实现 32 位或 64 位的 popcount。完成后，您将在 XMM 寄存器中得到 2 或 4 组弹出计数；最后一步是将这些流行计数存储并添加在一起以获得最终答案。猜测，我希望你做 4 个并行的 32 位 popcounts 比 2 个并行的 64 位 popcounts 稍微好一点，因为后者在每次迭代中可能需要 1 或 2 个额外的指令，并且很容易添加 4、32 位值一起结束。
我在下面概述了我发现的用于大型缓冲区的总体计数/汉明权重的最佳 C/汇编函数。
最快的组装功能是此处ssse3_popcount3描述的。它需要SSSE3（可在 Intel Core 2 及更高版本以及 2011 年推出的 AMD 芯片组上使用）。它使用SIMD指令以 16 字节块进行 popcount 并一次展开 4 个循环迭代。
最快的 C 函数如下popcount_24words所述。它使用位切片算法。值得注意的是，我发现clang实际上可以生成适当的向量汇编指令，这带来了令人印象深刻的性能提升。除此之外，该算法仍然非常快。