Die schnellste branchless binäre Suche

• Dieser Artikel behandelt eine allgemeine C++-Implementierung der binären Suche, die kürzer ist und doppelt so schnell wie die Standardfunktion std::lower_bound.
• Die neue Implementierung ist „branchless“, weil sie zu bedingten Move-Instruktionen statt zu Verzweigungen/bedingten Sprüngen kompiliert wird.
• Die binäre Suche funktioniert, indem sie eine sortierte Liste am mittleren Element in zwei Teile aufteilt und den mittleren Wert mit einem gegebenen Wert vergleicht. Je nach Vergleichsergebnis wird entschieden, in welcher der beiden Teillisten weitergesucht wird.
• Der Artikel behandelt außerdem das Konzept der Sprungvorhersage, eine Technik, mit der Prozessoren Befehle parallel ausführen, um die Geschwindigkeit zu erhöhen. Da die binäre Suche jedoch unvorhersehbar ist, ist die Sprungvorhersage hier nicht ideal.
• Der Autor stellt sb_lower_bound vor, eine neue Implementierung der binären Suche, die schneller ist als die Standardimplementierung und die Version branchless_lower_bound. Sie ist schneller, weil die Schleife deutlich weniger Instruktionen enthält.
• Der Autor präsentiert außerdem bb_lower_bound, eine noch schnellere Version, die eine andere Methode zum Aufteilen der Suchliste verwendet.
• Der Artikel endet mit dem Vorschlag: Wenn der langsamste Teil eines Programms Suchvorgänge und/oder Vergleiche enthält, die der Prozessor nicht vorhersagen kann, sollte man clang mit -mllvm -x86-cmov-converter=false ausprobieren. Wenn eine schnellere binäre Suche benötigt wird, sollte man sb_lower_bound testen.
• Der Autor stellt außerdem Code für die neuen Implementierungen der binären Suche bereit und diskutiert ihre jeweilige Leistung im Detail.
• Der Artikel wurde außerdem mit einer refaktorierten Version von sb_lower_bound aktualisiert, die die Anzahl der Assembler-Instruktionen in der Hot Loop von 9 auf 8 reduziert, was zu einer leichten Geschwindigkeitssteigerung führt.
• Der Autor behandelt außerdem das Konzept des Prefetching, bei dem bestimmte Speicherbereiche in den Cache geladen werden, sodass beim tatsächlichen Bedarf der vorab geholten Daten nur noch L1/L2-Cache-Latenzen anfallen. Es wird auch eine Version von sb_lower_bound mit zusätzlichem Prefetching für 256 KB+ bereitgestellt.
• Der Artikel wurde von Mihail Dumitrescu geschrieben und am 24. Juni 2023 veröffentlicht.

[GN⁺]

Hacker-News-Kommentare

• Der Artikel diskutiert das Konzept und die potenziellen Vorteile einer branchlosen binären Suche.
• Ein Kommentar stellt die Notwendigkeit der Eliminierung von Branches infrage und legt nahe, dass Pipeline-Stalls durch fehlgeschlagene Branch-Prediction kein wesentlicher Teil der Architektur sind.
• Im Kommentar wird weiter erläutert, dass im Grunde jede Operation ein Branch ist und dass diese Branches der Performance nicht schaden, weil sie keine Branches in der Haupt-Pipeline sind.
• Ein anderer Kommentar schlägt vor, für die Implementierung von lowerBound die Sprache Nim zu verwenden, die in eine "Bare-Metal"-Sprache kompiliert wird.
• Es gibt eine Diskussion darüber, ob der Code den ersten Treffer oder irgendeinen Treffer zurückgibt, was die Bedeutung des Verständnisses der Funktionsweise des Codes hervorhebt.
• Ein Kommentar lobt die intuitive Einführung des Blogposts, der schnell die schnellste allgemeine C++-Implementierung der binären Suche präsentiert.
• In den Kommentaren wird darauf hingewiesen, dass die Zig-Stdlib für die binäre Suche kein C++ aufruft, und es wird ein Link zur binären Suche in der Zig-Stdlib bereitgestellt.
• Es gibt eine Diskussion über die Probleme bei binärer Suche und Branches, wobei vorgeschlagen wird, dass das Problem nicht die Branches selbst sind, sondern die Datenabhängigkeit, bei der der nächste zu ladende Speicherort unbekannt ist, bis der Vergleich abgeschlossen ist.
• In den Kommentaren werden Performance-Ergebnisse der binären Suche auf einem Cascade-Lake-Prozessor geteilt, und es wird nahegelegt, dass clang bei der Optimierung dieses speziellen Codes schlechter ist als gcc.
• Ein Kommentar stellt das Ziel des Links "BUT RUST" infrage und merkt an, dass dieser Link veraltet zu sein scheint.
• In den Kommentaren wird darauf hingewiesen, dass die Ergebnisse bei komplexeren Vergleichsfunktionen nicht bestehen bleiben, und es wird vorgeschlagen, die beste Performance zu erzielen, indem man für primitive Typen sb_lower_bound und ansonsten std::lower_bound verwendet.
• Im letzten Kommentar wird erwähnt, dass die Eigenschaft der Unvorhersagbarkeit nun den cmov-Transformations-Pass beeinflusst, und es wird ein Link für weitere Informationen bereitgestellt.