Warum alle Entwickler SIMD kennen sollten

 (mitchellh.com)
1 Punkte von GN⁺ 2 시간 전 | 1 Kommentare | Auf WhatsApp teilen
  • SIMD ist keine komplizierte Technik nur für Software mit maximaler Performance, sondern ein alltägliches Optimierungsmittel, das gewöhnliche Schleifen beschleunigt, indem es zusammenhängende Daten mehrere Werte auf einmal verarbeitet
  • Typischer SIMD-Code folgt einer 5-Schritte-Struktur: Konstanten-Broadcast, Iteration in Vektoreinheiten, parallele Operationen, Reduktion bzw. Speichern der Ergebnisse und Verarbeitung des skalaren Rests
  • Die Codepoint-Suchschleife von Ghostty vergleicht jeweils 4, 8 oder 16 u32-Werte auf einmal und kann den theoretischen Durchsatz auf ARM NEON um bis zu 4×, mit AVX2 um 8× und mit AVX-512 um 16× erhöhen
  • Auf einem Intel-Desktop mit AVX2 wurde der gesamte Terminal-Durchsatz um etwa 5× schneller; wenn keine unterstützte Vektorbreite vorhanden ist oder Eingaben übrig bleiben, verarbeitet die bestehende skalare Schleife die gesamte Eingabe bzw. den Rest
  • Die Auto-Vektorisierung von Compilern kann selbst bei einfachen Schleifen Chancen verpassen; man sollte daher zunächst die optimierte Ausgabe prüfen, wichtige Hot Loops aber mit explizitem SIMD in Verhalten und Performance vorhersehbar halten

Was SIMD macht

  • SIMD ermöglicht es der CPU, mit einer einzigen Instruktion mehrere Werte parallel zu verarbeiten
    • Statt Bytes einzeln zu vergleichen, lassen sich 4, 8 oder mehr auf einmal vergleichen
    • Schleifen wie for (byte in bytes), for (character in string) oder for (value in array) bieten die Chance, auf Verarbeitung in Vektorbreite umgestellt zu werden
  • Wenn die Daten Hunderte, Tausende oder Millionen Bytes umfassen, lässt sich je nach Parallelbreite eine lokale Beschleunigung um 4×, 8× oder mehr erzielen
  • Wenn es nur um einige wenige oder einige Dutzend Werte geht, lohnt sich SIMD nicht
  • simdutf und simdjson verwenden komplexe SIMD-Techniken, aber alltägliches SIMD muss nicht annähernd so kompliziert sein
  • Die Beispiele verwenden Zig, doch die 5-Schritte-Struktur gilt auch für andere Sprachen; wie SIMD-Instruktionen unterstützt werden, unterscheidet sich je nach Sprache

Die wiederkehrende 5-Schritte-Struktur

  1. Benötigte Konstanten auf alle Lanes broadcasten und bei Bedarf Vektor-Akkumulatoren initialisieren
  2. Die Eingabe jeweils in Vektorbreite durchlaufen
  3. Vergleiche oder arithmetische Operationen auf allen Lanes parallel ausführen
  4. Die Vektorergebnisse passend zum Algorithmus reduzieren oder speichern
  5. Reste, die nicht in einen vollständigen Vektor passen, mit der bestehenden Schleife als skalaren Rest (scalar tail) verarbeiten
  • Wenn man mit dieser Struktur vertraut ist, kann man gewöhnliche Schleifen in dieselben 5 Schritte zerlegen; SIMD-Code wird dadurch so einfach wie eine skalare Schleife
  • Lässt sich eine Schleife nicht einfach in dieser Struktur ausdrücken, ist es vorerst sinnvoll, auf SIMD zu verzichten

Die reale Suchschleife in Ghostty

  • Ghostty verbraucht Daten aus einem Array dekodierter Codepoints, bis es auf einen Wert von 0xF oder kleiner trifft
    • Der Großteil der Terminaldaten sind normale auszugebende Zeichen, daher werden sie gebündelt verarbeitet
    • Die Schleife findet das Ende des nächsten ausgabefähigen Bereichs so schnell wie möglich
  • Die ursprüngliche skalare Implementierung prüft die Codepoints einzeln
