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;
c++
c++11
operator-precedence
S2108887
źródło
źródło
__sync_synchronize()
być pomocny?foo
potrzebnego do uruchomienia, który kompilator może zignorować podczas zmiany kolejności, tak jak może ignorować obserwację z innego wątku.Odpowiedzi:
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
foo
pełni widoczną dla realizacji. Wyodrębniłem również (nieprzenośną) wersję programuDoNotOptimize
z biblioteki Google Benchmark, którą można znaleźć tutaj: https://github.com/google/benchmark/blob/master/include/benchmark/benchmark_api.h#L208Tutaj zapewniamy, że dane wejściowe i dane wyjściowe są oznaczone jako niemożliwe do optymalizacji wokół obliczeń
foo
i 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:Tutaj możesz zobaczyć kompilator optymalizujący wywołanie do
foo(input)
pojedynczej instrukcjiaddl %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
DoNotOptimize
tutaj.źródło
Clock::now()
to zmianie kolejności wywołań względem foo ()? Czy optymalizatora trzeba założyć, żeDoNotOptimize
iClock::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?DoNotOptimize
w 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.foo
funkcja wykonuje pewne operacje, takie jak odczyt z gniazda, które może być na chwilę zablokowane, czy liczy się to obserwowalna operacja? A skororead
nie jest to operacja „całkowicie znana” (prawda?), Czy kod będzie w porządku?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:
GCC 5.3.0:
g++ -S --std=c++11 -O0 fred.cpp
:Ale:
g++ -S --std=c++11 -O2 fred.cpp
:Teraz z foo () jako funkcją zewnętrzną:
g++ -S --std=c++11 -O2 fred.cpp
:ALE, jeśli jest to połączone z -flto (optymalizacja czasu łącza):
źródło
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
( 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 lubvolatile
odczytu.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”?)
źródło
asm
wpływa na czas wykonywania instrukcji pomiędzy wywołaniami timera: kod po przejściu pamięci musi przeładować wszystkie zmienne z pamięci.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ślifoo()
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ę doClock::now()
kodu, to nie ma obserwowalnych konsekwencji przenoszenieClock::now()
połączeń.Jeśli
foo()
interakcje z pliku lub wyświetlacza, a kompilator nie może udowodnić, żeClock::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:
i zawija to w ten sposób:
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:
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.źródło
volatile
dostępu lub wywołania zewnętrznego kodu.Nie, nie może. Zgodnie ze standardem C ++ [intro.execution]:
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ą.
źródło
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.
źródło
int x = 0; clock(); x = y*2; clock();
nie ma zdefiniowanych sposobówclock()
interakcji kodu ze stanemx
. Zgodnie ze standardem C ++ nie musi wiedzieć, coclock()
robi - może zbadać stos (i zauważyć, kiedy nastąpią obliczenia), ale to nie jest problem C ++ .t2
a drugiego dot1
, 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, cofoo()
robi (na przykład, ponieważ ma to wbudowane) i dlatego (mówiąc luźno) jest to czysta funkcja, może ją przesuwać.y*y
przed 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órymx
zostanie użyta, dlatego nie będzie nic robić między wywołaniamiclock()
. To samo dotyczy wszystkiego, cofoo
robi funkcja wbudowana , pod warunkiem, że nie ma skutków ubocznych i nie może zależeć od stanu, który może zostać zmienionyclock()
.noinline
funkcja + wbudowana czarna skrzynka zestawu + pełne zależności danychOpiera 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”::now
zależność the i od danych.main.cpp
GitHub upstream .
Skompiluj i uruchom:
Jedyną drobną wadą tej metody jest to, że dodajemy jedną dodatkową
callq
instrukcję doinline
metody.objdump -CD
programymain
zawierające:więc widzimy, że
foo
było to wstawione, aleget_clock
nie 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: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, żecall
jest 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 danychByłoby to najskuteczniejsze możliwe rozwiązanie, przezwyciężające nawet dodatkowe
jmpq
wspomniane 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.
źródło
"+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.