SIMD-Algorithmen von Grund auf entwerfen

 (mcyoung.xyz)
2 Punkte von GN⁺ 2023-11-29 | 1 Kommentare | Auf WhatsApp teilen
  • Der mit Rusts std::simd entwickelte vb64-Base64-Codec wird nicht dadurch schnell und portabel als SIMD-Code, dass man prozedurale Schleifen direkt vektorisiert, sondern indem man Datenlayout und Ablauf der Operationen wie eine Schaltung neu entwirft
  • Die zentrale Optimierung besteht darin, Stalls durch Branches und Speicherzugriffe zu reduzieren und mit Vergleichen, Masken, Select und Shuffle eine branchless Struktur zu schaffen, die unabhängig von der Eingabe dieselben Operationen ausführt
  • Beim Base64-Decoding wird ein Perfect Hash mit byte >> 4 und einer Korrektur für / erstellt, um ASCII-Zeichen in Sextets umzuwandeln; der Offset wird über eine Lookup Table innerhalb des SIMD-Vektors und Shuffle ermittelt
  • Beim Packen von vier 6-Bit-Sextets in drei Bytes werden die Lanes auf u16 erweitert und verschoben; anschließend werden Low-/High-Byte getrennt und Byte-Fragmente benachbarter Lanes mit rotate_lanes_left und OR zusammengeführt
  • In Benchmarks zeigte die Kombination aus -Zbuild-std, -Ctarget-cpu=native, N = 32 und optimiertem Laden des Remainders gegenüber der Baseline-Base64-Implementierung von crates.io über fast alle Bereiche hinweg rund doppelte Performance

Der physische Hintergrund für SIMD

  • Verbesserungen der Computerleistung hängen nicht nur mit theoretischer Informatik zusammen, sondern direkt mit physikalischen Grenzen
  • Moore’s Law scheint Stand 2023 weiterhin zu gelten, doch in den vergangenen 15 Jahren ist der Effekt des Dennard Scaling zusammengebrochen: Dichter gepackte Transistoren führen zu höherer Leistungsdichte
  • Nachdem es immer schwieriger wurde, die Taktfrequenz weiter zu erhöhen, verlagerte sich der wichtigste Weg zu mehr Performance seit Anfang der 2000er darauf, mehr Kerne zu nutzen
  • Multithreading erfordert Kooperation zwischen Kernen und verursacht dadurch Synchronisationskosten; Kontrollflüsse wie Sprünge, virtuelle Aufrufe und Synchronisation führen zu Stalls
  • Die Hauptursachen für Stalls sind zwei Dinge
    • Branches: Kontrollfluss wie if, Schleifen, Funktionsaufrufe, Funktionsrückgaben und switch in C
    • Speicheroperationen: Load/Store, insbesondere cache-unfreundliche Zugriffe

Prozeduraler Code und Parallelität auf Befehlsebene

  • Moderne CPU-Kerne führen Code nicht Zeile für Zeile aus, sondern geben voneinander unabhängige Operationen gleichzeitig aus
  • Operationen wie a = x + y und b = x ^ y, die nicht voneinander abhängen, können die Add- und XOR-Schaltungen gleichzeitig nutzen
  • Dieses Verfahren heißt Parallelität auf Befehlsebene; Abhängigkeiten, die sie behindern, werden als Data Hazards bezeichnet
  • Je besser eine CPU ihre Functional Units auslastet, desto mehr Operationen kann sie pro Zeiteinheit verarbeiten
  • Bei Branches muss auf die Berechnung der Bedingung gewartet werden, bevor die nächsten Instruktionen geholt werden können; bei Speicheroperationen müssen die Daten physisch bis zur CPU gelangen, wodurch Stalls entstehen
  • GPUs behandeln Bilder als Pixel in Vektorform und führen viele Operationen mit hoher Lokalität aus; sie ähneln daher SIMD-Maschinen, die für Batch-Operationen und begrenzten Kontrollfluss ausgelegt sind
  • SIMD steht für single instruction, multiple data: Eine Instruktion führt parallel Operationen auf mehreren Daten-Lanes aus

Denken in Lanes

  • SIMD und Vector werden häufig synonym verwendet; die Grundeinheit einer SIMD-Instruktion ist ein Vector, also ein Zahlenarray fester Größe
  • Jedes Element eines Vectors wird Lane genannt
  • SIMD-Vektoren müssen in Register passen und sind daher meist klein
    • Die maximale Vektorbreite der Beispielumgebung beträgt 256 Bit
    • Das entspricht 32 Bytes bei u8x32 oder 4 Doubles bei f64x8
  • Wenn selbst ein kleiner Vector die Belastung durch Pipeline-Auslastung um den Faktor 4 reduzieren kann, kann sich das entsprechend in geringerer Latenz niederschlagen

