Ich arbeite an einer x86 oder x86_64 Maschine. Ich habe ein Array unsigned int a[32] , dessen Elemente alle den Wert 0 oder 1 haben. Ich möchte die einzelne Variable unsigned int b so einstellen, dass (b >> i) & 1 == a[i] für alle 32 Elemente von a gilt. Ich arbeite mit GCC unter Linux (sollte nicht viel ausmachen, denke ich).
Was ist der schnellste Weg, dies in C zu tun?
Der schnellste Weg bei den letzten x86-Prozessoren ist vermutlich, die MOVMSKB-Familie von Befehlen zu verwenden, die die MSBs eines SIMD-Wortes extrahieren und sie in ein normales Integer-Register packen.
Ich fürchte, SIMD-Intrinsics sind nicht wirklich mein Ding, aber etwas in dieser Richtung sollte funktionieren, wenn Sie einen AVX2-Prozessor haben:
%Vor% Annahme von sizeof(bool) = 1 . Für ältere SSE2-Systeme müssen Sie stattdessen ein Paar 128-Bit-Operationen aneinanderreihen. Ausrichten des Arrays auf einer 32-Byte-Grenze und sollte einen weiteren Zyklus oder so speichern.
Andere Antworten enthalten eine offensichtliche Schleifenimplementierung.
Hier ist eine erste Variante:
%Vor%Auf modernen x86-CPUs denke ich, dass Verschiebungen jeder Entfernung in einem Register konstant sind, und diese Lösung wird nicht besser sein. Deine CPU ist vielleicht nicht so nett. dieser Code minimiert die Kosten von Fernverschiebungen; es macht 32 1-Bit-Shifts, die jede CPU ausführen kann (Sie können das Ergebnis immer zu sich selbst hinzufügen, um den gleichen Effekt zu erzielen). Die offensichtliche Schleifenimplementierung, die von anderen gezeigt wird, macht etwa 900 (Summe von 32) 1-Bit-Verschiebungen, indem eine Distanz verschoben wird, die gleich dem Schleifenindex ist. (Siehe @ Jongwares Messungen von Unterschieden in Kommentaren; anscheinend sind lange Verschiebungen auf x86 keine Einheitszeit).
Lasst uns etwas radikaleres ausprobieren.
Angenommen, Sie können m booleans irgendwie in ein int packen (trivialerweise können Sie das für m == 1 tun), und Sie haben zwei Instanzvariablen i1 und i2 , die solche m gepackten Bits enthalten.
Dann packt der folgende Code m * 2 booleans in ein int:
%Vor%Mit diesem können wir 2 ^ n Bits wie folgt packen:
%Vor%Angenommen, unser freundlicher Compiler löst einen [k] in einen (skalaren) direkten Speicherzugriff auf (wenn nicht, können Sie einfach die Variable an [k] durch an_k ersetzen), der obige Code (abstrakt) 63 holt, 31 schreibt , 31 Schichten und 31 addiert. (Es gibt eine offensichtliche Erweiterung auf 64 Bits).
Auf modernen x86-CPUs denke ich, dass Verschiebungen jeder Entfernung in einem Register konstant sind. Wenn nicht, minimiert dieser Code die Kosten von Fernverschiebungen; es führt tatsächlich 64 1-Bit-Verschiebungen durch.
Auf einer x64-Maschine, anders als die Abrufe der ursprünglichen booleschen a1 [k], würde ich erwarten, dass der Rest der Skalare vom Compiler so geplant werden kann, dass er in die Register passt, also 32 Speicherabrufe, 31 Schichten und 31 fügt hinzu. Es ist ziemlich schwierig, die Fetches zu vermeiden (wenn die ursprünglichen Booleans verstreut sind) und die Shifts / Adds passen zu der offensichtlichen einfachen Schleife. Aber da keine Schleife ist, vermeiden wir 32 Inkrement- / Vergleichs- / Indexoperationen.
Wenn die Start-Booleans wirklich in einem Array sind, wobei jedes Bit das untere Bit des Bytes belegt und ansonsten null ist:
%Vor%Dann können wir unser Wissen über das Speicherlayout missbrauchen, um mehrere gleichzeitig zu holen:
%Vor%Hier sind unsere Kosten 8 Abrufe (Sätze von 4) booleans, 7 Verschiebungen und 7 Hinzufügungen. Nochmals, keine Schleife Overhead. (Wiederum gibt es eine offensichtliche Verallgemeinerung auf 64 Bits).
Um schneller zu werden, müssen Sie wahrscheinlich in Assembler gehen und einige der vielen wundervollen und seltsamen Anweisungen verwenden, die dort verfügbar sind (die Vektorregister haben wahrscheinlich Scatter / Gather-Ops, die gut funktionieren könnten).
Wie immer mussten diese Lösungen getestet werden.
Wenn sizeof(bool) == 1 , dann können Sie 8 bool s gleichzeitig in 8 Bits (mehr mit 128-Bit-Multiplikationen) unter Verwendung der besprochenen Technik hier in einem Computer mit schneller Multiplikation.
Das Behandeln der 8 aufeinanderfolgenden bool s als ein 64-Bit-Wort mit den Bits 1 bis 8 sind die niedrigstwertigen Bits der bools und multiplizieren sie mit der magischen Zahl, die 8 lsbs im oberen Byte erhalten . Das funktioniert, weil die Multiplikation mit jedem 1 Bit in der magischen Zahl die Zahl auf die Position dieses 1 Bit verschiebt.
Also, mit der magischen Zahl 0000 0001 0000 0010 0000 0100 0000 1000 0001 0000 0010 0000 0100 0000 1000 0000 oder 0x0102040810204080 haben wir den folgenden Code
Natürlich müssen Sie sicherstellen, dass das Bool-Array korrekt 8-Byte ausgerichtet ist. Sie können den Code auch ausrollen und optimieren, z. B. nur einmal verschieben, anstatt nach links zu springen, 56 Bits
Um festzustellen, wie der schnellste Weg ist, sollten Sie alle möglichen Vorschläge berücksichtigen. Hier ist ein , dass gut als "der" am schnellsten enden kann (mit Standard C, keine prozessorabhängige SSE oder dergleichen) :
Der erste Wert im Array ist das linkeste Bit: der höchstmögliche Wert.
Der Proof-of-Concept mit einigen groben Timings zeigt, dass dies in der Tat nicht besser ist als die einfache Schleife mit b |= (a[i]<<(31-i)) :
(Relatives Timing mit den gleichen Compiler-Optionen.)
(Die "adds" -Routine gehört mir, wobei die Indizierung durch einen Zeiger auf und eine explizite Hinzufügung für beide indizierten Arrays ersetzt wird. Sie ist 10% langsamer, was bedeutet, dass mein Compiler den indizierten Zugriff effizient optimiert. Gut zu wissen.) p>
Tags und Links c c++ performance bit-manipulation