Die Verwendung dieses Zeigers führt zu einer merkwürdigen Deoptimierung im Hot-Loop

122

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 rightgefolgt von einem andund dann ein storezum targetPuffer. 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 loadvor jeder Schicht eine zusätzliche Redundanz aus dem Speicher eingeführt ( mov rdx,QWORD PTR [rdi]). Es scheint, dass der targetZeiger (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 targetin 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-19ubuntu1mit -O3Optimierung. Ich habe es auch clang++ 3.4-1ubuntu3mit ähnlichen Ergebnissen versucht : Clang kann die Methode sogar mit dem lokalen targetZeiger vektorisieren . Die Verwendung des this->targetZeigers 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 thisimmer 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.

Gexizid
quelle
5
Ich bin mir nicht sicher, warum dies abgelehnt wurde - es ist eine interessante Frage. FWIW Ich habe ähnliche Optimierungsprobleme bei Nicht-Zeiger-Mitgliedsvariablen gesehen, bei denen die Lösung ähnlich war, dh die Mitgliedsvariable wurde für die Lebensdauer der Methode in einer lokalen Variablen zwischengespeichert. Ich vermute, es hat etwas mit Aliasing-Regeln zu tun?
Paul R
1
Der Compiler scheint nicht zu optimieren, da er nicht sicherstellen kann, dass auf das Mitglied nicht über einen "externen" Code zugegriffen wird. Wenn das Mitglied also außerhalb geändert werden kann, sollte es bei jedem Zugriff neu geladen werden. Scheint als eine Art flüchtiger ...
Jean-Baptiste Yunès
Nein, nicht zu verwenden 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.
Jean-Baptiste Yunès
Was hat das mit Zeiger-Aliasen zu tun?
Yves Daoust
3
Semantischer ausgedrückt gilt "vorzeitige Optimierung" nur für vorzeitige Optimierung, dh bevor die Profilerstellung ein Problem festgestellt hat. In diesem Fall haben Sie sorgfältig ein Profil erstellt und dekompiliert und die Ursache eines Problems gefunden sowie eine Lösung formuliert und profiliert. Es ist absolut nicht "verfrüht", diese Lösung anzuwenden.
raptortech97

Antworten:

106

Zeiger-Aliasing scheint das Problem zu sein, ironischerweise zwischen thisund this->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 von this(und damit this->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 von XXdarauf hinweisen this.

Ich bin besser mit C vertraut, wo dies behoben werden kann, indem Zeigervariablen mit dem __restrict__Schlüsselwort deklariert werden.

Peter Boncz
quelle
18
Ich kann das bestätigen! Das Ändern targetvon uint8_tvon uint16_t(damit strenge Aliasing-Regeln gelten) hat es geändert. Mit uint16_twird die Last immer optimiert.
Gexizid
3
Das Ändern des Inhalts von thisist nicht das, was Sie meinen (es ist keine Variable); du meinst den Inhalt von zu ändern *this.
Marc van Leeuwen
@gexicide Gedanken darüber, wie streng der Alias ​​eintritt und das Problem behebt?
HCSF
33

Mit strengen Aliasing-Regeln kann char*jeder andere Zeiger aliasisiert werden. So this->targetkann Alias ​​mit thisund in Ihrer Codemethode der erste Teil des Codes,

target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;

ist in der Tat

this->target[0] = t & 0x7;
this->target[1] = (t >> 3) & 0x7;
this->target[2] = (t >> 6) & 0x7;

Dies thiskann geändert werden, wenn Sie this->targetInhalte ändern .

Sobald this->targetes in einer lokalen Variablen zwischengespeichert ist, ist der Alias ​​mit der lokalen Variablen nicht mehr möglich.

Jarod42
quelle
1
Können wir also generell sagen: Wenn Sie ein char*oder void*in Ihrer Struktur haben, müssen Sie es in einer lokalen Variablen zwischenspeichern, bevor Sie darauf schreiben?
Gexizid
5
In der Tat ist es, wenn Sie ein verwenden char*, nicht als Mitglied erforderlich.
Jarod42
24

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 :

typedef unsigned char       uint8_t;

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:

Wenn ein Programm versucht, über einen anderen Wert als einen der folgenden Typen auf den gespeicherten Wert eines Objekts zuzugreifen, ist das Verhalten undefiniert

und enthält die folgende Kugel:

  • ein char oder ein nicht signierter char-Typ.

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:

Die triviale Problemumgehung besteht jedoch darin, das Schlüsselwort Restrict zu verwenden oder den Zeiger auf eine lokale Variable zu kopieren, deren Adresse niemals verwendet wird, damit sich der Compiler keine Gedanken darüber machen muss, ob die Objekte uint8_t einen Alias ​​dafür erstellen können.

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.

Shafik Yaghmour
quelle
Dies ist ein Beispiel für einen Ort, an dem der Standard für Optimierer schlechter ist als eine Regel, die es einem Compiler ermöglichen würde, anzunehmen, dass zwischen zwei Zugriffen auf ein Objekt vom Typ T oder einem solchen Zugriff und dem Beginn oder Ende einer Schleife / Funktion Dabei tritt bei allen Zugriffen auf den Speicher dasselbe Objekt auf, es sei denn, eine dazwischenliegende Operation verwendet dieses Objekt (oder einen Zeiger / Verweis darauf), um einen Zeiger oder Verweis auf ein anderes Objekt abzuleiten . Eine solche Regel würde die Notwendigkeit einer "Ausnahme vom Zeichentyp" beseitigen, die die Leistung von Code beeinträchtigen kann, der mit Folgen von Bytes arbeitet.
Supercat