Die schnellste branchless Binärsuche

 (mhdm.dev)
1 Punkte von GN⁺ 2023-08-13 | 1 Kommentare | Auf WhatsApp teilen
  • sb_lower_bound behält dieselbe Schnittstelle wie std::lower_bound bei und zeigte bis zu doppelt so hohe Geschwindigkeit wie die normale Binärsuche, wenn der Vergleichszweig zu bedingten Verschiebungen (cmov) kompiliert wird
  • Das Vergleichsergebnis bei der Binärsuche führt häufig zu fehlgeschlagener Branch Prediction, weil die Suchposition nicht im Voraus bekannt ist; unter x86 hilft die Option clang -mllvm -x86-cmov-converter=false, dies zu verringern
  • Diese Implementierung halbiert in jeder Schleife length und aktualisiert abhängig vom Vergleichsergebnis nur first, wodurch die Anzahl der Instruktionen sinkt; im Bereich 2^k <= n < 2^(k+1) vergleicht sie immer k+1 Mal
  • Im clang -cmov-Benchmark lagen die durchschnittlichen Laufzeiten bei std::lower_bound 61.30ns, sb_lower_bound 33.24ns und bb_lower_bound 32.73ns; auch das geometrische Mittel zeigte mit 39.17ns, 19.81ns bzw. 21.33ns einen deutlichen Unterschied
  • Bei der Suche in 8-Byte-Strings mit langsamer Vergleichsfunktion lag std::lower_bound teils leicht vorn; bei großen Arrays war eine Variante mit zusätzlichem Prefetching im Mittel etwa 2,3-mal schneller als std::lower_bound

Grundstruktur von sb_lower_bound

  • sb_lower_bound ist eine C++-Funktion in derselben Form wie std::lower_bound
    • Eingaben sind first, last, value, comp
    • Der Rückgabewert ist der Iterator an der Position, an der der Vergleich erstmals fehlschlägt; wenn alle Elemente die Bedingung erfüllen, wird last zurückgegeben
  • Die Kernschleife halbiert length und verschiebt first nur dann nach vorn, wenn comp(first[length], value) wahr ist
  • „branchless“ bedeutet hier nicht, dass if verschwindet, sondern dass dieses if statt zu einem bedingten Sprung zu einer bedingten Verschiebung wie cmov kompiliert wird
  • Unter clang kann diese Form mit der Option -mllvm -x86-cmov-converter=false zu bedingten Verschiebungen kompiliert werden

Wo std::lower_bound langsamer wird

  • Die gewöhnliche Binärsuche vergleicht das mittlere Element mit value und wählt danach das linke oder rechte Teilintervall
  • Wenn die Zielposition unbekannt ist, wird if (comp(first[half], value)) leicht zu einem schwer vorhersagbaren Zweig
  • Die CPU führt mit Branch Prediction die nächsten Instruktionen vorab aus, muss diese Arbeit bei einer Fehlvorhersage aber verwerfen
  • Mit bedingten Verschiebungen lassen sich abhängig vom Vergleichsergebnis Werte auswählen und bedingte Sprünge reduzieren
  • clang -cmov konnte auch einige if/else-Stellen von std::lower_bound in bedingte Verschiebungen umwandeln und beschleunigte es damit um etwa 25 %
  • Für gcc gibt es in derselben Situation keine gute Option, um bedingte Verschiebungen zu erzwingen, und auch sb_lower_bound wird dort derzeit unabhängig vom Optimierungsgrad nicht als branchless Code ausgegeben

„Optimale“ Suche aus Sicht der Vergleichsanzahl

  • „Optimal“ bedeutet hier, dass die Anzahl der Vergleiche bei der Binärsuche minimal ist
  • In einer Liste der Größe n hat std::lower_bound insgesamt n+1 mögliche Ergebnisse: n Elementpositionen plus die Endposition
  • Hat die Liste die Größe 2^k - 1, dann gibt es 2^k mögliche Ergebnisse; da jeder Vergleich 1 Bit Information in Form von wahr/falsch liefert, beträgt die optimale Vergleichsanzahl k
  • Im „schönen“ Fall einer Länge von 2^k - 1 ist eine optimale Suche mit einer sehr kurzen Schleife möglich
  • Passt die Länge nicht dazu, kann es zu Zugriffen außerhalb des Bereichs kommen, etwa wenn in [0, 1, 2, 3, 4, 5] nach dem Wert 4 gesucht wird