Divide and Conquer am Beispiel popcnt

  • Die einfachsten Vektoroperationen sind bitweise AND/OR/XOR-Operationen
  • Auch normale Integer lassen sich aus Sicht bitweiser Operationen als Vector aus 1-Bit-Lanes betrachten
    • i32 entspricht aus dieser Perspektive i1x32
  • popcnt zählt die Anzahl der 1-Bits in einem Integer; betrachtet man i32 als i1x32, ist es eine Reduce-Operation
  • Eine naive Implementierung, die die 32 Bits als Array extrahiert und addiert, kann schlechten Code erzeugen
  • Besser ist es, benachbarte Bitpaare zu addieren und dann wiederum Paare von Paaren zu addieren, wobei die Lane-Breite schrittweise wächst
    • Gerade/ungerade Bits mit den Masken 0x55555555 und 0xaaaaaaaa trennen
    • Die Lanes per Shift ausrichten und anschließend addieren
    • Danach in Einheiten von 2 Bit, 4 Bit, 8 Bit und 16 Bit wiederholen
  • Diese Implementierung wird zwar nicht zur popcnt-Instruktion optimiert, ist aber auf Systemen ohne eine solche Instruktion kleiner und schneller Code
  • Sie lässt sich auch auf u64 anwenden, indem man nur eine weitere Reduktionsstufe hinzufügt; eine vollständige u64-Addition ist nicht nötig
  • Dieser Divide-and-Conquer-Ansatz ist ein zentrales Muster der SIMD-Programmierung

Wichtige Werkzeuge von SIMD-Befehlssätzen

  • Reale SIMD-Vektoren bieten komplexere Semantik als Skalare; besonders wichtig sind Funktionen, die langsamen Kontrollfluss ersetzen
  • Welche Instruktionen verfügbar sind, hängt stark von der Architektur ab
    • Viele performante x86-Kerne implementieren AVX2
    • AVX2 bietet 256-Bit-ymm-Vektoren
    • Die Register selbst haben keine feste Lane-Zahl; die Instruktion bestimmt, wie die Lanes interpretiert werden
    • vpaddb interpretiert ymm beispielsweise als i8x32
  • Typischerweise stehen folgende Operationen zur Verfügung
    • Bitweise Operationen: Die Lane-Breite ist implizit immer 1 Bit
    • Lane-wise Arithmetik: Addition, Subtraktion, Multiplikation, Division, Integer-Shift, min/max usw.
    • Lane-wise Vergleiche: Erzeugen einen Mask Vector wie m[i] = a[i] < b[i]
    • Select: Wählt mithilfe einer Maske pro Lane Werte aus zwei Vektoren aus
    • Shuffle/Swizzle: Betrachtet einen Vektor als Lookup Table und ordnet die Lanes anhand eines Index-Vektors neu an
  • True/False in einem Mask Vector verwendet meist Bitmuster aus lauter Einsen oder lauter Nullen
  • Vergleiche und Select sind zentrale Werkzeuge, damit SIMD-Code branchless bleibt
  • Branchless Code führt unabhängig von der Eingabe dieselben Operationen aus und verwirft unnötige Ergebnisse über Eigenschaften wie x * 0 = 0 oder a ^ b ^ a = b

Datenpositionen mit Shuffle anpassen

  • Shuffle ist in SIMD ein zentrales Werkzeug, um Daten an die „richtige Position“ zu bringen
  • Broadcast oder Splat erzeugt einen Vektor, in dem alle Lanes denselben Skalarwert haben; das lässt sich als Index-Shuffle [0, 0, ...] ausdrücken
  • Interleave oder Zip/Pack ordnet die Lanes zweier Vektoren a und b abwechselnd an
    • c = [a[0], b[0], a[1], b[1], ...]
    • Das lässt sich mit shuffle2 implementieren
  • Deinterleave oder Unzip/Unpack ist das Gegenstück zu Interleave
  • Rotate rotiert Lanes in der Form b[i] = a[(i + j) % n]; auch das ist ein Shuffle
  • In der SIMD-Programmierung werden Datenblöcke, die größer als Integer sind, häufig als kleinere Blöcke unterschiedlicher Größe neu interpretiert und umgeordnet

