Który jest szybszy: while (1) czy while (2)?


587

To było pytanie do wywiadu zadane przez kierownika wyższego szczebla.

Który jest szybszy?

while(1) {
    // Some code
}

lub

while(2) {
    //Some code
}

Powiedziałem, że oba mają tę samą szybkość wykonywania, ponieważ wyrażenie wewnątrz whilepowinno ostatecznie ocenić na truelub false. W takim przypadku zarówno ocena, jak truei brak dodatkowych instrukcji warunkowych wewnątrz whilewarunku. Oba będą miały tę samą szybkość wykonywania i wolę while (1).

Ale ankieter powiedział pewnie: „Sprawdź swoje podstawy. while(1)Jest szybszy niż while(2)”. (Nie testował mojej pewności siebie)

Czy to prawda?

Zobacz także: Czy „for (;;)” jest szybsze niż „while (TRUE)”? Jeśli nie, dlaczego ludzie z niego korzystają?


202
Pół przyzwoity kompilator zoptymalizuje obie formy do zera.

64
W zoptymalizowanej kompilacji za każdym razem (n), n! = 0 lub for (;;) będą tłumaczone na nieskończoną pętlę montażu z etykietą na początku i goto na końcu. Dokładnie ten sam kod, ta sama wydajność.
Alex F

60
Nic dziwnego, że optymalizacja zapasów przynosi 0x100000f90: jmp 0x100000f90(adres oczywiście się zmienia) dla obu fragmentów. Ankieter prawdopodobnie zabezpieczył się przed testem rejestrowym w porównaniu z prostym skoczkiem z oznaczeniem. Zarówno pytanie, jak i ich przypuszczenie są kulawe.
WhozCraig

50
To pytanie zadawane przez ankietera ma takie same patenty jak dilbert.com/strips/comic/1995-11-17 - spotkasz kogoś, kto szczerze wierzy w to, co mówią, niezależnie od ilorazu głupoty w swoim oświadczeniu. Po prostu wybierz jedną z następujących opcji: głęboki oddech, przekleństwa, śmiech, płacz, niektóre kombinacje powyższych :)
GMasucci

3
@ Mike W: można się zastanawiać, co powinien zrobić kompilator: przetłumaczyć na instrukcję Halt, czy uznać, że pętla kończy się po nieskończonym czasie i zoptymalizować nieskończone opóźnienie?
Yves Daoust,

Odpowiedzi:


681

Obie pętle są nieskończone, ale możemy zobaczyć, która z nich pobiera więcej instrukcji / zasobów na iterację.

Korzystając z gcc, skompilowałem dwa następujące programy do montażu na różnych poziomach optymalizacji:

int main(void) {
    while(1) {}
    return 0;
}


int main(void) {
    while(2) {}
    return 0;
}

Nawet bez optymalizacji ( -O0) wygenerowany zestaw był identyczny dla obu programów . Dlatego nie ma różnicy prędkości między dwiema pętlami.

Dla odniesienia tutaj jest wygenerowany zespół (przy użyciu gcc main.c -S -masm=intelflagi optymalizacji):

Z -O0:

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    push    rbp
    .seh_pushreg    rbp
    mov rbp, rsp
    .seh_setframe   rbp, 0
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Z -O1:

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Z -O2i -O3(ta sama moc wyjściowa):

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .section    .text.startup,"x"
    .p2align 4,,15
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

W rzeczywistości zespół wygenerowany dla pętli jest identyczny dla każdego poziomu optymalizacji:

 .L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Najważniejsze bity to:

.L2:
    jmp .L2

Nie potrafię dobrze czytać asemblera, ale jest to oczywiście bezwarunkowa pętla. jmpInstrukcja bezwarunkowo resetuje programu tyłu do .L2etykiety bez nawet porównując wartość przed prawdą, i oczywiście od razu robi to ponownie, aż program jest jakoś skończyło. Odpowiada to bezpośrednio kodowi C / C ++:

L2:
    goto L2;

Edytować:

Co ciekawe, nawet bez optymalizacji wszystkie poniższe pętle dały dokładnie taki sam wynik (bezwarunkowy jmp) w zestawie:

while(42) {}

while(1==1) {}

while(2==2) {}

while(4<7) {}

while(3==3 && 4==4) {}

while(8-9 < 0) {}

while(4.3 * 3e4 >= 2 << 6) {}

while(-0.1 + 02) {}

I nawet ku mojemu zdumieniu:

#include<math.h>

while(sqrt(7)) {}

while(hypot(3,4)) {}

Sprawy stają się trochę bardziej interesujące dzięki funkcjom zdefiniowanym przez użytkownika:

int x(void) {
    return 1;
}

while(x()) {}


#include<math.h>

double x(void) {
    return sqrt(7);
}

while(x()) {}

Na -O0te dwa przykłady rzeczywiście wywołać xi wykonać porównania dla każdej iteracji.

Pierwszy przykład (zwracanie 1):

.L4:
    call    x
    testl   %eax, %eax
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Drugi przykład (powrót sqrt(7)):

.L4:
    call    x
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jp  .L4
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Jednak w -O1obu przypadkach oba wytwarzają ten sam zestaw co poprzednie przykłady (bezwarunkowy jmppowrót do poprzedniej etykiety).

TL; DR

W GCC różne pętle są kompilowane do identycznego zestawu. Kompilator ocenia stałe wartości i nie przeszkadza w faktycznym porównaniu.

Morał tej historii jest następujący:

  • Istnieje warstwa tłumaczenia między kodem źródłowym C ++ a instrukcjami procesora i ta warstwa ma ważne implikacje dla wydajności.
  • Dlatego wydajności nie można ocenić, patrząc tylko na kod źródłowy.
  • Kompilator powinien być wystarczająco inteligentny, aby zoptymalizować takie trywialne przypadki. Programiści nie powinni tracić czasu na myślenie o nich w zdecydowanej większości przypadków.

