Wymuszanie kolejności instrukcji w C ++

111

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;
S2108887
źródło
34
Jeśli kompilator uważa, że ​​są niezależne, a nie są, kompilator jest uszkodzony i powinieneś użyć lepszego kompilatora.
David Schwartz
1
może __sync_synchronize()być pomocny?
vsz
3
@HowardHinnant: Siła semantyczna standardu C byłaby ogromnie ulepszona, gdyby taka dyrektywa została zdefiniowana i gdyby reguły aliasingu zostały dostosowane tak, aby wykluczyć odczyty wykonywane po barierze danych, które zostały zapisane przed nią.
supercat
4
@DavidSchwartz W tym przypadku chodzi o pomiar czasu foopotrzebnego do uruchomienia, który kompilator może zignorować podczas zmiany kolejności, tak jak może ignorować obserwację z innego wątku.
CodesInChaos

Odpowiedzi:

100

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.

Chandler Carruth
źródło
1
Dziękuję za Twoją odpowiedź. Oznaczyłem to jako nową najlepszą odpowiedź. Mogłem to zrobić wcześniej, ale od wielu miesięcy nie czytałem tej strony. Jestem bardzo zainteresowany wykorzystaniem kompilatora Clang do tworzenia programów w języku C ++. Między innymi podoba mi się to, że można używać znaków Unicode w nazwach zmiennych w Clang. Myślę, że zadam więcej pytań na temat Clang na Stackoverflow.
S2108887
5
Chociaż rozumiem, w jaki sposób zapobiega to całkowitej optymalizacji foo, czy możesz trochę wyjaśnić, dlaczego zapobiega Clock::now()to zmianie kolejności wywołań względem foo ()? Czy optymalizatora trzeba założyć, że DoNotOptimizei Clock::now()mieć dostęp i może modyfikować pewne wspólne stan globalny, co z kolei byłoby związać je do wejścia i wyjścia? A może polegasz na aktualnych ograniczeniach implementacji optymalizatora?
MikeMB
2
DoNotOptimizew tym przykładzie jest zdarzeniem „obserwowalnym” syntetycznie. To tak, jakby hipotetycznie wyświetlał widoczne wyjście na jakimś terminalu z reprezentacją wejścia. Ponieważ odczyt zegara jest również obserwowalny (obserwujesz upływający czas), nie można ich zmienić ponownie bez zmiany obserwowalnego zachowania programu.
Chandler Carruth
1
Nadal nie jestem do końca jasne, jeśli chodzi o pojęcie „obserwowalne”, jeśli foofunkcja wykonuje pewne operacje, takie jak odczyt z gniazda, które może być na chwilę zablokowane, czy liczy się to obserwowalna operacja? A skoro readnie jest to operacja „całkowicie znana” (prawda?), Czy kod będzie w porządku?
ravenisadesk
„Podstawowym problemem jest to, że semantyka operacyjna czegoś takiego jak dodawanie liczb całkowitych jest całkowicie znana implementacji”. Ale wydaje mi się, że problem nie dotyczy semantyki dodawania liczb całkowitych, ale semantyki wywoływania funkcji foo (). O ile foo () nie znajduje się w tej samej jednostce kompilacji, skąd wie, że foo () i clock () nie współdziałają?
Dave
59

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
Jeremy
źródło
3
Podobnie jak MSVC i ICC. Clang jest jedynym, który wydaje się zachowywać oryginalną sekwencję.
Cody Grey
3
nigdzie nie używasz t1 i t2, więc może pomyśleć, że wynik można odrzucić i zmienić kolejność kodu
phuclv
3
@Niall - nie mogę zaoferować nic bardziej konkretnego, ale myślę, że mój komentarz nawiązuje do podstawowego powodu: kompilator wie, że foo () nie może wpływać na now () ani na odwrót, podobnie jak zmiana kolejności. Potwierdzają to różne eksperymenty obejmujące funkcje i dane z zakresu zewnętrznego. Obejmuje to posiadanie statycznej funkcji foo () zależnej od zmiennej o zasięgu plikowym N - jeśli N jest zadeklarowane jako statyczne, następuje zmiana kolejności, podczas gdy jeśli jest zadeklarowane jako niestatyczne (tj. Jest widoczne dla innych jednostek kompilacji, a zatem potencjalnie podlega efektom ubocznym funkcje extern, takie jak now ()), zmiana kolejności nie występuje.
Jeremy
3
@ Lưu Vĩnh Phúc: Tyle że same wezwania nie są pomijane. Po raz kolejny, podejrzewam, to dlatego, że kompilator nie wie, jakie mogą być ich skutki uboczne - ale nie wiedzą, że te skutki uboczne nie mogą wpływać na zachowanie foo ().
Jeremy
3
I ostatnia uwaga: określenie -flto (optymalizacja czasu łącza) powoduje zmianę kolejności nawet w przypadkach, w których nie ma innej kolejności.
Jeremy
20

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”?)

