Wymuszanie kolejności instrukcji w C ++

Załóżmy, że mam kilka instrukcji, które chcę wykonać w ustalonej kolejności. Chcę używać g ++ z poziomem optymalizacji 2, aby można było zmienić kolejność niektórych instrukcji. Jakie narzędzia są potrzebne, aby wymusić określony porządek oświadczeń?

Rozważmy następujący przykład.

using Clock = std::chrono::high_resolution_clock;

auto t1 = Clock::now(); // Statement 1
foo();                  // Statement 2
auto t2 = Clock::now(); // Statement 3

auto elapsedTime = t2 - t1;

W tym przykładzie ważne jest, aby instrukcje 1-3 były wykonywane w podanej kolejności. Jednak czy kompilator nie uważa, że ​​instrukcja 2 jest niezależna od 1 i 3 i nie może wykonać kodu w następujący sposób?

using Clock=std::chrono::high_resolution_clock;

foo();                  // Statement 2
auto t1 = Clock::now(); // Statement 1
auto t2 = Clock::now(); // Statement 3

auto elapsedTime = t2 - t1;

Chciałbym spróbować udzielić nieco bardziej kompleksowej odpowiedzi po omówieniu tego z komitetem normalizacyjnym C ++. Poza tym, że jestem członkiem komitetu C ++, jestem także programistą kompilatorów LLVM i Clang.

Zasadniczo nie ma sposobu, aby użyć bariery lub jakiejś operacji w sekwencji, aby osiągnąć te przekształcenia. Podstawowym problemem jest to, że semantyka operacyjna czegoś takiego jak dodawanie liczb całkowitych jest całkowicie znana implementacji. Potrafi je symulować, wie, że nie można ich obserwować za pomocą odpowiednich programów i zawsze może je dowolnie przenosić.

Moglibyśmy próbować temu zapobiec, ale miałoby to wyjątkowo negatywne skutki i ostatecznie by się nie powiodło.

Po pierwsze, jedynym sposobem, aby temu zapobiec w kompilatorze, jest poinformowanie go, że wszystkie te podstawowe operacje są obserwowalne. Problem polega na tym, że wykluczałoby to przytłaczającą większość optymalizacji kompilatora. Wewnątrz kompilatora zasadniczo nie mamy dobrych mechanizmów do modelowania, że synchronizacja jest obserwowalna, ale nic więcej. Nie mamy nawet dobrego modelu tego, jakie operacje wymagają czasu . Na przykład, czy konwersja 32-bitowej liczby całkowitej bez znaku na 64-bitową liczbę całkowitą bez znaku zajmuje trochę czasu? Na x86-64 zajmuje to zero czasu, ale na innych architekturach zajmuje to niezerowy czas. Nie ma tutaj ogólnie poprawnej odpowiedzi.

Ale nawet jeśli odniesiemy sukces dzięki pewnym heroicznym próbom powstrzymania kompilatora przed zmianą kolejności tych operacji, nie ma gwarancji, że to wystarczy. Rozważ prawidłowy i zgodny sposób wykonania programu w C ++ na maszynie x86: DynamoRIO. Jest to system, który dynamicznie ocenia kod maszynowy programu. Jedyną rzeczą, jaką może zrobić, jest optymalizacja online, a nawet jest w stanie spekulacyjnie wykonać cały zakres podstawowych instrukcji arytmetycznych poza czasem. I to zachowanie nie jest unikalne dla dynamicznych oceniających, rzeczywisty procesor x86 również spekuluje (znacznie mniejsza liczba) instrukcji i zmienia ich kolejność dynamicznie.

Najważniejsze jest uświadomienie sobie, że fakt, że arytmetyka nie jest obserwowalna (nawet na poziomie czasowym) jest czymś, co przenika warstwy komputera. Dotyczy to kompilatora, środowiska uruchomieniowego, a często nawet sprzętu. Wymuszenie na nim widoczności spowodowałoby zarówno drastyczne ograniczenie kompilatora, jak i drastyczne ograniczenie sprzętu.

Ale to wszystko nie powinno powodować utraty nadziei. Jeśli chcesz zaplanować wykonanie podstawowych operacji matematycznych, dobrze poznaliśmy techniki, które działają niezawodnie. Zwykle są one używane podczas wykonywania mikro-benchmarkingu . Mówiłem o tym na CppCon2015: https://youtu.be/nXaxk27zwlk

Pokazane tam techniki są również dostarczane przez różne biblioteki mikro-benchmarków, takie jak Google: https://github.com/google/benchmark#preventing-optimization