Intrinsics, Target Features, Portable SIMD

  • Die in SIMD verfügbaren Operationen hängen von der Architektur und den Instruction-Set-Erweiterungen ab.
  • x86 kann Operationen haben, die ARM nicht bietet, und selbst innerhalb desselben Herstellers gibt es Erweiterungen wie Intel AVX-512, die nur auf High-End-Serverchips verfügbar sind.
  • Toolchains verallgemeinern solche Erweiterungen als Target Features.
    • lscpu unter Linux zeigt die Features, die die CPU erkennt.
    • LLVM wählt je nach Feature-Einstellung andere Instruktionen aus.
    • Erst mit +avx2 kann LLVM Code ausgeben, der ymm verwendet.
  • -march=native oder -Ctarget-cpu=native können guten Code für die Build-Maschine erzeugen, können aber die Portabilität auf andere Prozessoren verringern.
  • Runtime Feature Detection ist ein Verfahren, bei dem geprüft wird, welche Funktionen die CPU unterstützt, um zu entscheiden, welche Funktionsversion aufgerufen wird; es wird in Code eingesetzt, der wie Kryptografie-Bibliotheken auf viele verschiedene Geräte verteilt wird.
  • SIMD-Code in C++ verwendet üblicherweise Intrinsics wie _mm256_cvtps_epu32.
    • Sie repräsentieren Low-Level-Operationen eines bestimmten Instruction Sets.
    • Sie werden nicht zwingend auf eine einzelne Instruktion abgebildet.
    • Der Compiler kann Zusammenführen, Eliminierung von Duplikaten und Optimierungen bei der Instruktionsauswahl durchführen.
  • Wenn man für mehrere Instruction Sets immer wieder ähnlichen Code schreibt, kann der Wartungsvorteil gegenüber Assembly gering ausfallen.
  • Portable-SIMD-Bibliotheken verfolgen den Ansatz, einen Teil der Instruktionsauswahl auf Bibliotheksebene zu behandeln und den Rest dem Compiler zu überlassen.
  • Die Implementierung von vb64 ist ein Experiment, um zu prüfen, ob Rusts portable SIMD konkurrenzfähigen Code erzeugt.

Base64-Dekodierung auf SIMD umstellen

  • Base64 ist ein Verfahren, um beliebige Binärdaten als ASCII zu kodieren.
  • Die Eingabe-Bytefolge wird als Bitvektor betrachtet und in 6-Bit-Chunks, sogenannte Sextets, aufgeteilt.
  • Sextet-Werte werden auf die folgenden Zeichen abgebildet:
    • 0..25 → 'A'..'Z'
    • 26..51 → 'a'..'z'
    • 52..61 → '0'..'9'
    • 62 → +
    • 63 → /
  • Es gibt mehrere Base64-Varianten, aber der Großteil der Komplexität ist gemeinsam.
  • Zwei Punkte sind zu beachten:
    • Base64 ist ein Format, bei dem die Bits innerhalb eines Bytes big endian sind.
    • Die Eingabelänge ist nicht unbedingt durch 4 teilbar; prinzipiell wird sie mit =-Padding auf ein Vielfaches von 4 gebracht, aber auch Nachrichten mit nicht korrektem Padding können verarbeitet werden.
  • Die decoded length wird berechnet, indem zu input / 4 * 3 die Restlänge entsprechend input % 4 addiert wird.

Grundlegendes Refactoring hin zu Branchless

  • Ein einfacher Base64-Decoder enthält mehrere Branches:
    • die Schleife, die die Eingabe in Chunks durchläuft
    • die Byte-Schleife innerhalb eines Chunks
    • das match je ASCII-Zeichen
    • return Err bei Fehlern
    • das match innerhalb von decoded_len
    • mögliche Aufrufe von Vec::extend_from_slice und des Allocators
  • Die Optimierungsrichtlinie lautet, alle Branches zu entfernen.
  • Das match in decoded_len bildet die Werte 0, 1, 2, 3 von input % 4 auf 0, 1, 1, 2 ab.
  • Ersetzt man dies durch mod4 - mod4 / 2, erhält man eine branchless Version.
  • LLVM kann das ursprüngliche match zwar zu einer Switch Table zusammenfassen, doch in diesem Bereich senken unnötige Speicherzugriffe die Performance.

