You can beat the binary search

• Mitgliedschaftsprüfungen in sortierten Arrays können schneller gemacht werden als mit der lehrbuchmäßigen binären Suche; SIMD Quad war unter allen Messbedingungen schneller als std::binary_search
• SIMD Quad teilt sortierte Arrays aus 16-Bit-Unsigned-Integern in Blöcke zu 16 Elementen auf, verwendet an den Blockgrenzen eine 4-äre Interpolationssuche und innerhalb des Blocks SIMD-Parallelevergleiche
• Moderne 64-Bit-ARM- und x64-Systeme (Intel/AMD) können mit einem Befehl 8 16-Bit-Integer vergleichen, sodass man der Struktur der binären Suche, die jeweils nur einen Wert prüft, nicht mehr strikt folgen muss
• Das Benchmark wurde mit 100.000 sortierten Arrays der Größen 2 bis 4096 und 10 Millionen Mitgliedschaftsanfragen durchgeführt; der cold-Modus simuliert Cache-Misses, der warm-Modus Cache-Hits
• Auf Intel war SIMD Quad bei warmem Cache mehr als doppelt so schnell wie die binäre Suche, auf Apple bei kaltem Cache ebenfalls mehr als doppelt so schnell; bei großen Arrays mit kaltem Cache auf Intel nutzte der 4-äre Ansatz die Speicherparallelität besser aus

---

Flaschenhals bei Mitgliedschaftsprüfungen in sortierten Arrays

• Die einfachste Methode, um zu prüfen, ob ein Wert in einem sortierten Array enthalten ist, ist die lineare Suche, bei der die Werte nacheinander durchlaufen werden; in C++ lässt sich derselbe Effekt mit std::find erzielen
• Bei großen Arrays ist die binäre Suche schneller; dabei wird wiederholt anhand des mittleren Werts des Suchbereichs die obere oder untere Hälfte verworfen, bis der Wert gefunden ist oder ein leerer Bereich erreicht wird
• std::binary_search in C++ gibt einen booleschen Wert zurück, der angibt, ob der Wert vorhanden ist
• Das Roaring-Bitmap-Format verwendet Arrays aus 16-Bit-Integern der Größe 1 bis 4096 und nutzt die binäre Suche zur Prüfung, ob ein Wert vorhanden ist

Ausgangspunkt von SIMD Quad

• Die meisten modernen Prozessoren besitzen SIMD-Befehle für Datenparallelität; 64-Bit-ARM und x64 (Intel/AMD) können mit einem Befehl 8 16-Bit-Integer mit einem Zielwert vergleichen
• Dadurch muss die binäre Suche nicht bis auf Blöcke mit weniger als 8 Elementen fortgesetzt werden, und auch 16 oder mehr Elemente lassen sich günstig vergleichen
• Die binäre Suche prüft jeweils nur einen Wert, moderne Prozessoren können aber mehrere Werte gleichzeitig laden und prüfen und bieten zudem eine gute Speicherparallelität
• Statt das Array in zwei Hälften zu teilen, kann man eine 4-äre Suche ausprobieren; selbst wenn die Zahl der Befehle etwas steigt, ist es gut möglich, dass nicht die Befehlsanzahl der eigentliche Flaschenhals ist

Aufbau des SIMD-Quad-Algorithmus

• SIMD Quad ist ein Suchalgorithmus für sortierte Arrays aus 16-Bit-Unsigned-Integern, der 4-äre Interpolationssuche mit SIMD kombiniert
• Das Array wird in Blöcke fester Größe mit jeweils 16 Elementen aufgeteilt; der letzte Block kann eine Ausnahme bilden
• Die letzten Elemente jedes Blocks dienen als Interpolationsschlüssel, um den Bereich auf genau einen Block einzugrenzen, in dem der Zielwert wahrscheinlich liegt; anschließend werden die 16 Elemente dieses Blocks gleichzeitig per SIMD geprüft
• Der Kernablauf ist eine hierarchische Suche: An den Blockgrenzen reduziert Interpolationssuche die Anzahl der Vergleiche, innerhalb des Blocks führt SIMD parallele Vergleiche aus
• Die Schritte im Ablauf sind wie folgt
  • Wenn die Zahl der Elemente kleiner als 16 ist, wird das gesamte Array mit einer einfachen linearen Suche durchsucht
  • Das Array der Größe cardinality wird in Blöcke aus 16 aufeinanderfolgenden Elementen unterteilt; die Gesamtzahl der Blöcke ist num_blocks = cardinality / 16
  • Die letzten Elemente der Blöcke an Positionen wie 16-1, 32-1 usw. werden als Schlüssel verwendet, um die Viertelpunkte des aktuellen Suchbereichs mit dem Zielwert pos zu vergleichen und base anzupassen
  • Entsprechend dem Ergebnis der Interpolation wird der passende Blockindex lo gewählt
  • Falls es sich um einen gültigen Block handelt, werden auf ARM mit NEON, auf x64 mit SSE2 die 16 Elemente geladen und parallel auf Gleichheit mit dem Zielwert geprüft; bei einem Treffer wird true zurückgegeben
  • Verbleibende Elemente, die nicht in vollständigen 16er-Blöcken liegen, werden linear durchsucht