Kluczem do tych technik jest skupienie się na danych. Wprowadzasz dane wejściowe do obliczeń jako nieprzezroczyste dla optymalizatora, a wynik obliczeń nieprzezroczysty dla optymalizatora. Gdy to zrobisz, możesz niezawodnie mierzyć czas. Spójrzmy na realistyczną wersję przykładu w oryginalnym pytaniu, ale z definicją w foopełni widoczną dla realizacji. Wyodrębniłem również (nieprzenośną) wersję programu DoNotOptimizez biblioteki Google Benchmark, którą można znaleźć tutaj: https://github.com/google/benchmark/blob/master/include/benchmark/benchmark_api.h#L208

#include <chrono>

template <class T>
__attribute__((always_inline)) inline void DoNotOptimize(const T &value) {
  asm volatile("" : "+m"(const_cast<T &>(value)));
}

// The compiler has full knowledge of the implementation.
static int foo(int x) { return x * 2; }

auto time_foo() {
  using Clock = std::chrono::high_resolution_clock;

  auto input = 42;

  auto t1 = Clock::now();         // Statement 1
  DoNotOptimize(input);
  auto output = foo(input);       // Statement 2
  DoNotOptimize(output);
  auto t2 = Clock::now();         // Statement 3

  return t2 - t1;
}

Tutaj zapewniamy, że dane wejściowe i dane wyjściowe są oznaczone jako niemożliwe do optymalizacji wokół obliczeń fooi tylko wokół tych znaczników są obliczane czasy. Ponieważ używasz danych do ścisłego wykonywania obliczeń, gwarantuje się, że pozostanie między dwoma taktami, a jednak same obliczenia mogą być zoptymalizowane. Wynikowy zestaw x86-64 wygenerowany przez najnowszą kompilację Clang / LLVM to:

% ./bin/clang++ -std=c++14 -c -S -o - so.cpp -O3
        .text
        .file   "so.cpp"
        .globl  _Z8time_foov
        .p2align        4, 0x90
        .type   _Z8time_foov,@function
_Z8time_foov:                           # @_Z8time_foov
        .cfi_startproc
# BB#0:                                 # %entry
        pushq   %rbx
.Ltmp0:
        .cfi_def_cfa_offset 16
        subq    $16, %rsp
.Ltmp1:
        .cfi_def_cfa_offset 32
.Ltmp2:
        .cfi_offset %rbx, -16
        movl    $42, 8(%rsp)
        callq   _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, %rbx
        #APP
        #NO_APP
        movl    8(%rsp), %eax
        addl    %eax, %eax              # This is "foo"!
        movl    %eax, 12(%rsp)
        #APP
        #NO_APP
        callq   _ZNSt6chrono3_V212system_clock3nowEv
        subq    %rbx, %rax
        addq    $16, %rsp
        popq    %rbx
        retq
.Lfunc_end0:
        .size   _Z8time_foov, .Lfunc_end0-_Z8time_foov
        .cfi_endproc


        .ident  "clang version 3.9.0 (trunk 273389) (llvm/trunk 273380)"
        .section        ".note.GNU-stack","",@progbits

Tutaj możesz zobaczyć kompilator optymalizujący wywołanie do foo(input)pojedynczej instrukcji addl %eax, %eax, ale bez przenoszenia go poza taktowanie lub całkowite wyeliminowanie go pomimo ciągłego wprowadzania.

Mam nadzieję, że to pomoże, a komitet normalizacyjny C ++ rozważa możliwość ujednolicenia interfejsów API podobnych do DoNotOptimizetutaj.

Podsumowanie:

Wydaje się, że nie ma gwarantowanego sposobu na uniknięcie zmiany kolejności, ale dopóki nie jest włączona optymalizacja czasu łącza / pełnego programu, umieszczenie wywoływanej funkcji w oddzielnej jednostce kompilacji wydaje się całkiem dobrym pomysłem . (Przynajmniej w przypadku GCC, chociaż logika sugeruje, że jest to prawdopodobne w przypadku innych kompilatorów). Odbywa się to kosztem wywołania funkcji - wbudowany kod z definicji znajduje się w tej samej jednostce kompilacji i jest otwarty na zmianę kolejności.

Oryginalna odpowiedź:

GCC zmienia kolejność wywołań przy optymalizacji -O2:

#include <chrono>
static int foo(int x)    // 'static' or not here doesn't affect ordering.
{
    return x*2;
}
int fred(int x)
{
    auto t1 = std::chrono::high_resolution_clock::now();
    int y = foo(x);
    auto t2 = std::chrono::high_resolution_clock::now();
    return y;
}

GCC 5.3.0:

g++ -S --std=c++11 -O0 fred.cpp :

