Die `tolower()`-Funktion mit AVX-512

• Vor einigen Jahren habe ich darüber geschrieben, wie man tolower() mit einem SWAR-Trick beschleunigen kann. Vor ein paar Tagen wurde ich durch einen Beitrag von Olivier Giniaux auf eine interessante Optimierung aufmerksam, bei der SIMD-Instruktionen zum Verarbeiten kleiner Strings verwendet werden. Diese Methode kommt in einer schnellen Hash-Funktion zum Einsatz, die in Rust geschrieben ist.

• SIMD-Instruktionen können kurze Strings leicht verarbeiten, aber der Datentransfer zwischen Speicher und Vektorregistern war dabei immer ein Ärgernis. Oliviers Beitrag zeigt einen interessanten Weg, dieses Problem zu lösen.

Anzeichen der Hoffnung

• Einige SIMD-Befehlssätze bieten nützliche Funktionen für maskiertes Laden und Speichern zur String-Verarbeitung. Diese arbeiten auf Byte-Ebene.

  • ARM SVE: verfügbar auf aktuellen großen ARM-Neoverse-Kernen, zum Beispiel Amazon Graviton. Auf Apple Silicon jedoch nicht verfügbar.
  • AVX-512-BW: verfügbar auf aktuellen AMD-Zen-Prozessoren. AVX-512 ist ein komplexer Erweiterungssatz, dessen Unterstützung bei Intel eher zufällig ausfällt.

• Da ich eine Zen-4-Maschine habe, habe ich beschlossen, AVX-512-BW auszuprobieren.

tolower64()

• Mithilfe des Intel-Intrinsics-Guides habe ich eine grundlegende tolower()-Funktion geschrieben, die 64 Byte auf einmal verarbeiten kann.
  • Mit * als Wildcard nach mm512*epi8 suchen, um AVX-512-Funktionen auf Byte-Ebene zu finden.
  • Einige Register mit 64 nützlichen Bytes füllen.
  • Die Werte setzen, die nötig sind, um Großbuchstaben in Kleinbuchstaben umzuwandeln.
  • Die Eingabezeichen mit A und Z vergleichen, um festzustellen, ob es sich um Großbuchstaben handelt.
  • Mit einer Maske nur die Großbuchstaben in Kleinbuchstaben umwandeln.

Massenweises Laden und Speichern

• Der tolower64()-Kernel muss in eine praktischere Funktion eingebettet werden, etwa in eine Funktion, die einen String kopiert und dabei in Kleinbuchstaben umwandelt.
  • Für lange Strings werden unaligned Vektor-Lade- und Speicherbefehle verwendet.

Maskiertes Laden und Speichern

• Für kleine Strings und das Ende langer Strings werden maskierte unaligned Lade- und Speicherbefehle verwendet.
  • In der Maske sind die ersten len Bits gesetzt.
  • Laden und Speichern ähneln den Vollbreiten-Versionen, nur mit zusätzlicher Maske.

Benchmarking

• Die Performance mehrerer ähnlicher Funktionen wurde verglichen.

  • Kompiliert mit Clang 16 und ausgeführt auf einem AMD Ryzen 9 7950X.
  • Jede Funktion wurde separat kompiliert, um Störungen durch Inlining und Code-Bewegung zu vermeiden.

• Ergebnisse:

  • tolower64 ist die schnellste aller getesteten Funktionen.
  • copybytes64 verwendet AVX-512 ähnlich wie tolower64, ist aber nicht wesentlich schneller.
  • copybytes1 führt memcpy Byte für Byte aus und zeigt, dass die Auto-Vektorisierung von Clang 11 relativ schwach ist.
  • Das Standard-tolower() ist am langsamsten.
  • tolower1 ist ein Byte-für-Byte-tolower(), kompiliert mit Clang 16; die Auto-Vektorisierung ist besser geworden, aber es bleibt langsam.
  • tolower8 ist das SWAR-tolower() aus einem früheren Blogbeitrag; Clang versucht eine Auto-Vektorisierung, aber das Ergebnis ist nicht gut.
  • memcpy ist anfangs schnell, fällt dann aber auf die halbe Geschwindigkeit von copybytes64 zurück.

