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


153

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!


4
while(1) { MyMysteriousFunction(); }muszą być niezależnie kompilowalne bez znajomości definicji tej tajemniczej funkcji, prawda? Jak więc możemy określić, czy wywołuje ona dowolne funkcje we / wy biblioteki? Innymi słowy: z pewnością ten pierwszy punktor mógłby zostać sformułowany w żaden sposób nie wywołuje funkcji .
Daniel Earwicker

19
@Daniel: Jeśli ma dostęp do definicji funkcji, może udowodnić wiele rzeczy. Istnieje coś takiego jak optymalizacja międzyproceduralna.
Potatoswatter

3
Czy w tej chwili w C ++ 03 można zmienić kompilator int x = 1; for(int i = 0; i < 10; ++i) do_something(&i); x++;na for(int i = 0; i < 10; ++i) do_something(&i); int x = 2;? Lub być może w drugą stronę, z xinicjalizacją 2przed pętlą. Potrafi stwierdzić, do_somethingże nie dba o wartość x, więc jest to całkowicie bezpieczna optymalizacja, jeśli do_something nie powoduje zmiany wartości w itaki sposób, że kończy się w nieskończonej pętli.
Dennis Zickefoose

4
Czy to oznacza, że main() { start_daemon_thread(); while(1) { sleep(1000); } }może natychmiast zakończyć działanie, zamiast uruchamiać demona w wątku w tle?
Gabe

2
„Ten wnikliwy artykuł” zakłada, że ​​określone zachowanie jest niezdefiniowanym zachowaniem tylko dlatego, że nie ma wyraźnego, zdefiniowanego zachowania. To błędne założenie. Ogólnie rzecz biorąc, gdy standard pozostawia otwartą skończoną liczbę zachowań, implementacja musi wybrać dowolne z nich ( nieokreślone zachowanie). Nie musi to być deterministyczne. Zakończenie pętli „nic nie rób” jest zapewne wyborem logicznym; albo tak, albo nie. Robienie czegoś innego jest niedozwolone.
MSalters

Odpowiedzi:


33

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.


1
Czy są jakieś bezpieczne i użyteczne optymalizacje, które są ułatwione przez obecny język, których nie można by ułatwić mówiąc: „Jeśli zakończenie pętli zależy od stanu jakichkolwiek obiektów, czas potrzebny do wykonania pętli nie jest uważany za obserwowalny efekt uboczny, nawet jeśli taki czas jest nieskończony ”. Biorąc pod uwagę, że do { x = slowFunctionWithNoSideEffects(x);} while(x != 23);kod Hoisting po pętli, od którego nie byłby zależny, xwydawałby się bezpieczny i rozsądny, ale zezwolenie kompilatorowi na założenie x==23w takim kodzie wydaje się bardziej niebezpieczne niż przydatne.
supercat

47

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


„Dowodzenie 1) jest całkiem proste” - w rzeczywistości, czy z 3 warunków nie wynika bezpośrednio, aby kompilator mógł założyć zakończenie pętli zgodnie z klauzulą, o którą pyta Johannes? Myślę, że sprowadzają się do tego, że „pętla nie ma żadnego obserwowalnego efektu, z wyjątkiem być może kręcenia się w nieskończoność”, a klauzula zapewnia, że ​​„kręcenie na zawsze” nie jest gwarantowanym zachowaniem dla takich pętli.
Steve Jessop

@Steve: to proste, jeśli pętla się nie kończy; ale jeśli pętla się kończy, może mieć nietrywialne zachowanie, które wpływa na przetwarzanie pliku complex_io_operation.
Philip Potter

Ups, tak, przegapiłem, że może modyfikować nieulotne lokalizacje / aliasy / cokolwiek, co jest używane w operacjach IO. Więc masz rację: chociaż niekoniecznie tak jest, jest wiele przypadków, w których kompilatory mogą udowodnić, i faktycznie, nie ma takiej modyfikacji.
Steve Jessop

„Oznacza to jednak, że w rezultacie ucierpi nieskończone pętle używane w przykładach uczenia się i będą powodować problemy w kodzie początkującego. Nie mogę powiedzieć, że to całkiem dobra rzecz”. Po prostu skompiluj z wyłączoną optymalizacją i powinno nadal działać
KitsuneYMG

