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, wie popcnt im flags 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.

InformationsquelleAutor Matt Joiner | 2010-09-12
Schreibe einen Kommentar