SIMD-geeignete Algorithmen zur Teilstringsuche (2018)

• APIs wie strstr und std::string::find gehen von einer einmaligen Teilstringsuche aus, doch auf modernen CPUs können die Kosten für kurze String- und Vektorvergleiche so niedrig sein, dass ein SIMD-Ansatz vorteilhaft ist
• Die Kernidee besteht darin, die schwache Hash-Bedingung von Karp-Rabin in ein Vektorprädikat umzuwandeln und nur an Kandidatenpositionen einen exakten Teilstringvergleich auszuführen
• Der generische SIMD-Algorithmus reduziert Kandidaten, indem er das erste und letzte Zeichen der Needle parallel vergleicht, und verifiziert nur potenziell passende Positionen mit memcmp
• Auch Ansätze mit SSE4.1 MPSADBW und SSE4.2 PCMPESTRM werden verglichen; Messungen zeigen jedoch, dass generisches SIMD stabiler und schneller ist und PCMPESTRM tendenziell sogar langsamer als MPSADBW ist
• Generisches SIMD war auf allen Plattformen schneller als C strstr, ist aber nicht sicher, da es über den Eingabestring hinaus lesen kann; zudem sind die Vergleichsbedingungen nicht völlig identisch, weil Längeninformationen vorab übergeben werden

---

Veränderte Kostenannahmen bei der Stringsuche

• APIs wie C strstr, C++ std::string::find sowie pos und index bei Python-Strings sind auf die einmalige Suche nach einem Teilstring in einem gegebenen String ausgelegt
• Bisherige Algorithmen lassen sich grob in zwei Gruppen einteilen
  • Verfahren auf Basis deterministischer endlicher Automaten wie Knuth-Morris-Pratt und Boyer Moore
  • Verfahren auf Basis einfacher Vergleiche wie Karp-Rabin
• Standardalgorithmen setzen voraus, dass der Vergleich eines Zeichenpaars, das Nachschlagen in Hilfstabellen und bedingte Verzweigungen billig sind, während der Vergleich zweier Teilstrings teuer ist
• Auf modernen Desktop-CPUs trifft diese Annahme möglicherweise nicht mehr gut zu
  • Auf 64-Bit-CPUs gibt es keinen Kostenunterschied zwischen Vergleichen von 1, 2, 4 und 8 Byte
  • Mit SIMD-Unterstützung können auch Vektorvergleiche über 16, 32 oder 64 Byte so billig sein wie ein einzelner Bytevergleich
  • Tabellenzugriffe verursachen Speicherkosten in der Größenordnung eines L1-Cache-Roundtrips; zeichenweises Lesen hat ähnliche Kosten
  • Fehlvorhergesagte Branches können eine Strafe von etwa 10–20 Zyklen verursachen
  • Kurze Abhängigkeitsketten aus Zeichenlesen, Vergleich und bedingter Verzweigung erschweren es, die Out-of-Order-Ausführung der CPU auszunutzen

Ansatz: Vektorprädikat statt schwachem Hash

• Karp-Rabin führt nur dann einen exakten Vergleich aus, wenn der schwache Hash des gesuchten Teilstrings mit dem Hash des aktuellen Stringabschnitts übereinstimmt
• Der SIMD-Ansatz ersetzt diese Hash-Bedingung durch ein Vektorprädikat
  • Das Prädikat wird parallel berechnet
  • Ein exakter Teilstringvergleich wird nur für die Positionen ausgeführt, die im Prädikatvektor wahr sind
• Auch Spezialisierung nach Länge wird zur Leistungssteigerung genutzt
  • Eine allgemeine Implementierung ruft für den Teilstringvergleich eine Funktion wie memcmp auf
  • Wenn die Länge des gesuchten Teilstrings bekannt ist, kann der Funktionsaufruf durch einige CPU-Instruktionen, in manchen Fällen durch eine einzige Instruktion, ersetzt werden
  • Dadurch sinken die Kosten des Funktionsaufrufs und die internen Kosten von memcmp

Algorithmus 1: Generisches SIMD

• Der generische SIMD-Algorithmus ist auf verschiedene SIMD-Befehlssätze sowie auf SWAR-Verfahren anwendbar
• Das grundlegende Prädikat prüft, ob sowohl das erste Zeichen als auch das letzte Zeichen der Needle übereinstimmen
  • Das erste Zeichen wird in Register F gefüllt
  • Das letzte Zeichen wird in Register L gefüllt
  • In jeder Iteration wird im Haystack am aktuellen Offset i ein Chunk A gelesen, und bei i + k - 1 ein Chunk B
  • Anschließend werden F == A und B == L berechnet und die beiden Ergebnisse zu einer Maske für Kandidatenpositionen kombiniert
  • Nur an Positionen, an denen die Maske wahr ist, wird ein exakter Teilstringvergleich ausgeführt
