Static Search Trees: 40-mal schneller als die binäre Suche

• Implementierung eines statischen Suchbaums namens „S+ Tree“ für die schnelle Suche in sortierten Daten
• Ausgehend vom im Algorithmica-Beitrag vorgeschlagenen Code wurde dieser optimiert und um zusätzliche vorgeschlagene Ideen und Verbesserungen erweitert
• Analyse des Assembler-Codes und Optimierung aller möglichen Instruktionen zur Maximierung der Performance
• Einführung von Batching zur parallelen Verarbeitung vieler Anfragen, um den Durchsatz zu steigern
• Ziel ist es, mit dem S+ Tree Anfragen in sortierten Daten effizient auszuführen und dabei einen hohen Durchsatz aufrechtzuerhalten

1. Einführung und Motivation

• Problemdefinition:

  • Eingabe: sortierte Liste 32-Bit großer vorzeichenloser Ganzzahlen vals: Vec<u32>
  • Ausgabe: eine Datenstruktur mit minimaler Größe, die für eine bestimmte Anfrage (q) einen Wert zurückgibt, der größer oder gleich ist
  • Metrik: Anzahl unabhängig verarbeitbarer Anfragen pro Sekunde

• Ziel:

  • Aufbau effizienter Datenstrukturen in der Bioinformatik, insbesondere zur Beschleunigung der Suche in Suffix-Arrays für DNA-Sequenzindizes
  • Maximale Performance durch Nutzung von CPU-Leistung und SIMD-Instruktionen

• Empfohlene Ressourcen:

  • Forschung zu binärer Suche und Array-Layouts („Array Layouts for Comparison-Based Searching“)
  • Einführungen in S+ Trees und statische B-Trees

2. S+ Tree und Optimierungen

2.1 Binäre Suche und Eytzinger-Layout

• Die binäre Suche in der Rust-Standardbibliothek ist wenig cache-effizient und verliert bei wachsender Datengröße an Performance
• Eytzinger-Layout:
  • Speicherung eines binären Suchbaums in Array-Form zur maximalen Nutzung des Caches
  • Performance: bei Daten, die über den L3-Cache hinausgehen, bis zu 4-mal schneller als binäre Suche

2.2 Konzept des S+ Tree

• S-Tree:
  • Hexadezimaler Baum mit 15 sortierten Werten pro Knoten
  • Effizienter als ein B-Tree und besser komprimierbar als das Eytzinger-Layout
• S+ Tree:
  • Speichert alle Daten in Blattknoten und hält Kopien davon in den oberen Knoten
  • Bietet eine einfache Suche und eine effiziente Struktur

2.3 Optimierung der Funktion find

• Grundlegende lineare Suche:
  • Durchläuft die Daten und gibt einen passenden Wert zurück (ineffizient)
• Automatische Vektorisierung:
  • Umwandlung in branchless Code, 2-mal höhere Performance durch Nutzung von SIMD-Instruktionen
• Manuelle SIMD-Implementierung:
  • Manuelle Optimierung mit SIMD-Instruktionen; maximale Performance mit fünf Instruktionen

3. Batching und Prefetching

3.1 Batching

• Parallele Verarbeitung mehrerer Anfragen, um Speicherlatenzen zu überdecken
• Mit wachsender Batch-Größe steigt der Durchsatz; Sättigung bei einer maximalen Batch-Größe von 16

3.2 Prefetching

• Vorab-Laden des nächsten Knotens in den Speicher verbessert die Performance bei Daten, die über den L3-Cache hinausgehen
• In Kombination mit Batching sinkt die Verarbeitungszeit von 45 ns/query auf 30 ns/query

4. Optimierung von Datenlayout und Struktur

4.1 Änderung der Knotengröße

• Reduktion auf 15 Werte pro Knoten vereinfacht Multiplikationsoperationen und verbessert die Cache-Effizienz
• Leichte Performance-Steigerung für Daten innerhalb des L3-Cache

4.2 Änderung des Speicherlayouts

• Experimente mit umgekehrter Layout-Speicherung oder Konfigurationen mit minimalem Padding
• Weder umgekehrtes Layout noch weniger Padding hatten großen Einfluss auf die Performance

5. Datenpartitionierung

5.1 Präfixbasierte Partitionierung

• Aufteilung der Daten anhand der oberen Bits
• Performance-Gewinn bei kleinen Datenmengen, jedoch mit zusätzlichem Speicher-Overhead

