Bit PopCount für große Puffer mit Core 2 CPU (SSSE3)

Question

Ich bin auf der Suche nach dem schnellsten Weg zu PopCount auf großen Puffer von 512 oder mehr Bytes. Ich kann jede erforderliche Ausrichtung gewährleisten, und die Puffergröße ist immer eine Potenz von 2 ist der Puffer entspricht Zuweisungen zu blockieren, so dass typischerweise die Bits entweder alle gesetzt, keine festgelegt, oder überwiegend „links“ des Puffers gesetzt begünstigt, mit gelegentliche Löcher.

Einige Lösungen, die ich in Betracht gezogen habe, sind:

• GCC ist __builtin_popcount
• BitSlice popcount_24words
• Zählen Bits gesetzt, Brian Kernighan Weg

Ich bin in der schnellsten Lösung interessiert, muss sie arbeiten auf 32-Bit-x86-Chipsatz core2 gehören oder jünger. SSE und SIMD sind von großen Interesse. Ich werde auf dem folgenden Quad-Core-CPU Testen werden:

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:

Answer 1

umreißen ich die beste C / Montagefunktionen I für Bevölkerungszahl / Hamminggewicht großer gefunden Puffer unten.

Die schnellste Montage Funktion ist ssse3_popcount3 , beschrieben hier . Es erfordert SSSE3 , auf dem Intel Core 2 und höher und AMD-Chipsatz der Ankunft im Jahr 2011. Es nutzt SIMD Anweisungen an PopCount in 16-Byte-Chunks und entrollt 4 Schleifeniterationen zu einem Zeitpunkt.

Die schnellste C-Funktion ist popcount_24words , beschrieben hier . Es verwendet den Bit-Slicing-Algorithmus. Bemerkenswert fand ich, dass Klirren tatsächlich geeignete Vektor Montageanleitung erzeugen könnte, die eindrucksvollen Leistungssteigerungen gab. Davon abgesehen, ist der Algorithmus immer noch extrem schnell.

Answer 2

Hier finden Sie eine 32-Bit-Version in der AMD Software Optimization führen , Seite 195 für eine Implementierung. Dies gibt Ihnen Assembler-Code für einen x86 direkt.

Hier finden Sie eine Variante unter Stanford-Bit-twiddling Hacks Die Stanford-Version sieht aus wie die besten für mich. Es sieht sehr einfach zu Code wie x86 asm.

Keine dieser Verwendung Verzweigungsbefehle.

Diese können auf 64-Bit-Versionen verallgemeinert werden.

Mit den 32 oder 64-Bit-Versionen, könnten Sie tun, eine SIMD-Version betrachten. SSE2 tun 4 Doppelwörtern oder zwei Quad-Wörter (128 Bits oder so) auf einmal. Was Sie tun möchten, ist die PopCount implementieren für 32 oder 64 Bits in jedem der 2 oder 4 Register verfügbar. Sie werden am mit 2 oder 4 Sätzen von popcounts in den XMM-Registern Ende wenn du fertig bist; letzter Schritt ist, diejenigen zu speichern und hinzufügen popcounts zusammen, um die endgültige Antwort zu erhalten. Erraten, Ich würde erwarten, dass Sie so etwas besser tun 4 parallel 32 Bit popcounts anstatt 2 parallele 64-Bit-popcounts, da letztere wahrscheinlich zusätzliche Anweisungen aufzunehmen 1 oder 2 ist, in jeder Iteration, und die einfachen 4, 32-Bit-Werten addieren das Ende.

Answer 3

Wenn Sie had popcnt:

http: // kent-Vandervelden .blogspot.com / 2009/10 / Zählen Bit-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

Answer 4

Ich würde vorschlagen, eine der optimierte 32-Bit-popcnt Routinen Implementierung von Hacker Delight , aber es für 4 x 32-Bit-integer-Elemente in einem SSE-Vektor. Sie können dann 128 Bits pro Iteration verarbeiten, die Sie um 4x Durchsatz im Vergleich zu einer optimierten 32-Bit-Skalar Routine geben sollte.