Den heißesten Loop isolieren

  • Die Stärke von SIMD liegt darin, viele Daten auf einmal zu verarbeiten, Loops stark zu unrollen und sie nahezu branchless zu machen.
  • Ziel des Hot Loops ist es, maximal 4 Bytes zu lesen, maximal 3 Bytes Dekodierergebnis zu erzeugen und außerdem anzugeben, ob ein Syntaxfehler vorliegt.
  • Drei Tatsachen lassen sich nutzen:
    • Die Ausgabelänge kann mit dem branchless decoded_len() berechnet werden.
    • Ungültiges Base64 wird als sehr seltener Pfad betrachtet; falls die Fehlerposition benötigt wird, kann anschließend erneut gescannt werden.
    • Da A in Base64 den Wert 0 hat, ändert sich der Wert nicht, wenn ein gekürzter Chunk mit A gepaddet wird.
  • decode_hot() wird so abgetrennt, dass es vier Eingabe-Bytes verarbeitet und das Dekodierergebnis sowie ein boolesches Erfolgssignal zurückgibt.
  • Gibt man statt Option<[u8; 3]> ein separates bool zurück, lässt sich der spätere Branch if !ok leichter entfernen.
  • In der SIMD-Version wird Simd<u8, 4> als Eingabe verwendet, und auch die Ausgabe bleibt entsprechend der Lane-Anzahl als Zweierpotenz bei Simd<u8, 4>.
    • Tatsächlich benötigt werden 3 Ausgabe-Bytes.
    • Die letzte Lane wird nicht verwendet.

ASCII in Sextets umwandeln

  • Der Großteil des match, das ASCII-Zeichen in Sextets umwandelt, lässt sich als byte - C ausdrücken.
    • 'A'..'Z' → byte - 'A'
    • 'a'..'z' → byte - 'a' + 26
    • '0'..'9' → byte - '0' + 52
    • '+' → byte - '+' + 62
    • '/' → byte - '/' + 63
  • Man kann einen Offset-Vektor pro Lane bilden und ascii - offsets ausführen.
  • Der erste Ansatz ist Compare-and-Select.
    • Für A-Z, a-z, 0-9, + und / werden Masken erzeugt.
    • Eine Lane, in der keine Maske ausgewählt wurde, gilt als invalid.
    • Der zur jeweiligen Maske passende Offset wird gesplatet und per OR zusammengeführt.
  • Dieser Ansatz kann eleganten und konkurrenzfähigen Code erzeugen, benötigt aber insgesamt 8 Vergleiche und kann wegen vieler live Werte Register Pressure erzeugen.

SIMD-Hash-Tabelle und Perfect Hash

  • Die Bytebereiche von A-Z, a-z und 0-9 sind jeweils 0x41..0x5b, 0x61..0x7b und 0x30..0x3a; ihre High Nibbles unterscheiden sich.
  • + und / sind 0x2b und 0x2f, daher lassen sie sich größtenteils allein mit byte >> 4 unterscheiden.
  • Wenn man im Fall von / eins abzieht, ergibt sich ein Perfect Hash für die Bereiche.
  • Das Mapping von (byte >> 4) - (byte == '/') sieht wie folgt aus:
    • A-Z → 4 oder 5
    • a-z → 6 oder 7
    • 0-9 → 3
    • + → 2
    • / → 1
  • Da diese Werte klein sind, lässt sich eine Offset-Lookup-Tabelle in einen SIMD-Vektor legen und per Shuffle nachschlagen.
  • Diese Perfect-Hash-Idee wurde von einem anonymen Nutzer in einem GitHub-Issue vorgeschlagen.
  • Simd::swizzle_dyn() hat die Einschränkung, dass das Index-Array und die Länge der Lookup-Tabelle gleich sein müssen.
  • Beim Perfect-Hash-Ansatz erhält man die Validierung nicht als Nebeneffekt der Sextet-Berechnung; daher wird zur Prüfung der Byte-Gültigkeit der Exact Bloom Filter aus demselben GitHub-Issue verwendet.
  • Ein Implementierungsbeispiel findet sich in simd.rs von vb64.

Vier Sextets in drei Bytes packen

  • Der Schritt, vier 6-Bit-Sextets zu drei Bytes zusammenzuführen, ist anspruchsvoller.
  • Wenn man ein bestimmtes Eingabe-Sextet auf all-ones setzt und prüft, wohin sich die Bits in der Ausgabe bewegen, lässt sich die Anordnung nachverfolgen.
  • Ein Shuffle auf Byte-Ebene allein reicht nicht aus.
    • Das Ziel, zu dem verschoben werden muss, ist ein Byte-Fragment.
    • Auch Shift allein reicht nicht aus.
    • Overshiftete Bits müssen in die benachbarte Lane wandern.
  • Die Lösung besteht darin, die Lanes größer zu machen.
  • sextets wird in einen u16-Vektor gecastet und anschließend pro Lane geshiftet.
    • input[0] wird um 2 Bit geshiftet.
    • input[1] wird um 4 Bit geshiftet.
    • input[2] wird um 6 Bit geshiftet.
    • input[3] wird um 8 Bit geshiftet.
  • Aus dem Shift-Ergebnis werden Low-Byte- und High-Byte-Vektoren getrennt.
  • Mit hi.rotate_lanes_left::<1>() wird das Stück auf der High-Byte-Seite an die benachbarte Lane angepasst und anschließend mit lo | hi_rotated zusammengeführt.
  • Dieser Ansatz nutzt Hardware-Primitives aktiv aus und erzeugt daher kleinen und effizienten Code.