196
Może ankieter nie używał gcc
MM

106
@Matt McNabb To dobra uwaga, ale jeśli ankieter opierał się na optymalizacjach specyficznych dla kompilatora, to w swoim pytaniu muszą wyrazić się jasno i muszą zaakceptować odpowiedź „nie ma różnicy” jako poprawną dla niektóre (większość?) kompilatory.
Jonathan Hartley

109
Aby usunąć wszelkie wątpliwości, przetestowałem to w punkcie 3.4.2 i obie pętle produkują ten sam zestaw na każdym -Opoziomie.
Martin Tournoij,

16
Nie wydaje mi się to wcale zaskakujące, ponieważ wszystko, co umieściłeś w sekcji warunkowej pętli, to stałe czasowe kompilacji. Jako taki, podejrzewam, że kompilator zobaczy, że pętle będą zawsze prawdziwe lub fałszywe i albo odpowiednio, po prostu jmpwrócą do początku, albo całkowicie usuną pętlę.
sherrellbc

10
@hippietrail Nie rozumiem, w jaki sposób zawartość (lub jej brak) pętli mogłaby wpłynąć na te optymalizacje (z wyjątkiem możliwości jakichkolwiek breakinstrukcji), ale i tak ją przetestowałem i nie, nawet z kodem wewnątrz pętli skok jest absolutne i bezwarunkowe dla obu while(1)i while(2). Jeśli naprawdę jesteś zaniepokojony, możesz sam przetestować innych.
ApproachingDarknessFish

282

Tak, while(1)jest o wiele szybszy niż while(2), aby człowiek czytał! Jeśli widzę while(1)w nieznanej bazie kodu, od razu wiem, co zamierzał autor, a moje oczy mogą przejść do następnej linii.

Jeśli zobaczę while(2), pewnie zatrzymam się i spróbuję dowiedzieć się, dlaczego autor nie napisał while(1). Czy palec autora poślizgnął się na klawiaturze? Czy opiekunowie tej bazy kodu używają while(n)niejasnego mechanizmu komentowania, aby pętle wyglądały inaczej? Czy to prymitywne obejście fałszywego ostrzeżenia w uszkodzonym narzędziu do analizy statycznej? Czy jest to wskazówka, że ​​czytam wygenerowany kod? Czy jest to błąd wynikający z niewłaściwego znalezienia i zastąpienia wszystkich, złego scalenia lub kosmicznego promienia? Może ta linia kodu ma robić coś zupełnie innego. Może miał to przeczytać while(w)lub while(x2). Lepiej znajdę autora w historii pliku i wyślę mu wiadomość e-mail „WTF” ... a teraz przełamałem swój kontekst mentalny.while(2)while(1) zajęłoby ułamek sekundy!

Przesadzam, ale tylko trochę. Czytelność kodu jest naprawdę ważna. I warto o tym wspomnieć w wywiadzie!


Moje myśli dokładnie i dokładnie, dlaczego chociaż (1) jest szybszy lol Chociaż myślę, że był to po prostu stary przypadek menedżera próbującego przekonać się, że wie o kodowaniu, kiedy tego nie widzi, wszyscy to widzieli, wszyscy chcą być jedi.
ekerner

8
Oczywiście, to wcale NIE jest przesada. Zdecydowanie użyjemy tutaj svn-annotate lub git blame(lub cokolwiek) i ogólnie ładowanie historii winy pliku zajmuje kilka minut. Potem w końcu zdecydowałem: „Ach, rozumiem, autor napisał ten wiersz, gdy wyszedł z liceum”, właśnie straciłem 10 minut ...
w.oddou

11
Głosowałem, bo mam dość konwencji. Deweloper ma tę mizerną okazję do napisania numeru, który mu się podoba, a potem pojawia się ktoś nudny i zastanawia się, dlaczego tak nie jest 1.
Utkan Gezer

1
Głosowane z powodu retoryki. Odczyt podczas gdy (1) jest dokładnie taki sam jak podczas gdy (2).
hdante

4
Przeszedłem dokładnie ten sam proces myślowy, jaki opisano w tej odpowiedzi przed chwilą, kiedy zobaczyłem while(2)w kodzie (aż do rozważenia: „Czy opiekunowie tej bazy kodu używają, podczas gdy (n) jako niejasny mechanizm komentowania, aby pętle wyglądały inaczej?” ). Więc nie, nie przesadzasz!
Hisham HM

151

Istniejące odpowiedzi pokazujące kod wygenerowany przez określony kompilator dla określonego celu z określonym zestawem opcji nie odpowiadają w pełni na pytanie - chyba że pytanie zostało zadane w tym konkretnym kontekście („Które jest szybsze przy użyciu gcc 4.7.2 dla x86_64 z domyślnymi opcjami? ”, na przykład).

Jeśli chodzi o definicję języka, w abstrakcyjnej maszynie while (1) ocenia stałą całkowitą 1i while (2)ocenia stałą całkowitą 2; w obu przypadkach wynik jest porównywany dla równości do zera. Standard językowy absolutnie nic nie mówi o względnej wydajności obu konstrukcji.

Mogę sobie wyobrazić, że niezwykle naiwny kompilator może generować inny kod maszynowy dla tych dwóch formularzy, przynajmniej po skompilowaniu bez żądania optymalizacji.

Z drugiej strony, kompilatory C absolutnie muszą oceniać niektóre wyrażenia stałe w czasie kompilacji, gdy pojawiają się w kontekstach wymagających wyrażenia stałego. Na przykład:

int n = 4;
switch (n) {
    case 2+2: break;
    case 4:   break;
}

