13

我正在寻找对 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:
4

4 回答 4

5

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

查看Stanford bit-twiddling hacks 的变体 斯坦​​福版本在我看来是最好的版本。它看起来很容易编码为 x86 asm。

这些都不使用分支指令。

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

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

于 2010-09-13T01:39:38.710 回答
2

我概述了我为下面的大缓冲区的人口计数/汉明权重找到的最佳 C/汇编函数。

最快的汇编函数是ssse3_popcount3，描述here。它需要SSSE3，可用于 Intel Core 2 及更高版本，以及 2011 年推出的 AMD 芯片组。它使用SIMD指令以 16 字节块的形式弹出计数，并一次展开 4 个循环迭代。

最快的 C 函数是popcount_24words，描述here。它使用位切片算法。值得注意的是，我发现clang实际上可以生成适当的向量汇编指令，这带来了令人印象深刻的性能提升。除此之外，该算法仍然非常快。

于 2011-02-21T14:14:44.957 回答
1

我建议实现Hacker's Delight中优化的 32 位 popcnt 例程之一，但对 SSE 向量中的 4 x 32 位整数元素执行此操作。然后，您可以每次迭代处理 128 位，与优化的 32 位标量例程相比，这应该为您提供大约 4 倍的吞吐量。

于 2010-09-12T17:02:04.383 回答