peterchen
źródło
2
Twój hack asmwpływa na czas wykonywania instrukcji pomiędzy wywołaniami timera: kod po przejściu pamięci musi przeładować wszystkie zmienne z pamięci.
Ruslan
@Ruslan: Ich hack, nie mój. Istnieją różne poziomy oczyszczania, a zrobienie czegoś takiego jest nieuniknione, aby uzyskać powtarzalne wyniki.
peterchen
2
Zwróć uwagę, że hack z „asm” pomaga tylko jako bariera dla operacji, które dotykają pamięci, a OP jest zainteresowany czymś więcej. Zobacz moją odpowiedź, aby uzyskać więcej informacji.
Chandler Carruth
11

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.

Yakk - Adam Nevraumont
źródło
19
„innym podejściem jest próba przechytrzenia kompilatora”. Jeśli ta fraza nie jest oznaką zagłębienia się w króliczą norę, to nie wiem, co nią jest. :-)
Cody Grey
1
Myślę, że warto zauważyć, że czas potrzebny do wykonania bloku kodu nie jest uważany za „obserwowalne” zachowanie, które kompilatory muszą utrzymywać . Gdyby czas na wykonanie bloku kodu był „obserwowalny”, wówczas żadne formy optymalizacji wydajności nie byłyby dozwolone. Chociaż byłoby pomocne dla C i C ++ zdefiniowanie „bariery przyczynowości”, która wymagałaby od kompilatora wstrzymania się z wykonaniem dowolnego kodu za barierą, dopóki wszystkie efekty uboczne sprzed bariery nie zostaną obsłużone przez wygenerowany kod [kod, który chce mieć pewność, że dane w pełni ...
supercat
1
... propagowane przez sprzętowe pamięci podręczne wymagałyby do tego zastosowania środków specyficznych dla sprzętu, ale specyficzne dla sprzętu środki czekania, aż wszystkie wysłane zapisy zostaną zakończone, byłyby bezużyteczne bez dyrektywy barierowej, aby zapewnić, że wszystkie oczekujące zapisy są śledzone przez kompilator muszą zostać przesłane do sprzętu, zanim sprzęt zostanie poproszony o upewnienie się, że wszystkie wysłane zapisy są kompletne.] Nie znam żadnego sposobu, aby to zrobić w żadnym języku bez użycia fikcyjnego volatiledostępu lub wywołania zewnętrznego kodu.
supercat
4

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