wymaga diagnostyki; leniwy kompilator nie ma możliwości odroczenia oceny 2+2do czasu wykonania. Ponieważ kompilator musi mieć możliwość oceny stałych wyrażeń w czasie kompilacji, nie ma dobrego powodu, aby nie korzystać z tej możliwości, nawet jeśli nie jest to wymagane.

Tak mówi standard C ( N1570 6.8.5p4)

Instrukcja iteracyjna powoduje, że instrukcja zwana ciałem pętli jest wykonywana wielokrotnie, aż wyrażenie kontrolne nie będzie równe 0.

Odpowiednimi stałymi wyrażeniami są 1 == 0i 2 == 0oba, które oceniają intwartość 0. (Te porównania są niejawne w semantyce whilepętli; nie istnieją jako rzeczywiste wyrażenia C.)

Przewrotnie naiwny kompilator mógłby wygenerować inny kod dla obu konstrukcji. Na przykład, dla pierwszego może wygenerować bezwarunkową nieskończoną pętlę (traktując to 1jako przypadek specjalny), a dla drugiego może wygenerować wyraźne porównanie w czasie wykonywania odpowiadające 2 != 0. Ale nigdy nie spotkałem kompilatora C, który zachowywałby się w ten sposób i poważnie wątpię, czy taki kompilator istnieje.

Większość kompilatorów (mam ochotę powiedzieć, że wszystkie kompilatory o jakości produkcyjnej) mają opcje żądania dodatkowej optymalizacji. Przy takiej opcji jest jeszcze mniej prawdopodobne, że kompilator wygeneruje inny kod dla tych dwóch formularzy.

Jeśli Twój kompilator generuje inny kod dla dwóch konstrukcji, najpierw sprawdź, czy różne sekwencje kodu mają różną wydajność. Jeśli tak, spróbuj skompilować ponownie z opcją optymalizacji (jeśli jest dostępna). Jeśli nadal się różnią, prześlij raport o błędzie do dostawcy kompilatora. Nie jest to (koniecznie) błąd w sensie niezgodności ze standardem C, ale prawie na pewno jest to problem, który należy naprawić.

Podsumowując: while (1)i while(2) prawie na pewno mają taką samą wydajność. Mają dokładnie taką samą semantykę i żaden kompilator nie ma żadnego powodu, aby nie generować identycznego kodu.

I chociaż kompilator generuje szybszy kod dla while(1)niż całkowicie while(2), to równie legalny jest dla kompilatora generowanie szybszego kodu while(1)niż dla innego wystąpienia while(1)tego samego programu.

(W tym, które zadałeś, kryje się jeszcze jedno pytanie: jak radzisz sobie z ankieterem, który nalega na niewłaściwy punkt techniczny. Prawdopodobnie byłoby to dobre pytanie dla witryny Workplace ).


8
„W tym przypadku odpowiednimi (domyślnymi) wyrażeniami stałymi są 1! = 0 i 2! = 0, przy czym oba wyrażają się w wartości int 1” ... To jest zbyt skomplikowane i niedokładne. Standard mówi po prostu, że wyrażenie kontrolne whilemusi być typu skalarnego, a ciało pętli powtarza się, aż wyrażenie porówna się równe 0. Nie oznacza to, że istnieje domniemanie, expr != 0które jest oceniane ... które wymagałoby wyniku że - 0 lub 1 - z kolei porównuje się do 0, ad infinitum. Nie, wyrażenie jest porównywane z 0, ale to porównanie nie daje wartości. PS I głosował.
Jim Balter

3
@JimBalter: Rozumiem twój punkt widzenia i zaktualizuję swoją odpowiedź, aby rozwiązać ten problem. Chodziło mi jednak o to, że sformułowanie standardu „… dopóki wyrażenie kontrolne nie będzie równe 0” oznacza ocenę <expr> == 0; To właśnie „porównuje równe 0” środków w C. To porównanie jest częścią semantyki whilepętli. Nie ma żadnego znaczenia, ani w standardzie, ani w mojej odpowiedzi, że wynik należy 0ponownie porównać . (Powinienem ==raczej napisać niż !=.) Ale ta część mojej odpowiedzi była niejasna i zaktualizuję ją.
Keith Thompson,

1
„” porównuje równe 0 ”oznacza w C” - ale ten język jest w standardzie , nie w C… implementacja dokonuje porównania, nie generuje porównania w języku C. Piszesz „oba oceniają do wartości int 1” - ale taka ocena nigdy się nie zdarza. Jeśli spojrzeć na kod wygenerowany dla while (2), while (pointer), while (9.67), przez najbardziej naiwnej, niezoptymalizowanych kompilatora, nie będzie widać żadnego kodu wygenerowanego że plony 0lub 1. „Powinienem był napisać == zamiast! =” - nie, to nie miałoby sensu.
Jim Balter

2
@JimBalter: Hmmm. Nie chcę sugerować, że „porównuje równe 0” oznacza istnienie ... == 0wyrażenia C. Chodzi mi o to, że zarówno „porównania równe 0” wymagane przez opis whilepętli standardu, jak i wyraźne x == 0wyrażenie logicznie implikują tę samą operację. I myślę, że boleśnie naiwny kompilator C może generować kod, który generuje intwartość 0lub 1dla dowolnej whilepętli - chociaż nie sądzę, aby jakikolwiek rzeczywisty kompilator był tak naiwny.
Keith Thompson,


141

Poczekaj minutę. Ankieter, czy wyglądał jak ten facet?

wprowadź opis zdjęcia tutaj

Na tyle źle, że sam ankieter nie zdał tego wywiadu, co jeśli inni programiści w tej firmie „zdali” ten test?

