Popcount von SSE-Vektoren für binäre Korrelation?
Ich habe diese einfache binäre Korrelationsmethode, es schlägt Tabellensuche und Hakmem Bit Twiddling-Methoden um x3-4 und% 25 besser als GCC's __builtin_popcount (die ich denke, eine Popcnt-Anweisung zugeordnet, wenn SSE4 aktiviert ist.)
Hier ist der viel vereinfachte Code:
%Vor%Ich habe versucht, die Schleife zu entrollen, aber ich denke, GCC macht das bereits automatisch, also endete ich mit der gleichen Leistung. Glauben Sie, dass die Leistung weiter verbessert wurde, ohne den Code zu kompliziert zu machen? Angenommen, v1 und v2 haben die gleiche Größe und Größe ist gerade.
Ich bin mit seiner aktuellen Leistung zufrieden, aber ich war nur neugierig, ob es noch verbessert werden könnte.
Danke.
Edit: Es wurde ein Fehler in der Union behoben und es stellte sich heraus, dass dieser Fehler diese Version schneller machte als in __builtin_popcount, trotzdem änderte ich den Code noch einmal etwas schneller als jetzt (15%), aber ich denke nicht es lohnt sich, dafür Zeit zu investieren. Danke für alle Kommentare und Vorschläge.
%Vor%Second Edit: Es stellte sich heraus, dass builtin der schnellste Seufzer ist. besonders mit -funroll-loops und -fprefetch-loop-arrays. Etwas wie das:
%Vor%Dritte Bearbeitung:
Dies ist ein interessanter SSE3-Parallel-4-Bit-Lookup-Algorithmus. Die Idee stammt von Wojciech Muła , die Implementierung stammt von Marat Dukhans Antwort . Danke an @Apriori für die Erinnerung an diesen Algorithmus. Unten ist das Herz des Algorithmus, es ist sehr schlau, im Grunde zählen Bits für Bytes mit einem SSE-Register als 16-Wege-Lookup-Tabelle und unteren Nibbles als Index der Tabellenzellen ausgewählt sind. Dann summiert die Anzahl.
%Vor%Bei meinen Tests ist diese Version auf Augenhöhe; etwas schneller bei kleineren Eingaben, etwas langsamer bei größeren als bei Verwendung von hw popcount. Ich denke, das sollte wirklich glänzen, wenn es in AVX implementiert wird. Aber ich habe keine Zeit dafür, wenn jemand Lust darauf hat, ihre Ergebnisse zu hören.
2 Antworten
Das Problem ist, dass popcnt (das ist, was __builtin_popcnt in Intel-CPUs compiliert) auf den Integer-Registern arbeitet. Dies veranlaßt den Compiler, Anweisungen zum Verschieben von Daten zwischen den SSE- und Integer-Registern auszugeben. Ich bin nicht überrascht, dass die Nicht-SSE-Version schneller ist, da die Fähigkeit, Daten zwischen den Vektor- und Ganzzahlregistern zu bewegen, ziemlich begrenzt / langsam ist.
Dies läuft bei ca. 2.36 Uhren pro Schleife auf kleinen Datensätzen (passt in den Cache). Ich denke, dass es wegen der 'langen' Abhängigkeitskette auf sum langsam läuft, was die Fähigkeit der CPU einschränkt, mehr Dinge in der falschen Reihenfolge zu handhaben. Wir können es verbessern, indem wir die Schleife manuell pipelining:
Dies läuft bei 1,75 Uhren pro Artikel. Meine CPU ist ein Sandy-Bridge-Modell (i7-2820QM fest @ 2.4Ghz).
Wie wäre es mit Vier-Wege-Pipelining? Das sind 1,65 Uhren pro Stück. Was ist mit 8-Wege? 1,57 Uhren pro Stück. Wir können ableiten, dass die Laufzeit pro Element (1.5n + 0.5) / n ist, wobei n die Anzahl der Pipelines in unserer Schleife ist. Ich sollte beachten, dass 8-Wege-Pipelining aus irgendeinem Grund schlechter läuft als die anderen, wenn der Datensatz wächst, ich habe keine Ahnung warum. Der generierte Code sieht gut aus.
Nun, wenn Sie genau hinsehen, gibt es eine xor , eine add , eine popcnt und eine mov Anweisung pro Element. Es gibt auch einen LEA-Befehl pro Schleife (und einen Zweig und ein Dekrement, die ich ignoriere, weil sie ziemlich frei sind).
Sie können mit Agner Fogs Optimierungshandbuch überprüfen, dass ein lea für einen halben Taktzyklus steht und der mov / xor / popcnt / add Combo ist anscheinend 1,5 Taktzyklen, obwohl ich nicht genau verstehe warum genau.
Leider denke ich, dass wir hier feststecken. Der PEXTRQ -Befehl ist das, was normalerweise verwendet wird, um Daten von den Vektorregistern zu den Ganzzahlregistern zu bewegen, und wir können diese Anweisung und eine popcnt-Anweisung sauber in einem Taktzyklus anpassen. Fügen Sie eine Integer add Anweisung hinzu und unsere Pipeline ist mindestens 1.33 Zyklen lang und wir müssen noch eine Vektorlast und Xor irgendwo dazwischen hinzufügen ... Wenn Intel Befehle zum Verschieben mehrerer Register zwischen den Vektor- und Integerregistern gleichzeitig anbietet wäre eine andere Geschichte.
Ich habe keine AVX2-CPU zur Hand (xor auf 256-Bit-Vektorregistern ist eine AVX2-Funktion), aber meine vektorisierte Last-Implementierung führt bei niedrigen Datengrößen ziemlich schlecht aus und erreicht ein Minimum von 1,97 Taktzyklen pro Element .
Als Referenz sind dies meine Benchmarks:
"pipe 2", "pipe 4" und "pipe 8" sind 2-, 4- und 8-polige Versionen des oben gezeigten Codes. Die schlechte Darstellung von "sse load" scheint eine Manifestation des lzcnt / tzcnt / popcnt falscher Abhängigkeitsfehler welcher gcc vermieden wird, indem das gleiche Register für Eingabe und Ausgabe verwendet wird. "sse load 2" folgt unten:
%Vor%Tags und Links optimization x86 performance sse bit-manipulation