Benchmark-Methode

• Für das Benchmark wurden für jede Arraygröße von 2 bis 4096 jeweils 100.000 sortierte Arrays aus 16-Bit-Unsigned-Integern erzeugt
• Für jede Größe wurden 10 Millionen Mitgliedschaftsanfragen in zwei Modi ausgeführt
  • cold-Modus: Jede Anfrage durchsucht ein anderes Array und simuliert damit Cache-Misses
  • warm-Modus: Anfragen werden pro Array gebündelt und dasselbe Array 100-mal in Folge durchsucht, um Cache-Hits zu simulieren
• Gemessen wurde die durchschnittliche Zeit pro Anfrage; verglichen wurden lineare Suche (std::find), binäre Suche (std::binary_search) und SIMD Quad
• Die Messsysteme waren ein Apple M4 mit Apple LLVM sowie ein Intel-Emerald-Rapids-Prozessor mit GCC

Messergebnisse

• Im Vergleich zwischen linearer und binärer Suche gewinnt die binäre Suche bei größeren Arrays
• Bei kaltem Cache ist die lineare Suche relativ stärker im Nachteil, weil mehr Datenzugriffe zu mehr Cache-Fehlzugriffen führen
• Nachdem sich die binäre Suche insgesamt gegenüber der linearen Suche als überlegen erwiesen hatte, wurde sie mit SIMD Quad verglichen
• Die Ergebnisse auf Intel- und Apple-Plattformen unterschieden sich deutlich
  • Auf der Intel-Plattform war SIMD Quad bei warmem Cache mehr als doppelt so schnell wie die binäre Suche
  • Auf der Intel-Plattform war der Vorteil bei kaltem Cache geringer
  • Auf der Apple-Plattform war es umgekehrt: Dort war SIMD Quad bei kaltem Cache mehr als doppelt so schnell, bei warmem Cache war der Vorteil begrenzter
• In allen Fällen war SIMD Quad schneller als die binäre Suche
• Der SIMD-Teil reduziert die Arbeit durch spezielle Befehle; mit weniger Befehlen und Verzweigungen lässt sich die Geschwindigkeitssteigerung leicht nachvollziehen

Wirkung der 4-ären Suche

• Es wurde auch eine SIMD binary-Variante verglichen, die die SIMD-Optimierung beibehält, aber die 4-äre Interpolationssuche durch eine normale binäre Suche ersetzt
• Auf der Apple-Plattform war die Wirkung des 4-ären Ansatzes gering
• Auf der Intel-Plattform war der 4-äre Ansatz bei großen Arrays und kaltem Cache eine sinnvolle Optimierung
• Auf Intel-Servern nutzte die 4-äre Suche die Speicherparallelität besser aus

Kernelemente der Implementierung

• Die Funktion simd_quad nimmt ein uint16_t-Array, die Elementanzahl cardinality und den zu suchenden Wert pos entgegen und gibt einen booleschen Wert zurück
• gap ist fest auf 16 gesetzt; wenn cardinality < gap ist, wird der Wert per einfacher Schleife gesucht
• In der Blocksuchschleife werden solange n > 3 ist die letzten Blockwerte an den Positionen 1/4, 2/4 und 3/4 gelesen, mit pos verglichen und base um die Summe der drei Vergleichsergebnisse verschoben
• Danach wird solange n > 1 ist ein Vergleich an der Halbierungsgrenze durchgeführt, um den verbleibenden Bereich weiter zu verkleinern; anschließend wird der Block lo ausgewählt
• Im ausgewählten Block werden die 16 Elemente auf ARM NEON mit vceqq_u16 oder auf x64 SSE2 mit _mm_cmpeq_epi16 in zwei Gruppen verglichen
• Im restlichen Elementbereich wird an der Stelle, an der v >= pos wird, geprüft, ob v == pos gilt; falls kein Treffer bis zum Ende gefunden wird, wird false zurückgegeben

Fazit und Materialien

• Die lehrbuchmäßige binäre Suche ist ein brauchbarer Algorithmus, lässt sich in der Praxis aber auf sinnvolle Weise deutlich beschleunigen
• Standardalgorithmen sind oft nicht unter der Annahme der heute verfügbaren hohen Parallelität moderner Computer entworfen worden
• SIMD Quad ist ein Ansatz, der sowohl Speicherparallelität als auch Datenparallelität ausnutzen will
• Noch bessere Algorithmen könnten möglich sein; dafür sind kreativere Ansätze nötig
• Quellcode
• Faster intersections between sorted arrays with shotgun