Nie Ocenianie oświadczenia 1 == 0i 2 == 0 powinno być równie szybki. Możemy sobie wyobrazić słabe implementacje kompilatora, w których jedna może być szybsza od drugiej. Ale nie ma dobrego powodu, aby jeden był szybszy od drugiego.

Nawet jeśli istnieją jakieś niejasne okoliczności, w których twierdzenie byłoby prawdziwe, programiści nie powinni być oceniani na podstawie wiedzy o niejasnych (aw tym przypadku przerażających) ciekawostkach. Nie martw się o ten wywiad, najlepszym krokiem tutaj jest odejść.

Uwaga: To NIE jest oryginalna kreskówka Dilberta. To jest tylko mashup .


6
To byłoby śmieszne, gdyby również zawierać odpowiedź na pytanie.
Cody Gray

nie, ale naprawdę wszyscy możemy sobie łatwo wyobrazić, że wszystkie kompilatory napisane przez poważne firmy będą produkować rozsądny kod. weźmy „niezoptymalizowany przypadek” / O0, może skończy się tak, jak napisał anatolyg. To jest kwestia procesora, czy cmpoperand będzie działał w mniejszej liczbie cykli, porównując 1 do 0 niż 2 do 0? ile cykli zajmuje ogólnie wykonanie cmp? czy jest zmienny zgodnie z wzorami bitowymi? czy są bardziej „złożonymi” wzorcami bitowymi, które spowalniają cmp? Nie wiem osobiście. możesz sobie wyobrazić super idiotyczną implementację sprawdzającą krok po kroku od rangi 0 do n (np. n = 31).
v.oddou

5
O to też chodzi: cmpoperand powinien być równie szybki dla 1 i 200. Prawdopodobnie moglibyśmy wyobrazić sobie idiotyczne implementacje, w których tak nie jest. Ale czy możemy sobie wyobrazić non-idiotyczną implementację, gdzie while(1)jest szybsza niż while(200)? Podobnie, jeśli w jakimś przedhistorycznym wieku jedyna dostępna implementacja była taka idiotyczna, czy powinniśmy dziś o to niepokoić? Nie sądzę, to jest rozmowa szefa ze spiczastymi włosami i to prawdziwy klejnot!
janos

@ v.ouddou "operand cmp będzie działał w mniejszej liczbie cykli, porównując 1 do 0 niż 2 do 0" - Nie. Powinieneś dowiedzieć się, co to jest cykl. „Nie wiem osobiście. Można sobie wyobrazić super idiotyczną implementację sprawdzającą krok po kroku od rangi 0 do n” - lub odwrotnie, wciąż czyniącą ankietera bezsensownym idiotą. I po co martwić się sprawdzaniem krok po kroku? Wdrożeniem może być mężczyzna w pudełku, który decyduje się zrobić przerwę na lunch w trakcie oceny twojego programu.
Jim Balter

79

Twoje wyjaśnienie jest poprawne. To wydaje się być pytaniem, które oprócz wiedzy technicznej sprawdza Twoją pewność siebie.

Przy okazji, jeśli odpowiedziałeś

Oba fragmenty kodu są równie szybkie, ponieważ oba zajmują nieskończenie dużo czasu

powiedziałby ankieter

Ale while (1)może zrobić więcej iteracji na sekundę; czy możesz mi wytłumaczyć dlaczego? (to nonsens; ponownie sprawdź swoją pewność siebie)

Odpowiadając tak jak ty, zaoszczędziłeś czas, który w innym przypadku zmarnowałbyś na omawianie tego złego pytania.


Oto przykładowy kod wygenerowany przez kompilator w moim systemie (MS Visual Studio 2012) z wyłączonymi optymalizacjami:

yyy:
    xor eax, eax
    cmp eax, 1     (or 2, depending on your code)
    je xxx
    jmp yyy
xxx:
    ...

Przy włączonych optymalizacjach:

xxx:
    jmp xxx

Tak więc wygenerowany kod jest dokładnie taki sam, przynajmniej z kompilatorem optymalizującym.


28
Ten kod jest naprawdę tym, co kompilator wyświetla w moim systemie. Nie wymyśliłem tego.
anatolyg

10
icepack „Operand for while jest typu boolean” - kompletny nonsens. Czy jesteś ankieterem? Sugeruję zapoznanie się z językiem C i jego standardem przed złożeniem takich roszczeń.
Jim Balter

29
„Nie wymyśliłem tego”. - Proszę nie zwracać uwagi na lodowego plecaka, który mówi bzdury. C nie ma typu boolowskiego (w stdbool.h ma _Bool, ale to nie to samo, a semantyka whiledługo go poprzedza), a operand whilenie jest boolean, _Bool ani żadnego innego określonego typu. Argumentem whilemoże być dowolne wyrażenie ... while załamuje się na 0 i kontynuuje na non-0.
Jim Balter

36
„Oba fragmenty kodu są równie szybkie, ponieważ ukończenie ich zajmuje nieskończenie dużo czasu”, pomyślałem o czymś interesującym. Jedynym sposobem na zakończenie nieskończonej pętli byłoby odwrócenie nieco naładowanej cząstki lub awarii sprzętu: zmiana instrukcji z while (00000001) {}na while (00000000) {}. Im więcej prawdziwych bitów, tym mniejsza szansa, że ​​wartość zmieni się na false. Niestety, 2 ma również tylko jeden prawdziwy bit. 3 jednak działałby znacznie dłużej. Dotyczy to również kompilatora, który nie zawsze optymalizuje to (VC ++).
Jonathan Dickinson

8
@ mr5 nope. Aby odrobina odwrotności faktycznie spowodowała coś takiego, mówisz o czasach wykonania za dziesiątki tysięcy lat. Sam eksperyment myślowy. Jeśli pochodzisz z nieśmiertelnej rasy, możesz użyć -1, aby zapobiec wpływaniu bitów na twój program.
Jonathan Dickinson