• Beim Beispiel, "cat" in "a_cat_tries" zu suchen, gibt es nur eine Position, nämlich Index 2, an der sowohl das erste Zeichen c als auch das letzte Zeichen t passen; daher wird auch nur ein exakter Vergleich durchgeführt
• Die Wahl von erstem und letztem Zeichen ist nicht immer gut
  • Wenn der Eingabestring überwiegend aus 'A' besteht und die Needle "AjohndoeA" ist, können viele Kandidaten entstehen
  • Die Implementierung kann statt des letzten Zeichens das vom ersten Zeichen am weitesten entfernte andere Zeichen auswählen
  • Wenn alle Zeichen der Needle gleich sind, kann ein spezielles Verfahren für Muster wie "AAAAA" verwendet werden

Unterschiede zwischen Implementierungen

• SSE- und AVX2-Implementierungen sind strukturell nahezu identisch und verwenden die minimale Anzahl an Instruktionen
  • Da bereits bekannt ist, dass erstes und letztes Zeichen übereinstimmen, müssen diese Zeichen in memcmp nicht erneut verglichen werden
• Das SWAR-Verfahren nutzt aus, dass Bytes gleich sind, wenn das XOR-Ergebnis 0 ist
  • Statt Zwischenergebnisse wie bei SSE/AVX2 mit AND zu verknüpfen, verwendet es OR
  • Das Finden von Positionen mit 0-Byte erfordert mehr Arbeit
  • In der C++-Implementierung für 64-Bit-Vektoren wird eine exakte Bytemaske berechnet
• AVX512F hat keine Byteoperationen, und das kleinste Vektorelement ist ein 32-Bit-Word; daher ist eine SWAR-Technik nötig
  • Zwei XORs und ein OR werden mit AVX512F-Instruktionen berechnet
  • Es werden 32-Bit-Elemente gesucht, die ein 0-Byte enthalten
  • Für jedes entsprechende 32-Bit-Element werden vier Kandidaten-Teilstrings geprüft
• Die 32-Bit-Implementierung für ARM Neon nutzt 128-Bit-SIMD-Register
  • Der lange Roundtrip von der Neon-Einheit zurück zur CPU wird zum Flaschenhals
  • Vergleichsergebnisse werden zur Verarbeitung als 64-Bit-Words im Speicher abgelegt
  • Wenn zwei innere Schleifen entrollt werden, wird sie etwa 1,2-mal schneller
• Die AArch64-Implementierung ist dem ARM-Neon-Verfahren fast gleich, das direkte Lesen von Lanes aus SIMD-Registern ist jedoch schnell

Algorithmus 2: SSE4.1 MPSADBW

• MPSADBW in SSE4.1 und AVX2 berechnet die Manhattan-Distanz zwischen einem 4-Byte-Subvektor eines Registers und acht aufeinanderfolgenden 4-Byte-Subvektoren eines anderen Registers
• Wenn zwei Subvektoren gleich sind, ist die L1-Distanz 0; das wird zur Suche nach Kandidatenpositionen genutzt
  • Dieses Verfahren verwendet die Gleichheit der ersten 4 Zeichen als Prädikat
• Da die ersten 4 Zeichen verglichen werden, wirkt es stärker als der Vergleich von erstem und letztem Zeichen, doch im Worst Case lässt sich quadratische Komplexität nicht vermeiden
  • Wenn der Haystack vollständig aus "a" besteht und die Needle "aaaabcde" ist, ist das Prädikat für jedes Eingabezeichen wahr
• Das MPSADBW-Verfahren hat einige Einschränkungen
  • Für Teilstrings mit weniger als 4 Zeichen ist es grundsätzlich nicht geeignet
  • Eine Behandlung von Länge 3 ist möglich, erfordert aber zusätzlichen Code
  • SSE MPSADBW verarbeitet nur 8 Byte auf einmal
  • AVX2 MPSADBW arbeitet nicht über die gesamten 256 Bit hinweg, sondern laneweise in 128-Bit-Lanes, was zusätzlichen Ladecode erfordert
  • Die Latenz der Instruktion ist je nach CPU mit 5–7 Zyklen hoch, der Durchsatz liegt aber bei 1–2 Zyklen, sodass sich die Latenz durch Loop-Unrolling verbergen lässt
• AVX512F enthält kein MPSADBW, aber da 32-Bit-Elemente nativ unterstützt werden, lässt sich ein Prädikat für die Gleichheit eines 4-Byte-Präfixes nachbilden
  • In jeder Iteration werden vier AVX512-Vektoren erstellt, die mögliche 4-Byte-Präfixe enthalten
  • Für den Aufbau jedes Vektors sind zwei Shifts und ein OR nötig
  • Die Vergleichsschleife wird komplizierter, und um das letzte Element zu füllen, werden 4 Byte jenseits des Vektors benötigt

Algorithmus 3: SSE4.2 PCMPESTRM

• SSE4.2 führte den STNI-Befehlssatz als Baustein für Stringoperationen ein
• Intel hat STNI in späteren Prozessoren faktisch nicht weitergeführt und auch keine AVX2-Version eingeführt; diese Instruktionen sind sehr langsam
  • Eine Latenz von 11 Zyklen wird als schwer akzeptabel bewertet
