Heute stellen wir Open-Source-Code vor, der Arrays von Zahlen etwa zehnmal so schnell sortieren kann wie C++ std::sort und modernste architekturspezifische Algorithmen übertrifft, während er auf allen modernen CPU-Architekturen portabel ist. Im Folgenden erläutern wir, wie wir dies erreicht haben.

Zunächst etwas Hintergrund. Es gibt einen recenten Trend zu spaltenorientierten Datenbanken, die alle Werte einer bestimmten Spalte aufeinanderfolgend speichern, anstatt alle Felder eines Datensatzes oder „Zeile“ vor denen des nächsten Datensatzes zu speichern. Dies kann schneller zu filtern oder zu sortieren sein, was Schlüsselbausteine für SQL-Abfragen sind; daher konzentrieren wir uns auf dieses Datenlayout.

Angesichts der Tatsache, dass Sortieren intensiv untersucht wurde, wie können wir eine 10-fache Beschleunigung finden? Die Antwort liegt in SIMD/Vektor-Befehlen. Diese führen Operationen an mehreren unabhängigen Elementen in einem einzigen Befehl aus—zum Beispiel die Arbeit an 16 float32 gleichzeitig bei Verwendung des AVX-512-Befehlssatzes oder an vier bei Arm NEON.

Wenn Sie bereits mit SIMD vertraut sind, haben Sie vielleicht gehört, dass es in Supercomputern, linearer Algebra für Machine-Learning-Anwendungen, Videoverarbeitung oder Bildcodecs wie JPEG XL verwendet wird. Aber wenn SIMD-Operationen nur unabhängige Elemente betreffen, wie können wir sie dann sortieren, was das Neuordnen benachbarter Array-Elemente beinhaltet? Stellen Sie sich vor, wir haben eine spezielle Methode zum Sortieren, zum Beispiel von 256-Element-Arrays. Dann besteht der Quicksort-Algorithmus zum Sortieren eines größeren Arrays darin, es in zwei Teilarrays zu partitionieren: diejenigen, die kleiner als ein „Pivot“-Wert (idealerweise der Median) sind, und alle anderen; dann rekursiv, bis ein Teilarray höchstens 256 Elemente groß ist, und unsere spezielle Methode zum Sortieren dieser zu verwenden. Die Partitionierung macht den größten Teil der CPU-Zeit aus, also wenn wir sie mit SIMD beschleunigen können, haben wir eine schnelle Sortierung.

Glücklicherweise enthalten moderne Befehlssätze (Arm SVE, RISC-V V, x86 AVX-512) einen speziellen Befehl, der für die Partitionierung geeignet ist. Bei einer separaten Eingabe von Ja/Nein-Werten (ob ein Element kleiner als der Pivot ist) speichert dieser „Compress-Store“-Befehl nur die Elemente in aufeinanderfolgendem Speicher, deren entsprechende Eingabe „Ja“ ist. Wir können dann die Ja/Nein-Werte logisch negieren und den Befehl erneut anwenden, um die Elemente in die andere Partition zu schreiben. Diese Strategie wurde in einem AVX-512-spezifischen Quicksort verwendet. Aber was ist mit anderen Befehlssätzen wie AVX2, die kein Compress-Store haben? Frühere Arbeiten haben gezeigt, wie man diesen Befehl mit Permute-Befehlen emuliert. Wir bauen auf diesen Techniken auf, um den ersten vektorisierten Quicksort zu erreichen, der auf sechs Befehlssätze über drei Architekturen portierbar ist und tatsächlich frühere architekturspezifische Sortierungen übertrifft.

Unsere Implementierung verwendet die portablen SIMD-Funktionen von Highway, sodass wir nicht etwa 3.000 Zeilen C++ für jede Plattform neu implementieren müssen. Highway verwendet Compress-Store, wenn verfügbar, andernfalls die äquivalenten Permute-Befehle. Im Gegensatz zum vorherigen Stand der Technik—der auch spezifisch für 32-Bit-Ganzzahlen war—unterstützen wir eine vollständige Bandbreite von 16-128-Bit-Eingaben. Trotz unserer einzigen portablen Implementierung erreichen wir rekordverdächtige Geschwindigkeiten sowohl auf AVX2, AVX-512 (Intel Skylake) als auch Arm NEON (Apple M1). Für eine Million 32/64/128-Bit-Zahlen kann unser Code auf Apple M1 sortierte Ausgaben mit Raten von 499/471/466 MB/s erzeugen. Auf einem 3 GHz Skylake mit AVX-512 liegen die Geschwindigkeiten bei 1123/1119/1120 MB/s. Interessanterweise ist AVX-512 1,4-1,6-mal so schnell wie AVX2—eine lohnende Beschleunigung für null zusätzlichen Aufwand (Highway prüft, welche Befehle auf der CPU verfügbar sind, und verwendet die besten verfügbaren). Bei Ausführung auf AVX2 messen wir 798 MB/s, während der frühere, für AVX2 optimierte Stand der Technik nur 699 MB/s erreicht. Zum Vergleich: Die Standardbibliothek erreicht 58/128/117 MB/s auf derselben CPU, sodass wir je nach Art der Zahlen eine 9-19-fache Beschleunigung erzielt haben.

Früher galt Sortieren als teuer. Wir sind gespannt, welche neuen Anwendungen und Fähigkeiten durch die Möglichkeit, mit 1 GB/s auf einem einzelnen CPU-Kern zu sortieren, erschlossen werden. Die Apache2-lizenzierte Quelle ...