Fazit

• AVX-512-BW ist besonders beim Verarbeiten kurzer Strings sehr nützlich.

• Auf Zen 4 ist es sehr schnell, und die Intrinsics sind einfach zu verwenden.

• Die Performance von AVX-512-BW ist sehr gleichmäßig.

• Ich habe keine Maschine mit ARM-SVE-Unterstützung, daher konnte ich das nicht genauer untersuchen, bin aber neugierig, wie gut SVE bei kurzen Strings funktioniert.

• Ich hoffe, dass sich diese Befehlssatz-Erweiterungen weiter verbreiten. Sie könnten die Performance der String-Verarbeitung deutlich verbessern.

• Der Code zu diesem Blogbeitrag ist auf meiner Website verfügbar.

Zusammenfassung von GN⁺

• Dieser Beitrag erklärt, wie sich kurze Strings mit SIMD-Instruktionen effizient verarbeiten lassen.
• Er zeigt, dass die Befehlssätze AVX-512-BW und ARM SVE für die String-Verarbeitung nützlich sind.
• Die Benchmarks zeigen, dass AVX-512-BW besonders bei kurzen Strings eine hervorragende Performance liefert.
• Der Beitrag ist nützlich für Entwickler, die sich für Performance-Optimierung interessieren.

[GN⁺]

Hacker-News-Kommentare

• Im Rust- und LLVM-Speichermodell gilt der Trick „unsafe read beyond of death“ als undefiniertes Verhalten

  • Der Compiler kann für Optimierungen annehmen, dass ein solches Verhalten nicht auftritt
  • Um das zu vermeiden, muss man Inline-Assembler verwenden

• Es gibt Neugier auf AMDs AVX512-Implementierung und den Wettbewerb mit Intels AVX10

  • AVX10 soll Intels Problem mit P- vs.-E-Kernen lösen
  • AMD verwendet je nach Situation die volle Breite von Zen5 oder das 256-Bit-Double-Pump-Verfahren bei Zen4 sowie Zen5 Mobile
  • Die großen Leistungssteigerungen kommen bei Zen4-Kernen zustande

• SWAR-Optimierung ist nur für auf 8-Byte-Adressen ausgerichtete Strings nützlich

  • Auf nicht ausgerichtete Strings angewendet ist sie langsamer als der ursprüngliche Algorithmus
  • Wenn man den Algorithmus in drei Teile aufteilt, werden mehr Instruktionen benötigt

• Das Hinzufügen von Masken wirkt sauber

  • Es wäre wünschenswert, wenn es in den .NET-Built-ins eine Möglichkeit gäbe, die Maskenregister von AVX512 direkt zu steuern

• Mit Clang kann man bessere Ergebnisse erzielen

  • Es bietet eine bessere Instruktionsauswahl und ein gut entfaltetes Ergebnis

• Die Kernschleife für kurze Strings benötigt eine Instruktion weniger

  • Es ist wichtig, kurze Strings schnell zu verarbeiten

• Eine ähnliche Implementierung zur Umwandlung von ASCII in UTF-8 in Groß-/Kleinschreibung wurde in C# geschrieben

  • Da kurze Strings die meisten Codebasen dominieren, ist eine schnelle Verarbeitung wichtig

• Es gibt ein Beispiel für den Einsatz von SIMD, um Text mit AVX512 in uwu umzuwandeln

• Unter Berücksichtigung der Unicode-Zeichenumwandlung wäre es noch beeindruckender

  • Die meisten Programmierer kümmern sich nur um ASCII, aber jenseits des Standardzeichensatzes gibt es noch eine große Welt

• In der Vergangenheit gab es Erfahrungen damit, schwarze Ränder um Bilder hinzuzufügen, um Buffer-SIMD-Probleme zu vermeiden

  • Man hat die Eingabe nicht immer vollständig unter Kontrolle, auch nicht in solchen Fällen