Optymalizacja z dala od „while (1);” w C ++ 0x

Zaktualizowano, patrz poniżej!

Słyszałem i przeczytałem, że C ++ 0x umożliwia kompilatorowi wydrukowanie „Hello” dla następującego fragmentu kodu

#include <iostream>

int main() {
  while(1) 
    ;
  std::cout << "Hello" << std::endl;
}

Najwyraźniej ma to coś wspólnego z wątkami i możliwościami optymalizacji. Wydaje mi się jednak, że może to zaskoczyć wielu ludzi.

Czy ktoś ma dobre wyjaśnienie, dlaczego było to konieczne, aby zezwolić? Dla porównania, najnowsza wersja robocza C ++ 0x mówi o6.5/5

Pętla, która poza instrukcją for-init w przypadku instrukcji for,

• nie wywołuje funkcji biblioteki we / wy, a
• nie uzyskuje dostępu do obiektów ulotnych ani nie modyfikuje ich, oraz
• nie wykonuje operacji synchronizacji (1.10) ani operacji atomowych (klauzula 29)

może zostać uznane przez implementację za zakończone. [Uwaga: ma to na celu umożliwienie transformacji kompilatora, takich jak usuwanie pustych pętli, nawet jeśli nie można udowodnić zakończenia. - notatka końcowa]

Edytować:

Ten wnikliwy artykuł mówi o tym tekście Standardów

Niestety, słowa „niezdefiniowane zachowanie” nie są używane. Jednak za każdym razem, gdy standard mówi, że „kompilator może założyć P”, zakłada się, że program, który ma właściwość not-P, ma niezdefiniowaną semantykę.

Czy to prawda i czy kompilator może wydrukować „Do widzenia” dla powyższego programu?

Jest tu jeszcze bardziej wnikliwy wątek , który dotyczy analogicznej zmiany do C, zapoczątkowanej przez Guy'a wykonującego powyższy linkowany artykuł. Wśród innych przydatnych faktów przedstawiają rozwiązanie, które wydaje się mieć również zastosowanie do C ++ 0x ( Aktualizacja : To już nie zadziała z n3225 - patrz poniżej!)

endless:
  goto endless;

Wydaje się, że kompilator nie może tego zoptymalizować, ponieważ nie jest to pętla, ale skok. Inny facet podsumowuje proponowaną zmianę w C ++ 0x i C201X

Pisząc pętlę, programista stwierdza , że albo pętla robi coś z widocznym zachowaniem (wykonuje operacje we / wy, uzyskuje dostęp do obiektów ulotnych, przeprowadza synchronizację lub operacje atomowe), albo że ostatecznie się kończy. Jeśli naruszę to założenie, pisząc nieskończoną pętlę bez skutków ubocznych, okłamuję kompilator, a zachowanie mojego programu jest nieokreślone. (Jeśli mam szczęście, kompilator może mnie o tym ostrzec.) Język nie zapewnia (już nie zapewnia?) Sposobu na wyrażenie nieskończonej pętli bez widocznego zachowania.

Aktualizacja z 3.1.2011 z n3225: Komisja przeniosła tekst do 1.10 / 24 i powiedz

Implementacja może zakładać, że dowolny wątek w końcu wykona jedną z następujących czynności:

• zakończyć,
• wywołanie funkcji wejścia / wyjścia biblioteki,
• uzyskać dostęp do zmiennego obiektu lub zmodyfikować go, lub
• wykonać operację synchronizacji lub operację atomową.

Ta gotosztuczka już nie zadziała!

Czy ktoś ma dobre wyjaśnienie, dlaczego było to konieczne, aby zezwolić?

Tak, Hans Boehm uzasadnia to w N1528: Dlaczego niezdefiniowane zachowanie dla nieskończonych pętli? chociaż jest to dokument WG14, uzasadnienie dotyczy również C ++ i dokument odnosi się zarówno do WG14, jak i WG21:

Jak słusznie wskazuje N1509, obecny szkic zasadniczo nadaje nieokreślone zachowanie nieskończonym pętlom w 6.8.5p6. Głównym problemem związanym z tym jest to, że pozwala on kodowi poruszać się przez potencjalnie nie kończącą się pętlę. Na przykład załóżmy, że mamy następujące pętle, w których count i count2 są zmiennymi globalnymi (lub mają swój adres), a p jest zmienną lokalną, której adres nie został zajęty:

for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

Czy te dwie pętle można scalić i zastąpić następującą pętlą?

for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}

Bez specjalnej zwolnienia w 6.8.5p6 dla nieskończonych pętli byłoby to niedozwolone: ​​Jeśli pierwsza pętla nie kończy się, ponieważ q wskazuje na okrągłą listę, oryginał nigdy nie zapisuje do count2. W ten sposób może być uruchamiany równolegle z innym wątkiem, który uzyskuje dostęp lub aktualizuje count2. Nie jest to już bezpieczne w przekształconej wersji, która ma dostęp do count2 pomimo nieskończonej pętli. Zatem transformacja potencjalnie wprowadza wyścig danych.

W takich przypadkach jest bardzo mało prawdopodobne, aby kompilator był w stanie udowodnić zakończenie pętli; musiałby zrozumieć, że q wskazuje na listę acykliczną, która, jak sądzę, jest poza możliwościami większości kompilatorów głównego nurtu, a często niemożliwa bez pełnej informacji o programie.

Ograniczenia nałożone przez pętle nie kończące się są ograniczeniem dla optymalizacji pętli kończących, dla których kompilator nie może udowodnić zakończenia, a także dla optymalizacji pętli faktycznie nie kończących się. Te pierwsze są znacznie częstsze niż te drugie i często są bardziej interesujące w optymalizacji.

Oczywiście istnieją również pętle for ze zmienną pętli typu integer, w których kompilatorowi byłoby trudno udowodnić zakończenie, a zatem kompilator miałby trudności z restrukturyzacją pętli bez 6.8.5p6. Nawet coś takiego

for (i = 1; i != 15; i += 2)

lub

for (i = 1; i <= 10; i += j)

wydaje się nietrywialne w obsłudze. (W pierwszym przypadku do udowodnienia terminacji wymagana jest pewna podstawowa teoria liczb, w drugim przypadku musimy wiedzieć coś o możliwych wartościach j, aby to zrobić. Zawijanie liczb całkowitych bez znaku może jeszcze bardziej skomplikować to rozumowanie. )

Wydaje się, że ten problem dotyczy prawie wszystkich transformacji restrukturyzacji pętli, w tym transformacji zrównoleglania kompilatora i transformacji optymalizacji pamięci podręcznej, z których oba prawdopodobnie zyskają na znaczeniu i są już często ważne dla kodu numerycznego. Wydaje się, że może to oznaczać znaczny koszt na korzyść możliwości pisania nieskończonych pętli w najbardziej naturalny możliwy sposób, zwłaszcza że większość z nas rzadko pisze celowo nieskończone pętle.

Jedną z głównych różnic w C jest to, że C11 zapewnia wyjątek dla kontrolowania wyrażeń, które są wyrażeniami stałymi, które różnią się od C ++ i sprawiają, że twój konkretny przykład jest dobrze zdefiniowany w C11.

Dla mnie odpowiednim uzasadnieniem jest:

Ma to na celu umożliwienie transformacji kompilatora, takich jak usuwanie pustych pętli, nawet jeśli nie można udowodnić zakończenia.

Prawdopodobnie dzieje się tak dlatego, że mechaniczne udowodnienie zakończenia jest trudne , a niemożność udowodnienia zakończenia utrudnia kompilatorom, które w innym przypadku mogłyby dokonać użytecznych transformacji, takich jak przenoszenie niezależnych operacji z przed pętlą do po lub odwrotnie, wykonywanie operacji po pętli w jednym wątku, podczas gdy pętla jest wykonywana w innej i tak dalej. Bez tych przekształceń pętla mogłaby zablokować wszystkie inne wątki podczas oczekiwania na zakończenie wspomnianej pętli przez jeden wątek. (Używam luźno terminu „wątek” na oznaczenie dowolnej formy przetwarzania równoległego, w tym oddzielnych strumieni instrukcji VLIW).

EDYCJA: głupi przykład:

while (complicated_condition()) {
    x = complicated_but_externally_invisible_operation(x);
}
complex_io_operation();
cout << "Results:" << endl;
cout << x << endl;

