Czy kompilatory tworzą lepszy kod dla pętli do-while w porównaniu z innymi typami pętli?

W bibliotece kompresji zlib (która jest używana między innymi w projekcie Chromium) jest komentarz, który sugeruje, że pętla do-while w C generuje „lepszy” kod na większości kompilatorów. Oto fragment kodu, w którym się pojawia.

do {
} while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         scan < strend);
/* The funny "do {}" generates better code on most compilers */

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c&l=1225

Czy istnieją dowody na to, że większość (lub jakikolwiek) kompilator wygenerowałaby lepszy (np. Wydajniejszy) kod?

Aktualizacja: Mark Adler , jeden z oryginalnych autorów, podał trochę kontekstu w komentarzach.

Po pierwsze:

do-whilePętli nie jest taki sam jak while-loop lub for-loop.

• whilea forpętle mogą w ogóle nie uruchamiać treści pętli.
• do-whilePętla zawsze przebiega ciało pętli przynajmniej raz - pomija początkową sprawdzić stan.

To jest logiczna różnica. To powiedziawszy, nie wszyscy ściśle przestrzegają tego. Pętle whilelub są dość powszechne, fornawet jeśli jest zagwarantowane, że zawsze będą się zapętlać co najmniej raz. (Szczególnie w językach z pętlami foreach ).

Aby uniknąć porównywania jabłek i pomarańczy, będę zakładał, że pętla zawsze będzie działać co najmniej raz. Ponadto nie będę forponownie wspominał o pętlach, ponieważ zasadniczo sąwhile pętlami z odrobiną cukru składniowego dla licznika pętli.

Odpowiem więc na pytanie:

Jeśli whilepętla jest gwarantowana co najmniej raz, czy użycie do-whilepętli powoduje wzrost wydajności .

A do-whilepomija pierwszą kontrolę stanu. Jest więc jedna gałąź mniej i jeden warunek mniej do oceny.

Jeśli sprawdzenie tego warunku jest drogie i wiesz, że masz gwarancję wykonania pętli co najmniej raz, do-whilepętla może być szybsza.

I chociaż jest to uważane w najlepszym przypadku za mikro-optymalizację, jest to taka, której kompilator nie zawsze może zrobić: w szczególności, gdy kompilator nie jest w stanie udowodnić, że pętla zawsze wejdzie co najmniej raz.

Innymi słowy, pętla while:

while (condition){
    body
}

W praktyce to to samo:

if (condition){
    do{
        body
    }while (condition);
}

Jeśli wiesz, że zawsze będziesz co najmniej raz zapętlić, ta instrukcja if jest zbędna.

Podobnie na poziomie zespołu, w ten sposób z grubsza kompilują się różne pętle, aby:

pętla do-while:

start:
    body
    test
    conditional jump to start

pętla while:

    test
    conditional jump to end
start:
    body
    test
    conditional jump to start
end:

Zwróć uwagę, że warunek został zduplikowany. Alternatywnym podejściem jest:

    unconditional jump to end
start:
    body
end:
    test
    conditional jump to start

... który zamienia zduplikowany kod na dodatkowy skok.

Tak czy inaczej, jest to nadal gorsze niż normalna do-whilepętla.

To powiedziawszy, kompilatorzy mogą robić, co chcą. A jeśli uda im się udowodnić, że pętla zawsze pojawia się raz, to wykonała pracę za Ciebie.

Ale sytuacja wygląda nieco dziwnie w przypadku konkretnego przykładu w pytaniu, ponieważ ma on pustą treść pętli. Ponieważ nie ma ciała, nie ma logicznej różnicy między whileido-while .

FWIW, przetestowałem to w Visual Studio 2012:

• Z pustą treścią faktycznie generuje ten sam kod dla whilei do-while. Więc ta część jest prawdopodobnie pozostałością po dawnych czasach, kiedy kompilatory nie były tak świetne.

• Ale z niepustą treścią VS2012 udaje się uniknąć powielania kodu warunku, ale nadal generuje dodatkowy skok warunkowy.

To ironiczne, że chociaż przykład w pytaniu podkreśla, dlaczego do-whilepętla może być szybsza w ogólnym przypadku, sam przykład nie wydaje się przynosić żadnych korzyści dla nowoczesnego kompilatora.