Erweiterung der Lane-Anzahl und Entfernen von Garbage-Lanes

  • Da Simd<u8, 4> kleiner ist als das minimale 128-Bit-Vektorregister auf x86, wurde decode_hot() generisch über die Lane-Anzahl N gemacht
  • Die Einschränkung LaneCount<N>: SupportedLaneCount stellt kleine Lane-Anzahlen sicher, die Potenzen von zwei sind
  • Lookup-Tabelle und Shift-Tabelle erzeugen mit dem Helper tiled() Vektoren mit wiederholtem Muster
  • Bei N = 4 reichte es, den Garbage-Wert in der letzten Lane zu ignorieren; wird N größer, mischt sich jedoch in jede vierte Lane Garbage
  • Zum Entfernen wird ein Shuffle verwendet
    • Die gewünschte Beziehung lautet shuffled[i] = output[i + i / 3]
    • Bei jedem vierten Index wird übersprungen, um die Garbage-Lane zu löschen
    • Der überlaufende Teil ist das obere Viertel des finalen Ausgabevektors und wird daher ignoriert
  • So kann decode_hot::<32>() 32 base64-Bytes parallel dekodieren

Optimierung der äußeren Schleife

  • Auch decode() wurde generisch über die interne Lane-Anzahl N gemacht
  • Die verbleibenden Kosten sind:
    • der Längenvergleichs-Branch in for chunks in ...
    • das memcpy variabler Länge von [T]::copy_from_slice
    • der ok-Branch in jeder Loop-Iteration
    • ein möglicher Allocator-Aufruf von Vec::extend_from_slice und ein weiteres memcpy
  • Da die Ausgabelänge bekannt ist, wird mit out.reserve(final_len + N / 4) vorab Speicher reserviert
  • Zusätzlich wird Slop-Speicher vorgesehen, um statt eines memcpy variabler Länge einen vollständigen SIMD-Store auszuführen
  • Jede Iteration schreibt den gesamten SIMD-Vektor, und der nächste Schreibvorgang rückt um 3/4 * N weiter und überschreibt dabei das vorherige Garbage-Byte
  • Das letzte Garbage-Byte ist nicht in Vec::set_len() enthalten und wird daher so behandelt, als wäre es gelöscht
  • Selbst wenn wegen if !ok ein Early Return erfolgt, wurde nicht per set_len() committet; out bleibt daher unverändert

Fehlerbehandlung aus dem Hot Loop verschieben

  • Statt in jeder Iteration mit if !ok zurückzukehren, wird mit error |= !ok akkumuliert
  • Erst unmittelbar vor dem finalen set_len() wird einmal geprüft, ob ein Fehler vorliegt
  • Unter der Annahme, dass die meisten base64-Blobs valide sind, wird der Fehlerpfad aus dem Hot Loop herausgeschoben
  • Selbst bei einem Syntaxfehler verhalten sich die nachfolgenden SIMD-Operationen nicht willkürlich falsch, sodass Garbage-Writes nicht committet werden und verschwinden
  • Spätere Aufrufe wie Vec::push() können denselben Pufferbereich überschreiben

Unroll and Jam und Behandlung des Rests

  • Um memcpy variabler Länge durch copy_from_slice zu reduzieren, wird Unroll and Jam angewendet
  • Die Schleife wird in zwei Teile aufgeteilt
    • Hot vectorized loop: verarbeitet immer Eingaben der Länge N
    • Cold remainder part: verarbeitet höchstens einmal Eingaben mit i < N
  • Mit Rusts Iterator::chunks_exact() wird ein handgeschriebenes Unroll-and-Jam umgesetzt
  • Im Hot Loop wird Simd::from_slice() aufgerufen, um einen einzelnen Load in Vektorgröße auszuführen
  • Bounds Checks liegen dadurch in einer Form vor, die der Compiler leicht entfernen kann