while (end < cps.len and cps[end] > 0xF) end += 1;
  • Die Vektorimplementierung verwendet generische Vektoren ohne CPU-spezifische Built-ins und ist nur 12 Zeilen länger als die skalare Implementierung
  • Die erwartete Durchsatzsteigerung entspricht der Anzahl der Vektor-Lanes
    • ARM NEON und Apple Silicon: bis zu 4×
    • AVX2, das die meisten modernen x86-CPUs unterstützen: bis zu 8×
    • AVX-512, das einige Intel-CPUs und AMD Zen 4 oder neuer unterstützen: bis zu 16×
  • Auf einem Intel-Desktop mit AVX2 wurde der gesamte Durchsatz vom Eingabestrom eines Terminalprogramms bis zum finalen Terminalzustand um etwa 5× schneller
    • Wegen der Arbeit rund um SIMD wird nicht die gesamte theoretische Beschleunigung erreicht
  • C0-Steuerzeichen existieren auch jenseits von 0xF, aber 0xF ist der in diesem Ghostty-Codepfad verwendete Schwellenwert
    • ESC und andere Steuersequenzen werden in einem separaten Pfad verarbeitet

Schritt 1: Konstanten-Broadcast

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
  • Ghosttys simd.lanes(u32) gibt zurück, wie viele u32-Werte die Ziel-CPU gleichzeitig verarbeiten kann
    • Jeder einzelne Wert wird Lane genannt
    • ARM gibt 4 zurück, AVX2 8 und AVX-512 16
    • Gibt es keine nutzbare Vektorgröße, wird null zurückgegeben und der SIMD-Code übersprungen
  • @Vector(lanes, u32) erzeugt einen Vektortyp mit dieser Anzahl an Lanes
    • Wenn lanes 8 ist, enthält ein V acht u32-Werte, die parallel verarbeitet werden können
  • Für einen Vektorvergleich müssen beide Seiten Vektoren sein, daher repliziert @splat(0xF) den Wert 0xF auf alle Lanes
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
  • Dieser Algorithmus benötigt keinen Vektor-Akkumulator, andere Algorithmen könnten in diesem Schritt jedoch einen Akkumulator initialisieren

Schritt 2: Einen Vektor nach dem anderen durchlaufen

