Bit-popcount für große Puffer, mit Core 2 CPU (SSSE3)
Ich bin auf der Suche nach der Schnellste Weg, um popcount auf großen Puffer von 512 Byte. Ich kann garantieren jede gewünschte Ausrichtung, und die Puffer Größe ist immer eine Potenz von 2 ist. Der Puffer entspricht block-Zuordnungen, also in der Regel die bits sind entweder alle gesetzt, werden keine gesetzt, oder meist zugunsten der "linken" des Puffers, mit gelegentlichen Löchern.
Einige Lösungen habe ich schon berücksichtigt:
Interessiere ich mich für die Schnellste Lösung, es muss funktionieren auf 32-bit-x86-Chipsatz gehörenden core2 oder mehr die jüngsten. SSE und SIMD sind von großem Interesse. Ich werde testen auf den folgenden 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:
- SSE4 hat popcnt
- Karpfen: Bitte geben Sie ein code-Beispiel nutzt diese als Antwort! Links zu den kanonischen Beschreibungen von popcnt und wie Sie es auf GCC sind auch eine gute Idee.
- Sie finden es hier erwähnt, secure.wikimedia.org/wikipedia/en/wiki/SSE4
- Gustedt: ich kenne die Anleitung (obwohl es nicht unterstützt wird auf meiner CPU), aber nicht-Nutzung auf den GCC.
- wenn Sie
gcc
ich würde nicht sorgen in jedem Fall zu implementieren, diese in assembler. Ich vertraue den Jungs, die Nutzung__builtin_popcountll
und kompilieren Sie mit-march=native
. Aber ich glaube nicht, dass der Unterricht entweder auf meinem Rechner, ich kann also nicht bestätigen, dass dies die richtige Sache zu machen: auf meiner Maschine diese Ergebnisse noch in einen Aufruf der Funktion. - Warum? Die ersten Google-Treffer für "popcount" scheint sich zu einer letzten Seite von Bart Massey (Autor XCB) dokumentieren seine Suche nach dem besten popcount-Algorithmus, welche umfasst nicht nur die algorithmen, die er versucht, aber auch seine benchmarking-code und die Ergebnisse.
- Die CPU hast du oben gezeigt, nicht die
popcnt
Unterricht sowieso (es gibt ein bestimmtes feature flag für das Vorhandensein dieser Anleitung, die zeigt, wiepopcnt
imflags
Linie in/proc/cpuinfo
). - Slattery: ja, ich wies darauf hin, bereits, erwartete ich
sse4
für die POPCNT instruction. - Ja habe ich schon angeschaut, und übergeben Sie über diese, Sie sind nicht optimiert für große Puffer.
- Vielleicht bin ich etwas fehlt, aber was (außer möglicherweise SIMD-Befehle) hätte zur Folge, dass die meisten effizienten Algorithmus für einzelne Wörter, nicht die effizienteste für große Puffer?
- Einige Beispiele: 24words verbunden, meine Frage ist in der Lage den Betrieb auf 96 bytes-Blöcken ohne einen einzigen Zweig. Die Beschleunigung von Operationen auf einzelne Worte, ist schön, aber es gibt noch einen O(n) Kosten, die mit der impliziten bounds checking etc. für ein großes array. Ein weiterer ist entrollt, optimierte algorithmen für große Puffer können die beschäftigen diese enorme Wirkung. Oft ist die Kombination eines nicht-trivialen Sequenz von Anweisungen auszuführen, kann die popcount (oder eine andere Aufgabe) in weit weniger Zyklen als Betriebssystem auf Wörter einzeln. Ein anderer Algorithmus, den ich gefunden verwalteten die Verwendung einer MULT-Instruktion, sich zu rasieren off-Zyklen.
- gibt es irgendwelche Anforderungen an die Atomarität / multi-thread-Zugriff?
- Ich nicht Folgen.
- Ich würde erwarten, dass POPCNT umgesetzt werden in eine sehr kleine Anzahl von Zyklen, und wenn das der Fall ist, es ist wahrscheinlich schwer zu schlagen, vor allem, wenn Sie entrollen einer Schleife mit POPCNT 16x oder so. Wenn Sie nicht haben, POPCNT, dann knifflig Assembler-code angewendet werden könnte.
- [Sorry für den necro-ing solch einem alten Q], Während ein solcher Experimente sind immer lustig und manchmal auch hilfreich, ich möchte Sie darauf hinweisen, dass (für die kein vernünftiger, einleuchtender Grund) habe ich gerade kompiliert und lief der test-suite auf meinem Moderat-den letzten (Skylake) desktop. Es überrascht nicht, ist der einfachste, direkteste, die meisten lesbare Lösung mit dem compiler intrinsic läuft mehr als 4-mal schneller als die "besten" optimiert (und völlig unleserlich) version.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Finden Sie eine 32-bit-version in der AMD Software Optimization guide, Seite 195 für eine Umsetzung.
Dies gibt Ihnen Assembler-code für x86-direkt.
Finden Sie eine Variante an Stanford-bit-twiddling hacks
Der Stanford-version sieht aus wie das beste für mich.
Es sieht sehr einfach zu code als x86 asm.
Weder dieser Einsatz branch-Instruktionen.
Diese kann verallgemeinert werden, um 64-bit-Versionen.
Mit der 32-oder 64-bit-Versionen, die Sie vielleicht in Erwägung ziehen ein SIMD-version.
SSE2 wird do 4 Doppel-Wörter oder zwei quadwords (entweder Weg 128 bits)
auf einmal. Was Sie tun möchten, implementieren Sie den popcount für 32
oder 64 bits in jedem der 2 oder 4 Registern zur Verfügung.
Du wirst am Ende mit 2 oder 4 Sätze popcounts in den XMM-Registern
wenn Sie fertig sind, Letzte Schritt ist das speichern und fügen Sie diese
popcounts zusammen, um die endgültige Antwort. Erraten,
Ich würde erwarten, dass Sie so etwas besser zu machen, 4 parallel 32
bit popcounts anstatt 2 parallel 64-bit-popcounts,
da letzteres wird wahrscheinlich 1 oder 2 zusätzliche Anweisungen
in jeder iteration, und es ist einfach zu fügen Sie 4, 32-bit-Werten zusammen
Ende.
Wenn Sie hatte 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
Skizziere ich die beste C - /Montage-Funktionen fand ich für Bevölkerungszahl/Hamming-Gewicht der große Puffer unten.
Die Schnellste Montage ist die Funktion
ssse3_popcount3
, beschrieben hier. Es erfordert SSSE3, zur Verfügung, die auf Intel-Core-2 und höher und AMD-Chipsätze der Ankunft im Jahr 2011. Es nutzt SIMD Anweisungen, um popcount in 16 byte-Blöcken und entrollt 4 loop-Iterationen gleichzeitig.Die Schnellste C-Funktion ist
popcount_24words
, beschrieben hier. Es nutzt das bit-slicing-Algorithmus. Der Hinweis fand ich, dass clang könnte tatsächlich generiert die entsprechenden Vektor-assembly-Anweisungen, die gab beeindruckende Leistung erhöht. Dies beiseite, der Algorithmus ist immer noch extrem schnell.POPCNT
Unterricht.POPCNT
ist der Schnellste Weg, es zu tun. Benchmarks und detaillierte Erklärung hier.popcnt
auf modernen Intel (Haswell-und später). Aber nur mit 256-bit-Vektoren: AVX1 / SSSE3 sind nicht schneller, IIRC. Ryzen ist interessant; es hat 4 pro Takt 64-bit -popcnt
, so ist es wahrscheinlich am besten mit skalaren. AVX512vpternlogd
ermöglicht weitere Optimierungen: Large (0,1) - matrix-Multiplikation unter Verwendung des bitweisen UND-und popcount anstelle der tatsächlichen int-oder float-multipliziert?, speziell github.com/WojciechMula/sse-popcount/blob/master/... hat 30x vpternlogd + 1 Vektor popcnt für 16x ZMM Vektoren (16x 512 bits).Ich würde vorschlagen, die Implementierung der optimierten 32-bit-popcnt-Routinen aus Hacker ' s Delight, aber tun Sie es mit 4 x 32-bit-integer-Elemente in ein SSE-Vektor. Sie kann dann 128 bits pro iteration, die Ihnen rund um 4x den Durchsatz im Vergleich zu einer optimierten 32-bit-Skalar-routine.