_ZL3fooi:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    %ecx, 16(%rbp)
        movl    16(%rbp), %eax
        addl    %eax, %eax
        popq    %rbp
        ret
_Z4fredi:
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $64, %rsp
        movl    %ecx, 16(%rbp)
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, -16(%rbp)
        movl    16(%rbp), %ecx
        call    _ZL3fooi
        movl    %eax, -4(%rbp)
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, -32(%rbp)
        movl    -4(%rbp), %eax
        addq    $64, %rsp
        popq    %rbp
        ret

Ale:

g++ -S --std=c++11 -O2 fred.cpp :

_Z4fredi:
        pushq   %rbx
        subq    $32, %rsp
        movl    %ecx, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        call    _ZNSt6chrono3_V212system_clock3nowEv
        leal    (%rbx,%rbx), %eax
        addq    $32, %rsp
        popq    %rbx
        ret

Teraz z foo () jako funkcją zewnętrzną:

#include <chrono>
int foo(int x);
int fred(int x)
{
    auto t1 = std::chrono::high_resolution_clock::now();
    int y = foo(x);
    auto t2 = std::chrono::high_resolution_clock::now();
    return y;
}

g++ -S --std=c++11 -O2 fred.cpp :

_Z4fredi:
        pushq   %rbx
        subq    $32, %rsp
        movl    %ecx, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movl    %ebx, %ecx
        call    _Z3fooi
        movl    %eax, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movl    %ebx, %eax
        addq    $32, %rsp
        popq    %rbx
        ret

ALE, jeśli jest to połączone z -flto (optymalizacja czasu łącza):

0000000100401710 <main>:
   100401710:   53                      push   %rbx
   100401711:   48 83 ec 20             sub    $0x20,%rsp
   100401715:   89 cb                   mov    %ecx,%ebx
   100401717:   e8 e4 ff ff ff          callq  100401700 <__main>
   10040171c:   e8 bf f9 ff ff          callq  1004010e0 <_ZNSt6chrono3_V212system_clock3nowEv>
   100401721:   e8 ba f9 ff ff          callq  1004010e0 <_ZNSt6chrono3_V212system_clock3nowEv>
   100401726:   8d 04 1b                lea    (%rbx,%rbx,1),%eax
   100401729:   48 83 c4 20             add    $0x20,%rsp
   10040172d:   5b                      pop    %rbx
   10040172e:   c3                      retq

Zmiana kolejności może być wykonana przez kompilator lub przez procesor.

Większość kompilatorów oferuje metodę specyficzną dla platformy, aby zapobiec zmianie kolejności instrukcji odczytu i zapisu. To jest na gcc

asm volatile("" ::: "memory");

( Więcej informacji tutaj )

Zauważ, że to tylko pośrednio zapobiega operacjom zmiany kolejności, o ile zależą one od odczytów / zapisów.

W praktyce nie widziałem jeszcze systemu, w którym wywołanie systemowe Clock::now()ma taki sam efekt jak taka bariera. Możesz sprawdzić wynikowy zespół, aby mieć pewność.

Jednak nierzadko zdarza się, że testowana funkcja jest oceniana w czasie kompilacji. Aby wymusić „realistyczne” wykonanie, może być konieczne wyprowadzenie danych wejściowych foo()z wejścia / wyjścia lub volatileodczytu.

Inną opcją byłoby wyłączenie wbudowania dla foo()- znowu jest to specyficzne dla kompilatora i zwykle nie przenośne, ale miałoby ten sam efekt.

Na gcc to byłoby __attribute__ ((noinline))

@Ruslan porusza fundamentalną kwestię: na ile realistyczny jest ten pomiar?

Na czas wykonania wpływa wiele czynników: jeden to rzeczywisty sprzęt, na którym pracujemy, a drugi to współbieżny dostęp do współdzielonych zasobów, takich jak pamięć podręczna, pamięć, dyski i rdzenie procesora.

Więc to, co zwykle robimy, aby uzyskać porównywalne czasy: upewnij się, że są odtwarzalne z niskim marginesem błędu. To sprawia, że ​​są nieco sztuczne.

Wydajność wykonania „gorącej pamięci podręcznej” i „zimnej pamięci podręcznej” może z łatwością różnić się o rząd wielkości - ale w rzeczywistości będzie to coś pośredniego („letniego”?)

Język C ++ definiuje to, co można zaobserwować na wiele sposobów.