Benchmarks und Optimierung durch manuelles Laden

  • Die Benchmarks dekodieren Nachrichten mit Längen von 0 bis etwa 200 oder 500 Byte und vergleichen sie mit der Baseline-base64-Implementierung von crates.io
  • Als Compiler-Optionen werden -Zbuild-std und -Ctarget-cpu=native verwendet
  • Das Tuning ergab, dass N = 32 am besten war; pro Hot-Loop-Iteration wird ein YMM-Register verwendet
  • Anfangs wurde die Baseline geschlagen, aber es traten heartbeat-artige Leistungsschwankungen auf, die stark mit data.len() % 32 korrelierten
  • Nach Prüfung des Assembly wurde geschlossen, dass copy_from_slice offenbar als Byte-für-Byte-Load-Loop inlined/unrolled wurde
  • Simd::gather_or() wurde ebenfalls ausprobiert, erzeugte aber schlechteres Assembly und wurde daher nicht verwendet
  • Stattdessen wurde eine manuelle Loading-Funktion für Daten variabler Länge geschrieben
    • Der Hot Part führt in der Schleife möglichst große skalare Loads aus, nämlich u128-Loads
    • LLVM senkt 16-Byte-Chunks auf XMM-Loads ab
    • Der Remainder nutzt überlappende u64-, u32- und u8-Loads
  • Beim Lesen von 15 Byte wird bei p ein u64 und bei p + 7 ein u64 gelesen, sodass sich 1 Byte überlappt; anschließend wird per OR kombiniert
  • Für 4–7 Byte werden überlappende u32-Loads verwendet
  • Für 1–3 Byte wird bei p, p + len/2 und p + len - 1 gelesen; dabei können einige Bytes doppelt geladen werden, aber die Anzahl der Branches sinkt
  • Nach Anwendung des neuen Loading-Codes wurde die Varianz sehr klein, und gegenüber der Baseline zeigte sich über fast den gesamten Bereich hinweg doppelte Performance

Encoding und web-safe base64

  • Für die Encoding-Funktion genügt es, encode_hot() zu implementieren, das die Operationen von decode_hot() umkehrt
  • Der beim Decoding verwendete Perfect Hash passt nicht zum Encoding; dafür ist ein neuer Hash nötig
  • Auch der Loading-/Storing-Code rund um den Encoder unterscheidet sich etwas vom Decoder
  • vb64 implementiert auch eine effiziente Encoding-Routine
  • Web-safe base64 ist eine Variante, die + und / durch - und _ ersetzt
  • Die Konstruktion eines Perfect Hash für web-safe base64 ist schwieriger; als Beispiel könnte ein Ansatz wie (byte >> 4) - (byte == '_' ? '_' : 0) nötig sein
  • vb64 unterstützt web-safe base64 noch nicht