Leistungseigenschaften und Einschränkungen von sb_lower_bound

  • Wenn sb_lower_bound ein Intervall gerader Länge teilt, überspringt es in manchen Fällen selbst bei wahrem Vergleichsergebnis nicht genug Elemente
  • Im Bereich 2^k <= n < 2^(k+1) werden immer k+1 Vergleiche durchgeführt
  • Im selben Bereich benötigt std::lower_bound entweder k oder k+1 Vergleiche und im Mittel etwa log2(n+1) Vergleiche
  • Es kann also mehr Vergleiche geben, doch die Zahl der Instruktionen in der Schleife ist deutlich kleiner, sodass die Gesamtlaufzeit trotzdem schneller ausfällt
  • Wenn die Vergleichsfunktion sehr langsam ist, kann der Unterschied zwischen k+1 und log2(n+1) die Leistung beeinflussen
  • Um unter gcc bedingte Verschiebungen zu erzwingen, kann man x86-spezifisches Inline-Assembly mit cmov verwenden; die einfache Variante erhöht jedoch die Instruktionszahl, während Alternativen getrenntes typspezifisches Assembly erfordern

Die schnellere Variante bb_lower_bound

  • bb_lower_bound teilt das Intervall zunächst auf andere Weise, bis die Länge die Form 2^k - 1 hat, und sucht dann in einer schnellen zweiten Schleife weiter
  • length & (length + 1) wird verwendet, um zu prüfen, ob die Länge die Form 11..1, also 2^k - 1, hat
  • Bei ungünstigen Längen wird der MAGIC-Wert auto step = length / 8 * 6 + 1 verwendet, um sich schnell einem „schönen“ Intervall zu nähern
  • step sollte meist mindestens length / 2 sein, damit oft in die schnelle Schleife gewechselt werden kann; liegt es aber zu nahe an length, geht der Vorteil der Binärsuche verloren
  • Wegen break hat bb_lower_bound eine Form mit Verzweigung
  • Ein Ansatz mit einer vorberechneten Tabelle der schnellsten step-Werte für alle Längen wurde noch nicht untersucht

Eine vollständig branchless Implementierung war nicht schneller

  • Auf 64-Bit-Maschinen läuft die Schleife von sb_lower_bound höchstens 64-mal, daher lässt sich mit switch und absichtlichem Fall-through eine „vollständig branchless“ Version bauen, die sogar die length-Prüfung entfernt
  • Diese Struktur springt mithilfe von std::bit_width(length) direkt an die passende Codeposition für die benötigte Vergleichsanzahl
  • In der Praxis war sie nicht schneller
  • Moderne x86-CPUs verarbeiten gut vorhersagbare Zweige wie Schleifenbedingungen sehr effizient, daher brachte das Entfernen der length-Prüfung keinen Vorteil
  • Auch weil sich so Templates, Makros und Copy-and-Modify für 64 Fälle vermeiden lassen, wurde die normale Schleife als bessere Lösung bewertet

Benchmark-Ergebnisse

  • Die Ergebnisse der durchschnittlichen Laufzeit (ns) unter clang -cmov waren wie folgt
    • std::lower_: 61.30
    • branchless_lower_: 43.43
    • asm_lower_: 54.32
    • sb_lower_: 33.24
    • sbm_lower_: 35.54
    • bb_lower_: 32.73
  • Auch beim geometrischen Mittel der Laufzeit (ns) war sb_lower_ am niedrigsten
    • std::lower_: 39.17
    • branchless_lower_: 25.14
    • asm_lower_: 31.21
    • sb_lower_: 19.81
    • sbm_lower_: 20.91
    • bb_lower_: 21.33
  • sbm_lower_bound ist eine Variante, die mit first += comp(first[length], value) * (length + rem) statt if arbeitet, um gcc zur Erzeugung bedingter Verschiebungen zu bewegen
  • Diese Optimierung könnte in einer zukünftigen gcc-Version verschwinden und sollte daher kommentiert und mit Vorsicht verwendet werden
  • Für den Benchmark wurden g++-10, clang++-10 und clang++-10 -mllvm -x86-cmov-converter=false mit -march=haswell verwendet
  • -march=native oder ein nicht gesetztes -march hatten keinen großen Einfluss auf die Rangfolge; getestet wurde auf einem Intel i7 Kaby Lake