Biorąc pod uwagę wiek komentarza, możemy tylko zgadywać, dlaczego miałby to znaczenie. Jest bardzo możliwe, że kompilatory w tym czasie nie były w stanie rozpoznać, że ciało było puste. (A jeśli tak, to nie wykorzystali informacji).

Czy istnieją dowody na to, że większość (lub jakikolwiek) kompilator wygenerowałaby lepszy (np. Wydajniejszy) kod?

Niewiele, chyba że spojrzysz na rzeczywisty wygenerowany zestaw rzeczywistego, konkretnego kompilatora na określonej platformie z niektórymi określonymi ustawieniami optymalizacji.

Prawdopodobnie warto było się tym martwić kilkadziesiąt lat temu (kiedy napisano ZLib), ale z pewnością nie teraz, chyba że dzięki prawdziwemu profilowaniu odkryłeś, że usuwa to wąskie gardło z twojego kodu.

W skrócie (tl; dr):

Trochę inaczej interpretuję komentarz w kodzie PO, myślę, że „lepszy kod”, który podobno zaobserwowali, był spowodowany przeniesieniem rzeczywistej pracy do „stanu” pętli. Całkowicie się jednak zgadzam, że jest to bardzo specyficzne dla kompilatora i że dokonane przez nich porównanie, będąc w stanie stworzyć nieco inny kod, jest w większości bezcelowe i prawdopodobnie przestarzałe, jak pokazuję poniżej.

Detale:

Trudno powiedzieć, co pierwotny autor miał na myśli, mówiąc o swoim komentarzu na temat do {} whiletworzenia lepszego kodu, ale chciałbym spekulować w innym kierunku niż to, co zostało tutaj podniesione - uważamy, że różnica między pętlami do {} whilei while {}jest dość niewielka (jedna gałąź mniej niż Mistyczne powiedziane), ale jest w tym kodzie coś jeszcze „zabawniejszego”, a to umieszcza całą pracę w tym zwariowanym stanie i utrzymuje wewnętrzną część pustą ( do {}).

Wypróbowałem następujący kod na gcc 4.8.1 (-O3) i daje on interesującą różnicę -

#include "stdio.h" 
int main (){
    char buf[10];
    char *str = "hello";
    char *src = str, *dst = buf;

    char res;
    do {                            // loop 1
        res = (*dst++ = *src++);
    } while (res);
    printf ("%s\n", buf);

    src = str;
    dst = buf;
    do {                            // loop 2
    } while (*dst++ = *src++);
    printf ("%s\n", buf);

    return 0; 
}

Po kompilacji -

00000000004003f0 <main>:
  ... 
; loop 1  
  400400:       48 89 ce                mov    %rcx,%rsi
  400403:       48 83 c0 01             add    $0x1,%rax
  400407:       0f b6 50 ff             movzbl 0xffffffffffffffff(%rax),%edx
  40040b:       48 8d 4e 01             lea    0x1(%rsi),%rcx
  40040f:       84 d2                   test   %dl,%dl
  400411:       88 16                   mov    %dl,(%rsi)
  400413:       75 eb                   jne    400400 <main+0x10>
  ...
;loop 2
  400430:       48 83 c0 01             add    $0x1,%rax
  400434:       0f b6 48 ff             movzbl 0xffffffffffffffff(%rax),%ecx
  400438:       48 83 c2 01             add    $0x1,%rdx
  40043c:       84 c9                   test   %cl,%cl
  40043e:       88 4a ff                mov    %cl,0xffffffffffffffff(%rdx)
  400441:       75 ed                   jne    400430 <main+0x40>
  ...

Zatem pierwsza pętla wykonuje 7 instrukcji, a druga 6, mimo że mają wykonywać tę samą pracę. Teraz nie mogę powiedzieć, czy za tym kryje się jakiś spryt kompilatora, prawdopodobnie nie i jest to po prostu przypadkowe, ale nie sprawdziłem, jak współdziała z innymi opcjami kompilatora, których może używać ten projekt.

