Ich bin kürzlich auf eine seltsame Deoptimierung gestoßen (oder habe eher eine Optimierungsmöglichkeit verpasst).
Betrachten Sie diese Funktion zum effizienten Entpacken von Arrays aus 3-Bit-Ganzzahlen in 8-Bit-Ganzzahlen. In jeder Schleifeniteration werden 16 Zoll entpackt:
void unpack3bit(uint8_t* target, char* source, int size) {
while(size > 0){
uint64_t t = *reinterpret_cast<uint64_t*>(source);
target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;
target[3] = (t >> 9) & 0x7;
target[4] = (t >> 12) & 0x7;
target[5] = (t >> 15) & 0x7;
target[6] = (t >> 18) & 0x7;
target[7] = (t >> 21) & 0x7;
target[8] = (t >> 24) & 0x7;
target[9] = (t >> 27) & 0x7;
target[10] = (t >> 30) & 0x7;
target[11] = (t >> 33) & 0x7;
target[12] = (t >> 36) & 0x7;
target[13] = (t >> 39) & 0x7;
target[14] = (t >> 42) & 0x7;
target[15] = (t >> 45) & 0x7;
source+=6;
size-=6;
target+=16;
}
}
Hier ist die generierte Assembly für Teile des Codes:
...
367: 48 89 c1 mov rcx,rax
36a: 48 c1 e9 09 shr rcx,0x9
36e: 83 e1 07 and ecx,0x7
371: 48 89 4f 18 mov QWORD PTR [rdi+0x18],rcx
375: 48 89 c1 mov rcx,rax
378: 48 c1 e9 0c shr rcx,0xc
37c: 83 e1 07 and ecx,0x7
37f: 48 89 4f 20 mov QWORD PTR [rdi+0x20],rcx
383: 48 89 c1 mov rcx,rax
386: 48 c1 e9 0f shr rcx,0xf
38a: 83 e1 07 and ecx,0x7
38d: 48 89 4f 28 mov QWORD PTR [rdi+0x28],rcx
391: 48 89 c1 mov rcx,rax
394: 48 c1 e9 12 shr rcx,0x12
398: 83 e1 07 and ecx,0x7
39b: 48 89 4f 30 mov QWORD PTR [rdi+0x30],rcx
...
Es sieht ziemlich effizient aus. Einfach ein shift right
gefolgt von einem and
und dann ein store
zum target
Puffer. Aber jetzt schauen Sie, was passiert, wenn ich die Funktion in eine Methode in einer Struktur ändere:
struct T{
uint8_t* target;
char* source;
void unpack3bit( int size);
};
void T::unpack3bit(int size) {
while(size > 0){
uint64_t t = *reinterpret_cast<uint64_t*>(source);
target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;
target[3] = (t >> 9) & 0x7;
target[4] = (t >> 12) & 0x7;
target[5] = (t >> 15) & 0x7;
target[6] = (t >> 18) & 0x7;
target[7] = (t >> 21) & 0x7;
target[8] = (t >> 24) & 0x7;
target[9] = (t >> 27) & 0x7;
target[10] = (t >> 30) & 0x7;
target[11] = (t >> 33) & 0x7;
target[12] = (t >> 36) & 0x7;
target[13] = (t >> 39) & 0x7;
target[14] = (t >> 42) & 0x7;
target[15] = (t >> 45) & 0x7;
source+=6;
size-=6;
target+=16;
}
}
Ich dachte, die generierte Assembly sollte ziemlich gleich sein, ist es aber nicht. Hier ist ein Teil davon:
...
2b3: 48 c1 e9 15 shr rcx,0x15
2b7: 83 e1 07 and ecx,0x7
2ba: 88 4a 07 mov BYTE PTR [rdx+0x7],cl
2bd: 48 89 c1 mov rcx,rax
2c0: 48 8b 17 mov rdx,QWORD PTR [rdi] // Load, BAD!
2c3: 48 c1 e9 18 shr rcx,0x18
2c7: 83 e1 07 and ecx,0x7
2ca: 88 4a 08 mov BYTE PTR [rdx+0x8],cl
2cd: 48 89 c1 mov rcx,rax
2d0: 48 8b 17 mov rdx,QWORD PTR [rdi] // Load, BAD!
2d3: 48 c1 e9 1b shr rcx,0x1b
2d7: 83 e1 07 and ecx,0x7
2da: 88 4a 09 mov BYTE PTR [rdx+0x9],cl
2dd: 48 89 c1 mov rcx,rax
2e0: 48 8b 17 mov rdx,QWORD PTR [rdi] // Load, BAD!
2e3: 48 c1 e9 1e shr rcx,0x1e
2e7: 83 e1 07 and ecx,0x7
2ea: 88 4a 0a mov BYTE PTR [rdx+0xa],cl
2ed: 48 89 c1 mov rcx,rax
2f0: 48 8b 17 mov rdx,QWORD PTR [rdi] // Load, BAD!
...
Wie Sie sehen, haben wir load
vor jeder Schicht eine zusätzliche Redundanz aus dem Speicher eingeführt ( mov rdx,QWORD PTR [rdi]
). Es scheint, dass der target
Zeiger (der jetzt ein Mitglied anstelle einer lokalen Variablen ist) immer neu geladen werden muss, bevor er darin gespeichert wird. Dies verlangsamt den Code erheblich (ca. 15% bei meinen Messungen).
Zuerst dachte ich, dass das C ++ - Speichermodell möglicherweise erzwingt, dass ein Elementzeiger möglicherweise nicht in einem Register gespeichert wird, sondern neu geladen werden muss, aber dies schien eine umständliche Wahl zu sein, da dies viele praktikable Optimierungen unmöglich machen würde. Ich war also sehr überrascht, dass der Compiler hier nicht target
in einem Register gespeichert hat.
Ich habe versucht, den Elementzeiger selbst in einer lokalen Variablen zwischenzuspeichern:
void T::unpack3bit(int size) {
while(size > 0){
uint64_t t = *reinterpret_cast<uint64_t*>(source);
uint8_t* target = this->target; // << ptr cached in local variable
target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;
target[3] = (t >> 9) & 0x7;
target[4] = (t >> 12) & 0x7;
target[5] = (t >> 15) & 0x7;
target[6] = (t >> 18) & 0x7;
target[7] = (t >> 21) & 0x7;
target[8] = (t >> 24) & 0x7;
target[9] = (t >> 27) & 0x7;
target[10] = (t >> 30) & 0x7;
target[11] = (t >> 33) & 0x7;
target[12] = (t >> 36) & 0x7;
target[13] = (t >> 39) & 0x7;
target[14] = (t >> 42) & 0x7;
target[15] = (t >> 45) & 0x7;
source+=6;
size-=6;
this->target+=16;
}
}
Dieser Code liefert auch den "guten" Assembler ohne zusätzliche Speicher. Meine Vermutung lautet also: Der Compiler darf die Last eines Elementzeigers einer Struktur nicht erhöhen, daher sollte ein solcher "Hot Pointer" immer in einer lokalen Variablen gespeichert werden.
- Warum kann der Compiler diese Lasten nicht optimieren?
- Ist es das C ++ - Speichermodell, das dies verbietet? Oder ist es einfach ein Mangel meines Compilers?
- Ist meine Vermutung richtig oder was ist der genaue Grund, warum die Optimierung nicht durchgeführt werden kann?
Der verwendete Compiler war g++ 4.8.2-19ubuntu1
mit -O3
Optimierung. Ich habe es auch clang++ 3.4-1ubuntu3
mit ähnlichen Ergebnissen versucht : Clang kann die Methode sogar mit dem lokalen target
Zeiger vektorisieren . Die Verwendung des this->target
Zeigers führt jedoch zu demselben Ergebnis: Eine zusätzliche Belastung des Zeigers vor jedem Speicher.
Ich habe den Assembler auf einige ähnliche Methoden überprüft und das Ergebnis ist das gleiche: Es scheint, dass ein Mitglied von this
immer vor einem Geschäft neu geladen werden muss, selbst wenn eine solche Last einfach außerhalb der Schleife gehoben werden könnte. Ich muss viel Code neu schreiben, um diese zusätzlichen Speicher zu entfernen, hauptsächlich indem ich den Zeiger selbst in eine lokale Variable zwischenspeichere, die über dem Hotcode deklariert ist. Aber ich dachte immer, dass das Fummeln mit Details wie dem Zwischenspeichern eines Zeigers in einer lokalen Variablen in diesen Tagen, in denen Compiler so clever geworden sind, sicherlich für eine vorzeitige Optimierung geeignet wäre. Aber anscheinend irre ich mich hier . Das Zwischenspeichern eines Elementzeigers in einer Hot-Loop scheint eine notwendige manuelle Optimierungstechnik zu sein.
this->
ist nur syntaktischer Zucker. Das Problem hängt mit der Art der Variablen (lokal gegen Mitglied) und den Dingen zusammen, die der Compiler aus dieser Tatsache ableitet.Antworten:
Zeiger-Aliasing scheint das Problem zu sein, ironischerweise zwischen
this
undthis->target
. Der Compiler berücksichtigt die ziemlich obszöne Möglichkeit, die Sie initialisiert haben:this->target = &this
In diesem Fall
this->target[0]
würde das Schreiben an den Inhalt vonthis
(und damitthis->target
) ändern .Das Speicher-Aliasing-Problem ist nicht auf das oben Gesagte beschränkt. Grundsätzlich kann jede Verwendung eines
this->target[XX]
gegebenen (in) angemessenen Werts vonXX
darauf hinweisenthis
.Ich bin besser mit C vertraut, wo dies behoben werden kann, indem Zeigervariablen mit dem
__restrict__
Schlüsselwort deklariert werden.quelle
target
vonuint8_t
vonuint16_t
(damit strenge Aliasing-Regeln gelten) hat es geändert. Mituint16_t
wird die Last immer optimiert.this
ist nicht das, was Sie meinen (es ist keine Variable); du meinst den Inhalt von zu ändern*this
.Mit strengen Aliasing-Regeln kann
char*
jeder andere Zeiger aliasisiert werden. Sothis->target
kann Alias mitthis
und in Ihrer Codemethode der erste Teil des Codes,ist in der Tat
Dies
this
kann geändert werden, wenn Siethis->target
Inhalte ändern .Sobald
this->target
es in einer lokalen Variablen zwischengespeichert ist, ist der Alias mit der lokalen Variablen nicht mehr möglich.quelle
char*
odervoid*
in Ihrer Struktur haben, müssen Sie es in einer lokalen Variablen zwischenspeichern, bevor Sie darauf schreiben?char*
, nicht als Mitglied erforderlich.Das Problem hierbei ist striktes Aliasing, das besagt, dass wir über ein char * einen Alias erstellen dürfen , wodurch die Compileroptimierung in Ihrem Fall verhindert wird. Es ist uns nicht gestattet, einen Alias über einen Zeiger eines anderen Typs durchzuführen, was ein undefiniertes Verhalten wäre. Normalerweise sehen wir bei SO dieses Problem, bei dem Benutzer versuchen, einen Alias über inkompatible Zeigertypen durchzuführen .
Es erscheint vernünftig, uint8_t als vorzeichenloses Zeichen zu implementieren. Wenn wir uns cstdint auf Coliru ansehen , enthält es stdint.h, das uint8_t wie folgt typisiert :
Wenn Sie einen anderen Typ ohne Zeichen verwendet haben, sollte der Compiler in der Lage sein, zu optimieren.
Dies wird im Entwurf des C ++ - Standardabschnitts
3.10
LWerte und rWerte behandelt, in dem Folgendes steht:und enthält die folgende Kugel:
Hinweis: Ich habe einen Kommentar zu möglichen Problemumgehungen in einer Frage veröffentlicht, in der gefragt wird, wann uint8_t ≠ Zeichen ohne Vorzeichen ist. und die Empfehlung war:
Da C ++ das Schlüsselwort Restrict nicht unterstützt , müssen Sie sich auf die Compiler-Erweiterung verlassen. Beispielsweise verwendet gcc __restrict__, sodass dies nicht vollständig portierbar ist, der andere Vorschlag sollte jedoch lauten.
quelle