Jeśli foo()nie robi nic obserwowalnego, można to całkowicie wyeliminować. Jeśli foo()tylko wykonuje obliczenia, które przechowują wartości w stanie „lokalnym” (czy to na stosie, czy w jakimś obiekcie), a kompilator może udowodnić, że żaden bezpiecznie wyprowadzony wskaźnik nie może dostać się do Clock::now()kodu, to nie ma obserwowalnych konsekwencji przenoszenie Clock::now()połączeń.

Jeśli foo()interakcje z pliku lub wyświetlacza, a kompilator nie może udowodnić, że Clock::now()robi nie oddziałują z pliku lub na wyświetlaczu, a następnie zmiana kolejności nie można tego zrobić, ponieważ interakcja z pliku lub wyświetlacz jest obserwowalne zachowanie.

Chociaż możesz użyć hacków specyficznych dla kompilatora, aby zmusić kod, aby się nie poruszał (jak asemblacja wbudowana), innym podejściem jest próba przechytrzenia kompilatora.

Utwórz dynamicznie ładowaną bibliotekę. Załaduj go przed odpowiednim kodem.

Ta biblioteka ujawnia jedną rzecz:

namespace details {
  void execute( void(*)(void*), void *);
}

i zawija to w ten sposób:

template<class F>
void execute( F f ) {
  struct bundle_t {
    F f;
  } bundle = {std::forward<F>(f)};

  auto tmp_f = [](void* ptr)->void {
    auto* pb = static_cast<bundle_t*>(ptr);
    (pb->f)();
  };
  details::execute( tmp_f, &bundle );
}

który pakuje zerową lambdę i używa biblioteki dynamicznej do uruchomienia jej w kontekście, którego kompilator nie może zrozumieć.

Wewnątrz biblioteki dynamicznej wykonujemy:

void details::execute( void(*f)(void*), void *p) {
  f(p);
}

co jest całkiem proste.

Teraz, aby zmienić kolejność wywołań execute, musi rozumieć bibliotekę dynamiczną, której nie może podczas kompilowania kodu testowego.

Wciąż może wyeliminować foo()je bez skutków ubocznych, ale niektóre wygrywasz, niektóre tracisz.

Nie, nie może. Zgodnie ze standardem C ++ [intro.execution]:

14 Każde obliczenie wartości i efekt uboczny związany z pełnym wyrażeniem jest sekwencjonowany przed każdym obliczeniem wartości i efektem ubocznym związanym z następnym ocenianym pełnym wyrażeniem.

Pełne wyrażenie to w zasadzie instrukcja zakończona średnikiem. Jak widać powyższa reguła stanowi, że wyciągi należy wykonywać w kolejności. To w obrębie instrukcji kompilator ma więcej swobody (tj. W pewnych okolicznościach może oceniać wyrażenia, które składają się na instrukcję w kolejności innej niż od lewej do prawej lub cokolwiek innego).

Zwróć uwagę, że warunki zastosowania reguły as-if nie są tutaj spełnione. Nieracjonalne jest myślenie, że jakikolwiek kompilator byłby w stanie udowodnić, że zmiana kolejności wywołań w celu uzyskania czasu systemowego nie wpłynie na obserwowalne zachowanie programu. Gdyby zaistniała okoliczność, w której dwa wywołania w celu uzyskania czasu mogłyby zostać przestawione bez zmiany obserwowanego zachowania, byłoby niezwykle nieefektywne stworzenie kompilatora, który analizuje program z wystarczającym zrozumieniem, aby móc to wywnioskować z pewnością.

Nie.

Czasami, zgodnie z regułą „as-if”, kolejność instrukcji może zostać zmieniona. Dzieje się tak nie dlatego, że są one logicznie niezależne od siebie, ale dlatego, że ta niezależność pozwala na taką zmianę kolejności bez zmiany semantyki programu.

Przeniesienie wywołania systemowego, które uzyskuje bieżący czas, oczywiście nie spełnia tego warunku. Kompilator, który robi to świadomie lub nieświadomie, jest niezgodny i naprawdę głupi.

Ogólnie rzecz biorąc, nie spodziewałbym się, że żadne wyrażenie, które powoduje, że wywołanie systemowe zostanie „odgadnięte w drugiej kolejności”, nawet przez agresywnie optymalizujący kompilator. Po prostu nie wie wystarczająco dużo o tym, co robi to wywołanie systemowe.

noinline funkcja + wbudowana czarna skrzynka zestawu + pełne zależności danych

Opiera się to na https://stackoverflow.com/a/38025837/895245, ale ponieważ nie widziałem żadnego jasnego uzasadnienia, dlaczego ::now()nie można tam zmienić kolejności, wolałbym być paranoikiem i umieścić go w funkcji noinline razem z jako M.