60

Najbardziej prawdopodobnym wyjaśnieniem tego pytania jest to, że ankieter uważa, że ​​procesor sprawdza poszczególne bity liczb, jeden po drugim, aż osiągnie niezerową wartość:

1 = 00000001
2 = 00000010

Jeśli „wynosi zero?” algorytm zaczyna się od prawej strony liczby i musi sprawdzać każdy bit, aż osiągnie wartość niezerową, while(1) { }pętla musiałaby sprawdzać dwa razy więcej bitów na iterację niż while(2) { }pętla.

Wymaga to bardzo błędnego modelu mentalnego działania komputerów, ale ma swoją własną logikę wewnętrzną. Jednym ze sposobów sprawdzenia byłoby pytanie, while(-1) { }czy while(3) { }byłoby równie szybkie, czy też while(32) { }byłoby jeszcze wolniejsze .


39
Zakładałem, że nieporozumienie ankietera brzmiałoby bardziej jak „2 to liczba całkowita, którą należy przekonwertować na wartość logiczną, aby użyć jej w wyrażeniu warunkowym, podczas gdy 1 jest już wartością logiczną”.
Russell Borogove

7
A jeśli algorytm porównania zaczyna się od lewej, jest na odwrót.
Paŭlo Ebermann

1
+1, dokładnie tak myślałem. można sobie doskonale wyobrazić, że ktoś w to wierzy, że cmpalgorytm procesora jest liniowym sprawdzaniem bitów z wczesnym wyjściem z pętli na pierwszej różnicy.
v.oddou

1
@PeterCordes „Nigdy nie słyszałem, aby ktokolwiek (oprócz ciebie) argumentował, że -O0dane wyjściowe gcc lub clanga nie są wystarczająco dosłowne”. Nigdy czegoś takiego nie powiedziałem i wcale nie miałem na myśli gcc ani brzęczenia. Musisz mnie źle odczytać. Po prostu nie jestem zdania, że ​​to, co produkuje MSVC, jest przezabawne.
blubberdiblub

1
@PeterCordes Myliłem się, w MSVC punkt przerwania na while(1)nie pęka przed pętlą, ale na wyrażeniu. Ale nadal zapada się w pętli podczas optymalizacji ekspresji. Weź ten kod z dużą ilością przerw. Dostajesz to w niezoptymalizowanym trybie debugowania . Podczas optymalizacji wiele punktów przerwania spada razem, a nawet przelewa się do następnej funkcji (IDE pokazuje wynikowe punkty przerwania podczas debugowania) - odpowiedni demontaż .
blubberdiblub

32

Oczywiście nie znam prawdziwych intencji tego menedżera, ale proponuję zupełnie inny punkt widzenia: zatrudniając nowego członka w zespole, warto wiedzieć, jak reaguje na sytuacje konfliktowe.

Doprowadzili cię do konfliktu. Jeśli to prawda, są sprytni, a pytanie było dobre. W niektórych branżach, takich jak bankowość, opublikowanie problemu w Stack Overflow może być przyczyną odrzucenia.

Ale oczywiście nie wiem, po prostu proponuję jedną opcję.


To jest rzeczywiście doskonałe, ale while (2) vs while (1) jest oczywiście zaczerpnięte z komiksów dilbert. NIE MOŻE go wymyślić ktoś o zdrowych zmysłach (jak ktokolwiek wymyślił while (2) jako coś, co można napisać?). Jeśli twoja hipoteza była prawdziwa, na pewno dałbyś problem tak wyjątkowy, że możesz go znaleźć w Google. Jak „jest, gdy (0xf00b442) jest wolniejszy niż podczas (1)”, w jaki sposób bank inaczej znalazłby pytanie ankietowanego? podejrzewasz, że są to NSA i mają dostęp do wyników z klucza?
v.oddou

25

Myślę, że wskazówką jest „zapytany przez kierownika wyższego szczebla”. Ta osoba oczywiście przestała programować, kiedy został menadżerem, a potem zajęło jej kilka lat, aby zostać menedżerem wyższego szczebla. Nigdy nie straciłem zainteresowania programowaniem, ale nigdy nie napisałem linii od tamtych czasów. Tak więc jego odniesieniem nie jest „jakikolwiek przyzwoity kompilator”, jak wspomniano w niektórych odpowiedziach, ale „kompilator, z którym ta osoba pracowała 20-30 lat temu”.

W tym czasie programiści spędzili znaczną część czasu na wypróbowywaniu różnych metod zwiększania szybkości i wydajności kodu, ponieważ czas procesora „centralnego minikomputera” był tak cenny. Podobnie jak ludzie piszący kompilatory. Zgaduję, że jedyny kompilator, który jego firma udostępniła w tamtym czasie, zoptymalizowany na podstawie „często spotykanych instrukcji, które można zoptymalizować” i skrócił się na chwilę (1) i wszystko ocenił jeszcze, w tym chwilę (2). Doświadczenie takie mogło wyjaśnić jego pozycję i zaufanie do niego.

Najlepszym sposobem, aby cię zatrudnić, jest prawdopodobnie takie, które pozwala starszemu menedżerowi dać się ponieść emocjom i wygłosić 2-3 minuty na temat „starych dobrych dni programowania”, zanim TY płynnie poprowadzisz go do następnego tematu rozmowy. (Ważny jest tutaj odpowiedni moment - zbyt szybko, a przerywasz historię - zbyt wolno i jesteś oznaczony jako osoba o niewystarczającym skupieniu). Po zakończeniu rozmowy powiedz mu, że chciałbyś dowiedzieć się więcej na ten temat.


19

