用于大型缓冲区的位弹出窗口，带有Core 2 CPU（SSSE3）

 

我正在寻找在512或更多字节的大缓冲区上弹出最快的方式。 我可以保证任何需要的对齐，并且缓冲区大小始终是2的幂。缓冲区对应于块分配，因此通常这些比特是全部设置的，没有设置或者主要设置为偏向缓冲区的“左边”，偶尔出现漏洞。

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

  • GCC的__builtin_popcount
  • Bitslice popcount_24words
  • 计数比特集，布赖恩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软件优化指南（第195页）中的32位版本以获取一个实现。 这可以直接为您提供x86的汇编代码。

    在斯坦福看到一个变种 - 颠倒黑客斯坦福版本看起来对我来说是最好的一个。 它看起来很容易编码为x86 asm。

    这些都不使用分支指令。

    这些可以概括为64位版本。

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

    如果你有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 ，在这里描述。 它需要Intel Core 2和更高版本的SSSE3以及2011年到来的AMD芯片组。它使用SIMD指令在16个字节的区块中弹出，并一次展开4次循环迭代。

    最快的C函数是popcount_24words ，这里描述。 它使用位分片算法。 值得注意的是，我发现clang实际上可以生成适当的矢量汇编指令，这使得性能显着提升。 除此之外，算法仍然非常快。

    链接地址: http://www.djcxy.com/p/12597.html

    上一篇: Bit popcount for large buffer, with Core 2 CPU (SSSE3)

    下一篇: Fastest way to count number of 1s in a register, ARM assembly