Smeeheey
źródło
12
Nadal obowiązuje zasada as-if
MM
18
Przez co-jeśli reguła kompilator może zrobić nic, aby kod dopóki nie zmieni się zaobserwować zachowanie. Czas wykonania nie jest obserwowalny. Więc może zmienić kolejność arbutralnych wierszy kodu, o ile wynik byłby taki sam (większość kompilatorów robi rozsądną rzecz i nie zmienia kolejności wywołań czasu, ale nie jest to wymagane)
Revolver_Ocelot
6
Czas wykonania nie jest obserwowalny. To dość dziwne. Z praktycznego, nietechnicznego punktu widzenia, czas wykonania (inaczej „wykonanie”) jest bardzo obserwowalny.
Frédéric Hamidi
3
Zależy od tego, jak mierzysz czas. Nie jest możliwe zmierzenie liczby cykli zegara potrzebnych do wykonania części kodu w standardowym C ++.
Peter
3
@dba Mieszasz kilka rzeczy razem. Konsolidator nie może już generować aplikacji Win16, to prawda, ale to dlatego, że usunęli obsługę generowania tego typu plików binarnych. Aplikacje WIn16 nie używają formatu PE. Nie oznacza to, że kompilator lub konsolidator mają specjalną wiedzę na temat funkcji API. Drugi problem jest związany z biblioteką wykonawczą. Nie ma absolutnie żadnego problemu z uzyskaniem najnowszej wersji MSVC do wygenerowania pliku binarnego działającego na NT 4. Zrobiłem to. Problem pojawia się, gdy tylko spróbujesz połączyć się w CRT, co wywołuje funkcje niedostępne.
Cody Grey
2

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.

Wyścigi lekkości na orbicie
źródło
5
Zgadzam się, że byłoby to głupie, ale nie nazwałbym tego niezgodnym . Kompilator może mieć wiedzę, co dokładnie robi wywołanie systemowe w systemie konkretnym i czy ma to skutki uboczne. Spodziewałbym się, że kompilatory nie zmieniają kolejności takiego wywołania tylko po to, aby objąć typowy przypadek użycia, umożliwiając lepsze wrażenia użytkownika, a nie dlatego, że standard tego zabrania.
Revolver_Ocelot
4
@Revolver_Ocelot: Optymalizacje, które zmieniają semantykę programu (dobrze, zachowaj do kopiowania) są niezgodne ze standardem, niezależnie od tego, czy się z tym zgadzasz.
Wyścigi lekkości na orbicie
6
W trywialnym przypadku int x = 0; clock(); x = y*2; clock();nie ma zdefiniowanych sposobów clock()interakcji kodu ze stanem x. Zgodnie ze standardem C ++ nie musi wiedzieć, co clock()robi - może zbadać stos (i zauważyć, kiedy nastąpią obliczenia), ale to nie jest problem C ++ .
Yakk - Adam Nevraumont
5
Kontynuując punkt widzenia Yakka: prawdą jest, że zmiana kolejności wywołań systemowych, tak aby wynik pierwszego był przypisany do, t2a drugiego do t1, byłaby niezgodna i głupia, gdyby te wartości zostały użyte, to, czego ta odpowiedź pomija, to to, że zgodny kompilator może czasami zmienić kolejność innego kodu w wywołaniu systemowym. W tym przypadku, pod warunkiem, że wie, co foo()robi (na przykład, ponieważ ma to wbudowane) i dlatego (mówiąc luźno) jest to czysta funkcja, może ją przesuwać.
Steve Jessop
1
.. znowu luźno, ponieważ nie ma gwarancji, że rzeczywista implementacja (aczkolwiek nie abstrakcyjna maszyna) nie obliczy spekulacyjnie y*yprzed wywołaniem systemowym, tylko dla zabawy. Nie ma również gwarancji, że rzeczywista implementacja nie użyje wyniku tego spekulatywnego obliczenia później w jakimkolwiek momencie, w którym xzostanie użyta, dlatego nie będzie nic robić między wywołaniami clock(). To samo dotyczy wszystkiego, co foorobi funkcja wbudowana , pod warunkiem, że nie ma skutków ubocznych i nie może zależeć od stanu, który może zostać zmieniony clock().
Steve Jessop
0

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:

Testowane z GCC 8.3.0, Ubuntu 19.04.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
źródło
1
Zwykle nie musisz wymuszać rozlewania / przeładowywania za "+m"pomocą, użycie "+r"jest znacznie bardziej wydajnym sposobem na zmaterializowanie wartości przez kompilator i założenie, że zmienna uległa zmianie.
Peter Cordes