W tym przypadku jeden wątek mógłby szybciej wykonać complex_io_operationdrugą, podczas gdy drugi wykonuje wszystkie złożone obliczenia w pętli. Ale bez cytowanej klauzuli kompilator musi udowodnić dwie rzeczy, zanim będzie mógł dokonać optymalizacji: 1) która complex_io_operation()nie zależy od wyników pętli oraz 2) że pętla się zakończy . Dowodzenie 1) jest dość łatwe, udowodnienie 2) jest problemem zatrzymania. Z klauzulą ​​może założyć, że pętla się kończy i uzyskać wygraną z równoległością.

Wyobrażam sobie również, że projektanci uważali, że przypadki, w których nieskończone pętle występują w kodzie produkcyjnym, są bardzo rzadkie i zwykle są to takie rzeczy jak pętle sterowane zdarzeniami, które w jakiś sposób uzyskują dostęp do I / O. W rezultacie pesymizowali rzadki przypadek (nieskończone pętle) na rzecz optymalizacji bardziej powszechnego przypadku (nieskończony, ale trudny do mechanicznego udowodnienia niedokończony, pętle).

Oznacza to jednak, że w rezultacie ucierpi nieskończone pętle używane w przykładach uczenia się, co spowoduje problemy w kodzie początkującego. Nie mogę powiedzieć, że to całkiem dobra rzecz.

EDYCJA: w odniesieniu do wnikliwego artykułu, który teraz łączysz, powiedziałbym, że „kompilator może założyć, że X na temat programu” jest logicznym odpowiednikiem „jeśli program nie spełnia wymagań X, zachowanie jest niezdefiniowane”. Możemy to pokazać w następujący sposób: załóżmy, że istnieje program, który nie spełnia właściwości X. Gdzie zdefiniowano by zachowanie tego programu? Standard definiuje tylko zachowanie przy założeniu, że właściwość X jest prawdziwa. Chociaż standard nie deklaruje wyraźnie zachowania jako niezdefiniowane, zadeklarował, że jest ono niezdefiniowane przez pominięcie.

Rozważmy podobny argument: „kompilator może założyć, że zmienna x jest przypisana najwyżej raz między punktami sekwencji” jest równoważne z „przypisaniem do x więcej niż raz między punktami sekwencji jest niezdefiniowane”.

Myślę, że właściwą interpretacją jest ta z twojej edycji: puste nieskończone pętle to niezdefiniowane zachowanie.

Nie powiedziałbym, że jest to szczególnie intuicyjne zachowanie, ale ta interpretacja ma więcej sensu niż alternatywna, że ​​kompilator może arbitralnie ignorować nieskończone pętle bez wywoływania UB.

Jeśli nieskończone pętle to UB, oznacza to po prostu, że programy nie kończące się nie są uważane za sensowne: zgodnie z C ++ 0x, nie mają semantyki.

To też ma sens. Są to szczególny przypadek, w którym wiele efektów ubocznych po prostu już nie występuje (na przykład nic nie jest zwracane main), a wiele optymalizacji kompilatora jest utrudnionych przez konieczność zachowania nieskończonych pętli. Na przykład przenoszenie obliczeń w pętli jest całkowicie poprawne, jeśli pętla nie ma skutków ubocznych, ponieważ ostatecznie obliczenia zostaną wykonane w każdym przypadku. Ale jeśli pętla nigdy nie kończy, nie możemy kod bezpiecznie przestawiać poprzek niego, bo może być po prostu zmieniając których operacje faktycznie zostanie wykonany przed zawiesza programowych. Chyba że potraktujemy zawieszony program jako UB.

Myślę, że jest to podobne do tego typu pytania , które odwołuje się do innego wątku . Optymalizacja może czasami usuwać puste pętle.

Istotną kwestią jest to, że kompilator może zmienić kolejność kodu, którego skutki uboczne nie powodują konfliktów. Zaskakująca kolejność wykonywania mogłaby wystąpić nawet wtedy, gdyby kompilator wygenerował niezakończony kod maszynowy dla nieskończonej pętli.

Uważam, że to właściwe podejście. Specyfikacja języka określa sposoby egzekwowania porządku wykonania. Jeśli chcesz mieć nieskończoną pętlę, której nie można zmienić w kolejności, napisz:

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");

