Wenn ich eine 64-Bit-Ganzzahl habe, die ich als Array gepackter 8-Bit-Ganzzahlen mit 8 Elementen interpretiere. Ich muss die Konstante 1
von jeder gepackten Ganzzahl subtrahieren, während ich den Überlauf behandle, ohne dass das Ergebnis eines Elements das Ergebnis eines anderen Elements beeinflusst.
Ich habe diesen Code im Moment und er funktioniert, aber ich brauche eine Lösung, die die Subtraktion jeder gepackten 8-Bit-Ganzzahl parallel ausführt und keine Speicherzugriffe ausführt. Auf x86 könnte ich solche SIMD-Anweisungen verwenden psubb
, die gepackte 8-Bit-Ganzzahlen parallel subtrahieren, aber die Plattform, für die ich codiere, unterstützt keine SIMD-Anweisungen. (RISC-V in diesem Fall).
Ich versuche also, SWAR (SIMD innerhalb eines Registers) auszuführen, um die Übertragsausbreitung zwischen Bytes von a manuell aufzuheben, uint64_t
und mache etwas Äquivalentes dazu:
uint64_t sub(uint64_t arg) {
uint8_t* packed = (uint8_t*) &arg;
for (size_t i = 0; i < sizeof(uint64_t); ++i) {
packed[i] -= 1;
}
return arg;
}
Ich denke, Sie könnten dies mit bitweisen Operatoren tun, aber ich bin mir nicht sicher. Ich suche nach einer Lösung, die keine SIMD-Anweisungen verwendet. Ich suche nach einer Lösung in C oder C ++, die ziemlich portabel ist oder nur die Theorie dahinter, damit ich meine eigene Lösung implementieren kann.
Antworten:
Wenn Sie eine CPU mit effizienten SIMD-Anweisungen haben, ist auch SSE / MMX
paddb
(_mm_add_epi8
) möglich. Die Antwort von Peter Cordes beschreibt auch die GNU C-Vektorsyntax (gcc / clang) und die Sicherheit für UB mit striktem Aliasing. Ich empfehle dringend, auch diese Antwort zu überprüfen.Das Selbermachen
uint64_t
ist vollständig portabel, erfordert jedoch weiterhin Sorgfalt, um Ausrichtungsprobleme und striktes Aliasing von UB beim Zugriff auf einuint8_t
Array mit a zu vermeidenuint64_t*
. Sie haben diesen Teil aus der Frage herausgelassen, indem Sie mit Ihren Daten in einemuint64_t
bereits begonnen haben, aber für GNU Cmay_alias
löst ein typedef das Problem (siehe Peters Antwort dafür odermemcpy
).Andernfalls können Sie Ihre Daten als zuordnen / deklarieren
uint64_t
und darauf zugreifen,uint8_t*
wenn Sie einzelne Bytes möchten.unsigned char*
darf alles aliasen, um das Problem für den speziellen Fall von 8-Bit-Elementen zu umgehen. (Wennuint8_t
es überhaupt existiert, ist es wahrscheinlich sicher anzunehmen, dass es eine istunsigned char
.)Beachten Sie, dass dies eine Änderung gegenüber einem früheren falschen Algorithmus ist (siehe Versionsverlauf).
Dies ist ohne Schleife für eine beliebige Subtraktion möglich und wird für eine bekannte Konstante wie
1
in jedem Byte effizienter . Der Haupttrick besteht darin, die Ausführung jedes Bytes durch Setzen des High-Bits zu verhindern und dann das Subtraktionsergebnis zu korrigieren.Wir werden die hier angegebene Subtraktionstechnik leicht optimieren . Sie definieren:
mit
H
definiert als0x8080808080808080U
(dh die MSBs jeder gepackten ganzen Zahl). Für eine Dekrementierungy
ist0x0101010101010101U
.Wir wissen, dass
y
alle MSBs klar sind, sodass wir einen der Maskenschritte überspringen können (dhy & ~H
der gleiche wiey
in unserem Fall). Die Berechnung läuft wie folgt ab:x
auf 1, damit sich ein Kredit nicht über das MSB hinaus zur nächsten Komponente ausbreiten kann. Nennen Sie dies den eingestellten Eingang.0x01010101010101
von der korrigierten Eingabe subtrahieren . Dies führt dank Schritt 1 nicht zu Ausleihen zwischen Komponenten. Nennen Sie dies den angepassten Ausgang.Die Operation kann wie folgt geschrieben werden:
Dies wird vorzugsweise vom Compiler eingefügt (verwenden Sie Compiler-Anweisungen , um dies zu erzwingen), oder der Ausdruck wird als Teil einer anderen Funktion inline geschrieben.
Testfälle:
Leistungsdetails
Hier ist die x86_64-Assembly für einen einzelnen Aufruf der Funktion. Für eine bessere Leistung sollte es in der Hoffnung eingefügt werden, dass die Konstanten so lange wie möglich in einem Register leben können. In einer engen Schleife, in der die Konstanten in einem Register leben, benötigt das tatsächliche Dekrement fünf Anweisungen: oder + nicht + und + addiere + xor nach der Optimierung. Ich sehe keine Alternativen, die die Optimierung des Compilers übertreffen würden.
Mit einigen IACA-Tests des folgenden Snippets:
Wir können zeigen, dass auf einer Skylake-Maschine das Dekrementieren, Xor und Vergleichen + Springen mit knapp 5 Zyklen pro Iteration durchgeführt werden kann:
(Natürlich würden Sie auf x86-64 nur oder
movq
in eine XMM-Registrierung für ladenpaddb
, daher ist es möglicherweise interessanter zu sehen, wie es für eine ISA wie RISC-V kompiliert wird.)quelle
uint8_t
darfuint8_t
Daten aliasen . Anrufer Ihrer Funktion (dieuint8_t
Daten in a übertragen müssenuint64_t
) müssen sich um striktes Aliasing sorgen! Daher sollte das OP wahrscheinlich nur Arrays deklarieren / zuweisen,uint64_t
da dieschar*
in ISO C ++ als Alias zulässig ist, aber nicht umgekehrt.Für RISC-V verwenden Sie wahrscheinlich GCC / clang.
Unterhaltsame Tatsache: GCC kennt einige dieser SWAR-Bithack-Tricks (in anderen Antworten gezeigt) und kann sie für Sie verwenden, wenn Sie Code mit nativen GNU C-Vektoren für Ziele ohne Hardware-SIMD-Anweisungen kompilieren . (Aber wenn Sie für RISC-V klirren, wird es nur naiv für skalare Operationen abgewickelt, sodass Sie es selbst tun müssen, wenn Sie eine gute Leistung über Compiler hinweg wünschen.)
Ein Vorteil der nativen Vektorsyntax besteht darin, dass beim Targeting einer Maschine mit Hardware-SIMD diese verwendet wird, anstatt Ihren Bithack oder etwas Schreckliches automatisch zu vektorisieren.
Es macht es einfach,
vector -= scalar
Operationen zu schreiben ; Die Syntax Just Works überträgt implizit den Skalar für Sie.Beachten Sie auch, dass eine
uint64_t*
Last von a einuint8_t array[]
striktes Aliasing für UB ist. Seien Sie also vorsichtig damit. (Siehe auch Warum muss glibc's strlen so kompliziert sein, um schnell zu laufen? Betreff: SWAR-Bithacks in reinem C sicher strikt aliasing machen). Möglicherweise möchten Sie, dass so etwas deklariert,uint64_t
dass Sie mit dem Zeiger auf andere Objekte zugreifen können, z. B. wie dieschar*
in ISO C / C ++ funktioniert.Verwenden Sie diese, um uint8_t-Daten in ein uint64_t zu übertragen und mit anderen Antworten zu verwenden:
Die andere Möglichkeit, aliasing-sichere Lasten auszuführen, ist
memcpy
in auint64_t
, wodurch auch diealignof(uint64_t
Ausrichtungsanforderung entfällt . Bei ISAs ohne effiziente nicht ausgerichtete Lasten wird gcc / clang jedoch nicht inline und optimiert,memcpy
wenn nicht nachgewiesen werden kann, dass der Zeiger ausgerichtet ist, was für die Leistung katastrophal wäre.TL: DR: Am besten deklarieren Sie Ihre Daten als
uint64_t array[...]
oder ordnen sie dynamisch zuuint64_t
, oder vorzugsweise.alignas(16) uint64_t array[];
Dies stellt die Ausrichtung auf mindestens 8 Bytes oder 16 Bytes sicher, wenn Sie dies angebenalignas
.Da dies
uint8_t
mit ziemlicher Sicherheit der Fall istunsigned char*
, ist es sicher, auf die Bytes einesuint64_t
Via zuzugreifenuint8_t*
(bei einem uint8_t-Array jedoch nicht umgekehrt). In diesem speziellen Fall, in dem es sich um einen schmalen Elementtyp handeltunsigned char
, können Sie das Problem des strengen Aliasing umgehen, dachar
es speziell ist.Beispiel für die native Vektorsyntax von GNU C:
GNU C-native Vektoren dürfen immer einen Alias mit ihrem zugrunde liegenden Typ haben (z. B.
int __attribute__((vector_size(16)))
können sicher Alias sein,int
aber nichtfloat
oderuint8_t
oder irgendetwas anderes.Bei RISC-V ohne HW-SIMD können Sie
vector_size(8)
nur die Granularität ausdrücken, die Sie effizient verwenden können, und doppelt so viele kleinere Vektoren erstellen.Aber
vector_size(8)
kompiliert sehr dumm für x86 mit GCC und clang: GCC verwendet SWAR-Bithacks in GP-Integer-Registern, Clang entpackt in 2-Byte-Elemente, um ein 16-Byte-XMM-Register zu füllen, und packt dann neu. (MMX ist so veraltet, dass GCC / Clang sich nicht einmal die Mühe macht, es zu verwenden, zumindest nicht für x86-64.)Aber mit
vector_size (16)
( Godbolt ) bekommen wir das erwartetemovdqa
/paddb
. (Mit einem All-One-Vektor generiert vonpcmpeqd same,same
). Da-march=skylake
wir immer noch zwei separate XMM-Operationen anstelle einer YMM erhalten, "vektorisieren" aktuelle Compiler leider auch keine Vektoroperationen automatisch in breitere Vektoren: /Für AArch64 ist es nicht so schlecht zu verwenden
vector_size(8)
( Godbolt ); ARM / AArch64 kann nativ in 8- oder 16-Byte-Blöcken mitd
oderq
Registern arbeiten.Sie möchten also wahrscheinlich
vector_size(16)
tatsächlich kompilieren, wenn Sie eine tragbare Leistung für x86, RISC-V, ARM / AArch64 und POWER wünschen . Einige andere ISAs machen jedoch SIMD innerhalb von 64-Bit-Integer-Registern, wie MIPS MSA, denke ich.vector_size(8)
erleichtert das Betrachten des asm (nur ein Register mit Daten): Godbolt Compiler ExplorerIch denke, es ist die gleiche Grundidee wie bei den anderen Antworten ohne Schleifen. Verhindern Sie das Tragen und korrigieren Sie das Ergebnis.
Dies sind 5 ALU-Anweisungen, schlimmer als die beste Antwort, denke ich. Es sieht jedoch so aus, als ob die kritische Pfadlatenz nur 3 Zyklen beträgt, wobei zwei Ketten mit jeweils 2 Befehlen zum XOR führen. Die Antwort von @Reinstate Monica - ζ - wird zu einer 4-Zyklus-Dep-Kette (für x86) kompiliert. Der 5-Zyklus-Schleifendurchsatz wird durch die Einbeziehung eines Naiven
sub
in den kritischen Pfad eingeschränkt, und die Schleife führt zu einem Engpass bei der Latenz.Dies ist jedoch bei Klirren nutzlos. Es wird nicht einmal in der Reihenfolge hinzugefügt und gespeichert, in der es geladen wurde, sodass es nicht einmal ein gutes Software-Pipelining durchführt!
quelle
Ich möchte darauf hinweisen, dass der Code, den Sie geschrieben haben, tatsächlich vektorisiert wird, sobald Sie anfangen, sich mit mehr als einem einzelnen uint64_t zu befassen.
https://godbolt.org/z/J9DRzd
quelle
__vector_loop(index, start, past, pad)
Konstrukts gedacht, das eine Implementierung alsfor(index=start; index<past; index++)
[dh jede Implementierung könnte Code mit ihm verarbeiten, indem sie lediglich ein Makro definiert] behandeln könnte, das aber eine lockere Semantik hätte, um einen Compiler zum Verarbeiten von Dingen einzuladen Jede Zweierpotenzgröße bis zupad
, wobei der Anfang nach unten und das Ende nach oben verlängert werden, wenn sie nicht bereits ein Vielfaches der Blockgröße sind. Nebenwirkungen in jedem Block wären nicht sequenziert, und wenn abreak
innerhalb der Schleife auftritt, werden andere Wiederholungen ...restrict
ist hilfreich (und wäre hilfreicher, wenn der Standard ein Konzept von "zumindest potenziell basierend auf" erkennen und dann "basierend auf" und "zumindest potenziell basierend auf" direkt ohne doofe und nicht praktikable Eckfälle definieren würde) Mein Vorschlag würde es einem Compiler auch ermöglichen, mehr Ausführungen der Schleife als angefordert durchzuführen - etwas, das die Vektorisierung erheblich vereinfachen würde, für das der Standard jedoch keine Vorkehrungen trifft.Sie können sicherstellen, dass die Subtraktion nicht überläuft, und dann das hohe Bit korrigieren:
quelle
splat(0x01)
undsplat(0x80)
anstatt eine Schicht voneinander zu entfernen. Selbst wenn Sie es so in die Quelle godbolt.org/z/6y9v-u schreiben , wird der Compiler nicht dazu gebracht, besseren Code zu erstellen. es macht nur eine konstante Ausbreitung.Ich bin mir nicht sicher, ob dies das ist, was Sie wollen, aber es führt die 8 Subtraktionen parallel zueinander aus:
Erläuterung: Die Bitmaske beginnt mit einer 1 in jeder der 8-Bit-Zahlen. Wir xor es mit unserem Argument. Wenn wir an dieser Stelle eine 1 hatten, haben wir 1 abgezogen und müssen aufhören. Dies erfolgt durch Setzen des entsprechenden Bits auf 0 in new_mask. Wenn wir eine 0 hatten, setzen wir sie auf 1 und müssen den Übertrag ausführen, sodass das Bit 1 bleibt und wir die Maske nach links verschieben. Sie sollten selbst prüfen, ob die Generierung der neuen Maske wie beabsichtigt funktioniert, aber eine zweite Meinung wäre nicht schlecht.
PS: Ich bin mir nicht sicher, ob die Überprüfung, ob
mask_cp
die Schleife nicht null ist, das Programm verlangsamen kann. Ohne sie wäre der Code immer noch korrekt (da die 0-Maske einfach nichts bewirkt) und es wäre für den Compiler viel einfacher, das Abrollen der Schleife durchzuführen.quelle
for
läuft nicht parallel, bist du verwirrt mitfor_each
?Sie können dies mit bitweisen Operationen tun, indem Sie die obigen Schritte ausführen, und Sie müssen nur Ihre Ganzzahl in 8-Bit-Teile teilen, um 8-mal in diese Funktion zu senden. Der folgende Teil stammt aus Wie teilt man eine 64-Bit-Zahl in acht 8-Bit-Werte auf? mit mir in der obigen Funktion hinzufügen
Es ist C oder C ++ gültig, unabhängig davon, wie jemand darauf stößt
quelle
for_each(std::execution::par_unseq,...
anstelle von whiles verwendet wirdSie werden nicht versuchen, den Code zu finden, aber für eine Dekrementierung um 1 können Sie die Gruppe um 8 1s dekrementieren und dann überprüfen, ob die LSBs der Ergebnisse "umgedreht" wurden. Jedes nicht umgeschaltete LSB zeigt an, dass ein Übertrag von den benachbarten 8 Bits aufgetreten ist. Es sollte möglich sein, eine Folge von ANDs / ORs / XORs ohne Verzweigungen zu erarbeiten.
quelle
Konzentrieren Sie die Arbeit auf jedes Byte ganz alleine und setzen Sie es wieder dort ab, wo es war.
quelle