Powinieneś był zapytać go, jak doszedł do tego wniosku. Pod jakimkolwiek przyzwoitym kompilatorem, oba kompilują się do tych samych instrukcji asm. Powinien więc był powiedzieć kompilatorowi, żeby zaczął. Mimo to musiałbyś bardzo dobrze znać kompilator i platformę, aby nawet zgadywać teoretycznie. I w końcu tak naprawdę nie ma to znaczenia w praktyce, ponieważ istnieją inne czynniki zewnętrzne, takie jak fragmentacja pamięci lub obciążenie systemu, które będą miały większy wpływ na pętlę niż ten szczegół.


14
@GKFX Jeśli udzieliłeś odpowiedzi i powiedzą ci, że się mylisz, nie ma powodu, dla którego nie możesz poprosić ich o wyjaśnienie przyczyny. Jeśli Anatolyg ma rację i jest to test pewności siebie, powinieneś wyjaśnić, dlaczego odpowiedziałeś tak, jak zrobiłeś i zapytać o to samo.
P.Turpie

Miałem na myśli jako pierwszą rzecz, którą im mówisz. Nie może być „Dlaczego x jest szybszy?” „Nie wiem; dlaczego x jest szybszy?”. Oczywiście po prawidłowej odpowiedzi możesz następnie zapytać.
GKFX

18

Ze względu na to pytanie powinienem dodać, że pamiętam Douga Gwyna z komitetu C, który napisał, że niektóre wczesne kompilatory C bez przepustki optymalizatora wygenerowałyby test zestawu dla while(1)(w porównaniu z for(;;)którym nie miałby tego).

Chciałbym odpowiedzieć ankieterowi, podając tę ​​historyczną notatkę, a następnie powiedzieć, że nawet jeśli byłbym bardzo zaskoczony, że jakikolwiek kompilator to zrobił, kompilator mógłby mieć:

  • bez zaliczenia optymalizatora kompilator wygeneruje test dla obu while(1)iwhile(2)
  • z przepustką optymalizatora kompilator otrzymuje polecenie optymalizacji (z bezwarunkowym skokiem), while(1)ponieważ są one uważane za idiomatyczne. To zostawiłoby while(2)test i dlatego czyni różnicę wydajności między tymi dwoma.

Dodałbym oczywiście do ankietera, że ​​nieuwzględnianie while(1)i while(2)ten sam konstrukt jest oznaką niskiej jakości optymalizacji, ponieważ są to konstrukty równoważne.


10

Innym podejściem do takiego pytania byłoby sprawdzenie, czy masz odwagę powiedzieć swojemu przełożonemu, że się myli! I jak delikatnie możesz to przekazać.

Moim pierwszym instynktem byłoby wygenerowanie danych wyjściowych zestawu, aby pokazać menedżerowi, że każdy porządny kompilator powinien się tym zająć, a jeśli tak się nie stanie, prześlesz następną łatkę :)


8

Aby zobaczyć, jak wiele osób zagłębia się w ten problem, pokazuje dokładnie, dlaczego może to być test sprawdzający, jak szybko chcesz mikrooptymalizować rzeczy.

Moja odpowiedź brzmiałaby; to nie ma większego znaczenia, wolę skupić się na problemie biznesowym, który rozwiązujemy. W końcu za to otrzymam zapłatę.

Co więcej, wybrałbym, while(1) {}ponieważ jest to bardziej powszechne, a inni członkowie drużyny nie musieliby tracić czasu, aby dowiedzieć się, dlaczego ktoś wybrałby liczbę wyższą niż 1.

Teraz napisz kod. ;-)


1
Chyba że otrzymujesz wynagrodzenie za optymalizację kodu w czasie rzeczywistym, dla którego musisz ogolić zaledwie 1 lub 2 milisekundy, aby dopasować się do jego wymagań dotyczących czasu działania. Oczywiście, jest to zadanie dla optymalizatora, niektórzy powiedzieliby - to znaczy, jeśli masz optymalizator dla swojej architektury.
Neowizard

6

Jeśli martwisz się optymalizacją, powinieneś użyć

for (;;)

ponieważ to nie ma testów. (tryb cyniczny)


2
Dlatego mądrze jest go używać while(2), pozostawia miejsce na optymalizację, a następnie przełączasz się na, for (;;)gdy jesteś gotowy na zwiększenie wydajności.
Groo

5

Wydaje mi się, że jest to jedno z tych pytań podczas wywiadu behawioralnego zamaskowanych jako pytanie techniczne. Niektóre firmy to robią - zadają pytanie techniczne, na które każdy kompetentny programista powinien udzielić dość łatwej odpowiedzi, ale gdy rozmówca udzieli prawidłowej odpowiedzi, ankieter powie im, że się mylą.

Firma chce zobaczyć, jak zareagujesz w tej sytuacji. Czy siedzisz tam cicho i nie naciskasz, że twoja odpowiedź jest prawidłowa z powodu wątpliwości lub strachu przed zdenerwowaniem ankietera? A może chcesz rzucić wyzwanie osobie sprawującej władzę, o której wiesz, że jest w błędzie? Chcą sprawdzić, czy jesteś gotów bronić swoich przekonań i czy możesz to zrobić w taktowny i pełen szacunku sposób.


3

Kiedyś programowałem C i kod asemblera z powrotem, gdy ten rodzaj bzdur mógł coś zmienić. Kiedy zrobiło to różnicę, napisaliśmy to na Zgromadzeniu.

Gdybym zadał to pytanie, powtórzyłbym słynny cytat Donalda Knutha z 1974 r. O przedwczesnej optymalizacji i poszedłbym, gdyby rozmówca się nie śmiał i nie ruszył dalej.