Wydaje mi się, że najlepiej byłoby określić ten problem, ponieważ „Jeśli późniejszy fragment kodu nie zależy od wcześniejszego fragmentu kodu, a wcześniejszy fragment kodu nie ma skutków ubocznych w żadnej innej części systemu, dane wyjściowe kompilatora może wykonać późniejszy fragment kodu przed, po lub zmieszany z wykonaniem pierwszego, nawet jeśli ten pierwszy zawiera pętle, bez względu na to, kiedy i czy poprzedni kod faktycznie się zakończy . Na przykład kompilator może przepisać:

void testfermat (int n)
{
  int a = 1, b = 1, c = 1;
  while (pow (a, n) + pow (b, n)! = pow (c, n))
  {
    if (b> a) a ++; inaczej, jeśli (c> b) {a = 1; b ++}; else {a = 1; b = 1; c ++};
  }
  printf ("Wynik to");
  printf ("% d /% d /% d", a, b, c);
}

tak jak

void testfermat (int n)
{
  if (fork_is_first_thread ())
  {
    int a = 1, b = 1, c = 1;
    while (pow (a, n) + pow (b, n)! = pow (c, n))
    {
      if (b> a) a ++; inaczej, jeśli (c> b) {a = 1; b ++}; else {a = 1; b = 1; c ++};
    }
    signal_other_thread_and_die ();
  }
  else // Drugi wątek
  {
    printf ("Wynik to");
    wait_for_other_thread ();
  }
  printf ("% d /% d /% d", a, b, c);
}

Generalnie nie jest to nierozsądne, chociaż mogę się martwić, że:

  int total = 0;
  for (i = 0; num_reps> i; i ++)
  {
    update_progress_bar (i);
    total + = do_something_slow_with_no_side_effects (i);
  }
  show_result (łącznie);

stanie się

  int total = 0;
  if (fork_is_first_thread ())
  {
    for (i = 0; num_reps> i; i ++)
      total + = do_something_slow_with_no_side_effects (i);
    signal_other_thread_and_die ();
  }
  jeszcze
  {
    for (i = 0; num_reps> i; i ++)
      update_progress_bar (i);
    wait_for_other_thread ();
  }
  show_result (łącznie);

Dzięki temu, że jeden procesor obsługuje obliczenia, a inny obsługuje aktualizacje paska postępu, przepisanie poprawiłoby wydajność. Niestety, aktualizacje paska postępu byłyby raczej mniej przydatne niż powinny.

Nie jest rozstrzygalne dla kompilatora w nietrywialnych przypadkach, jeśli w ogóle jest to nieskończona pętla.

W różnych przypadkach może się zdarzyć, że optymalizator osiągnie lepszą klasę złożoności dla twojego kodu (np. Było to O (n ^ 2) i po optymalizacji otrzymasz O (n) lub O (1)).

Tak więc włączenie takiej reguły, która zabrania usuwania nieskończonej pętli w standardzie C ++, uniemożliwiłoby wiele optymalizacji. A większość ludzi tego nie chce. Myślę, że to całkiem odpowiada na twoje pytanie.

Inna sprawa: nigdy nie widziałem żadnego ważnego przykładu, w którym potrzebna jest nieskończona pętla, która nic nie robi.

Jedynym przykładem, o którym słyszałem, był brzydki hack, który naprawdę powinien zostać rozwiązany w przeciwnym razie: dotyczyło to systemów wbudowanych, w których jedynym sposobem na wyzwolenie resetu było zamrożenie urządzenia, aby strażnik automatycznie uruchomił je ponownie.

Jeśli znasz jakiś ważny / dobry przykład, w którym potrzebujesz nieskończonej pętli, która nic nie robi, powiedz mi.

Myślę, że warto wskazać, że pętle, które byłyby nieskończone, gdyby nie fakt, że współdziałają z innymi wątkami za pośrednictwem nieulotnych, niezsynchronizowanych zmiennych, mogą teraz dawać nieprawidłowe zachowanie z nowym kompilatorem.

Innymi słowy, sprawiaj, że twoje globals będą ulotne - podobnie jak argumenty przekazywane do takiej pętli za pośrednictwem wskaźnika / referencji.