1
@supercat: To, co opisujesz, wydarzy się w praktyce, ale nie tego wymaga projekt normy. Nie możemy założyć, że kompilator nie wie, czy pętla się zakończy. Jeśli kompilator nie wiedzieć pętli nie zostanie rozwiązana, może robić, co mu się podoba. DS9K będzie tworzyć demony nosowe za każdym nieskończonej pętli bez I / O i inne (Dlatego rozwiązuje DS9K powstrzymania problemów.)
Philip Potter

15

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.


7
„Puste nieskończone pętle są niezdefiniowanym zachowaniem”? Alan Turing błagałby inaczej, ale tylko wtedy, gdy przestaje kręcić się w grobie.
Donal Fellows

11
@Donal: Nigdy nie powiedziałem nic o jego semantyce w maszynie Turinga. Omawiamy semantykę nieskończonej pętli bez skutków ubocznych w C ++ . I jak to czytam, C ++ 0x decyduje się powiedzieć, że takie pętle są niezdefiniowane.
jalf

Puste nieskończone pętle byłyby głupie i nie byłoby powodu, aby mieć dla nich specjalne zasady. Reguła została zaprojektowana tak, aby radzić sobie z użytecznymi pętlami o nieograniczonym (miejmy nadzieję nie nieskończonym) czasie trwania, które obliczają coś, co będzie potrzebne w przyszłości, ale nie natychmiast.
supercat

1
Czy to oznacza, że ​​C ++ 0x nie nadaje się do urządzeń wbudowanych? Prawie wszystkie urządzenia wbudowane nie powodują zakończenia i wykonują swoją pracę wewnątrz dużego tłuszczu while(1){...}. Nawet rutynowo używają while(1);do wywoływania resetowania wspomaganego przez watchdog.
vsz

1
@vsz: pierwsza forma jest w porządku. Nieskończone pętle są doskonale zdefiniowane, o ile mają jakieś obserwowalne zachowanie. Druga forma jest trudniejsza, ale przychodzą mi do głowy dwa bardzo proste sposoby: (1) kompilator przeznaczony dla urządzeń osadzonych może po prostu zdefiniować bardziej rygorystyczne zachowanie w takim przypadku lub (2) utworzyć treść, która wywołuje jakąś fikcyjną funkcję biblioteczną . Dopóki kompilator nie wie, co robi ta funkcja, musi założyć, że może ona mieć jakiś efekt uboczny, więc nie może zepsuć pętli.
jalf

8

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.


3
Fajne pytanie. Wygląda na to, że ten gość miał dokładnie ten problem, który ten akapit pozwala wywołać kompilatorowi. W połączonej dyskusji jednej z odpowiedzi jest napisane, że „Niestety, słowa„ nieokreślone zachowanie ”nie są używane. Jednak za każdym razem, gdy norma mówi„ kompilator może założyć P ”, zakłada się, że program, który ma właściwość nie-P ma niezdefiniowaną semantykę. " . To mnie zaskakuje. Czy to oznacza, że ​​mój przykładowy program powyżej ma niezdefiniowane zachowanie i może znikąd zniknąć?
Johannes Schaub - litb

@Johannes: tekst „można założyć” nie występuje nigdzie indziej w wersji roboczej, którą mam pod ręką, a „mogę założyć” pojawia się tylko kilka razy. Chociaż sprawdziłem to za pomocą funkcji wyszukiwania, która nie pasuje do podziałów wierszy, więc mogłem przegapić niektóre. Więc nie jestem pewien, czy uogólnienie autora jest uzasadnione na podstawie dowodów, ale jako matematyk muszę przyznać logikę argumentacji, że jeśli kompilator przyjmie coś fałszywego, to ogólnie może wydedukować cokolwiek ...
Steve Jessop