Messung fehlgeschlagener Branch Prediction

  • Eine normale clang-Ausführung, gemessen mit perf, verzeichnete etwa 6,94 Milliarden branches und etwa 1,20 Milliarden branch-misses; die branch-misses-Rate lag bei 17,34 %
  • Die Ausführung mit clang -cmov verzeichnete etwa 4,07 Milliarden branches und etwa 35,95 Millionen branch-misses; die branch-misses-Rate sank auf 0,88 %
  • -cmov eliminierte etwa 2,9 Milliarden Verzweigungen und etwa 1,2 Milliarden Fehlvorhersagen
  • Die entfernten Verzweigungen hatten eine Fehlvorhersagewahrscheinlichkeit von etwa 41 %
  • Das liegt nahe an den 50 %, die man bei vollständig unvorhersagbaren Verzweigungen erwarten würde

Bei langsamen Vergleichsfunktionen sieht das Ergebnis anders aus

  • Um einen Fall mit langsamerer Vergleichsfunktion zu betrachten, wurde die Suche in 8-Byte-Strings getestet
  • Bei den durchschnittlichen Laufzeiten (ns) war std::lower_bound leicht schneller als sb_lower_bound oder lag ungefähr gleichauf
    • gcc: std::lower_ 160.01, sb_lower_ 165.66
    • clang: std::lower_ 157.71, sb_lower_ 162.68, bb_lower_ 157.22
    • clang -cmov: std::lower_ 156.06, sb_lower_ 164.71, bb_lower_ 157.48
  • In diesem Fall war std::lower_bound durchgehend ein klein wenig schneller als sb_lower_bound
  • Für optimale Leistung kann eine Bibliothek sb_lower_bound bei primitiven Typen direkt verwenden und sonst std::lower_bound einsetzen

Unterschiede im Assembly

  • Die Hot-Loop von std::lower_bound unter clang -cmov enthält bedingte Verschiebungen wie cmova und cmovbe, verwendet aber mehrere Instruktionen für die Aktualisierung von Länge und Position
  • Die Hot-Loop von sb_lower_bound berechnet halbe Länge, Rest und den zu verschiebenden Pointer und aktualisiert first dann mit cmova
  • Das Assembly von branchless_lower_bound ist sehr kurz und sauber, aber in den Leistungstests erzielte sb_lower_bound dank geringerer Overheads bessere Ergebnisse

Update: noch kürzeres sb_lower_bound

  • Nach einem Kommentar des orlp.net author kann sb_lower_bound so refaktoriert werden, dass die Anzahl der Hot-Loop-Assemblyinstruktionen von 9 auf 8 sinkt
  • Der Kernpunkt ist, dass length - half gleich half + length % 2 ist
  • Die refaktorierte Form berechnet half = length / 2, führt bei wahrem Vergleich first += length - half aus und setzt danach length = half
  • Unter clang -cmov verbesserte sich die durchschnittliche Laufzeit dadurch leicht von etwa 33ns auf etwa 32ns