while (end + lanes <= cps.len) : (end += lanes) {
    const values: V = cps[end..][0..lanes].*;
  • Wenn lanes 8 ist, wird die Schleife nur betreten, wenn mindestens 8 Werte übrig sind; diese 8 werden in values geladen
  • Am Ende jeder Iteration wird end nicht um 1, sondern um die Anzahl der Lanes erhöht
  • Da ein vollständiger Vektor geladen werden können muss, wird bei nur noch 5 verbleibenden Werten kein 8-Lane-Vektor gelesen
  • Werte, die nicht in einen Vektor passen, werden in Schritt 5 vom skalaren Rest verarbeitet

Schritt 3: Paralleler Vergleich aller Lanes

const greater_than_threshold = values > threshold;
  • Da values und threshold beide Vektoren sind, vergleicht > die jeweils entsprechenden Lanes als eine Vektoroperation
  • Bei 8 Lanes werden die 8 Vergleiche, die cps[end] > 0xF entsprechen, parallel ausgeführt
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              {  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
  • Es gibt keine explizite innere Schleife; das Ergebnis ist ein Vektor mit booleschen Werten pro Lane
  • Dieselbe Struktur lässt sich nicht nur auf Vergleiche anwenden, sondern auch auf Operationen, die der Vektortyp unterstützt, etwa Addition, Multiplikation, Minimum oder Maximum
  • Der Vergleich selbst ist eine Vektoroperation, aber für das Laden des Vektors, die Ergebnisreduktion und die Suche nach der fehlgeschlagenen Lane sind zusätzliche Instruktionen nötig

Schritt 4: Vektorergebnis reduzieren

if (@reduce(.And, greater_than_threshold)) continue;
  • @reduce(.And, ...) kombiniert alle booleschen Werte mit and zu einem einzelnen booleschen Wert
  • Wenn alle Lanes true sind, geht es mit dem nächsten Vektor weiter; ist auch nur eine false, wird die exakte Position des Fehlschlags gesucht
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
  • @bitCast wandelt den Booleschen Vektor in eine Integer-Maske mit 1 Bit pro Lane um
    • 1 bedeutet, dass der Wert größer als 0xF ist
    • 0 bedeutet, dass der Vergleich fehlgeschlagen ist
  • Wird die Maske invertiert, wird der fehlgeschlagene Vergleich zu 1, und @ctz zählt die Anzahl der 0-Bits vor der ersten 1
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask:                   {    1,    1,    1,     0,    1,    1,    1,    1 }
~mask:                  {    0,    0,    0,     1,    0,    0,    0,    0 }
  • In diesem Beispiel gibt @ctz(~mask) den Wert 3 zurück und verschiebt end auf Lane 3, wo sich das erste Steuerzeichen 0x0A befindet
  • Die Ergebnisreduktion ist von den 5 Schritten der Teil, der sich je nach Algorithmus am stärksten unterscheidet
    • Eine Summe kann einen Vektor-Akkumulator auf eine einzelne Zahl reduzieren
    • Eine Transformation kann den ganzen Vektor in einen Ausgabepuffer speichern
    • Diese Suche erzeugt eine Bitmaske, um die Position einer bestimmten Lane zu finden

Schritt 5: Skalaren Rest verarbeiten

while (end < cps.len and cps[end] > 0xF) end += 1;
  • Wenn die Eingabelänge kein exaktes Vielfaches der Vektorbreite ist, verarbeitet die ursprüngliche skalare Schleife den Rest
  • Nach einer 8-Lane-Vektorschleife können 0 bis 7 Werte übrig bleiben
  • Auf CPUs, bei denen simd.lanes(u32) null ergibt, wird der SIMD-Abschnitt übersprungen und die skalare Schleife verarbeitet die gesamte Eingabe
  • Die ursprüngliche Implementierung übernimmt zugleich Restverarbeitung und Kompatibilitäts-Fallback
  • Generische Vektoren entfernen nur die CPU-spezifische Syntax, nicht aber die CPU-spezifische Codegenerierung
    • Zig übersetzt Vektoroperationen in die auf dem Ziel aktivierten Instruktionssätze

Was Auto-Vektorisierung übersieht

  • Compiler können einfachen Code auto-vektorisieren, etwa regelmäßige arithmetische Schleifen ohne komplexen Kontrollfluss
  • Bevor man manuelles SIMD schreibt, sollte man die skalare Version mit Optimierungsoptionen kompilieren und den generierten Code prüfen
  • Produktionscompiler verpassen häufig Vektorisierungsmöglichkeiten; Auto-Vektorisierung wird seit Jahrzehnten erforscht, doch auch neuere Forschung setzt bei diesem Problem an
  • Wenn eine Schleife so wichtig ist, dass eine 5×-Beschleunigung zählt, kann man die Vektorisierung explizit schreiben und das Verhalten vorhersehbar halten
    • So lässt sich vermeiden, dass nicht zusammenhängende Codeänderungen oder Compiler-Updates eine Vektorschleife stillschweigend wieder in eine skalare Schleife zurückverwandeln

Welchen Umfang von SIMD Entwickler lernen sollten

  • Wenn man einen Hot Loop findet, der große Mengen zusammenhängender Daten durchsucht, vergleicht, zählt oder transformiert, sollte man Verarbeitung in Vektorbreite in Betracht ziehen können
  • Alltägliches SIMD folgt einer regelmäßigen Form: Konstanten vorbereiten, Vektor laden, parallel operieren, Ergebnis reduzieren, skalaren Rest behandeln
  • Wenn eine Sprache SIMD gut unterstützt, kann man die Performance verbessern, ohne Assembly oder CPU-spezifische Details direkt kennen zu müssen
  • Das für alle Entwickler nötige Niveau sind nicht komplexe Techniken im Stil von simdutf oder simdjson, sondern die Fähigkeit, Gelegenheiten für SIMD zu erkennen und die gemeinsame Struktur zu nutzen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2 시간 전
Hacker-News-Kommentare

  • Guter Artikel, aber erst zu behaupten, SIMD sei leicht zu verstehen und so einfach zu schreiben wie eine for-Schleife, und dann schon im ersten Beispiel eine Zeile Skalar-Code in 12 Zeilen umzuwandeln, ist wenig überzeugend
    Ehrlicher wäre es, einfach zu sagen, dass SIMD schwierig ist, sich das Ergebnis aber lohnt. Wenn sich der Text an Einsteiger richtet, sollte man außerdem nicht schon in Schritt 1 SIMD-spezifische Begriffe wie broadcast ohne Erklärung verwenden; Schritt 5, der die Behandlung des skalaren Rests erklärt, ist dagegen gut aufgebaut

    • SIMD und das erste Beispiel sind weniger schwierig als vielmehr eine deutlich umständlichere Arbeit
      Man muss herausfinden, wie viele Elemente die Hardware auf einmal verarbeiten kann, die Arbeit in Blöcke dieser Größe aufteilen, die Ergebnisse wieder entpacken, übrige Elemente separat behandeln und Konstanten ebenfalls als replizierte Vektoren anlegen. Nichts davon ist einzeln schwer, aber alles zusammen macht mehr Arbeit und ist dadurch umständlich
    • Ich habe Parallel-C gelernt, das um 1990 während des Transputer-Booms entstand; das war eine Sprache, die C Parallelprogrammierungsfunktionen hinzufügte
      Mein Lieblingsfeature war par(; ; ), bei dem der Compiler unter bestimmten Randbedingungen for-Schleifen automatisch parallelisierte
    • Ich gehöre ziemlich genau zur Zielgruppe und fand den Text interessant, aber der Schwierigkeitsgrad steigt viel zu schnell an und wirkte fast wie das berüchtigte „Eule-zeichnen“-Meme
    • SIMD selbst ist einfach; unangenehm ist eher die Art, datenparallele Operationen in einer skalaren Sprache zu verwenden
    • Einer der größten Fehler in der technischen Ausbildung ist es, ein Thema einfach für simpel zu erklären, um den Leuten die Angst davor zu nehmen. Man sollte nicht sagen, dass es einfach sei, sondern es tatsächlich zeigen
      Wenn ein Thema tatsächlich komplex ist, sollte man es in kleinere, einfachere Teile zerlegen, die Reihenfolge so gestalten, dass man die steile Lernkurve bewältigen kann, und überzeugend zeigen, dass sich der Aufwand lohnt

  • Der bessere Rat wäre, dass alle Array-Programmierung lernen sollten. Für SIMD-Optimierung braucht man meistens genau diese Denkweise, und Techniken, die nur auf gepacktes SIMD spezialisiert sind, sind überraschend selten
    Array-Programmierung lässt sich für Compiler leicht automatisch vektorisieren, sodass man meist performanten Code bekommt, auch ohne SIMD direkt zu verwenden

    • Array-Programmierung, bei der man erst alle Vergleiche ausführt und später den ersten Fehlschlag sucht, hilft nicht viel, wenn der ausgeführte Abschnitt kurz ist. Sie bietet von sich aus kein frühes Beenden und kann dadurch viel Zeit für unnötige Vergleiche verschwenden
    • Ich mag keine Closed-Source-Sprachen und MATLAB hat viele Schwächen, aber an der Universität war es sehr natürlich, vektorisierten Code für numerische Simulationen effizient zu schreiben
      Ich habe nicht viel Erfahrung, aber Julia scheint einer moderneren und ausdrucksstärkeren Sprache mit ähnlichen Vektorisierungsfähigkeiten am nächsten zu kommen

  • Ich habe in den letzten Tagen Matrixoperationen in einem Bioinformatik-Projekt mit AVX-512 optimiert und bin sehr zufrieden
    Bei den meisten Anwendungen ist das Lesen großer Datensätze aus dem Speicher der Flaschenhals; statt für mehrere Operationen immer wieder zu lesen, kann man alles in einem Durchgang mit AVX-Registern und fusionierten Kerneln erledigen. Eine 5-fache Beschleunigung ist häufig, und obwohl ich Intrinsics direkt verwendet habe, macht das wide-Crate allgemeine Operationen sehr einfach: https://docs.rs/wide/latest/wide/

  • Die überwältigende Mehrheit der Entwickler muss SIMD überhaupt nicht lernen. Ich frage mich, warum man den Eindruck erzeugt, jeder müsse das kennen, um ein richtiger Entwickler zu sein

    • Zumindest sollte man über die Existenz und die Möglichkeiten von SIMD Bescheid wissen. Als Entwickler hat man wahrscheinlich schon Hot Loops geschrieben, die einfache Werte addieren oder vergleichen, und das Wissen, dass der Compiler so etwas für die Ziel-CPU-Architektur optimieren kann, ist in vielen Situationen nützlich

  • Der Titel sollte besser in „Jeder sollte wissen, wann SIMD nicht greift“ geändert werden
    Moderne Compiler vektorisieren sehr gut, fallen dann aber wegen einer einzigen Annahme oder eines datenabhängigen Zweigs plötzlich auf Skalar-Code zurück. Wertvoller als zu lernen, wie man SIMD schreibt, könnte es sein zu wissen, wie man die Optimierungsberichte des Compilers prüft

    • Die Lösung für miserable automatische Vektorisierung besteht darin, SIMD-Code von Hand zu schreiben; ob es wirklich wertvoller ist, zu wissen, wie man Optimierungsberichte liest, wage ich zu bezweifeln
      Wenn man das Problem nur identifizieren kann, endet es am Ende bei einem bloßen „schade“
    • Genau das ist tatsächlich passiert: https://xcancel.com/mitchellh/status/2079672171321081908#m

  • Ich habe letztes Jahr beim Bau eines Audio-Synthesizers begonnen, x86- und ARM-SIMD zu lernen: https://github.com/seclorum/SIMDSynth
    Die Architektur eines mehrtimbralen, polyphonen Synthesizers eignet sich sehr gut, um SIMD-Prinzipien zu lernen, weil dieselbe Verarbeitung auf mehrere Datenströme angewendet wird. Das Debugging war allerdings ziemlich schwierig, sodass ich dringend einen Simulator brauchte, mit dem sich der Zustand jeder Verarbeitungspipeline verstehen lässt; und um SIMD-Werkzeuge gründlich zu untersuchen, wäre wohl noch einmal eine große Investition nötig

  • Der Artikel ist gut, und es wäre schön, wenn mehr Sprachen SIMD unterstützen würden, aber in einer Situation, in der die zwei populärsten Sprachen SIMD nicht nativ unterstützen, wirkt die Formulierung „jeder Programmierer sollte es kennen“ etwas seltsam

    • Es ist schwer, sicher zu behaupten, dass die populärsten Sprachen auch die Sprachen sind, die von den Software Engineers, an die sich solche Artikel richten, am meisten verwendet werden

  • Auch wenn man SIMD nicht selbst schreiben oder es einer KI überlassen will, sollte man wissen, welche Aufgaben auf welcher Hardware durch SIMD schneller werden können. Nur dann kann man Algorithmus und Codestruktur so entwerfen, dass SIMD überhaupt anwendbar ist
    Die Auswirkungen von Datenabhängigkeiten, die Kosten größerer Vektorelementbreiten und wie man sie vermeidet, wie man Bedingungen und Verzweigungen in Masken umwandelt oder Eigenschaften wie „es gibt keine Divisionsinstruktion“ versteht man viel leichter, wenn man SIMD wenigstens ein wenig selbst benutzt hat

    • Wann SIMD schneller wird, wird nicht ausreichend behandelt
      Es funktioniert gut, wenn man große zusammenhängende Daten auf einmal prüft oder transformiert, aber wenn man alle paar Bytes der Eingabe eine Entscheidung treffen muss, kann es genauso schnell oder sogar langsamer als der skalare Ansatz sein. SIMD ist kein magischer Beschleunigungsknopf

  • Ein nützliches Video, in dem Casey Muratori erklärt, wie das Team hinter The Witness ein reales Performance-Problem mit SIMD gelöst hat: https://www.youtube.com/watch?v=Ge3aKEmZcqY

    • Großartige Präsentation, aber das Video ist zu lang, um es anderen einfach zu empfehlen; schön wäre eine Textversion, die sich auf das Wesentliche konzentriert
      Es ist ein gutes Beispiel für vertikale Integration zugunsten der Performance: Erst versteht man, warum allgemeine Abstraktionen existieren und warum sie generisch sein müssen, und dann sieht man, wie man für einen speziellen Anwendungsfall von der Problemdefinition bis hin zu SIMD vertikal integriert und dadurch große Gewinne erzielt

  • Bevor man sich an Mikrooptimierungen wie SIMD macht, sollte man zuerst Datenstrukturen und Zugriffsmuster ernsthaft überprüfen
    Ich habe früher SIMD auf alten Zig-Code angewendet, aber das Datenmodell war das genaue Gegenteil von optimierungsfreundlich — als würde man auf einen Schrotthaufen mit kaputtem Motor Hochleistungsreifen für Rennwagen montieren. Es war eine typische verfrühte Optimierung: keine Leistungsmessung und nicht einmal bedacht, wo Speicher allokiert wird
    Inzwischen betrachte ich Daten wie SQL-Tabellen und entwerfe Strukturen rund um potenzielle Primärschlüssel und Zugriffsmuster. Früher habe ich Bäume verwendet, die auf andere Strukturen auf dem Heap zeigen, und mir damit zugleich die Nachteile verketteter Listen, die Fragmentierung vieler Heap-Vektoren und die langsamen Kosten für Erzeugung und Freigabe eingehandelt; allein Drop verschlang einen beträchtlichen Teil der Laufzeit
    Bäume lassen sich jederzeit linearisieren, daher prüfe ich Zugriffsmuster und Einfügemuster, ob es tatsächlich ein Baum oder eher ein anderer Graph ist und ob man ihn als Vec oder als Struktur aus mehreren Vec speichern sollte. Das Ergebnis: Der Code wurde schneller und einfacher, die Daten liegen in homogenen Arrays zusammen, sodass der Compiler SIMD-Optimierungen und den L1-Cache leichter nutzen kann, und bei Bedarf kann man auch selbst verzweigungsfreien SIMD-Code schreiben
    Verwandtes Material: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

    • Um Hot Loops mit SIMD schnell zu machen, sind Datenlayout und cachefreundliche Strukturen entscheidend
      In realen Engpässen sollte man Speicherallokationen, Lookups in virtuellen Funktionstabellen und übermäßige indirekte Referenzen vermeiden. Auch C++-vector ist nicht immer die beste Wahl, wenn es unerwartet Allokationen auslösen kann
    • Als Performance Engineer begegne ich diesem Problem ständig. Performance beginnt in der Architektur, und auf Hot Paths mit schlechtem Datenlayout gibt es Grenzen dafür, wie viel Leistung man noch herausquetschen kann
      Datenorientierter Code unterstützt dagegen fast immer Threading und SIMD besonders leicht
    • Noch grundlegender sind Speicherzugriffsmuster wichtig
      Interessanterweise schreibt man selbst CPU-Code am Ende oft im GPU-Stil; ein möglicher Ansatz ist die Verwendung von Parquet-artigen Strukturen aus Arrays statt Arrays von Objekten
    • Tabellen sind eine effiziente Art, allgemeine Graphen zu implementieren, und solange man den Graphen nicht spezialisieren kann, ist das für mich die beste Darstellung, die ich kenne