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


122

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.


5
Nie jestem pewien, dlaczego głosowano przeciw - to interesujące pytanie. FWIW Widziałem podobne problemy z optymalizacją ze zmiennymi składowymi niebędącymi wskaźnikami, gdzie rozwiązanie było podobne, tj. Buforuj zmienną składową w zmiennej lokalnej przez cały okres istnienia metody. Zgaduję, że ma to coś wspólnego z regułami aliasingu?
Paul R

1
Wygląda na to, że kompilator nie optymalizuje, ponieważ nie może zapewnić, że do członka nie zostanie uzyskany dostęp przez jakiś „zewnętrzny” kod. Jeśli więc element członkowski można zmodyfikować na zewnątrz, należy go przeładowywać przy każdym dostępie. Wydaje się, że jest to rodzaj niestabilności ...
Jean-Baptiste Yunès

Żadne nieużywanie this->to tylko cukier syntaktyczny. Problem jest związany z naturą zmiennych (lokalna a składowa) i rzeczami, które kompilator wywnioskuje z tego faktu.
Jean-Baptiste Yunès

Coś wspólnego z aliasami wskaźników?
Yves Daoust

3
Mówiąc bardziej o znaczeniu semantycznym, „przedwczesna optymalizacja” dotyczy tylko optymalizacji, która jest przedwczesna, tj. Zanim profilowanie stwierdzi, że stanowi problem. W takim przypadku skrupulatnie sprofilowałeś i zdekompilowałeś, znalazłeś źródło problemu oraz sformułowałeś i sprofilowałeś rozwiązanie. Absolutnie nie jest „przedwczesne” zastosowanie tego rozwiązania.
raptortech97

Odpowiedzi:


107

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.


18
Mogę to potwierdzić! Zmiana targetz uint8_tna uint16_t(tak, że zaczęły obowiązywać ścisłe zasady aliasingu) zmieniła to. Dzięki uint16_ttemu obciążenie jest zawsze zoptymalizowane.
gexicide


3
Zmiana treści thisnie jest tym, co masz na myśli (nie jest to zmienna); masz na myśli zmianę zawartości *this.
Marc van Leeuwen,

@gexicide mind wyjaśnia, w jaki sposób ścisły alias działa i rozwiązuje problem?
HCSF

33

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


1
Tak więc, można powiedzieć, zgodnie z ogólną zasadą: Jeśli masz char*lub void*w swojej struktury, należy buforować go w zmiennej lokalnej przed napisaniem do niego?
gexicide

5
W rzeczywistości dzieje się tak, gdy używasz char*, nie jest to konieczne jako członek.
Jarod42

24

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


To jest przykład miejsca, w którym Standard jest gorszy dla optymalizatorów niż byłaby to reguła pozwalająca kompilatorowi założyć, że między dwoma dostępami do obiektu typu T lub takim dostępem a początkiem lub końcem pętli / funkcji gdzie to nastąpi, wszystkie próby dostępu do pamięci będą korzystały z tego samego obiektu, chyba że interweniująca operacja używa tego obiektu (lub wskaźnika / odniesienia do niego) w celu uzyskania wskaźnika lub odniesienia do innego obiektu . Taka reguła wyeliminowałaby potrzebę „wyjątku typu znakowego”, który może zabić wydajność kodu działającego z sekwencjami bajtów.
supercat
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.