W ten sposób jestem prawie pewien, że zmiana kolejności nie może się zdarzyć, ponieważ noinline„wiąże” ::nowzależność the i od danych.

main.cpp

#include <chrono>
#include <iostream>
#include <string>

// noinline ensures that the ::now() cannot be split from the __asm__
template <class T>
__attribute__((noinline)) auto get_clock(T& value) {
    // Make the compiler think we actually use / modify the value.
    // It can't "see" what is going on inside the assembly string.
    __asm__ __volatile__ ("" : "+g" (value));
    return std::chrono::high_resolution_clock::now();
}

template <class T>
static T foo(T niters) {
    T result = 42;
    for (T i = 0; i < niters; ++i) {
        result = (result * result) - (3 * result) + 1;
    }
    return result;
}

int main(int argc, char **argv) {
    unsigned long long input;
    if (argc > 1) {
        input = std::stoull(argv[1], NULL, 0);
    } else {
        input = 1;
    }

    // Must come before because it could modify input
    // which is passed as a reference.
    auto t1 = get_clock(input);
    auto output = foo(input);
    // Must come after as it could use the output.
    auto t2 = get_clock(output);
    std::cout << "output " << output << std::endl;
    std::cout << "time (ns) "
              << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count()
              << std::endl;
}

GitHub upstream .

Skompiluj i uruchom:

g++ -ggdb3 -O3 -std=c++14 -Wall -Wextra -pedantic -o main.out main.cpp
./main.out 1000
./main.out 10000
./main.out 100000

Jedyną drobną wadą tej metody jest to, że dodajemy jedną dodatkową callqinstrukcję do inlinemetody. objdump -CDprogramy mainzawierające:

    11b5:       e8 26 03 00 00          callq  14e0 <auto get_clock<unsigned long long>(unsigned long long&)>
    11ba:       48 8b 34 24             mov    (%rsp),%rsi
    11be:       48 89 c5                mov    %rax,%rbp
    11c1:       b8 2a 00 00 00          mov    $0x2a,%eax
    11c6:       48 85 f6                test   %rsi,%rsi
    11c9:       74 1a                   je     11e5 <main+0x65>
    11cb:       31 d2                   xor    %edx,%edx
    11cd:       0f 1f 00                nopl   (%rax)
    11d0:       48 8d 48 fd             lea    -0x3(%rax),%rcx
    11d4:       48 83 c2 01             add    $0x1,%rdx
    11d8:       48 0f af c1             imul   %rcx,%rax
    11dc:       48 83 c0 01             add    $0x1,%rax
    11e0:       48 39 d6                cmp    %rdx,%rsi
    11e3:       75 eb                   jne    11d0 <main+0x50>
    11e5:       48 89 df                mov    %rbx,%rdi
    11e8:       48 89 44 24 08          mov    %rax,0x8(%rsp)
    11ed:       e8 ee 02 00 00          callq  14e0 <auto get_clock<unsigned long long>(unsigned long long&)>

więc widzimy, że foobyło to wstawione, ale get_clocknie było i otaczało go.

get_clock sam w sobie jest jednak niezwykle wydajny, składający się z zoptymalizowanej instrukcji wywołania pojedynczego skrzydła, która nawet nie dotyka stosu:

00000000000014e0 <auto get_clock<unsigned long long>(unsigned long long&)>:
    14e0:       e9 5b fb ff ff          jmpq   1040 <std::chrono::_V2::system_clock::now()@plt>

Ponieważ precyzja zegara sama w sobie jest ograniczona, myślę, że jest mało prawdopodobne, abyś był w stanie zauważyć efekty czasowe jednego dodatkowego jmpq. Pamiętaj, że calljest to wymagane, niezależnie od tego, czy ::now()znajduje się w bibliotece współdzielonej.

Wywołaj ::now()z zestawu wbudowanego z zależnością od danych

Byłoby to najskuteczniejsze możliwe rozwiązanie, przezwyciężające nawet dodatkowe jmpqwspomniane powyżej.

Jest to niestety niezwykle trudne do wykonania poprawnie, jak pokazano na: Wywołanie printf w rozszerzonym wbudowanym ASM

Jeśli jednak pomiar czasu można wykonać bezpośrednio w asemblerze bez wywołania, wówczas można zastosować tę technikę. Dotyczy to na przykład instrukcji oprzyrządowania gem5 magic , RDTSC x86 (nie jestem pewien, czy jest to już reprezentatywne) i prawdopodobnie innych liczników wydajności.

Powiązane wątki:

• Czy optymalizator C ++ może zmieniać kolejność wywołań clock ()?

Testowane z GCC 8.3.0, Ubuntu 19.04.