Heute werden wir die Leistung verschiedener Implementierungen der Topper-Funktion messen, da dies dienstags der Fall ist.
Eigentlich
interessiert mich die
Topper- Funktion nicht, ich habe erst kürzlich einen weiteren Beitrag geschrieben und brauchte eine Art gemeinsamen Handlungskern, und
Topper scheint ein ziemlich interessanter und harmloser Kandidat für Benchmarks zu sein. Ich habe versucht, etwas so einfaches wie möglich zu wählen, das mich nicht zur Seite führt, aber es ist einfach so passiert, dass ich in diesem Test auf ein seltsames Problem gestoßen bin.
Dieser Beitrag wird klein sein - ein umfassenderer Artikel zum ursprünglichen, vielleicht interessanteren Thema wird in Kürze erwartet. Wenn du die Ergebnisse mit mir reproduzieren willst, kannst du
den Quellcode
auf github nehmen .
Schauen wir uns also drei Implementierungen der Funktion
toupper an , mit der die Zeichen eines Arrays, das aus Elementen vom Typ
char besteht, in Großbuchstaben konvertiert werden. Dabei wird ein Array als Argument verwendet und seine Elemente direkt so geändert, dass alle Kleinbuchstaben groß geschrieben werden.
In der ersten Implementierung rufen wir einfach
die Funktion toupper [1]
der C-Standardbibliothek auf und führen eine Schleife im C-Stil aus:
void toupper_rawloop(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { buf[i] = toupper(buf[i]); } }
In der zweiten Implementierung verwenden wir einen
moderneren Ansatz, indem wir den Rohzyklus durch
std :: transform ersetzen:
void toupper_transform(char* buf, size_t size) { std::transform(buf, buf + size, buf, ::toupper); }
Schließlich verwenden wir in der dritten Implementierung einen speziellen Algorithmus, der mit ASCII-Zeichen arbeitet. Es prüft, ob das Zeichen im Bereich von
a bis z liegt , und ersetzt bei Erfolg den gleichen Buchstaben in Großbuchstaben, wobei die Zahl 32 vom Zeichencode [2] abgezogen wird:
void toupper_branch(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { char c = buf[i]; if (c >= 'a' && c <= 'z') { buf[i] = c - 32; } } }
Sieht einfach aus, oder?
Jetzt messen wir die Geschwindigkeit dieser Implementierungen auf meinem Laptop mit dem Skylake i7-6700HQ-Prozessor auf dem gcc 5.5-Compiler mit den Standardeinstellungen. Die Ergebnisse werden in Form eines Streudiagramms angegeben [3]:
Wir werden uns sofort mit drei Fragen befassen, die für unsere Aufgabe irrelevant sind.
Schauen Sie sich zunächst das Diagramm des Verzweigungsalgorithmus an (grün dargestellt). Sie variiert je nach Größe der Eingabedaten erheblich - die beiden anderen Diagramme bleiben nahezu flach. Dies ist eigentlich nur ein Testartefakt. Die eingegebenen ASCII-Zeichen werden zufällig ausgewählt [4], daher ist der entscheidende Faktor im Fall der dritten Implementierung die Operation des Verzweigungsvorhersagealgorithmus. Mit einer kleinen Datenmenge wird die Reihenfolge der Elemente während der Iteration vollständig gespeichert, sodass die Anzahl der Fehlschläge gering und die Geschwindigkeit hoch ist,
wie in dieser Anmerkung gezeigt . Mit zunehmender Größe der Datensequenz merkt sich der Vorhersagealgorithmus immer weniger, bis er schließlich mit jedem Großbuchstaben (0,27 Fehler pro Zeichen) zu verfehlen beginnt, und dann wird der Graph nivelliert.
Achten Sie zweitens auf die Gruppe der grünen Punkte oben links, die den viel niedrigeren Geschwindigkeiten der Variante mit Verzweigung
toupper_branch entsprechen :
Dies ist kein isoliertes Artefakt: Solche Stellen traten bei mehreren Starts auf. Gleichzeitig können sie nicht reproduziert werden, wenn Sie den Algorithmus nur speziell für diese Datengrößen testen. Sie werden nur angezeigt, wenn der Test für alle Größen ausgeführt wird. In diesem Fall werden sie jedoch nicht immer angezeigt. Ich habe mich nicht speziell damit befasst, kann aber davon ausgehen, dass dies auf Konflikte bei Namen oder Aliasen im Algorithmus für die Verzweigungsvorhersage zurückzuführen ist oder wenn physische Seiten mit 4 kB Arbeitsspeicher auf virtuell abgebildet werden (obwohl die Randomisierung des virtuellen Adressraums deaktiviert war).
Drittens sieht die Implementierung von
toupper_rawloop (in Blau dargestellt) in der Grafik wie zwei separate Linien aus: eine geringfügig über der Marke von 2 Kennzahlen pro Zeichen und die andere auf der Ebene von 1,5 Kennzahlen pro Zeichen. Diese beiden Zeilen tauchten bei allen Testern auf. Die schnellere Option mit einer Geschwindigkeit von 1,57 Zeichen pro Zyklus verlangsamt die Download-Ports tatsächlich: Das Lesen der Daten an den Ports 2 und 3 erfolgt mit einer Geschwindigkeit von 1,54 Mikrooperationen pro Zyklus, sodass diese zu 98% ausgelastet sind. Ich konnte den Grund für das langsamere „Regime“ nicht feststellen.
Während ich mich mit diesem Thema beschäftigte, verschwand das schnelle „Regime“ plötzlich und nur das langsame blieb übrig. Vielleicht hat der Prozessor gemerkt, was ich versucht habe, und hat das Update für den Mikrocode heimlich heruntergeladen, um den Widerspruch zu beseitigen, aber ich habe (noch) Beweise - ein Vektorbild mit Diagrammen.
Was interessiert uns dann an diesem Beispiel?
Was uns jedoch interessiert, ist, dass die Version mit einem Rohzyklus 3-4 mal schneller ist als die Version mit
std :: transform : 1,5-2 Zyklen pro Zeichen gegenüber 7 mit einigen Zyklen pro Zeichen.
Was ist hier los? Haben mich Standardalgorithmen gescheitert? Hat
std :: transform einen Fehler?
Nicht wirklich. Genauer gesagt, überhaupt nicht.
Es stellt sich heraus, dass solche Ergebnisse auftreten, wenn Funktionen in
verschiedenen Dateien kompiliert
werden . Wenn Sie sie in dieselbe Datei einfügen, ist ihre Leistung gleichermaßen niedrig.
Und nein, Ausrichtung hat nichts damit zu tun.
Das ist aber noch nicht alles: Die schnelle Version mit einem Rohzyklus wird beim Kompilieren in einer separaten Datei langsamer, wenn Sie einfach die
<algorithm> -Headerdatei anhängen. Ja, das ist richtig: Verbinden Sie einfach diese Datei, die nie verwendet wird und keinen Code in der endgültigen Objektdatei generiert, und die Geschwindigkeit des "rohen" Zyklus wird 3-4 mal sinken. Im Gegensatz dazu wird die Version mit
std :: transform bis zum Limit beschleunigt, wenn Sie die Implementierung von
std :: transform aus der Datei
<algorithm> kopieren und einfügen, diese Datei jedoch nicht einschließen.
Seltsamkeiten hören hier nicht auf (ich verspreche, es wird keine weiteren geben): Das Einbeziehen der
<algorithm> -Datei führt nicht immer zu dem beschriebenen Effekt. Ein Geschwindigkeitsabfall tritt auf, wenn
<algorithm> früher als
<ctype.h> verbunden ist, wenn Sie sie jedoch
austauschen , dann nein:
Langsamer Code: #include <algorithm> #include <ctype.h>
Kurzcode: #include <ctype.h> #include <algorithm>
Eigentlich ist mir diese Anomalie (in einem anderen Projekt) aufgefallen, als clang-format die enthaltenen Header-Dateien automatisch sortiert und den
<Algorithmus> ganz am Anfang der Liste platziert hat, wo er hingehört (daher der Clickbait-Header des Artikels).
Natürlich mussten wir uns früher oder später in die Liste der Assembler stürzen. Wir werden diesen unangenehmen Moment nicht aufhalten.
Die
schnellen und langsamen Versionen der Funktionen [5] sind unten dargestellt, kleine Schleifen sind mit Anmerkungen versehen:
<algorithm> verbindet sich zuerst: toupper_rawloop(char*, unsigned long): push rbp push rbx lea rbp, [rdi+rsi] sub rsp, 8 test rsi, rsi je .L1 mov rbx, rdi .L5: movsx edi, BYTE PTR [rbx] ; char- *buf add rbx, 1 ; buf++ call toupper ; toupper(c) mov BYTE PTR [rbx-1], al ; buf[-1] cmp rbp, rbx ; buf == buf_end jne .L5 ; .L1: add rsp, 8 pop rbx pop rbp ret
<algorithm> ist an zweiter Stelle verbunden: toupper_rawloop(char*, unsigned long): test rsi, rsi je .L7 push rbp push rbx mov rbp, rsi mov rbx, rdi sub rsp, 8 call __ctype_toupper_loc lea rsi, [rbx+rbp] mov rdi, rbx .L4: ; char- buf movsx rcx, BYTE PTR [rdi] ; toupper ; ( __ctype_toupper_loc) mov rdx, QWORD PTR [rax] ; buf++ add rdi, 1 ; toupper , ; mov edx, DWORD PTR [rdx+rcx*4] mov BYTE PTR [rdi-1], dl ; cmp rsi, rdi ; buf == end_buf jne .L4 ; add rsp, 8 pop rbx pop rbp .L7: rep ret
Der Hauptunterschied besteht darin, dass in der langsamen Version die toupper-Funktion einfach in einer Schleife aufgerufen wird, während in der schnellen Version die Funktionsaufrufe vollständig fehlen und nur in der Entsprechungstabelle [6] gesucht wird, d. H Der Body der Funktion
std :: toupper wird an der Stelle des Aufrufs eingesetzt
Wenn Sie sich den
Quellcode der glibc-Bibliothek ansehen, finden wir dort die Implementierung der
toupper- Funktion:
__extern_inline int
Wie wir sehen können, ist
toupper als
externe Inline- Funktion definiert, die zuerst prüft, ob die Größe des
Zeichenzeichens in ein Byte passt [7] und dann in der von der Funktion
__ctype_toupper_loc () zurückgegebenen Entsprechungstabelle nach dem Zeichen sucht. Diese Funktion gibt einen lokalen Datenstromzeiger (vom Typ
const int ** ) zurück, der wiederum auf eine Entsprechungstabelle verweist, aus der auf eine Anfrage nach unserem Symbol hin die Großbuchstabenversion zurückgegeben wird [8].
Jetzt ist klar, was in der Auflistung passiert. In der schnellen Version des Algorithmus ersetzt der Compiler den Body der Funktion
toupper , kann jedoch den Aufruf der Funktion
__ctype_toupper_loc () nicht ersetzen [9]. Dieser Aufruf wird jedoch als
__attribute __ ((const)) deklariert, was bedeutet, dass der Rückgabewert nur von den Argumenten abhängt (die nicht hier sind). Der Compiler weiß, dass diese Funktion jedes Mal den gleichen Wert zurückgibt und daher ihren Aufruf außerhalb der Schleife ausführt. In der Schleife selbst gibt es nur wenige Leseoperationen, die mit dem Zugriff auf die Entsprechungstabelle, dem Schreiben eines neuen Werts in den Puffer und der Schleifensteuerung verbunden sind.
In der langsamen Version bleibt der Aufruf von
toupper () im Rumpf der Schleife. Die Schleife selbst ist um einen Befehl kürzer, aber jetzt müssen Sie natürlich noch den gesamten Code innerhalb der
toupper- Funktion ausführen. Auf meinem System sieht es so aus:
lea edx,[rdi+0x80] ; edx = rdi + 0x80 movsxd rax,edi ; c cmp edx,0x17f ; , c -128 255 ja 2a ; , mov rdx,QWORD PTR [rip+0x395f30] ; ; mov rdx,QWORD PTR fs:[rdx] ; ; mov rdx,QWORD PTR [rdx] ; ; mov rdx,QWORD PTR [rdx+0x48] ; toupper mov eax,DWORD PTR [rdx+rax*4+0x200] ; c 2a: ret
Da dies ein nicht eingebetteter Aufruf ist, erledigt das Programm mehr Arbeit. Es gibt mindestens fünf aufeinanderfolgende Operationen zum Zugreifen auf den Speicher (das sogenannte Verfolgen von Zeigern,
Zeigerjagen ). In der Schnellversion bleiben nur zwei übrig, da alle anderen aus der Schleife genommen werden. Die Verzögerung zwischen dem Aufruf und dem Verlassen einer Funktion sollte ungefähr 25 Zyklen betragen, und es werden ungefähr 7 Zyklen ausgegeben. Dies bedeutet, dass der Prozessor den Aufruf parallelisieren konnte, was unter den gegebenen Umständen recht gut ist.
Warum ist das so?
In einer langen Kette von Include-Dateien enthalten C ++ - Header-Dateien wie
<algorithm> wiederum die Datei
<bits / os_defines.h> , die die folgende Zeile enthält:
Wenn die Datei
<ctype.h> endgültig verbunden ist, kann aufgrund dieser Anweisung der Code, in dem
toupper als
extern inline definiert ist, nicht eingeschlossen werden:
#if !defined __NO_CTYPE # ifdef __isctype_f __isctype_f (alnum)
Beachten Sie, dass beim Verbinden von
<ctype.h> die C ++ - Version von
toupper niemals als Makro definiert wird - maximal als
externes Inline -, da die Definitionen der Makros durch die
! Defined __cplusplus-Prüfung geschützt sind und daher niemals wirksam werden.
Im Allgemeinen weiß ich nicht genau, ob
__NO_CTYPE in diesem Fall die als
extern inline deklarierten Körper der
tolower- und
toupper- Funktionen ausschließen soll, aber genau das passiert - und damit eine signifikante
Verringerung der Geschwindigkeit unseres Zyklus. Zusammenfassend kann ich sagen, dass, wenn Sie
<cctype> anstelle von
<ctype.h> einfügen (d. H. C ++ ist die Version der C-Header-Datei, die Funktionen in den
std :: -Namensraum schreibt ), der Code in diesem Fall langsam arbeitet weil
<cctype> letztendlich
<bits / os_defines.h> enthält .
Ist das alles so wichtig? Ja Nein.
Die Funktion
toupper eignet sich nicht für ernsthafte Arbeiten mit Zeichen verschiedener Sprachen. Wenn Sie also nur ASCII-Zeichen verarbeiten müssen, können Sie Ihre eigene schnellere Implementierung
erstellen . Wenn Sie ernsthaft mit Text arbeiten müssen, werden Sie höchstwahrscheinlich UTF-8 verwenden und eine Art ICU verwenden müssen, um regionale Einstellungen zu unterstützen, oder warten, bis die Unicode-Unterstützung in C ++ angezeigt wird (das Warten kann lange dauern). . Die Aussage „Clang-Format kann zu einem 4x Leistungseinbruch führen“ eignet sich daher nur als Clickbait-Header.
Wird dieser Effekt in allen libc-Versionen beobachtet? Ja, in fast allen Fällen, aber auch hier ist es nicht so einfach.
Die oben gezeigten Ergebnisse gelten für gcc 5.5 und glibc 2.23, da ich diese Versionen verwendet habe, aber in den neuen Versionen passiert etwas Neues (ab ungefähr glibc 2.27). Dort führt das Einschalten von
<algorithm> vor
<ctype.h> immer noch zu demselben Effekt, aber jetzt verursacht
<stdlib.h> [10] auch Probleme: Wenn Sie es vor
<ctype.h> einschalten , sinkt auch die Leistung, was nicht der Fall ist in früheren Versionen beobachtet. In neueren Versionen enthält die Datei
<stdlib.h> natürlich auch die Definition
__NO_CTYPE . Zumindest wird es jetzt nicht möglich sein, das Clang-Format für das Sortieren verantwortlich zu machen - hier kann es nur helfen, das Problem zu lösen (wenn die Liste der verbundenen Dateien keine anderen Problemdateien enthält).
Ich habe
einen Fehlerbericht in libc gepostet, daher ist es wahrscheinlich, dass dieser Fehler behoben wird. Es besteht jedoch kein Zweifel, dass Fehler in Bezug auf die Reihenfolge, in der Header-Dateien verbunden sind, uns weiter belästigen.
Kommentare
Ich habe kein Kommentarsystem auf meiner Website, arbeite jedoch daran (das heißt, ich jammere regelmäßig, was bei statischen Websites schwierig ist, Kommentare abzugeben).
In der Zwischenzeit können Sie diesen Artikel auf der
Hacker News- Website oder unter
lobste.rs diskutieren .
Danksagung
Wir danken dem ufo-Benutzer von Hacker News, der
darauf hingewiesen hat, dass es nicht erforderlich ist, die Lambda-Funktion zu verwenden, um
std :: toupper für die Verwendung in
std :: transform anzupassen, und auch Jonathan Muller, der
erklärte, dass die Lambda-Funktion weiterhin benötigt wird.
- Ja, die Funktion toupper (3) aus der Header-Datei <ctype.h> ist nicht für die Arbeit mit den meisten Nicht-ASCII-Zeichen geeignet Es können keine Zeichen verarbeitet werden, die größer als ein Byte sind, dies ist jedoch für unsere Aufgabe geeignet, da nur ASCII-Zeichenfolgen übergeben werden.
- In der ASCII-Tabelle befinden sich Klein- und Großbuchstaben sehr bequem in einem Abstand von 32 Positionen voneinander. Dies bedeutet, dass Sie Zeichen von einer Groß- / Kleinschreibung in eine andere übertragen können, indem Sie einfach 32 subtrahieren oder addieren. Wenn wir sicher wären, dass alle Eingaben vorhanden sind Da es sich bei den Daten um ASCII-Buchstaben handelt, könnten wir das 5. Bit ohne Prüfung zurücksetzen (z. B. c & 0b11011111 ), um jeden Großbuchstaben in Kleinbuchstaben umzuwandeln , was sich jedoch nicht in Kleinbuchstaben niederschlägt. Aber wir wissen es wahrscheinlich nicht, deshalb müssen wir prüfen, ob es sich bei dem Zeichen um einen Buchstaben handelt, um nicht versehentlich Buchstaben wie char zu unterbrechen .
- Es sollte ein Streudiagramm mit dem Zusatz von "Rauschen" an der Stelle der Punkte genannt werden. In der Tat ist dies ein gewöhnliches Streudiagramm, in dem der für uns interessante Parameter (die Größe der Eingabedaten) auf der x-Achse und die Arbeitsgeschwindigkeit auf der y-Achse aufgetragen sind (Maße pro Symbol - je niedriger der Wert, desto höher die Geschwindigkeit ). Das Hauptmerkmal dieses Diagramms ist, dass für jeden Parameterwert auf der x-Achse die Abtastung mehrmals durchgeführt wird. In diesem Fall wird der Test für jede Arraygröße zehnmal wiederholt.
- Die Zeichen werden nämlich zufällig und gleichmäßig aus dem Bereich [32, 127] ausgewählt, sodass die Bedingung in der Funktion in etwa 27% der Fälle erfüllt ist.
- Beide Auflistungen beziehen sich auf eine Raw-Cycle-Implementierung und unterscheiden sich nur in der Reihenfolge, in der die Dateien <algorithm> und <ctype.h> enthalten sind . Der generierte Quellcode ist für alle Implementierungen gleich - sowohl in schnellen als auch in langsamen Versionen. Eine Implementierung mit std :: transform erzeugt beispielsweise denselben langsamen Assembler-Code, wenn Sie die Datei <algorithm> einschließen, und denselben schnellen Code, wenn Sie nur die Funktionsdefinition kopieren und die Datei nicht einschließen.
- Diese schnelle Schleife ist jedoch langsamer als möglich, da der Zeiger auf die Entsprechungstabelle innerhalb der Schleife zu oft gelesen wird ( mov rdx, QWORD PTR [rax] ). Dieser Zeiger kann abhängig von den regionalen Einstellungen unterschiedlich sein, wird jedoch während der Ausführung des Zyklus nicht aktualisiert und kann daher außerhalb des Zyklus verschoben werden. Es muss sein, dass der Compiler der Ansicht ist, dass es nicht genug Gründe dafür gibt, da wir in ein Array von Elementen vom Typ char schreiben, und sie können im Prinzip als Aliase für [rax] dh verwendet werden Zeiger auf die Tabelle. Jedenfalls wird auch __restrict__ hier nicht helfen. In einer anderen Version der Schleife, in der lediglich die oberen Werte hinzugefügt und nichts in das Array geschrieben wird, wird diese Optimierung angewendet - der Zeiger wird außerhalb der Schleife gelesen.
- Diese Überprüfung spiegelt sich nicht im austauschbaren Assembler-Code wider, da der Compiler bereits weiß, dass die Zeichenwerte immer im Bereich [-128, 255] liegen . Die Prüfung ist nur erforderlich, weil die API der toupper © -Funktion einen Wert vom Typ int anstelle von char akzeptiert, sodass der Benutzer eine beliebige Anzahl von Typ int an sie übergeben kann , während Entsprechungstabellen nur für Werte vom Typ char konzipiert sind. Die Prüfung hilft daher, das Lesen außerhalb des Puffers zu vermeiden .
- Dies erklärt übrigens, warum die std :: toupper- Prozeduren unabhängig von der Größe der Eingabedaten sind: Sie verwenden keine Verzweigungen (mit Ausnahme von Bereichsprüfungen, die bemerkenswerterweise vorhergesagt werden), sondern eine verzweigungsunabhängige Entsprechungstabelle. ↵
- Das Ersetzen dieses Aufrufs funktioniert auch bei einem sehr starken Wunsch nicht: Der Hauptteil der Funktion ist in der Header-Datei nicht verfügbar.
- Ich kann nichts an stdlib.h (oder <algorithm> ) bemängeln - es ist gut möglich, dass viele andere C-Header-Dateien und alle C ++ - Header-Dateien ebenfalls dieses Verhalten verursachen. Ich habe sie nur nicht getestet. Ich habe stdlib.h angeschlossen, um size_t zu bestimmen.
Hinweis Dieser Artikel wurde erstmals auf der Website von
Performance Matters veröffentlicht. Übersetzte Artikel werden hier mit Genehmigung des Autors veröffentlicht.