1
Biorąc pod uwagę również, że „w ustalonych dyscyplinach inżynieryjnych poprawa o 12%, łatwo osiągalna, nigdy nie jest uważana za marginalną i uważam, że ten sam punkt widzenia powinien dominować w inżynierii oprogramowania”, myślę, że chodzenie jest nieuzasadnione.
Alice,

3

Może osoba przeprowadzająca wywiad celowo zadała takie głupie pytanie i chciała, abyś zrobił 3 punkty:

  1. Podstawowe rozumowanie. Obie pętle są nieskończone, trudno mówić o wydajności.
  2. Wiedza na temat poziomów optymalizacji. Chciał usłyszeć od ciebie, jeśli pozwolisz kompilatorowi wykonać dla ciebie jakąkolwiek optymalizację, zoptymalizuje to warunek, szczególnie jeśli blok nie będzie pusty.
  3. Wiedza na temat architektury mikroprocesorów. Większość architektur ma specjalną instrukcję procesora do porównania z 0 (choć niekoniecznie szybciej).

2

Oto problem: jeśli faktycznie piszesz program i mierzysz jego prędkość, prędkość obu pętli może być inna! Dla pewnego rozsądnego porównania:

unsigned long i = 0;
while (1) { if (++i == 1000000000) break; }

unsigned long i = 0;
while (2) { if (++i == 1000000000) break; }

z dodanym kodem, który drukuje czas, jakiś losowy efekt, taki jak położenie pętli w jednej lub dwóch liniach pamięci podręcznej, może mieć znaczenie. Jedna pętla może przypadkowo znajdować się całkowicie w obrębie jednej linii pamięci podręcznej lub na początku linii pamięci podręcznej, lub może obejmować dwie linie pamięci podręcznej. W rezultacie to, co twierdzi ankieter, jest najszybsze, może faktycznie być najszybsze - przez przypadek.

Scenariusz najgorszego przypadku: Kompilator optymalizacyjny nie wie, co robi pętla, ale stwierdza, że ​​wartości wytworzone podczas wykonywania drugiej pętli są takie same, jak wartości wytworzone przez pierwszą. I wygeneruj pełny kod dla pierwszej pętli, ale nie dla drugiej.


1
Rozumowanie „linii pamięci podręcznej” będzie działać tylko na chipie, który ma wyjątkowo małą pamięć podręczną.
sharptooth

10
To nie ma sensu. Pytania dotyczące prędkości zakładają „wszystko inne jest równe”.
Jim Balter

6
@JimBalter: To nie była kwestia szybkości, tylko pytanie o kłótnię z ankieterą. I możliwość, że wykonanie rzeczywistego testu może udowodnić ankieterowi „słuszność” - z powodów, które nie mają nic wspólnego z jego argumentem, ale są czystym zbiegiem okoliczności. Co postawiłoby cię w krępującej sytuacji, gdybyś próbował udowodnić, że się mylił.
gnasher729,

1
@ gnasher729 Pomijając wszystkie logiczne argumenty, warto przyjrzeć się przypadkowi, o którym mówisz. Ale wciąż ślepe przekonanie, że taki przypadek istnieje, jest nie tylko naiwne, ale głupie. Dopóki nie wyjaśnisz, co, jak i dlaczego tak się stanie, ta odpowiedź jest bezużyteczna.
user568109,

4
@ gnasher729 „To nie była kwestia szybkości” - nie będę debatować nad ludźmi, którzy stosują nieuczciwe techniki retoryczne.
Jim Balter

2

Oba są równe - to samo.

Zgodnie ze specyfikacjami wszystko, co nie jest 0, jest uważane za prawdziwe, więc nawet bez jakiejkolwiek optymalizacji, a dobry kompilator nie wygeneruje żadnego kodu dla while (1) lub while (2). Kompilator wygeneruje proste sprawdzenie != 0.


@djechlin - ponieważ oboje biorą 1 cykl procesora.
Wujek

Stała kompilatora składa ją, więc nie jest nawet analizowana w czasie wykonywania.
PaulHK,

2

Sądząc po ilości czasu i wysiłku, jaki ludzie spędzili na testowaniu, udowadnianiu i odpowiadaniu na to bardzo proste pytanie, twierdzę, że obaj spóźnili się, zadając to pytanie.

Aby spędzić na tym jeszcze więcej czasu ...

„while (2)” jest śmieszne, ponieważ,

„while (1)” i „while (true)” są historycznie używane do tworzenia nieskończonej pętli, która oczekuje, że „przerwa” zostanie wywołana na pewnym etapie wewnątrz pętli w oparciu o warunek, który z pewnością wystąpi.

„1” jest po prostu po to, aby zawsze oceniać na prawdę, a zatem powiedzenie „while (2)” jest tak samo głupie, jak powiedzenie „while (1 + 1 == 2)”, które również będzie oceniać na true.

A jeśli chcesz być całkowicie głupi, po prostu użyj:

while (1 + 5 - 2 - (1 * 3) == 0.5 - 4 + ((9 * 2) / 4)) {
    if (succeed())
        break;
}

Chciałbym pomyśleć, że twój programista napisał literówkę, która nie wpłynęła na działanie kodu, ale jeśli celowo użył „2” tylko po to, by być dziwnym, to spuść go, zanim wprowadzi dziwny sh! T przez cały kod, co utrudnia czytać i pracować z.


Wycofane cofnięcie przywraca edytowanie przez użytkownika o dużej liczbie powtórzeń. Ci ludzie zwykle dobrze znają zasady i są tutaj, aby cię ich nauczyć. Uważam, że ostatni wiersz twojego postu nie dodaje nic użytecznego do twojego postu. Nawet jeśli dostanę żart, którego oczywiście brakuje mi, uważam to za zbyt gadatliwe, nie warte dodatkowego akapitu.
Palec