Z drugiej strony na clang 3.3 (-O3) obie pętle generują ten kod 5 instrukcji:

  400520:       8a 88 a0 06 40 00       mov    0x4006a0(%rax),%cl
  400526:       88 4c 04 10             mov    %cl,0x10(%rsp,%rax,1)
  40052a:       48 ff c0                inc    %rax
  40052d:       48 83 f8 05             cmp    $0x5,%rax
  400531:       75 ed                   jne    400520 <main+0x20>

Co po prostu pokazuje, że kompilatory są zupełnie inne i rozwijają się w znacznie szybszym tempie, niż niektórzy programiści mogli przewidywać kilka lat temu. Oznacza to również, że ten komentarz jest dość bez znaczenia i prawdopodobnie istnieje, ponieważ nikt nigdy nie sprawdził, czy nadal ma sens.

Podsumowując - jeśli chcesz zoptymalizować do najlepszego możliwego kodu (i wiesz, jak powinien wyglądać), zrób to bezpośrednio w asemblerze i wytnij "pośrednika" (kompilator) z równania, ale weź pod uwagę, że nowszy kompilatory i nowsze HW mogą sprawić, że ta optymalizacja stanie się przestarzała. W większości przypadków znacznie lepiej jest po prostu pozwolić kompilatorowi wykonać ten poziom pracy za Ciebie i skupić się na optymalizacji dużych rzeczy.

Kolejna kwestia, na którą należy zwrócić uwagę - liczba instrukcji (zakładając, że właśnie o to chodziło w oryginalnym kodzie OP), nie jest bynajmniej dobrym miernikiem wydajności kodu. Nie wszystkie instrukcje są sobie równe, a niektóre z nich (np. Proste ruchy reg-to-reg) są naprawdę tanie, ponieważ są optymalizowane przez procesor. Inna optymalizacja może w rzeczywistości zaszkodzić wewnętrznym optymalizacjom procesora, więc ostatecznie liczą się tylko prawidłowe testy porównawcze.

whilePętla jest często zestawiane jako do-whilepętlę z początkowym odgałęzieniem do stanu, czyli

    bra $1    ; unconditional branch to the condition
$2:
    ; loop body
$1:
    tst <condition> ; the condition
    brt $2    ; branch if condition true

podczas gdy kompilacja do-whilepętli jest taka sama bez początkowej gałęzi. Widać z tego, że while()jest to z natury mniej wydajne, biorąc pod uwagę koszt początkowej gałęzi, który jest jednak opłacany tylko raz. [Porównaj z naiwnym sposobem implementacji, while,który wymaga zarówno gałęzi warunkowej, jak i gałęzi bezwarunkowej na iterację.]

To powiedziawszy, nie są to naprawdę porównywalne alternatywy. Przekształcenie whilepętli w do-whilepętlę i odwrotnie jest bolesne . Robią różne rzeczy. I w tym przypadku kilka połączeń metoda byłaby całkowicie dominują cokolwiek zrobił z kompilator whilewobecdo-while.

Uwaga nie dotyczy wyboru instrukcji sterującej (do vs. while), chodzi o rozwijanie pętli !!!

Jak widać, jest to funkcja porównywania ciągów (elementy łańcuchowe prawdopodobnie mają 2 bajty), która mogłaby zostać zapisana przy użyciu pojedynczego porównania zamiast czterech w skrócie i wyrażeniu.

Ta ostatnia implementacja jest z pewnością szybsza, ponieważ wykonuje pojedynczą kontrolę stanu końca łańcucha po każdych porównaniach czterech elementów, podczas gdy standardowe kodowanie wymagałoby jednego sprawdzenia na porównanie. Mówiąc inaczej, 5 testów na 4 elementy vs. 8 testów na 4 elementy.

W każdym razie zadziała to tylko wtedy, gdy długość łańcucha jest wielokrotnością czterech lub ma element wartowniczy (tak, że dwa łańcuchy będą się różnić poza strendgranicami). Dość ryzykowne!

Ta dyskusja na temat wydajności podczas i do jest w tym przypadku całkowicie bezcelowa, ponieważ nie ma ciała.

while (Condition)
{
}

i

do
{
}
while (Condition);

są absolutnie równoważne.