Fazit

  • vb64 ist keine Bibliothek, die einen wichtigen Bottleneck beseitigen soll; es wird erklärt, dass kein Ort bekannt ist, an dem base64-Decoding tatsächlich der Bottleneck ist
  • Branchless Code ist oft übertrieben, hilft aber dabei zu verstehen, was Compiler leisten können und was nicht
  • Rusts std::simd ist insgesamt gut und erzeugt hervorragenden Code
  • Es gibt zwar Rough Edges, deren Behebung SIMD-Code einfacher machen würde, aber mit dem aktuellen Arbeitsergebnis zeigt man sich zufrieden
  • SIMD und Performance-Optimierung sind komplexe Themen, die viele Tricks und Hardwarewissen erfordern; vieles davon ist nicht dokumentiert

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-11-29
Hacker-News-Meinungen

  • Es war interessant zu sehen, dass portable SIMD tatsächlich verwendet wird, und als ich den Benchmark auf einem Zen-3-System reproduziert habe, ergab sich derselbe Geschwindigkeitszuwachs.
    Auf einem M1 MacBook Pro begann der Leistungsgewinn bei einer Eingabelänge von 110 Byte bei 1,4× und stieg allmählich auf 2×; das ist zwar weniger als auf x86_64, aber das Ziel scheint erreicht zu sein.
    Allerdings bestätigt der Code meine Erfahrung, dass Rust bei SIMD- und Pointer-bezogener Arbeit – und allgemeiner im Performance Engineering – eine ziemlich schlechte Ergonomie hat.

    • Aus Sicht eines Rust-Engineers stimme ich dem bis zu einem gewissen Grad zu, aber Pointer- und Raw-Memory-Arbeit ist aus Sicherheitsgründen absichtlich stark eingeschränkt, und die Sprache hat auch den Aspekt, einen wirklich darüber nachdenken zu lassen, was man tut.
      Trotzdem ist Rusts portable SIMD im Vergleich zu C++ noch keine schöne Geschichte, und wenn man auf rohe Bytebereiche, Pointer und Buffer-Manipulation herunter will, muss man mit Pin, MaybeUninit und Ähnlichem vertraut sein.
      portable_simd und allocator_api sind seit Jahren instabil, haben eine hohe Einstiegshürde und sind noch sperriger, was aber größtenteils beabsichtigtes Design ist.
      Allerdings hindert einen nichts daran, innerhalb des eigenen Programms angenehmere Abstraktionen zu bauen oder Third-Party-Crates zu verwenden.
    • Ich stimme nicht zu, dass die Ergonomie schlecht ist.
      C++-SSE-Intrinsics sind mit ihren Unterstrichen hässlich und mit ihren Namen schwer zu merken, also deutlich schlimmer.

  • Ich habe einmal eine klassische C++-Implementierung nach bestem Können geschrieben, und manchmal ist es wirklich erstaunlich, wenn jemand mit einer SIMD-Version kommt, die mehr als 10× schneller ist.
    Dafür ist dieser Code weniger portabel.
    Ich wünschte, die automatische Vektorisierung der Compiler würde besser, und es gäbe auch Unterstützung wie Annotationen auf Sprachebene, mit denen man lokal bestimmte Umordnungen von Operationen erlauben kann.

    • Guter SIMD-Code muss sehr sorgfältig berücksichtigen, wie Daten im Speicher angeordnet sind.
      Außerhalb eines sehr lokalen Kontexts kann der Compiler die Daten nicht einfach für einen umstrukturieren, weshalb automatische Vektorisierung wirklich schwierig wird.
    • Selbst wenn der Compiler perfekt optimieren könnte, gibt es viele unvermeidbare Garantien für serielle Ausführung.
      Zum Beispiel gilt bei for(double v: vec) sum+=v, dass Gleitkommaaddition nicht assoziativ ist; daher ist es nicht dasselbe, die Werte der Reihe nach zu addieren, wie bei SIMD in 8er-Abständen zu addieren und anschließend die Reste zusammenzuführen.
      Aus Sicht des Compilers mag das wie eine offensichtliche Optimierung wirken, aber solange man ihm nicht sagt, dass bestimmte Garantien gelockert werden dürfen, priorisiert er die Garantie serieller Semantik gegenüber der Optimierung.
      Dadurch wird es unübersichtlich, und wie janwas sagt, halte ich es für besser, für Hot Paths Bibliotheken zu verwenden, insbesondere Google Highway oder Intel ISPC.
    • Das ist einer der Punkte von Systemprogrammiersprachen wie C++.
      Sie versuchen, möglichst portabel effizient zu sein, machen aber zugleich zielsystemspezifische Programmierung leicht, wenn man sie braucht.
      Automatische Vektorisierung beherrschen FORTRAN-Compiler eindeutig besser, weil Aliasing dort nicht erlaubt ist.
      C++ wird dadurch ausgebremst, dass es dem Speichermodell von C folgt.
    • Man könnte auch einfach CUDA verwenden.
      CUDA ist C++ für GPUs, die ultimative SIMD-Maschine unserer Zeit, und ROCm ist im Grunde CUDA für AMD.
      Persönlich mochte ich Microsofts C++AMP, das meiner Ansicht nach am einfachsten zu erlernen war.
      Schade nur, dass es sich letztlich nicht durchgesetzt hat.
    • Nach meiner Erfahrung passiert so etwas häufig.
      Außerdem kann man es mit SIMD-Wrapper-Bibliotheken in der Praxis ziemlich portabel machen.

  • Als kleine Anmerkung: Der Compiler konnte die betreffende popcount-Implementierung nicht zu einer einzelnen Instruktion optimieren, bei anderen Implementierungen ist das aber möglich.
    Natürlich ist es ziemlich knifflig: https://godbolt.org/z/T69KxWWW8

  • Es hieß, _mm256_cvtps_epu32 stelle eine Low-Level-Operation eines bestimmten Befehlssatzes dar und sei ein float-to-int-Cast in AVX2, aber diese Instruktion gehört zu AVX-512.
    AVX2 hat keinen float-to-int-Cast, und in AVX1 ist das Integer-Ergebnis signed; die Instruktion heißt _mm256_cvtps_epi32.

  • Ich frage mich, wie es im Vergleich zu fastbase64[0] abschneidet.
    Der Artikel ist hervorragend, und es ist schön, solche Inhalte online zu sehen, aber den Optimismus des Autors gegenüber portable SIMD libraries kann ich nicht ganz teilen.
    [0]: https://github.com/lemire/fastbase64

  • Ich denke, ISPC ist schlicht besser, als SIMD an C++ oder Rust anzuflanschen.
    Es unterstützt auch dynamisches Dispatching, eine Funktion, die selbst zu implementieren schmerzhaft ist.

    • Wenn ein Tool mehr Menschen dazu bringt, SIMD zu nutzen, ist das im Allgemeinen eine gute Sache, aber persönlich bevorzuge ich es, wenn SIMD in derselben Toolchain integriert ist.
      So kann man Inline-Aufrufe zurück nach C++ machen, in SIMD-Code Templates und Klassen verwenden und mehrere SIMD-Codebereiche gemeinsam inlinen.
      Ich stimme zu, dass dynamisches Dispatching schwer zu implementieren ist, aber Highway kümmert sich um diesen Teil.
    • Ich frage mich, ob es bei kleinen Subroutinen wie im Artikel einfach ist, ISPC aus C++ oder Rust aufzurufen.

  • Ein hervorragender Artikel, und er hinterlässt stark das Gefühl: „So schlau werde ich nie sein.“

    • Es ist einfach nicht dein Arbeitsgebiet.
      So ähnlich, wie normale Menschen keine Software Engineers oder Physiker sind.
      Wenn man sich ein paar Monate konzentriert damit beschäftigt, kann man ein ähnliches Niveau erreichen.
    • Wenn du Gelegenheit hast, einen Arbeitgeber oder ein Projekt zu finden, bei dem so etwas gebraucht wird, kannst du vermutlich „so schlau werden“.
      Am Ende ist es eine Frage von Interesse und Bedarf.
      Ich selbst mache in persönlichen Projekten immer wieder Performance-Optimierung oder eher systemnahes Bare-Metal-Engineering, aber ich wünschte, es wäre im Job stärker gefragt.
      Die meisten Aufgaben in der Branche verlangen allerdings nicht danach.
    • Es lohnt sich, AoC ’23 mit APL/j/k, BQN, Python/numpy, CUDA usw. zu machen.
      Also nicht idiomatisches Python, sondern alles mit numpy lösen.
      Das macht Spaß, man kann diese Art von Cleverness lernen, und vieles im Artikel wirkt aus der Denkweise heraus, mit der man Probleme in solchen Sprachen löst, sehr natürlich.
      Mit der Zeit beginnt man, Probleme in dieser Form zu sehen.
    • https://fgiesen.wordpress.com/2016/02/05/smart/

  • Interessanter Artikel
    Im ersten Beispiel am Anfang heißt es, dass eine nicht vektorisierte popcnt-Implementierung „ehrlich gesagt lächerlich schlechten Code“ erzeugt. Im Release-Modus mit nativer Ziel-CPU scheint diese Funktion jedoch ziemlich ordentlich vektorisiert zu werden.
    https://godbolt.org/z/WE1Eq65jY

    • Der folgende Code sollte dieselbe Ausgabe erzeugen:
      pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
      Das wird zu popcnt eax, edi; ret kompiliert.
      Bei großen Bitvektoren kann eine AVX2-Implementierung schneller sein als POPCNT.
      Siehe „Faster Population Counts Using AVX2 Instructions“: https://academic.oup.com/comjnl/article/61/1/111/3852071
      32 Bit sind nicht groß genug, und der von Rust erzeugte Code ist tatsächlich lächerlich schlecht.
    • Idealerweise sollte das wohl auf die popcnt-Instruktion abgesenkt werden.
    • Automatische Vektorisierung funktioniert mal und mal nicht.
      Kürzlich habe ich Code geschrieben, der die Anzahl der Bits in der Ergebnis-Maske einer Vektoroperation zählen musste; das wurde sauber zu popcnt umgewandelt.
      https://godbolt.org/z/zT9Whcnco

  • Wegen Stellen wie „Das klingt wie eine Fangfrage … ist es nicht einfach add?“ möchte man normalerweise eher auf eine intermediäre Vektordarstellung abzielen und die Details dem Compiler überlassen.
    Haswell-Chips hatten zum Beispiel mehrere Gleitkomma-Ausführungseinheiten pro Kern, und die CPU konnte mehr als eine pipelined Gleitkommaoperation gleichzeitig ausführen; von den add-Instruktionen war jedoch nur eine möglich.
    Wenn es viele Additionen gab, die nicht vom vorherigen Ergebnis abhingen, sodass sich Latenz vermeiden ließ, konnte man zusätzlich eine Fused-Multiply-Add-Instruktion mit einem Multiplikationsfaktor von 1 mitschicken und so den Additionsdurchsatz verdoppeln.
    Diese Instruktion konnte gleichzeitig mit einer normalen Vektor-Gleitkommaaddition ausgeführt werden.