• Die PCMPxSTRx-Instruktionen haben vier Varianten, abhängig davon, wie Stringlängen bestimmt und Ergebnisse gespeichert werden
  • Die Länge kann explizit angegeben werden, oder wie bei traditionellen C-Strings kann das erste 0-Byte als Ende gelten
  • Das Ergebnis kann als Bit-/Bytemaske oder als Nummer des ersten/letzten gesetzten Bits der Maske gespeichert werden
• Hier wird die Vergleichsart range ordered verwendet
  • Anders als der Name nahelegt, findet sie Teilstrings oder deren Präfix, wenn sie über die Registerbreite hinausreichen
  • Wenn im Beispiel "ABCD" in "ABCD_ABC_ABCD_AB" gesucht wird, kann auch das Suffix "AB" als Treffer behandelt werden
  • Daher kann man sicher nur eine Übereinstimmung des ersten Zeichens annehmen; der Rest muss mit memcmp geprüft werden

Umgebung für Leistungsmessungen

• Die Performance mehrerer SIMD-Implementierungen wurde gemessen, einschließlich Laufzeit-Spezialisierung für kurze Teilstrings
• C strstr wurde als Vergleichsbasis einbezogen, aber wegen eines Performance-Bugs in std::string::find der GNU libc aus der x64-Tabelle ausgeschlossen
• Jeder Test wurde dreimal ausgeführt
• x64-Testumgebung
  • Westmere i5 M540, GCC 6.2.0
  • Bulldozer FX-8150, GCC 4.8.4
  • Haswell i7 4470, GCC 5.4.1
  • Skylake i7 6700, GCC 5.4.1
  • Knights Landing 7210, GCC 5.3.0
• ARM-Testumgebung
  • ARMv7 Raspberry Pi 3, 32-Bit-Code, GCC 4.9.2
  • ARMv8 ARM Cortex A57 / AMD Opteron A1100, 64-Bit-Code, Clang 3.8.0

x64-Ergebnisse

• Die generische SIMD-Implementierung zeigte auf x64 die größten Geschwindigkeitsgewinne gegenüber strstr
  • Auf Westmere: SSE2 generic 0,74589 Sekunden, strstr 0,82246 Sekunden
  • Auf Haswell: AVX2 generic 0,38653 Sekunden, strstr 0,52786 Sekunden
  • Auf Skylake: AVX2 generic 0,36309 Sekunden, strstr 0,66148 Sekunden
  • Auf KNL: AVX512F generic 1,14057 Sekunden, strstr 4,94606 Sekunden
• Die maximalen Geschwindigkeitssteigerungen betragen 1,10× auf Westmere, 1,37× auf Haswell, 1,82× auf Skylake und 4,33× auf KNL
• Die strstr-Performance auf Bulldozer war mit 9,37792 Sekunden sehr schlecht und ist daher als Referenz schwer zu verwenden
• Das MPSADBW-Verfahren war abgesehen von Skylake insgesamt nicht gut und auf KNL besonders schlecht
• Das PCMPESTRM-Verfahren war noch langsamer als MPSADBW

ARM-Ergebnisse

• Auf ARMv7 benötigte std::strstr 7,30405 Sekunden, std::string::find 4,17131 Sekunden
• Auf ARMv7 erreichte ARM Neon 32-bit generic 1,29861 Sekunden und war damit bis zu 3,1× schneller als std::string::find
• Auf ARMv8 benötigte std::strstr 3,37546 Sekunden, std::string::find 1,81368 Sekunden
• Auf ARMv8 erreichte AArch64 64-bit generic 0,27897 Sekunden und war damit bis zu 6,5× schneller als std::string::find
• Auf ARMv8 erreichte SWAR 64-bit generic 0,46269 Sekunden und kam damit nahe an die Performance des 32-Bit-SIMD-Verfahrens heran

Fazit und Grenzen

• Der generische SIMD-Algorithmus war auf allen Plattformen schneller als C strstr
• Die Implementierung sollte die höchste SIMD-Version wählen, die auf der jeweiligen CPU verfügbar ist
• MPSADBW liefert abgesehen von der Skylake-Ausnahme keine gute Performance und ist auf Knights Landing sehr schlecht
• PCMPESTRM ist langsamer als MPSADBW
• Die ARM-Neon-Performance war einschließlich der SWAR-Implementierung gut
  • Die SWAR-Version ist 1,7× schneller als string::find
  • Die SIMD-Version ist 3,1× schneller als string::find
• Der Vergleich mit strstr ist möglicherweise nicht völlig fair
  • strstr verarbeitet Strings, deren Länge unbekannt ist
  • Diese Implementierungen erhalten die Länge als Argument und nutzen sie
• Die Implementierung ist nicht sicher
  • Sie kann Daten außerhalb des Eingabestrings lesen
  • Befindet sich der String direkt vor nicht gemapptem Speicher, kann es zu einer Zugriffsverletzung kommen
  • Auch Address Sanitizer können das Problem melden
  • Eine sichere Umsetzung wäre möglich, war aber nicht das Ziel
• Alle Implementierungen und Testprogramme befinden sich auf GitHub