Bei großen Arrays ist Prefetching effektiv

  • Das in den Kommentaren vorgeschlagene Prefetching lädt benötigte Daten vorab in den L1-/L2-Cache, um die Latenz beim eigentlichen Zugriff zu verringern
  • Beispielhafte Latenzen sind etwa 4 Zyklen für L1, 12 Zyklen für L2, 40 Zyklen für L3 und 200 Zyklen für Hauptspeicher
  • Sowohl gcc als auch clang unterstützen __builtin_prefetch()
  • Beim Prefetchen der Position length / 4 ist jeder zweite Zugriff vergeudet; fügt man length / 8 hinzu, sind fünf von sechs Zugriffen vergeudet
  • Auch die Berechnung der Prefetch-Positionen und die Aufrufe selbst verursachen Overhead, der in einer kurz gehaltenen Hot-Loop relevant ist
  • Mehrere Prefetch-Strategien halfen bei Arrays unter 256KB nicht
  • Ab 256KB verbesserte sbp_lower_bound mit zusätzlichem Prefetching die durchschnittliche Laufzeit in Tests bis etwa 4 Millionen Einträgen bzw. 16MB von etwa 32ns auf etwa 26ns
  • In späteren Tests mit bis zu etwa 128 Millionen Einträgen bzw. 512MB war die Prefetch-Version nach durchschnittlicher Laufzeit etwa 2,3-mal schneller als std::lower_bound
    • Zum Vergleich: std::lower_bound etwa 161ns, Prefetch-Version etwa 71ns

Beobachtungen bei großen Datensätzen und Alternativen

  • Bei sehr großen Größen war die von clang -cmov erzeugte branchless Variante von std::lower_bound langsamer als die Version mit Verzweigungen
  • Moderne CPUs können entlang korrekt vorhergesagter Zweige Speicherladungen und spekulative Ausführung vorziehen, was faktisch wie Prefetching wirken kann
  • sbpm_lower_bound ist eine Version von sbm_lower_bound mit zusätzlichem Prefetching und nutzt boolesche Multiplikation, um gcc zur Erzeugung branchless Codes zu bewegen
  • Zwischen 1 Million und 10 Millionen Elementen gab es Sprünge in der Leistungskurve, sodass theoretisch noch Raum für eine schnellere Implementierung besteht
  • Allerdings wird der Prefetching-Code immer komplexer und enthält mehr magische Konstanten, wodurch eine mögliche Aufnahme in gcc/libstdc++ oder llvm/libc++ mit zunehmender Komplexität unwahrscheinlicher erscheint
  • Eine Alternative, die die Einschränkungen von std::lower_bound aufbricht, ist Eytzinger Binary Search, bei der das Eingabearray in Form eines Heap aus binären Mittelpunkten umgeordnet wird, um cachefreundlicher zu suchen
  • Im Test eines int-16-ary-tree von Sergey Slotin at CppCon 2022 ergaben sich Geschwindigkeiten von 7x bis 15x gegenüber std::lower_bound

