Użycie tego wskaźnika powoduje dziwną deoptimization w gorącej pętli

Niedawno natknąłem się na dziwną dezoptymalizację (a raczej straciłem okazję do optymalizacji).

Rozważ tę funkcję w celu wydajnego rozpakowywania tablic 3-bitowych liczb całkowitych na 8-bitowe liczby całkowite. Rozpakowuje 16 int w każdej iteracji pętli:

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;
   }
}

Oto wygenerowany zestaw części kodu:

 ...
 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
 ...

Wygląda dość skutecznie. Po prostu a, shift rightpo którym następuje an and, a następnie a storedo targetbufora. Ale teraz spójrz, co się stanie, gdy zmienię funkcję na metodę w strukturze:

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;
        }
}

Myślałem, że wygenerowany zestaw powinien być taki sam, ale tak nie jest. Oto jego część:

...
 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!
 ...

Jak widać, wprowadziliśmy dodatkową redundancję loadz pamięci przed każdym przesunięciem ( mov rdx,QWORD PTR [rdi]). Wygląda na to, że targetwskaźnik (który jest teraz składnikiem, a nie zmienną lokalną) musi być zawsze ładowany ponownie przed zapisaniem w nim. To znacznie spowalnia kod (około 15% w moich pomiarach).

Najpierw pomyślałem, że może model pamięci C ++ wymusza, aby wskaźnik składowy nie był przechowywany w rejestrze, ale musiał zostać ponownie załadowany, ale wydawało się to niezręcznym wyborem, ponieważ uniemożliwiłoby wiele wykonalnych optymalizacji. Byłem więc bardzo zaskoczony, że kompilator nie przechował targettutaj rejestru.

Próbowałem buforować wskaźnik elementu członkowskiego w zmiennej lokalnej:

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;
    }
}

Ten kod również daje "dobry" asembler bez dodatkowych magazynów. Domyślam się więc: kompilatorowi nie wolno podnosić obciążenia wskaźnika składowego struktury, więc taki „gorący wskaźnik” powinien zawsze być przechowywany w zmiennej lokalnej.

• Dlaczego więc kompilator nie może zoptymalizować tych obciążeń?
• Czy to model pamięci C ++ zabrania tego? Czy jest to po prostu wada mojego kompilatora?
• Czy moje przypuszczenia są prawidłowe lub jaki jest dokładny powód, dla którego nie można przeprowadzić optymalizacji?

Używany kompilator był g++ 4.8.2-19ubuntu1z -O3optymalizacją. Próbowałem też clang++ 3.4-1ubuntu3z podobnymi wynikami: Clang jest nawet w stanie wektoryzować metodę za pomocą lokalnego targetwskaźnika. Jednak użycie this->targetwskaźnika daje ten sam wynik: dodatkowe obciążenie wskaźnika przed każdym sklepem.

Sprawdziłem w assemblerze kilka podobnych metod i wynik jest taki sam: wydaje się, że członek thiszawsze musi być przeładowywany przed sklepem, nawet jeśli taki ładunek można po prostu podnieść poza pętlę. Będę musiał przepisać dużo kodu, aby pozbyć się tych dodatkowych sklepów, głównie przez buforowanie wskaźnika w lokalnej zmiennej, która jest zadeklarowana nad gorącym kodem. Ale zawsze myślałem, że majstrowanie przy takich szczegółach, jak buforowanie wskaźnika w zmiennej lokalnej z pewnością kwalifikowałoby się do przedwczesnej optymalizacji w dzisiejszych czasach, gdy kompilatory stały się tak sprytne. Ale wygląda na to, że się mylę . Buforowanie wskaźnika elementu członkowskiego w gorącej pętli wydaje się być niezbędną ręczną techniką optymalizacji.

Wydaje się, że problemem jest aliasowanie wskaźnika, ironicznie między thisa this->target. Kompilator bierze pod uwagę raczej nieprzyzwoitą możliwość, którą zainicjowałeś:

this->target = &this

W takim przypadku pisanie do this->target[0]zmieniłoby zawartość this(a tym samym this->target).

Problem aliasingu pamięci nie ogranicza się do powyższego. W zasadzie każde użycie this->target[XX]danej (nie) odpowiedniej wartości XXmoże wskazywać this.

Jestem lepiej zorientowany w C, gdzie można temu zaradzić, deklarując zmienne wskaźnikowe za pomocą __restrict__słowa kluczowego.

Ścisłe reguły aliasingu pozwalają char*na aliasowanie dowolnego innego wskaźnika. Więc this->targetmoże alias z thispierwszą częścią kodu, a w metodzie kodu,

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

Jest w rzeczywistości

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

jak thismoże ulec zmianie podczas modyfikowania this->targettreści.

Po this->targetzbuforowaniu w zmiennej lokalnej alias nie jest już możliwy ze zmienną lokalną.

Problemem jest tutaj ścisły alias, który mówi, że możemy aliasować za pomocą znaku * , co zapobiega optymalizacji kompilatora w twoim przypadku. Nie wolno nam tworzyć aliasów przez wskaźnik innego typu, co byłoby niezdefiniowanym zachowaniem, zwykle na SO widzimy ten problem, który polega na tym, że użytkownicy próbują aliasować za pomocą niekompatybilnych typów wskaźników .

Wydaje się rozsądne, aby zaimplementować uint8_t jako znak bez znaku i jeśli spojrzymy na cstdint w Coliru , zawiera on stdint.h, który typedefs uint8_t w następujący sposób:

typedef unsigned char       uint8_t;

jeśli użyłeś innego typu non-char, kompilator powinien być w stanie zoptymalizować.

Jest to omówione w roboczej wersji standardowej C ++ sekcji 3.10 Lvalues ​​and rvalues, która mówi:

Jeśli program próbuje uzyskać dostęp do przechowywanej wartości obiektu za pomocą wartości glut innej niż jeden z poniższych typów, zachowanie jest niezdefiniowane

i zawiera następujący punkt:

• typ char lub unsigned char.

Uwaga, opublikowałem komentarz dotyczący możliwych obejść w pytaniu, które zawiera pytanie When is uint8_t ≠ unsigned char? a rekomendacja brzmiała:

Jednak trywialnym obejściem jest użycie słowa kluczowego restrykcja lub skopiowanie wskaźnika do zmiennej lokalnej, której adres nigdy nie jest pobierany, aby kompilator nie musiał martwić się o to, czy obiekty uint8_t mogą go aliasować.

Ponieważ C ++ nie obsługuje słowa kluczowego ogranicz , musisz polegać na rozszerzeniu kompilatora, na przykład gcc używa __restrict__, więc nie jest to całkowicie przenośne, ale inna sugestia powinna być.