Kann schneller als die binäre Suche sein
(lemire.me)- Die häufig verwendete binäre Suche zum Finden eines Werts in einem sortierten Array vergleicht jeweils nur einen Wert, moderne CPUs können jedoch mit einem Befehl mehrere Werte gleichzeitig vergleichen; nutzt man diese Fähigkeit, lässt sich die Suchgeschwindigkeit deutlich steigern
- SIMD Quad ist ein hierarchischer Suchalgorithmus: Das Array wird in Blöcke zu je 16 Elementen aufgeteilt, die Blockposition wird per quartärer Interpolationssuche schnell eingegrenzt und innerhalb des Blocks werden 16 Elemente per SIMD-Befehl auf einmal verglichen
- In Benchmarks zeigte sich auf Intel mit warmem Cache gegenüber der binären Suche eine mehr als doppelt so hohe Leistung, auf Apple mit kaltem Cache ebenfalls mehr als doppelt so hoch; unter allen Messbedingungen war SIMD Quad besser als
std::binary_search - Wenn man die binäre Suche statt in zwei Hälften in vier Teile aufteilt, steigt die Zahl der Befehle leicht an, auf großen Intel-Arrays wird jedoch Memory-Level Parallelism besser genutzt, was die Cold-Cache-Performance verbessert
- Da Lehrbuchalgorithmen ohne die Datenparallelität und Speicherparallelität heutiger CPUs entworfen wurden, sind durch eine Neugestaltung unter Berücksichtigung der Hardwareeigenschaften reale Performancegewinne möglich
Kerngedanke
- Die binäre Suche ist so aufgebaut, dass jeweils nur ein Wert gleichzeitig verglichen wird, moderne 64-Bit-ARM- und x64-Prozessoren können jedoch mit einem Befehl 8 16-Bit-Integer gleichzeitig vergleichen
- Nutzt man diese Hardwarefähigkeit, kann man die Sucheinheit von einzelnen Elementen auf Blockebene verlagern und die Zahl der Vergleiche drastisch verringern
- Wenn man ein Array nicht halbiert, sondern viertelt (quartäre Suche), steigt die Zahl der Befehle nur leicht; wahrscheinlich ist aber nicht die Befehlszahl der Flaschenhals, und zudem lässt sich Memory-Level Parallelism besser nutzen
Grundlegende Verfahren zur Mitgliedschaftsprüfung in sortierten Arrays
- Die einfachste Methode, um zu prüfen, ob ein Wert in einem sortierten Array vorhanden ist, ist die lineare Suche, bei der die Werte nacheinander geprüft werden; in C++ lässt sich derselbe Effekt mit
std::finderzielen - Bei großen Arrays ist die binäre Suche schneller; dabei wird wiederholt anhand des mittleren Werts des Suchbereichs entschieden, ob die obere oder untere Hälfte verworfen wird
std::binary_searchin C++ gibt die Existenz des Werts als Boolean zurück- Das Roaring-Bitmap-Format verwendet Arrays von 16-Bit-Integern der Größe 1 bis 4096 und nutzt zur Prüfung auf Vorhandensein die binäre Suche
Aufbau des SIMD-Quad-Algorithmus
- Ein sortiertes Array aus vorzeichenlosen 16-Bit-Integern wird in Blöcke fester Größe mit 16 Elementen aufgeteilt
- Das letzte Element jedes Blocks dient als Interpolationsschlüssel, um den Bereich auf einen einzelnen Block mit hoher Trefferwahrscheinlichkeit einzugrenzen; anschließend werden die 16 Elemente dieses Blocks per SIMD gleichzeitig geprüft
- Ablauf:
- Wenn weniger als 16 Elemente vorhanden sind, wird das gesamte Array per einfacher linearer Suche geprüft
- Das Array wird in Blöcke aus je 16 aufeinanderfolgenden Elementen geteilt, die Gesamtzahl der Blöcke ist
num_blocks = cardinality / 16 - Mit dem letzten Element eines Blocks als Schlüssel werden die 1/4-Punkte des aktuellen Suchbereichs mit dem Zielwert verglichen und
baseentsprechend angepasst - Wenn ein gültiger Block gefunden wurde, werden auf ARM mit NEON und auf x64 mit SSE2 16 Elemente geladen und per parallelem Gleichheitsvergleich geprüft
- Verbleibende Elemente, die nicht in einen vollständigen Block fallen, werden linear durchsucht
Benchmark-Methode
- Für jede Arraygröße von 2 bis 4096 wurden 100.000 sortierte Arrays aus vorzeichenlosen 16-Bit-Integern erzeugt
- Für jede Größe wurden in zwei Modi 10 Millionen Membership-Abfragen durchgeführt
- Cold-Modus: Jede Abfrage sucht in einem anderen Array, um Cache-Misses zu simulieren
- Warm-Modus: Dasselbe Array wird 100-mal hintereinander durchsucht, um Cache-Hits zu simulieren
- Gemessen wurde die durchschnittliche Abfragezeit; verglichen wurden lineare Suche (
std::find), binäre Suche (std::binary_search) und SIMD Quad - Getestet wurde auf Apple M4 (Apple LLVM) und Intel Emerald Rapids (GCC)
Messergebnisse
- Bei größeren Arrays schlägt die binäre Suche die lineare Suche klar; bei kaltem Cache ist die lineare Suche wegen der häufigeren Datenzugriffe noch im Nachteil
- Intel-Plattform: Bei warmem Cache war SIMD Quad mehr als doppelt so schnell wie die binäre Suche, bei kaltem Cache fiel der Vorteil geringer aus
- Apple-Plattform: Bei kaltem Cache war SIMD Quad mehr als doppelt so schnell, bei warmem Cache war der Vorteil begrenzter
- In allen Fällen war SIMD Quad schneller als
std::binary_search - Der SIMD-Teil reduziert die Arbeit durch spezielle Befehle; weniger Befehle und weniger Verzweigungen erklären den Geschwindigkeitsgewinn klar
Wirkung der quartären Suche
- Zum Vergleich wurde auch eine SIMD binary-Variante getestet, die die SIMD-Optimierung beibehält, aber die quartäre Interpolationssuche durch binäre Suche ersetzt
- Auf der Apple-Plattform war der Effekt des quartären Ansatzes gering
- Auf der Intel-Plattform war der quartäre Ansatz bei großen Arrays mit kaltem Cache eine sinnvolle Optimierung
- Auf Intel-Servern nutzt die quartäre Suche Memory-Level Parallelism besser aus
Kernelemente der Implementierung
- Die Funktion
simd_quadnimmt einuint16_t-Array, die Elementzahlcardinalityund den gesuchten Wertposentgegen und liefert einen Boolean zurück gapist fest auf 16 gesetzt; wenncardinality < gap, wird mit einer einfachen Schleife gesucht- In der Blocksuchschleife werden solange
n > 3gilt die letzten Blockwerte an den Positionen 1/4, 2/4 und 3/4 gelesen und verglichen; anhand der Summe der drei Vergleichsergebnisse wirdbaseverschoben - Der ausgewählte Block wird auf ARM NEON mit
vceqq_u16oder auf x64 SSE2 mit_mm_cmpeq_epi16geprüft, wobei 16 Elemente in zwei Gruppen parallel verglichen werden - Im restlichen Elementbereich wird an der Stelle, an der
v >= posgilt,v == poszurückgegeben
Fazit
- Die binäre Suche aus dem Lehrbuch ist ein ordentlicher Algorithmus, lässt sich aber in der Praxis auf sinnvolle Weise noch deutlich beschleunigen
- Standardalgorithmen wurden oft nicht unter der Annahme der hohen Parallelität heutiger Computer entworfen
- SIMD Quad ist ein Ansatz, der sowohl Memory-Level Parallelism als auch Datenparallelität ausnutzen will
- Noch bessere Algorithmen könnten möglich sein; dafür braucht es kreativere Ansätze
- Quellcode
- Schnellere Schnittmengen zwischen sortierten Arrays mit shotgun
1 Kommentare
Hacker-News-Kommentare
Unabhängig von der Low-Level-Hardwareoptimierung, von der Daniel Lemire sprach, sind binäre Suche oder ihre Implementierungsvarianten nur dann optimal, wenn man außer der Tatsache, dass die Daten sortiert/monoton sind, nichts weiter weiß.
Wenn man Vorwissen über die Datenverteilung hat, kann man dieses nutzen, um einen deutlich schnelleren Algorithmus zu bauen. Ein Beispiel ist, wie Menschen in einem Papierwörterbuch schneller zu einem passenden Seitenblock springen als mit einer rein binären Suche.
Mathematisch ist die Suche in einer sortierten Liste eher mit einem geschlossenen Regelalgorithmus vergleichbar, der die Umkehrfunktion einer monotonen Funktion findet; man könnte auch eine Kostenfunktion definieren und Gradientenabstieg oder beschleunigte Varianten verwenden. Allgemeiner gilt: Statt Lösungen aus einer zu stark abstrahierten Problemformulierung zu übernehmen, ist es immer effizienter, mehr Information über das konkrete Problem zu nutzen, das man lösen will. Das kann wesentlich größere, skalierbare Geschwindigkeitsgewinne bringen als nur konstante Faktorverbesserungen durch bessere Hardwareausnutzung.
Eine feste Iterationszahl ist gut für den Branch Predictor, und die Kernschleife ist außerdem ziemlich eng auf die Zielhardware optimiert, wobei Multiplikationen vermieden werden. Versuche, sie noch cleverer zu machen, haben die Schleife verschlechtert und nichts gebracht. Das Format ist ein Struct-Array mit Größe 12, und N ist meist klein, was es zusätzlich schwierig macht.
Ich habe es nicht gebookmarkt und suche es deshalb etwa zweimal im Jahr wieder. Der Legende nach suche ich noch immer.
Deshalb sind in Datenbanken B-Bäume der Standard. Die Daten können alles Mögliche sein, und wenn man viele neue Zeilen importiert, können sich ihre Eigenschaften jederzeit stark ändern.
Man kann Algorithmen bauen, die Abfragen mit Methoden wie Gradientenabstieg beschleunigen, aber B-Bäume sind bereits sehr schnell und haben außerdem viele Vorteile wie vorhersagbares Worst-Case-Verhalten und I/O-Anforderungen, Range-Scans, sortierte Traversierung und Unterstützung für Präfixbedingungen.
Man kann für bestimmte Datenverteilungen effizientere Lookup-Algorithmen bauen, verliert dabei aber oft wichtige Eigenschaften. Ein anderer Algorithmus kann eine bessere Anfangsschätzung liefern, aber beim Finden des letzten Elements langsam sein, oder er ist im Mittel schneller, hat aber ein so schlechtes Worst-Case-Verhalten, dass er unbrauchbar wird.
Selbst im Papierwörterbuch wurde nach der ersten Schätzung fast immer eine Art binäre Suche verwendet, und die dadurch eingesparten Schritte waren nur wenige. Sobald man beim ungefähr richtigen Seitenblock angekommen ist, blättert man linear weiter, obwohl eine strikt binäre Suche vielleicht schneller wäre; man muss das aber gegen die Zeit fürs Umblättern abwägen.
Ed Kmett hat die Idee dann in die Haskell-Bibliothek discrimination[2] überführt, und der zugehörige Vortrag[3] ist ebenfalls sehr interessant.
[1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
[2]: https://hackage.haskell.org/package/discrimination
[3]: https://www.youtube.com/watch?v=cB8DapKQz-I
Ist „Vierfachsuche“ am Ende nicht einfach eine um eine Stufe entrollte Schleife der binären Suche? Um das Intervall mit dem gesuchten Element zu finden, braucht man ungefähr ähnlich viele Vergleiche, nur dass man anscheinend vier statt zwei auf einmal verarbeitet. Es wirkt, als könnte simples Loop Unrolling denselben Effekt erzielen.
Aus Sicht des Prozessors sind also praktisch alle Schleifen ohnehin schon bis zu einem gewissen Grad entrollt, und es bleibt nur der kleine Overhead der Schleife selbst. Bei binärer Suche entstehen die Hauptkosten dadurch, Daten aus dem Speicher oder Cache zu holen; der eigentliche Kampf besteht also darin, Anforderungen für später benötigte Daten möglichst früh auszulösen, damit man weniger auf ihr Eintreffen warten muss.
Der Unterschied bei Algorithmen wie Vierfachsuche ist, dass nicht nur eine Seite eines Zweigs tief vorab geholt wird, sondern alle möglichen Fälle flach prefetched werden. Damit werden die Prefetches, die später tatsächlich gebraucht werden, garantiert ausgelöst, während etwas weniger Bandbreite auf Daten verschwendet wird, die auf dem tatsächlichen Ausführungspfad nicht benutzt werden.
Wenn man die reale Performance eines Suchalgorithmus vorhersagen will, ist die „Anzahl der Vergleiche“ fast nutzlos. Der Flaschenhals ist nicht, wie viele Vergleiche man machen kann, sondern wie gut man Speicher- und Cache-Bandbreite ausnutzt. Wenn man das Verzweigungsverhalten moderner Prozessoren im Detail betrachtet, kann man es durchaus als eine Form von Loop Unrolling sehen.
Am Ende sind beide Suchen O(log N), nur mit unterschiedlichen Konstanten. Im Algorithmenunterricht spielen Konstanten kaum eine Rolle, in der Praxis können sie aber erheblich sein.
Ich habe kürzlich auch einen Artikel[1] über exponentielle Suche[2] geschrieben. Das ist ein Algorithmus für den Fall, dass auch die gesuchten Elemente selbst sortiert sind und man wiederholt in einem Array binär suchen muss; in unserer Last brachte das einen 8x-Speedup.
[1] https://lalitm.com/post/exponential-search/
[2] https://en.wikipedia.org/wiki/Exponential_search
HEAD /users/1 -> 200 OK
HEAD /users/2 -> 200 OK
HEAD /users/4 -> 200 OK
...
HEAD /users/2048 -> 200 OK
HEAD /users/4096 -> 404 Not Found
Danach kann man zwischen 2048 und 4096 binär suchen und so den neuesten Benutzer und nebenbei auch die Benutzerzahl finden. Praktisch zu wissen, wenn man konkurrierende SaaS-Unternehmen untersucht.
Die CPU greift immer auf eine ganze Cache-Zeile zu, normalerweise 64 Byte auf einmal, also wäre es besser, gleich die ganze Cache-Zeile zu durchsuchen. Sobald die Daten in der CPU sind, ist das praktisch fast kostenlos.
Deshalb würde ich gern ausprobieren, bei einer „binären“ Suche alle Werte in der mittleren Cache-Zeile zu prüfen und, falls kein Treffer dabei ist, nach links oder rechts weiterzugehen. Die Suche innerhalb der Cache-Zeile ließe sich mit einem einzelnen 512-Bit-SIMD-Befehl erledigen. 64 Byte Cache-Zeile sind 32 16-Bit-Integer, also könnte das fast 32-mal schneller sein als eine einfache binäre Suche, oder zumindest die Zahl der Speicherzugriffe um das 32-Fache senken, was in den meisten realen Programmen dominieren dürfte.
Mit 4-Byte-Schlüsseln und 4-Byte-Kindzeigern oder Array-Indizes kann ein interner Knoten 7 Schlüssel, 8 Kindzeiger und 1 Next-Pointer enthalten und so eine 64-Byte-Cache-Zeile vollständig füllen. Bei 1 Million Einträgen sinkt die Baumtiefe von etwa 20 auf etwa 7, und die oberen Stufen bleiben wahrscheinlich im Cache.
Mit etwas Überlegung kann man die Suche innerhalb eines B-Baum-Knotens per SIMD beschleunigen, aber die Datenabhängigkeit ist sehr hoch.
Für kleinere Arrays ist lineare Suche mit einem Sentinel-Wert am Ende ohnehin schwer zu schlagen. Das Problem an dieser Aussage ist nur, dass „klein“ eine so vage Bedingung ist, dass man kaum ein Gefühl dafür bekommt.
Insgesamt gefällt mir der Artikel. Er hat etwas, worüber ich mich schon länger gewundert habe, gründlich untersucht, inklusive nützlicher Ausschlussexperimente.
Ich habe ein bisschen mit Suchen in kleinen Arrays mit 16 bis 32 Einträgen experimentiert, und binäre Suche war wegen der vielen Verzweigungen eine der schlechtesten Methoden. Am schnellsten war bei kleinen Arrays eine branchless lineare Suche.
Dabei wird die Schleife nicht vorzeitig beendet, sondern man läuft über alle Elemente. Wenn man zum Beispiel wissen will, ob eine Zahl im Array vorkommt, verknüpft man die Prüfergebnisse aller Einträge mit logischem OR. Ich habe kein SIMD benutzt, aber bei kleinen Arrays sind Verzweigungen sehr teuer, deshalb ist es schneller, einfach alle Elemente ohne Branches zu prüfen.
Die Erklärung des Algorithmus fand ich etwas verwirrend.
Der SIMD-Teil wird nur in der letzten Phase genutzt, also beim Durchsuchen der letzten 16 Elemente.
Der Vierfachsuch-Teil prüft drei Positionen und erzeugt damit vier Pfade, sucht aber nicht einfach den richtigen Schlüssel, sondern den richtigen Block.
Die Details sind interessant: Der Autor verwendet das letzte Element jedes Blocks für die Vierfachsuche. Ich frage mich, wie sich der Algorithmus ändern würde, wenn man stattdessen das erste oder ein beliebiges Element nähme.
Die zentrale Intuition hier, nämlich SIMD-Mehrfachvergleiche, scheint sich auch auf größeren Skalen als nur die letzte Phase anwenden zu lassen.
Die grobe Idee wäre: a) per Gather mehrere Elemente an 16 gleichmäßig verteilten Positionen holen b) per SIMD parallel vergleichen c) auf den richtigen Block fokussieren d) bei kleinem Block auf lineare Suche umschalten, sonst den Gather/Vergleich-Zyklus wiederholen.
Gather-Befehle lesen aus nicht zusammenhängendem Speicher und würden bei binärer Suche mehr laden, als nötig ist. Trotzdem könnte das bei großen Tabellen gewinnen, wenn dadurch mehrwegige Vergleiche möglich werden und man vier Schritte der binären Suche zusammenfalten kann.
Vollständige 16-Wege-Vergleiche sind außerdem nicht für alle Datentypen möglich. Bei der Suche in float64 ist man selbst mit AVX-512 auf 8-Wege-Vergleiche beschränkt, während int32 und float32 16-Wege-Vergleiche erlauben.
Ich halte es für gut möglich, dass binäre Suche in der Praxis schneller ist als ein Gather-basierter Ansatz.
Klassische Informatikalgorithmen wurden im Grunde für CPUs „entworfen“, die praktisch keine Parallelität hatten: keine Mehrkernprozessoren, kein Hyper-Threading, keine SIMD-Befehle, gleiche Zugriffszeiten auf allen Speicheradressen, also keine Konzepte wie L1/L2/L3-Cache-Latenzen, und die Annahme allgemeiner/zufälliger Daten.
Sobald auch nur eine dieser Annahmen wegfällt, gibt es viele Stellschrauben für bessere Performance.
Klassische Algorithmen sind ein sehr guter Ausgangspunkt, um danach stärker optimierte Lösungen zu entwickeln, sobald man mehr über die konkrete Datenform oder die Eigenschaften/Funktionen einer bestimmten CPU weiß.
An der äußersten Spitze der Optimierung betrachtet man oft, wie Daten im Speicher abgelegt und gelesen werden und ob Änderungen zur Verbesserung davon nicht spätere Schritte verschlechtern. In einem früheren Job hat einmal jemand einen bestimmten Codeteil zu lange optimiert; durch die Optimierung wurden später viele benötigte Informationen aus dem Cache verdrängt, und die Gesamtanwendung wurde langsamer.
Das ist wahrscheinlich nahe an Rob Pikes fünfter Regel des Programmierens, also eher eine Neuformulierung von etwas, das Fred Brooks in The Mythical Man Month gesagt hat. Siehe: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
Als Teenager habe ich einmal ein ganzes Wochenende darüber nachgedacht: Wenn binäre Suche gut ist, weil sie den Suchraum in jedem Schritt halbiert, müsste ternäre Suche dann nicht noch besser sein, weil sie ihn auf ein Drittel reduziert?
Statt nur den mittleren Wert zu vergleichen, vergleicht man einen Wert beim 1/3-Punkt und, wenn der zu klein ist, einen weiteren beim 2/3-Punkt.
Ich dachte damals aber, dass man pro Schritt zwar statt auf 1/2 auf 1/3 reduziert, dafür im Mittel 3/2-mal so viele Vergleiche braucht, also am Ende ungefähr gleich herauskommt.
Korrektur: Nach der Antwort von zamadatix sind es tatsächlich 5/3-mal so viele Vergleiche im Mittel, weil man in 2/3 der Fälle zwei Vergleiche braucht.
Erstes Drittel: 1 Vergleich
Zweites Drittel: 2 Vergleiche
Drittes Drittel: 2 Vergleiche
(1+2+2)/3 = im Mittel 5/3 Vergleiche. Man verschätzt sich leicht auf 50 %, weil es sich anfühlt wie „man vergleicht einmal oder zweimal“, tatsächlich ist aber die Wahrscheinlichkeit für einen Treffer beim ersten Vergleich nur 1/3 und für zwei Vergleiche 2/3.
Damit lässt sich zeigen, dass ternäre Suche bei der Gesamtzahl der Vergleiche minimal schlechter ist: 5/3*Log_3[n] = 1.052... * Log_2[n]
Also weniger Stufen, aber im Mittel mehr Vergleiche bis zum Ende. Das gilt im Allgemeinen für Suchverfahren dieser Art, also mit einer Aufteilung in mehr als 2 Teile. Natürlich basiert das auf einigen Annahmen wie gleichverteilten Suchwerten und idealisierten Operationskosten, und genau an diesem Punkt setzt die Diskussion im Artikel an.
Nicht als ternäre Version des binären Suchalgorithmus. Das wäre nämlich keine echte ternäre Suche, sondern eher eine schiefe binäre Suche. Vergleiche sind ihrem Wesen nach binär, daher ist jeder Suchalgorithmus mit Vergleichen letztlich eine Form von binärer Suche, und jede Wahl außer dem mittleren Element ist aus Sicht der algorithmischen Komplexität weniger effizient. Auf realer Hardware kann das unter bestimmten Bedingungen trotzdem besser sein. Für echte ternäre Suche bräuchte man als Grundoperation einen Dreiwegevergleich.
Interessant wird es, wenn man die „Radix-Effizienz“[1] betrachtet. Die beste Wahl ist 3, die natürliche Zahl, die e am nächsten liegt. Das hängt auch mit Baumsuchen zusammen, weshalb ternäre Bäume besser sein können als binäre.
[1] https://en.wikipedia.org/wiki/Optimal_radix_choice
Deshalb könnte die Idee, die auf damaligen CPUs nicht praktikabel war, auf heutigen CPUs deutlich eher funktionieren.