Code und Einsatzbedingungen

  • Wenn Suchen oder Vergleiche der langsamste Teil des Programms sind und der Prozessor das Vergleichsergebnis schwer vorhersagen kann, kann man unter x86 die clang-Option -mllvm -x86-cmov-converter=false ausprobieren
  • Wenn eine schnellere Binärsuche benötigt wird, kann sb_lower_bound ausprobiert werden; unter gcc ist auch sbm_lower_bound eine Option
  • Der Code ist unter der MIT-Lizenz veröffentlicht
  • Code und Benchmarks sind unter github.com/mh-dm/sb_lower_bound/ verfügbar

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-08-13
Meinungen auf Hacker News

  • Jedes Mal, wenn ich sehe, dass Leute versuchen, Branches zu eliminieren, frage ich mich, ob ihnen bewusst ist, dass es kein notwendiger Bestandteil einer CPU-Architektur ist, dass Branch-Mispredictions lange Pipelines zum Stillstand bringen
    Pipelines sind lang, weil kurz vor der Ausführung viel Analyse und Transformation stattfindet; da es sich aber nicht um Algorithmen mit starker Zustandsabhängigkeit handelt, ließe sich das meiste im Voraus erledigen
    Die Transmeta-Crusoe-CPU arbeitete auf diese Weise, und man kann sich eine Welt vorstellen, in der man sich um Branches keine Gedanken machen muss
    Tiefer betrachtet ist jede Operation ein Branch, der den Bitzustand betrachtet und das Ergebnis ändert, aber solche lokalen Branches innerhalb der ALU liegen nicht als Branches auf der Hauptpipeline und schaden der Performance daher nicht stark

    • Bist du Dave? :-) Es gab früher ein Paper, das superskalares CISC und uniskalares RISC unter dem Gesichtspunkt von Durchsatz pro Zeit und Instruktionen pro Takt verglich
      Ich erinnere mich, dass ich damals auch srk sagte, dass die Wahl zwischen IPC und Durchsatz als Metrik beeinflusst, was man als gut oder schlecht ansieht
      Die IPC-Seite geht davon aus: Wenn man eine höhere IPC erreicht, erhöht die Fertigung den Takt und alle gewinnen; die Durchsatz-Seite verfolgt den realistischeren Ansatz, dass Moores Gesetz tot ist und Silizium schmilzt, wenn man es schneller betreibt, also gewinnt die Seite mit dem klügeren ISA-Design
      In den letzten 20 Jahren hatten beide Seiten Erfolge und Rückschläge, und es ist interessant, dass RISC-V diese Frage in der CPU-Architektur heute wieder aufgreift
      Es ist auch ein guter Ort, um zu verfolgen, wie auf Basis der Flexibilität des Instruktionssatzes moderne superskalare Ideen ergänzt werden, und langfristig wird sich diese Richtung meiner Meinung nach durchsetzen
    • Das ist völlig falsch gedacht
      Die Übersetzung von Transmeta hat die Kosten von Branches nicht beseitigt
      Mir ist in Erinnerung geblieben, dass Linus, der bei Transmeta arbeitete, in einem comp.arch-Thread sinngemäß sagte: „Die Aufgabe einer CPU ist es, Cache-Misses so schnell wie möglich zu erzeugen“
      Erzwungene Cache-Misses existieren, und kein JIT kann sie eliminieren
      In der realen Welt lassen sich selbst mit den heute riesigen Caches auch Kapazitäts-Misses nicht vermeiden
      Auch Itanium ging davon aus, Branch-Kosten durch statische Analyse beseitigen zu können; man muss sich nur ansehen, wie das ausging
      Ich wünschte, Programmierer würden ein paar Bücher über Computerarchitektur lesen, bevor sie selbstbewusst schließen, dass sie leicht etwas Besseres bauen können als moderne Prozessoren
      Meiner Ansicht nach unterschätzen sie den Umfang der geistigen Arbeit, die in heutigen Prozessoren steckt, um mindestens 7 Größenordnungen
    • Es mag zustandslos sein können, hängt aber stark von Faktoren ab, die zur Compile-Zeit unbekannt sind
      Einer davon sind die Eingabedaten, die verarbeitet werden
      Binäre Suche ist genau so ein Fall: Der Compiler weiß nicht, an welcher Position das Ergebnis gefunden wird
      Ein weiterer ist die Mikroarchitektur, insbesondere die Cache-Hierarchie und die Konfiguration der Ausführungseinheiten
      Wenn man auf eine ISA umstellt, deren Instruktionen den Mikro-Operationen heutiger CPUs ähneln, müsste man für jede Mikroarchitektur neu kompilieren
      Technisch ließe sich das allerdings durch einen OS-JIT lösen, ähnlich wie heutige GPUs Programme in Bytecode-Formaten (DXBC, SPIR-V, NVPTX) ausliefern und der User-Mode-GPU-Treiber sie in die tatsächlichen Hardware-Instruktionen rekompiliert
      Die größere Variable ist, dass andere CPU-Threads unbekannten Code ausführen
      Selbst wenn man Hyperthreading abschafft und Kerne unabhängig macht, bleiben weiterhin chipweit geteilte Ressourcen wie L3-Cache, externer Speicher, I/O-Bandbreite, Leistung und Wärme
    • Ich glaube, der Kern liegt in der Definition von Branch
      Wenn man alles als Branch™ neu definiert, lassen sich manche Branches™ im Voraus berechnen, einschließlich Dingen, die eigentlich keine Branches sind
      Aber geht es bei dem, was man üblicherweise Branch-Eliminierung nennt, nicht um Fälle, in denen sich der tatsächliche Rechenpfad in Code wie if/else aufteilt?
      Auch in einer solchen Welt wären nützliche Optimierungen möglich, aber sie wären auf Branches™ beschränkt, die versuchen, mehrere zukünftige Ergebnisse gleichzeitig zu berechnen
    • Man könnte den Grund für lange Pipelines auch so umformulieren, dass es im Prozessor viele unabhängige Arbeiten gibt, die gleichzeitig erledigt werden können
      Jedes Mal, wenn es unabhängig ausführbare Operationen gibt, entsteht entsprechend die Möglichkeit, sie parallel auszuführen
      Es geht nicht nur um Decoding, Fetching und Ausführung
      Wenn es eine unabhängige ALU und einen Shifter gibt, kann man während einer Addition auch shiften; wenn es einen dedizierten Addierer und einen Multiplizierer gibt, gibt es keinen Grund, nicht beides gleichzeitig zu versuchen
      Das führt unmittelbar dazu, dass man mehrere Instruktionen gleichzeitig in Arbeit haben möchte, und bedeutet, dass man Instruktionen schneller fetchen und decodieren können muss, als sie verarbeitet werden
      Außerdem führt es natürlich zu Situationen, in denen man umordnen möchte, damit N Add-Instruktionen einen unabhängigen Shift nicht blockieren
      Man kann der Meinung sein, dass die heutige Struktur unnötig komplex ist, und damit vielleicht nicht falsch liegen
      Dennoch steckt enorme Ingenieursarbeit darin, die aktuelle Struktur zu bauen; wenn man also glaubt, dass es ohne diesen Ansatz viel schneller ginge, sollte man gründlich untersuchen, wie zutreffend diese Behauptung ist

  • Bei der Stelle „Wenn es doch nur eine saubere und schnelle Bare-Metal-Sprache gäbe, um all das zu schreiben …“ hat der Autor zwar Fußnoten zu „BUT RUST..“ und „BUT ZIG..“ eingefügt, aber ich frage mich, wie es mit Nim wäre
    Es scheint eine native Library-Implementierung von lowerBound zu geben: https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
    Streng genommen ist es keine „Bare-Metal“-Sprache, aber da es nach C oder C++ kompiliert, wäre interessant zu sehen, zu welchem Code das hier kompiliert
    Und ich frage mich auch, was an C das Problem ist

  • Ich bin mir nicht sicher, ob das immer noch lower_bound ist
    Vielleicht lese ich den Code falsch, aber bei Duplikaten scheint er nicht den ersten Treffer, sondern irgendeinen Treffer zurückzugeben
    Wenn die Vergleichsfunktion für Autovervollständigung nach einem bestimmten String-Präfix sucht, können auch in einer eindeutigen Liste mehrere Einträge passen, und dann will man den ersten Eintrag in der Liste

    • Bei jedem Treffer wird die verbleibende Länge halbiert, und die Schleife wird erst verlassen, wenn die Länge 0 ist, also sollte der erste Eintrag zurückgegeben werden
    • Es wirkt gut, eine Option für höhere Geschwindigkeit zu haben, wenn einem egal ist, welcher Treffer genau zurückkommt
    • Für mich sieht es so aus, als würde der erste passende Eintrag zurückgegeben
      Mich würde interessieren, warum du das anders siehst

  • Ich wünschte, alle Blogposts würden so anfangen wie dieser: „Sie sind beschäftigt, also kommen wir direkt zur Sache. Hier ist die schnellste, allgemeinste und einfachste C++-Implementierung der binären Suche“

  • Die Zig-Standardbibliothek ruft für die binäre Suche nicht C++ auf
    Die aktuelle binäre Suche ist hier: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

  • Ich verstehe es nicht ganz
    Das Problem bei binärer Suche und Branches ist nicht der Branch an sich, sondern dass man bis zum Abschluss des Vergleichs nicht weiß, welche Speicherposition im Array als Nächstes geholt werden muss
    Ob man Branches oder etwas anderes verwendet, ist egal; letztlich geht es darum, was man vom Prozessor möchte
    Es gibt eine Datenabhängigkeit
    Bevor man den mittleren Index gelesen hat, weiß man nicht, ob man im oberen oder im unteren Bereich suchen muss
    Man kann spekulieren und Reads für beide Seiten ausgeben, dann ist die Abhängigkeit gelöst, aber der Speichertraffic steigt
    Ob das der richtige Trade-off ist, ist der Kernpunkt; einfach nur Branches zu entfernen ist nicht die Antwort

  • Auf meinem Cascade-Lake-Prozessor senkt -mllvm -x86-cmov-converter=false die Performance der binären Suche fast um die Hälfte
    Die Zahlen sind Nanosekunden pro bsearch auf einem 100-MB-uint32-Array
    clang 15.0.7 scheint bei dieser speziellen Code-Optimierung deutlich schlechter zu sein als gcc 13.2.1
    Das Assembly kann man hier sehen: https://godbolt.org/z/cbx5Kdjs6
    Das gcc-Assembly sieht deutlich sauberer aus

    Benchmark gcc clang clang -cmov
    slow u32 23.4 46.7 45.8
    fast u32 18.1 19.8 31.4
    • Dann sollte man sich https://mhdm.dev/posts/sb_lower_bound/#prefetching ansehen
      100 MB sind groß genug, dass die Version mit Branches leicht im Vorteil ist, aber eher wegen der Eigenschaften der spekulativen Ausführung auf x86, nicht weil sie besser wäre

  • Weiß jemand, wohin der „BUT RUST“-Link ursprünglich führen sollte?
    Er war nicht versionsfixiert und scheint schon kaputt zu sein; vielleicht sollte er auch nur mitten in den Doku-Kommentar von starts_with zeigen

    • Wenn man sich die archive.org-Snapshots kurz vor [1] und kurz nach [2] der Veröffentlichung des Artikels ansieht, scheint er auf diese Codezeile gezeigt haben zu sollen, die jetzt Zeile 2779 [3] ist
      let mid = left + size / 2;

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

  • Sollte auf Rusts Implementierung der binären Suche verlinken
    Wurde auf https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#... aktualisiert

  • Interessant ist, dass das Ergebnis bei komplexeren comp-Vergleichsfunktionen nicht bestehen bleibt
    Im Artikel wurden einigermaßen realistische Szenarien für binäre Suche mit langsamen Vergleichsfunktionen betrachtet, etwa IDs, Telefonnummern, Konten und Keywords; deshalb wurden Suchen nach 8-Byte-Strings getestet
    In diesem Fall ist std::lower_bound ganz leicht, aber konsistent schneller als sb_lower_bound; um stets die beste Performance zu erzielen, sollte die Bibliothek demnach sb_lower_bound verwenden, wenn sie primitive Typen direkt behandelt, und ansonsten std::lower_bound
    Die Analyse hierzu würde ich gern sehen

    • Ich vermute, dass dies dank Branch Prediction passiert: Mehrere Vergleiche können gleichzeitig in die Pipeline geschickt und bei einer Fehlvorhersage zurückgerollt werden
      Bei wirklich zufälligen Daten und Eingaben läge die Vorhersage ungefähr in der Hälfte der Fälle falsch
      Der CMOV-Ansatz wird nach der Vergleichsfunktion durch eine Datenabhängigkeit ausgebremst
      Im Schnitt führt der Branch-Ansatz zwei Vergleiche auf einmal aus, CMOV dagegen einen; wenn die Vergleichszeit also größer wird als die Penalty einer Branch-Misprediction, dürfte es einen Kipppunkt geben
    • Wenn das der Fall ist, gibt es für primitive Typen vermutlich eine deutlich bessere Version der binären Suche
      Etwas, das ich früher grob mit SIMD gebaut habe, war bis zum Erreichen der Speicherbandbreiten-Grenze 3-mal schneller als std::lower_bound: https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
    • Abgesehen von der Aussage, dass sie „unvorhersagbar“ seien, konnte ich im Artikel keine Garantien zum Inhalt des Eingabedatensatzes oder der Suchschlüssel finden
      Ich nehme reine Zufälligkeit an, aber wenn diese 8-Byte-Strings keine reine Information sind, können moderne Branch Predictor leicht besser abschneiden als cmov

  • Das Attribut unpredictable scheint nun die cmov-Transformations-Pass zu beeinflussen
    Stand 1. Juni, dürfte also vermutlich in clang 17/18 landen: https://reviews.llvm.org/D118118