大缓冲区的位弹出计数，采用 Core 2 CPU (SSSE3)
我正在寻找在 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:
I'm looking for the fastest way to popcount on large buffer of 512 or more bytes. I can guarantee any required alignment, and the buffer size is always a power of 2. The buffer corresponds to block allocations, so typically the bits are either all set, none set, or mostly set favoring the "left" of the buffer, with occasional holes.
Some solutions I've considered are:
I'm interested in the fastest solution, it must work on 32bit x86 chipset belonging to core2 or more recent. SSE and SIMD are of great interest. I'll be testing on the following quad core 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:
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
请参阅 AMD 软件优化指南第 195 页中的 32 位版本执行。
这会直接为您提供 x86 的汇编代码。
请参阅斯坦福位旋转黑客的变体
斯坦福大学的版本对我来说是最好的。
看起来很容易编写 x86 asm 代码。
这些都不使用分支指令。
这些可以推广到 64 位版本。
对于 32 位或 64 位版本，您可能会考虑使用 SIMD 版本。
SSE2 将执行 4 个双字或两个四字（无论哪种方式都是 128 位）
立刻。你想要做的是将 popcount 实现为 32
或 2 个或 4 个可用寄存器中的每个寄存器中的 64 位。
您最终会在 XMM 寄存器中得到 2 或 4 组 popcount
当你完成时；最后一步是存储并添加这些
一起popcount得到最终的答案。猜测，
我希望你做 4 个并行 32 会做得更好一些
位弹出计数而不是 2 个并行 64 位弹出计数，
因为后者可能需要 1 或 2 条额外的指令
在每次迭代中，很容易将 4、32 位值加在一起
结束。
See a 32 bit version in the AMD Software Optimization guide, page 195 for one implementation.
This gives you assembly code for an x86 directly.
See a variant at Stanford bit-twiddling hacks
The Stanford version looks like the best one to me.
It looks very easy to code as x86 asm.
Neither of these use branch instructions.
These can be generalized to 64 bit versions.
With the 32 or 64 bit versions, you might consider doing a SIMD version.
SSE2 will do 4 double-words or two quadwords (either way 128 bits)
at once. What you want to do is implement the popcount for 32
or 64 bits in each of the 2 or 4 registers available.
You'll end up with 2 or 4 sets of popcounts in the XMM registers
when you are done; final step is to store and add those
popcounts together to get the final answer. Guessing,
I'd expect you do so slightly better doing 4 parallel 32
bit popcounts rather than 2 parallel 64 bit popcounts,
as the latter is likely to take 1 or 2 additional instructions
in each iteration, and its easy to add 4, 32 bit values together
the end.
如果您有 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
If you had 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
我在下面概述了我为大型缓冲区的总体计数/汉明权重找到的最佳 C/汇编函数。
最快的汇编函数是
ssse3_popcount3，描述为此处。它需要 SSSE3，可在 Intel Core 2 及更高版本以及 2011 年推出的 AMD 芯片组上使用。 SIMD 指令以 16 字节块进行 popcount 并一次展开 4 个循环迭代。最快的 C 函数是
popcount_24words，描述为 此处。它使用位切片算法。值得注意的是，我发现 clang 实际上可以生成适当的向量汇编指令，这带来了令人印象深刻的性能提升。除此之外，该算法仍然非常快。I outline the best C/assembly functions I found for population count/Hamming weight of large buffers below.
The fastest assembly function is
ssse3_popcount3, described here. It requires SSSE3, available on Intel Core 2 and later, and AMD chipsets arriving in 2011. It uses SIMD instructions to popcount in 16 byte chunks and unrolls 4 loop iterations at a time.The fastest C function is
popcount_24words, described here. It uses the bit-slicing algorithm. Of note I found that clang could actually generate appropriate vector assembly instructions, which gave impressive performance increases. This aside, the algorithm is still extremely fast.我建议实现 Hacker's Delight 中优化的 32 位 popcnt 例程之一，但对 SSE 向量中的 4 x 32 位整数元素执行此操作。然后，您可以每次迭代处理 128 位，与优化的 32 位标量例程相比，这将为您提供大约 4 倍的吞吐量。
I would suggest implementing one of the optimised 32 bit popcnt routines from Hacker's Delight, but do it for 4 x 32 bit integer elements in an SSE vector. You can then process 128 bits per iteration, which should give you around 4x throughput compared to an optimised 32 bit scalar routine.