Ein SIMD-geeigneter Algorithmus zur Teilstringsuche (2018)

 (0x80.pl)
1 Punkte von GN⁺ 2025-06-15 | 1 Kommentare | Auf WhatsApp teilen
  • Es geht um einen SIMD-freundlichen Algorithmus zur Teilstringsuche
  • Vorgestellt wird ein technischer Ansatz für eine schnelle String-Suche
  • Durch die Nutzung von Parallelverarbeitung wird eine höhere Effizienz gegenüber bestehenden Verfahren angestrebt
  • Das Thema gilt als nützlicher Performance-Tipp für Entwickler und IT-Fachleute
  • Der Algorithmus steht im Zusammenhang mit der Optimierung für moderne Hardware

Überblick

  • Dieses Dokument stellt einen Teilstring-Suchalgorithmus vor, der für den SIMD-Befehlssatz (Single Instruction, Multiple Data) optimiert ist
  • In der heutigen IT-Umgebung, in der die Geschwindigkeit der String-Verarbeitung immer wichtiger wird, behandelt es einen Parallelisierungsansatz, der die Grenzen herkömmlicher sequentieller Suchverfahren ergänzt
  • Mit SIMD können mehrere Daten gleichzeitig verglichen werden, wodurch sich bei der Suche in großen Zeichenmengen erhebliche Leistungsverbesserungen erwarten lassen

Zentrale Inhalte

  • Der SIMD-Algorithmus teilt den Eingabestring in mehrere Abschnitte und vergleicht mit derselben Anweisung mehrere Bytes auf einmal
  • Dadurch ist eine schnellere und effizientere Suche möglich als bei klassischen vergleichen auf Basis von Schleifen
  • Besonders wirksam ist der Ansatz in Bereichen mit Anforderungen an schnelle Verarbeitung großer Datenmengen, etwa Textsuche, Log-Analyse oder DNA-Sequenzierung

Vorteile für Entwickler und Ingenieure

  • Durch den Einsatz eines SIMD-freundlichen Algorithmus lässt sich mit minimalen Codeänderungen das Potenzial moderner CPUs maximal ausschöpfen
  • Gegenüber bestehender Suchlogik bietet er Vorteile bei Geschwindigkeit und Effizienz
  • Auch die Leistungsskalierung in Multicore-Umgebungen ist ausgezeichnet

Fazit

  • In Bereichen wie IT-Services, Datenanalyse und Echtzeit-Suchmaschinen, in denen die Performance der Teilstringsuche entscheidend ist, kann die Einführung eines SIMD-basierten Algorithmus zu spürbaren Leistungssteigerungen führen
  • Es handelt sich um eine unverzichtbare Optimierungsstrategie zur Nutzung aktueller Hardwareumgebungen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-06-15