@Palec: Dzięki za komentarz. Odkryłem, że ten sam facet zredagował wiele moich postów, głównie po to, by usunąć podpis. Uznałem więc, że był tylko trollem reputacji i stąd jego reputacja. Czy fora internetowe wyczerpały język - i powszechne uprzejmości - tak bardzo, że nie podpisujemy już naszych pism? może jestem trochę starą szkołą, ale po prostu niemiło jest zapomnieć o cześć i do widzenia. Używamy aplikacji, ale nadal jesteśmy ludźmi.
ekerner

1
Na Giełdzie Stos , pozdrowienia, slogany, dzięki itp nie są mile widziane . To samo zostało wspomniane w centrum pomocy , szczególnie w przypadku oczekiwanego zachowania . Żadna część Stack Exchange , nawet Stack Overflow , nie jest forum - to strony z pytaniami i odpowiedziami. Edycja jest jedną z różnic. Komentarze powinny również służyć wyłącznie do przekazywania opinii na temat postu, a nie do dyskusji ( Czat przepełnienia stosu ). Istnieje wiele innych sposobów, w jakie pytania i odpowiedzi różnią się od forum. Więcej na ten temat w Centrum pomocy i na Meta Stack Overflow .
Palec

Pamiętaj, że jeśli masz ponad 2000 powtórzeń (uprawnienie do edycji), nie zyskujesz więcej powtórzeń z edycji. Jeśli masz wątpliwości, dlaczego i edytowanie, z którymi się nie zgadzasz, zostało zastosowane do Twojego posta lub widzisz czyjeś złe zachowanie, zapytaj w Meta Stack Overflow . Jeśli redaktor zrobił coś złego, może zostać powiadomiony przez mod (może nie zdawał sobie sprawy) lub nawet zostać w jakiś sposób ukarany (jeśli zachowanie było celowo złośliwe). W przeciwnym razie otrzymasz wskazówki wyjaśniające, dlaczego edycja / zachowanie jest poprawne. Historia zmian niepotrzebnych bałaganów i może doprowadzić cię do wojny o wycofanie. Cofam tylko wtedy, gdy naprawdę jestem pewien, że edycja jest niepoprawna.
Palec,

Wreszcie o podpisaniu, powitaniu,…: Nie powinno się uwzględniać tych formalności, ale zwiększa stosunek sygnału do szumu i nie traci żadnych informacji. Możesz wybrać dowolny pseudonim, który chcesz podpisać. W większości miejsc masz również swojego awatara.
Palec

1

To zależy od kompilatora.

Jeśli zoptymalizuje kod lub jeśli oceni 1 i 2 na wartość true przy użyciu tej samej liczby instrukcji dla określonego zestawu instrukcji, szybkość wykonywania będzie taka sama.

W rzeczywistych przypadkach zawsze będzie tak samo szybko, ale można by sobie wyobrazić konkretnego kompilatora i konkretnego systemu, gdyby był on oceniany inaczej.

Mam na myśli: tak naprawdę nie jest to pytanie związane z językiem (C).


0

Ponieważ ludzie, którzy chcą odpowiedzieć na to pytanie, chcą najszybszej pętli, odpowiedziałbym, że oba kompilują się w tym samym kodzie asemblera, jak podano w innych odpowiedziach. Niemniej jednak możesz zasugerować ankieterowi za pomocą „rozwijania pętli”; pętla do {} while zamiast pętli while.

Ostrożnie: musisz upewnić się, że pętla przynajmniej raz uruchomi się raz .

Pętla powinna mieć stan pęknięcia w środku.

Również dla tego rodzaju pętli osobiście wolałbym używać do {} while (42), ponieważ każda liczba całkowita, z wyjątkiem 0, wykonałaby zadanie.


Dlaczego miałby sugerować pętlę do {} while? Podczas gdy (1) (lub while (2)) robi to samo.
Catsunami,

rób podczas usuwa jeden dodatkowy skok, więc lepszą wydajność. Oczywiście w przypadku, gdy wiesz, że pętla zostanie wykonana co najmniej raz
Antonin GAVREL

0

Oczywista odpowiedź brzmi: jak napisano, oba fragmenty uruchomiłyby równie zajętą ​​nieskończoną pętlę, co czyni program nieskończenie wolnym .

Chociaż redefiniowanie słów kluczowych C jako makr technicznie miałoby nieokreślone zachowanie, jest to jedyny sposób, w jaki mogę wymyślić szybki fragment fragmentu kodu: możesz dodać ten wiersz powyżej 2 fragmentów:

#define while(x) sleep(x);

rzeczywiście będzie while(1)dwa razy szybszy (lub o połowę wolniejszy) niż while(2).


@ MaxB: rzeczywiście sztuczka makro musi być jeszcze bardziej zniekształcona. Myślę, że nowa wersja powinna działać, chociaż nie jest gwarantowana przez standard C.
chqrlie,

-4

Jedyny powód, dla którego mogę wymyślić, dlaczego while(2)byłoby wolniej, to:

  1. Kod optymalizuje pętlę do

    cmp eax, 2

  2. Kiedy następuje odejmowanie, zasadniczo odejmujesz

    za. 00000000 - 00000010 cmp eax, 2

    zamiast

    b. 00000000 - 00000001 cmp eax, 1

cmpustawia tylko flagi i nie ustawia wyniku. Więc na najmniej znaczących bitach wiemy, czy musimy pożyczyć, czy nie za pomocą b . Podczas gdy przy pomocy musisz wykonać dwa odejmowania, zanim otrzymasz pożyczkę.


15
cmp zajmie 1 cykl procesora niezależnie od obu przypadków.
Wujek

8
Ten kod byłby niepoprawny. Prawidłowy kod załaduje 2 lub 1 do rejestru eax, a następnie porówna eax z 0.
gnasher729,
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.