5.2 Komprimierte Teilbäume

• Packen jedes Teilbaums zur Verbesserung der Platzeffizienz
• Erfordert Nachverfolgung der Partitionsgröße; die Anfragegeschwindigkeit sinkt leicht

6. Vergleich mit mehreren Threads

• Bei Verwendung von 6 Threads sinkt die Anfragezeit von 27 ns auf 7 ns
• Die RAM-Bandbreite wird zum Flaschenhals

7. Fazit und weitere Forschung

• Mehr als 40-fache Performance-Steigerung gegenüber binärer Suche (1150 ns/query → 27 ns/query)
• Nächste Aufgaben:
  • Optimierung der Datenbalance und Reduktion von RAM-Zugriffen
  • Verarbeitung von Range Queries und sortierten Anfragen
  • Integration in die Suche in Suffix-Arrays

[beenzinozino]

Wow … wenn das in die eingebauten Bibliotheken verschiedener Sprachen übernommen wird, könnte die Wirkung ziemlich enorm sein.

[GN⁺]

Hacker-News-Kommentare

• Es fällt auf, dass Rust bei Low-Level-Inhalten zu Algorithmen immer häufiger verwendet wird. Früher dominierten Inhalte in C(++) oder wissenschaftlichem Pseudocode. Die zunehmende Nutzung von Rust wird positiv gesehen

  • Rust ist mir nicht besonders vertraut, aber ich konnte Inhalte, die in Rust geschrieben sind, trotzdem verstehen. Ähnlich dazu können Rust-Programmierer wohl Algorithmusbeispiele verstehen, die in C geschrieben sind
  • Ich würde es begrüßen, wenn Rust zum Standard würde, und fände es gut, wenn daneben auch Zig verwendet würde

• Die Methode, Queries in Batches aufzuteilen, wurde nicht untersucht. Das Nachschlagen in einer Tabelle außerhalb des Caches ist der Hauptkostenfaktor

  • Wenn es genügend viele Queries gibt, kann man mehrere Ebenen des Baums auf einmal verarbeiten
  • Dabei kann das Problem entstehen, die Ergebnisse wieder in die richtige Ausgabereihenfolge zu sortieren

• Die Anzahl der int32-Werte ist nicht besonders groß, und das vollständige Bitset ist 512 MB groß. Als allgemeine Datenstruktur werden Roaring Bitmaps empfohlen

  • Wenn nur einfache Lookups nötig sind, lohnt es sich, eine minimale perfekte Hashfunktion in Betracht zu ziehen

• Es ist überraschend, wie man in Rust Low-Level-Effizienz steigern kann. Ich würde das gern mit einer C++-Implementierung vergleichen

• Der Vorteil des Eytzinger-Baums besteht darin, dass es eine Formel gibt, um Knotenindizes in Inorder-Traversal-Positionen umzuwandeln

  • Das ist nützlich, wenn der zugrunde liegende Key-Store aus einer sortierten Menge von Schlüsseln besteht
  • Mit Eytzinger kann man mehrere Schleifeniterationen im Voraus vorhersagen

• Es ist erstaunlich, dass beim Suchen von u32 in 4 GB Speicher ein Overhead von ~27 ns entsteht

  • Ich frage mich, wie die Optimierung bei einer Batch-Größe von 8 abläuft
  • Auch die Multithreading-Ergebnisse sind interessant. Beim Wechsel von 1 auf 6 Threads verbessert sich der Overhead um das Vierfache

• Es gibt viel Diskussion über Rust und C++, aber ich überlege, wie man das unter Beibehaltung von SIMD in Common Lisp implementieren könnte

• Jedes Mal, wenn ich einen Artikel über Low-Level-Optimierung lese, bin ich dem Autor dankbar, dass er Zeit investiert hat, um Nanosekunden einzusparen

  • Ich frage mich, wie viel Zeit der Menschheit durch die Summe solcher Optimierungen bereits erspart geblieben ist

• Ich glaube, in Abbildung 3 von 1.7 gibt es einen Fehler. Ich würde vorschlagen, dass die y-Achsenbeschriftung in Abbildung 1 von 1.3 "Rücktransfermenge" heißen sollte

• Wenn gelegentlich Schreibzugriffe unterstützt werden müssen, könnte man einen großen statischen Suchbaum und einen kleinen beschreibbaren Baum verwenden

  • Wenn genug Änderungen zusammengekommen sind, kann man sie in eine neue Version des statischen Baums übernehmen