- Eine experimentelle Überprüfung der zuletzt diskutierten Schieflage zwischen I/O-Leistung und CPU-Verarbeitungsgeschwindigkeit zeigt, dass in der Praxis weiterhin die CPU die zentrale Begrenzung ist
- Die sequenzielle Lesegeschwindigkeit erreicht 1,6 GB/s mit kaltem Cache und 12,8 GB/s mit warmem Cache, während die Wortfrequenzberechnung in einem einzelnen Thread bei nur 278 MB/s liegt
- Die Branch-Struktur des Codes behindert die Vektorisierung; selbst eine einfache Optimierung der Kleinschreibungs-Konvertierung verbessert die Leistung nur auf etwa 330 MB/s
- Selbst der Befehl
wc -w erreicht nur 245 MB/s, was bestätigt, dass CPU-Berechnung und Branch-Verarbeitung statt der Festplatte den Flaschenhals bilden
- Durch manuelle Vektorisierung auf Basis von AVX2 wurde die Leistung auf 1,45 GB/s gesteigert, doch das entspricht immer noch nur etwa 11 % der sequenziellen Lesegeschwindigkeit und belegt, dass nicht I/O, sondern die CPU der Flaschenhals ist
Vergleich von I/O-Geschwindigkeit und CPU-Leistung
- Auf Grundlage der Behauptung von Ben Hoyt wurde untersucht, ob die jüngsten Steigerungen der sequenziellen Lesegeschwindigkeit die stagnierende CPU-Geschwindigkeit inzwischen überholt haben
- Bei Messung auf dieselbe Weise wurden 1,6 GB/s mit kaltem Cache und 12,8 GB/s mit warmem Cache erreicht
- Wird jedoch in einem einzelnen Thread eine Wortfrequenzberechnung durchgeführt, sind nur 278 MB/s möglich
- Selbst bei warmem Cache entspricht das nur etwa einem Fünftel der Lesegeschwindigkeit
Experiment zur Wortfrequenzberechnung in C
optimized.c wurde mit GCC 12 und den Optionen -O3 -march=native kompiliert und anschließend mit einer 425-MB-Eingabedatei ausgeführt
- Ergebnis: 1,525 Sekunden Laufzeit, 278 MB/s Durchsatz
- Mehrere Branches und frühe Abbrüche im Code behindern die Vektorisierungsoptimierung des Compilers
- Nachdem die Logik zur Kleinschreibungs-Konvertierung aus der Schleife heraus verlagert wurde, stieg die Leistung auf 330 MB/s
- Mit Clang gelingt die Vektorisierung besser
Vergleich mit einfachem Wortzählen (wc -w)
- Statt einer Frequenzberechnung wurde der Befehl
wc -w zum einfachen Zählen von Wörtern ausgeführt
- Ergebnis: 245,2 MB/s, langsamer als erwartet
wc verarbeitet verschiedene Leerraumzeichen und Locale-Zeichen wie ' ', '\n', '\t'
- Dadurch ist der Rechenaufwand höher als bei Code, der nur anhand einfacher Leerzeichen trennt
Versuch der Vektorisierung mit AVX2
- Unter Nutzung moderner CPU-Funktionen wurde eine Vektorisierung mit dem AVX2-Befehlssatz implementiert
- Verwendung von 256-Bit-Registern, Daten auf 32 Bit ausgerichtet
- Für den Vergleich von Leerraumzeichen wurde der Befehl
VPCMPEQB verwendet
- Zur Erkennung von Wortgrenzen wurden Bitmasken (PMOVMSKB) und der Befehl Find First Set(ffs) eingesetzt
- Inspiriert von der
strlen-Implementierung in Cosmopolitan libc
Leistungsergebnisse und Fazit
- Der manuell vektorisierte Code (
wc-avx2) erreichte einen Durchsatz von 1,45 GB/s
- Verifiziert wurde dasselbe Ergebnis wie bei
wc -w (82.113.300 Wörter)
- Selbst bei kaltem Cache dominiert weiterhin die Rechenzeit im User Mode
- Damit wird bestätigt, dass CPU-Berechnung und nicht Festplatten-I/O den Flaschenhals bilden
- Insgesamt ist die Festplattengeschwindigkeit ausreichend hoch, doch CPU-Operationen wie Branch-Verarbeitung und Hash-Berechnung bleiben der begrenzende Faktor
- Code und Versuchsergebnisse sind auf GitHub (
haampie/wc-avx2) veröffentlicht
Noch keine Kommentare.