Hacker-News-Kommentare

  • Es wird erklärt, dass die Beschleunigung in ripgrep ein AVX2-(generischer)-Ansatz ist, der das Rust-regex-Crate nutzt. Hervorgehoben wird, dass selbst reguläre Ausdrücke wie \w+\s+Sherlock\s+\w+ schnell durchsucht werden können, indem Sherlock separat extrahiert wird. Die tatsächliche Implementierung ist hier zu finden. Als wesentlicher Unterschied zu dem Algorithmus in diesem Artikel wird genannt, dass statt des ersten/letzten Bytes des Needle eine Heuristik verwendet wird, die die Suche mit zwei seltener vorkommenden Bytes anhand der Hintergrundverteilung optimiert. Benchmark-Ergebnisse zeigen eine deutlich höhere Performance als beim einfachen Two-Way-Verfahren oder GNU libc memmem. Im prebuilt-Benchmark wird außerdem eine API-Einschränkung betont: Routinen vom Typ memmem sind ineffizient, weil sie den Zustand bei jedem fest vorgegebenen Needle erneut aufbauen müssen

    • Es wird hinterfragt, woher man die Hintergrundverteilung der Bytes kennen soll und ob das separate Scannen dieser Verteilung im Haystack die Performance nicht eher verschlechtern würde

  • Jemand teilt Erfahrungen aus dem Versuch, SIMD-Optimierungen für Wasm/WASI libc umzusetzen, und dabei einen solchen String-Suchalgorithmus implementiert zu haben. Es wird die Meinung geäußert, dass eine Kombination mit Quick Search nützlich ist, wenn die Länge des Haystack feststeht und das Needle ausreichend groß ist. Dazu werden zugehöriger Code und ein Link zur Algorithmusbeschreibung genannt

  • Es wird darauf hingewiesen, dass auch in C# SIMD bei IndexOf eingesetzt wird; Details finden sich hier

  • Jemand berichtet, ebenfalls den SIMD-Ansatz verwendet und verschiedene Algorithmen für String-Suche und split selbst implementiert zu haben. Veröffentlicht wird der conversion.cxx-Quellcode von tamgu. Dabei wird klargestellt, dass ein anderer Algorithmus als der im Haupttext erwähnte verwendet wurde

    • Es wird um eine kurze Zusammenfassung des eigenen Algorithmus gebeten. Als Beispiel wird ergänzt: Algorithmus 1 im Original vergleicht erstes/letztes Zeichen, Algorithmus 2 vergleicht die ersten vier Zeichen gleichzeitig und prüft mehrere Kandidatenpositionen

    • Es wird eine Erfahrung geteilt, vor einigen Jahren mit generischem SIMD in Zig eine für die LZ77-Window-Suche angepasste Version implementieren zu wollen. Relevante Details finden sich hier

  • Jemand merkt an, dass ihn das an das hparse-Projekt erinnert, das SIMD-Algorithmen für schnelles HTTP-Parsing verwendet

  • Es wird erwähnt, dass der SWAR-Algorithmus 1-Byte-ausgerichtete Daten auf 8-Byte-Einheiten castet und dadurch UB (undefiniertes Verhalten) verursacht. Außerdem wird angemerkt, dass unaligned loads Performance-Probleme verursachen könnten

    • Jemand meint, solchen Code oft als idealisierten Algorithmus oder als Pseudocode zur besseren Lesbarkeit verstanden zu haben. Es wird angemerkt, dass memcpy nicht verwendet wird und die Bounds-Prüfung ungenau ist. Es gebe sogar drei Fälle von UB: etwa die Annahme, dass die Haystack-Länge ein Vielfaches von 8 ist, oder bei leerem Needle ein unsigned integer overflow mit out-of-bounds-Zugriff. Aus Erfahrung würden SIMD-Democodes oft nur interessante Vektortricks zeigen und Randbedingungen auslassen

  • Dass strstr in libc langsam ist, sei bereits bekannt, aber es wird betont, dass musl schnell ist und moderne Algorithmen verwendet. Wenn nur noch ein Name festgelegt werde, könne es in das smart shootout aufgenommen werden. Man fragt sich, wie es im Vergleich zu den besten SIMD-Algorithmen abschneiden würde

    • Als Referenzbenchmark wird ein Vergleich zwischen musls Two-Way und einem selbst geteilten SIMD-optimierten libc-Algorithmus vorgestellt. Die Benchmark-Methode basiert auf diesem Code. Die Verbesserungen durch SIMD lassen sich in dieser Tabelle sehen. Ehrlich gesagt sei das keine herausragende, aber eine ziemlich ordentliche Verbesserung. musl sei auf Strings fester Länge (memmem) spezialisiert, während man selbst in der Wasm-Umgebung bei Strings unbekannter Länge (strstr) mehrere Optimierungen frei ausprobieren konnte. NUL-terminierte Strings erschwerten viele gute Algorithmen

    • Es wäre wünschenswert, wenn smart mehr SIMD-Algorithmen enthalten würde, und man würde das bei Gelegenheit gern selbst ausprobieren

  • Es wird gefragt, ob bei dem SIMD-Vergleich für String-Suche nicht die Version von 2018 fehlt

  • Es wird gefragt, ab welcher String-Größe SIMD tatsächlich effizient ist. Betont wird, dass bei kleinen Strings der Overhead für SIMD-Setup (Ausrichtung, Längenberechnung usw.) oft höher sein kann als bei einer einfachen bytebasierten Suche. Zugleich wird eingeräumt, dass dies stark von der Hardware-Architektur abhängen kann

    • Nach eigener Erfahrung sei eher das Gegenteil der Fall. Solche Algorithmen seien fast brute force und kämen ohne unnötiges Setup aus, hätten dafür aber bei langen und repetitiven Needles eine schlechte Zeitkomplexität. Fortgeschrittene String-Suchalgorithmen, die quadratische Probleme vermeiden oder sublineare Laufzeiten erreichen, benötigten dagegen kostspieliges Setup, weil sie die Struktur des Needle tiefer analysieren

  • Es wird der Wunsch geäußert, in Python SIMD direkt nutzen zu können, ohne andere Sprachen aufzurufen

    • Unter Verweis auf Austins Blog und die Sammlung „story on vowels detection“ (Link) wird konkret nachgefragt, was mit „SIMD direkt verwenden, ohne eine andere Sprache aufzurufen“ genau gemeint ist. Im Scherz wird angemerkt, dass letztlich auch Assembly eine „andere Sprache“ sei. Anschließend wird erklärt, dass das Python/SIMD-Ökosystem ein breites Spektrum bietet: von PeachPy (x86-Assembler in Python schreiben) über Mojo (eine neue Python-ähnliche Sprache) bis zu dünnen CPython-Bindings für SIMD-Bibliotheken. Es wird gefragt, welche konkrete Form gewünscht ist; für ASCII wird außerdem find_first_of von StringZilla empfohlen (Code)

    • Es wird infrage gestellt, warum man das unbedingt direkt in Python machen wolle. Wenn es um Performance-Grenzen geht, könne schon ein Sprachwechsel allein eine Leistungssteigerung um das 20- bis 50-Fache oder mehr bringen