... Dopuszczenie do sprzeczności w rozumowaniu kompilatora na temat programu z pewnością bardzo mocno wskazuje na UB, ponieważ w szczególności pozwala kompilatorowi, dla dowolnego X, wywnioskować, że program jest równoważny z X. Z pewnością pozwala kompilatorowi wywnioskować, że jest to pozwalając na to . Zgadzam się również z autorem, że jeśli UB jest zamierzone, to powinno być wyraźnie określone, a jeśli nie jest zamierzone, to tekst specyfikacji jest błędny i powinien zostać poprawiony (być może przez odpowiednik w języku spec, "kompilator może zastąpić pętla z kodem, który nie ma żadnego efektu ”, nie jestem pewien).
Steve Jessop

@SteveJessop: Co byś pomyślał, mówiąc po prostu, że wykonanie dowolnego fragmentu kodu - w tym nieskończonych pętli - może zostać odłożone do czasu, gdy coś, co zrobił fragment kodu, wpłynęłoby na obserwowalne zachowanie programu i że do celów tego reguła, czas wymagany do wykonania fragmentu kodu - nawet jeśli jest nieskończony - nie jest „obserwowalnym efektem ubocznym”. Jeśli kompilator może wykazać, że pętla nie może zakończyć się bez zmiennej posiadającej określoną wartość, można uznać, że zmienna posiada tę wartość, nawet można by również wykazać, że pętla nie może zakończyć się, gdy ma tę wartość.
supercat

@supercat: zgodnie z tym wnioskiem nie sądzę, aby poprawiało to sytuację. Jeśli pętla prawdopodobnie nigdy nie zostanie zakończona, wówczas dla dowolnego obiektu Xi wzorca bitowego xkompilator może wykazać, że pętla nie kończy się bez Xzatrzymania wzorca bitowego x. To bezmyślnie prawda. XMożna więc uznać, że zawiera każdy wzór bitu, a to jest tak samo złe jak UB w tym sensie, że za zło Xi xszybko spowoduje pewne. Dlatego uważam, że musisz być bardziej precyzyjny w swoim standardowym języku. Trudno jest mówić o tym, co dzieje się „na końcu” nieskończonej pętli i pokazywać to jako odpowiednik jakiejś skończonej operacji.
Steve Jessop

8

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");

2
@ JohannesSchaub-litb: Jeśli pętla - nieskończona lub nie - nie odczytuje ani nie zapisuje żadnych zmiennych podczas wykonywania i nie wywołuje żadnych funkcji, które mogłyby to zrobić, kompilator może odroczyć dowolną część pętli do pierwsza próba uzyskania dostępu do czegoś tam obliczonego. Biorąc pod uwagę unsigned int dummy; while(1){dummy++;} fprintf(stderror,"Hey\r\n"); fprintf(stderror,"Result was %u\r\n",dummy);, pierwszy fprintfmógł zostać wykonany, ale drugi nie (kompilator mógł przenieść obliczenia dummymiędzy nimi fprintf, ale nie poza to, które drukuje jego wartość).
supercat

1

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.


Myślę, że nie można oddzielić przypadku paska postępu, ponieważ wyświetlanie paska postępu jest wywołaniem we / wy biblioteki. Optymalizacje nie powinny w ten sposób zmieniać widocznego zachowania.
Philip Potter

@Philip Potter: Gdyby powolna rutyna miała skutki uboczne, z pewnością byłaby to prawda. W moim wcześniejszym przykładzie nie miałoby to znaczenia, gdyby tak nie było, więc zmieniłem to. Moja interpretacja specyfikacji jest taka, że ​​system może odroczyć wykonanie powolnego kodu do czasu, gdy jego efekty (inne niż czas potrzebny do wykonania) staną się widoczne, tj. Wywołanie show_result (). Gdyby kod paskowy postępu wykorzystywał bieżącą sumę lub przynajmniej udawał, że to robi, zmusiłoby to go do synchronizacji z wolnym kodem.
supercat

1
To wyjaśnia wszystkie te paski postępu, które szybko
przesuwają się

0

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.


1
Przykład miejsca, w którym możesz potrzebować nieskończonej pętli: system osadzony, w którym nie chcesz spać ze względu na wydajność, a cały kod zawiesza się z przerwaniem lub dwoma?
JCx

@JCx w standardzie C przerwania powinny ustawić flagę, którą sprawdza główna pętla, dlatego główna pętla miałaby obserwowalne zachowanie w przypadku ustawienia flag. Uruchamianie znacznego kodu w przerwaniach jest nieprzenośne.
MM

-1

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.


Jeśli wchodzą w interakcję z innymi wątkami, nie powinieneś uczynić ich niestabilnymi, uczynić z nich atomów lub chronić je zamkiem.
BCoates

1
To straszna rada. Tworzenie ich volatilenie jest ani konieczne, ani wystarczające, a to dramatycznie szkodzi wydajności.
David Schwartz,
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.