Jest if( a < 901 )szybszy niż if( a <= 900 ).

Niezupełnie jak w tym prostym przykładzie, ale występują niewielkie zmiany wydajności w złożonym kodzie pętli. Podejrzewam, że ma to coś wspólnego z wygenerowanym kodem maszynowym, na wypadek, gdyby było to w ogóle prawdą.

Nie, na większości architektur nie będzie szybciej. Nie określiłeś, ale na x86 wszystkie integralne porównania będą zazwyczaj zaimplementowane w dwóch instrukcjach maszyny:

• A testlub cmpinstrukcja, która ustawiaEFLAGS
• I Jccinstrukcja (skok) , w zależności od typu porównania (i układu kodu):
  • jne - Skok, jeśli nie jest równy -> ZF = 0
  • jz - Skok, jeśli zero (równe) -> ZF = 1
  • jg - Skok, jeśli większy -> ZF = 0 and SF = OF
  • (itp...)

Przykład (edytowany dla zwięzłości) Skompilowany z$ gcc -m32 -S -masm=intel test.c

    if (a < b) {
        // Do something 1
    }

Kompiluje do:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jge     .L2                          ; jump if a is >= b
    ; Do something 1
.L2:

I

    if (a <= b) {
        // Do something 2
    }

Kompiluje do:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jg      .L5                          ; jump if a is > b
    ; Do something 2
.L5:

Tak więc jedyną różnicą między nimi jest instrukcja jgkontra jgeinstrukcja. Obie zajmie tyle samo czasu.

Chciałbym odnieść się do komentarza, że ​​nic nie wskazuje na to, że różne instrukcje skoków zajmują tyle samo czasu. Odpowiedź na to pytanie jest nieco trudna, ale oto, co mogę dać: w Zestawie instrukcji Intel wszystkie są zgrupowane w ramach jednej wspólnej instrukcji Jcc(Przeskocz, jeśli warunek jest spełniony). Ta sama grupa została utworzona razem w Podręczniku optymalizacji , w Dodatku C. Opóźnienie i przepustowość.

Opóźnienie - liczba cykli zegara wymaganych przez rdzeń wykonawczy do wykonania wszystkich mikroprocesorów tworzących instrukcję.

Przepustowość - liczba cykli zegara wymaganych do oczekiwania, zanim porty wydające będą mogły ponownie zaakceptować tę samą instrukcję. W przypadku wielu instrukcji przepustowość instrukcji może być znacznie mniejsza niż jej opóźnienie

Wartości dla Jcc:

      Latency   Throughput
Jcc     N/A        0.5

z następującym przypisem Jcc:

7) Wybór instrukcji skoku warunkowego powinien opierać się na zaleceniu z sekcji 3.4.1, „Optymalizacja przewidywania rozgałęzień”, aby poprawić przewidywalność rozgałęzień. Po pomyślnym przewidywaniu rozgałęzień opóźnienie jccwynosi zero.

Zatem nic w dokumentach Intela nigdy nie traktuje jednej Jccinstrukcji inaczej niż inne.

Jeśli zastanowimy się nad rzeczywistym zespołem obwodów zastosowanym do wykonania instrukcji, można założyć, że na różnych bitach będą proste bramki ORAZ / OR EFLAGS, aby ustalić, czy warunki są spełnione. Nie ma zatem powodu, aby instrukcja testująca dwa bity zajmowała więcej lub mniej czasu niż jedna testująca tylko jeden (ignorowanie opóźnienia propagacji bramki, które jest znacznie krótsze niż okres zegara).

Edycja: zmiennoprzecinkowy

Odnosi się to również do zmiennoprzecinkowego x87: (Prawie taki sam kod jak powyżej, ale z doublezamiast int.)

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS
        fstp    st(0)
        seta    al                     ; Set al if above (CF=0 and ZF=0).
        test    al, al
        je      .L2
        ; Do something 1
.L2:

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; (same thing as above)
        fstp    st(0)
        setae   al                     ; Set al if above or equal (CF=0).
        test    al, al
        je      .L5
        ; Do something 2
.L5:
        leave
        ret

Historycznie (mówimy o latach 80. i wczesnych 90.) istniało kilka architektur, w których było to prawdą. Podstawowym problemem jest to, że porównanie liczb całkowitych jest z natury implementowane poprzez odejmowanie liczb całkowitych. Powoduje to następujące przypadki.

Comparison     Subtraction
----------     -----------
A < B      --> A - B < 0
A = B      --> A - B = 0
A > B      --> A - B > 0

Teraz, kiedy A < Bodejmowanie musi pożyczyć wysoki bit, aby odejmowanie było poprawne, tak samo jak nosisz i pożyczasz podczas dodawania i odejmowania ręcznie. Ten „pożyczony” bit był zwykle nazywany bitem przenoszenia i byłby testowany przez instrukcję rozgałęzienia. Drugi bit zwany bitem zerowym byłby ustawiony, gdyby odejmowanie było identyczne zero, co sugeruje równość.

Zazwyczaj były co najmniej dwie instrukcje rozgałęzienia warunkowego, jedno do rozgałęzienia na bicie przenoszenia i jedno na bicie zerowym.

Teraz, aby przejść do sedna sprawy, rozszerzmy poprzednią tabelę, aby uwzględnić wyniki przenoszenia i zero bitów.

Comparison     Subtraction  Carry Bit  Zero Bit
----------     -----------  ---------  --------
A < B      --> A - B < 0    0          0
A = B      --> A - B = 0    1          1
A > B      --> A - B > 0    1          0

Tak więc implementacja rozgałęzienia dla A < Bmoże być wykonana w jednej instrukcji, ponieważ bit przenoszenia jest wyraźny tylko w tym przypadku, to znaczy

;; Implementation of "if (A < B) goto address;"
cmp  A, B          ;; compare A to B
bcz  address       ;; Branch if Carry is Zero to the new address

Ale jeśli chcemy dokonać porównania mniejszego lub równego, musimy wykonać dodatkową kontrolę flagi zerowej, aby uchwycić przypadek równości.

;; Implementation of "if (A <= B) goto address;"
cmp A, B           ;; compare A to B
bcz address        ;; branch if A < B
bzs address        ;; also, Branch if the Zero bit is Set

Tak więc na niektórych komputerach użycie porównania „mniej niż” może zaoszczędzić jedną instrukcję maszyny . Było to istotne w erze szybkości procesora poniżej megaherca i stosunku prędkości procesora do pamięci 1: 1, ale dzisiaj jest to prawie zupełnie nieistotne.

Zakładając, że mówimy o wewnętrznych typach liczb całkowitych, nie ma możliwości, aby jeden był szybszy od drugiego. Są oczywiście semantycznie identyczne. Oboje proszą kompilator, aby zrobił dokładnie to samo. Tylko strasznie uszkodzony kompilator wygenerowałby gorszy kod dla jednego z nich.

Jeśli nie było pewne platforma gdzie <był szybszy niż <=w przypadku prostych typów całkowitych, kompilator powinien zawsze przekształcić <=się <na stałe. Każdy kompilator, który nie byłby po prostu złym kompilatorem (dla tej platformy).

Widzę, że żadne nie jest szybsze. Kompilator generuje ten sam kod maszynowy dla każdego warunku z inną wartością.

if(a < 901)
cmpl  $900, -4(%rbp)
jg .L2

if(a <=901)
cmpl  $901, -4(%rbp)
jg .L3

Mój przykład ifpochodzi z GCC na platformie x86_64 w systemie Linux.

Autorzy kompilatorów to całkiem sprytni ludzie, którzy myślą o tych rzeczach i wielu innych z nas uważa to za coś oczywistego.

Zauważyłem, że jeśli nie jest to stała, to w obu przypadkach generowany jest ten sam kod maszynowy.

int b;
if(a < b)
cmpl  -4(%rbp), %eax
jge   .L2

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3

W przypadku kodu zmiennoprzecinkowego porównanie <= może rzeczywiście być wolniejsze (według jednej instrukcji), nawet w nowoczesnych architekturach. Oto pierwsza funkcja:

int compare_strict(double a, double b) { return a < b; }

W PowerPC najpierw wykonuje porównanie zmiennoprzecinkowe (które aktualizuje crrejestr warunków), następnie przenosi rejestr warunków do GPR, przesuwa bit „porównywany mniej niż” na miejsce, a następnie wraca. Wymaga czterech instrukcji.

Teraz rozważ tę funkcję zamiast:

int compare_loose(double a, double b) { return a <= b; }

Wymaga to takiej samej pracy jak compare_strict powyżej, ale teraz są dwa elementy zainteresowania: „był mniejszy niż” i „był równy”. Wymaga to dodatkowej instrukcji ( cror- rejestr bitowy OR), aby połączyć te dwa bity w jeden. compare_looseWymaga więc pięciu instrukcji, a compare_strictczterech.

Możesz pomyśleć, że kompilator może zoptymalizować drugą funkcję w następujący sposób:

int compare_loose(double a, double b) { return ! (a > b); }

Jednak będzie to niepoprawnie obsługiwać NaN. NaN1 <= NaN2i NaN1 > NaN2musimy zarówno ocenić na fałsz.

Być może autor tej nienazwanej książki przeczytał, że a > 0biegnie szybciej a >= 1i uważa, że ​​to prawda.

Ale dzieje się tak dlatego, że a 0jest zaangażowane (ponieważ CMPmoże, w zależności od architektury, zastąpić np. OR), A nie z powodu <.

Przynajmniej, gdyby było to prawdą, kompilator mógłby w prosty sposób zoptymalizować <= b do! (A> b), a więc nawet gdyby samo porównanie było w rzeczywistości wolniejsze, przy wszystkich najbardziej naiwnych kompilatorach nie zauważyłbyś różnicy .

Mają tę samą prędkość. Może w jakiejś specjalnej architekturze to, co powiedział, jest słuszne, ale przynajmniej w rodzinie x86 wiem, że są takie same. Ponieważ w tym celu CPU wykona odejmowanie (a - b), a następnie sprawdzi flagi rejestru flag. Dwa bity tego rejestru nazywane są ZF (flaga zerowa) i SF (flaga znaku) i odbywa się to w jednym cyklu, ponieważ zrobi to za pomocą jednej operacji maski.

Byłoby to wysoce zależne od podstawowej architektury, do której skompilowano C. Niektóre procesory i architektury mogą mieć wyraźne instrukcje dla równości lub mniejszej i równej, które wykonują się w różnej liczbie cykli.

Byłoby to jednak dość niezwykłe, ponieważ kompilator mógłby go obejść, co czyni go nieistotnym.

TL; DR odpowiedź

W przypadku większości kombinacji architektury, kompilatora i języka nie będzie to szybsze.

Pełna odpowiedź

Inne odpowiedzi koncentrowały się na architekturze x86 i nie znam architektury ARM (którą wydaje się twój przykładowy asembler) wystarczająco dobrze, aby komentować konkretnie wygenerowany kod, ale jest to przykład mikrooptymalizacji, która jest bardzo architekturą specyficzne i równie prawdopodobne, że będzie antyoptymalizacją, jak optymalizacją .

Jako taki zasugerowałbym, że ten rodzaj mikrooptymalizacji jest przykładem programowania kultowego ładunku, a nie najlepszą praktyką inżynierii oprogramowania.

Prawdopodobnie istnieją pewne architektury, w których jest to optymalizacja, ale znam przynajmniej jedną architekturę, w której może być odwrotnie. Czcigodna architektura Transputera zawierała instrukcje kodu maszynowego tylko dla wartości równej i większej lub równej , więc wszystkie porównania musiały być zbudowane z tych prymitywów.

Nawet wtedy, w prawie wszystkich przypadkach, kompilator mógł zamówić instrukcje oceny w taki sposób, że w praktyce żadne porównanie nie miało żadnej przewagi nad innymi. W najgorszym przypadku może być konieczne dodanie instrukcji odwrotnej (REV), aby zamienić dwie górne pozycje na stosie operandów . Była to instrukcja jednobajtowa, której uruchomienie wymagało jednego cyklu, więc miało najmniejszy możliwy narzut.

To, czy taka mikrooptymalizacja jest optymalizacją czy antyoptymalizacją, zależy od konkretnej architektury, której używasz, więc zazwyczaj złym pomysłem jest przyzwyczajenie się do stosowania mikrooptymalizacji specyficznych dla architektury, w przeciwnym razie instynktownie użyj jednego, gdy jest to niewłaściwe, a wygląda na to, że właśnie to zaleca książka, którą czytasz.

Różnica nie powinna być zauważalna, nawet jeśli istnieje. Poza tym w praktyce będziesz musiał wykonać dodatkową akcję a + 1lub a - 1sprawić, by warunek się utrzymał, chyba że będziesz używał magicznych stałych, co jest bardzo złą praktyką pod każdym względem.

Można powiedzieć, że wiersz jest poprawny w większości języków skryptowych, ponieważ dodatkowy znak powoduje nieco wolniejsze przetwarzanie kodu. Jednak, jak wskazała najwyższa odpowiedź, nie powinno to mieć żadnego wpływu na C ++, a wszystko, co dzieje się z językiem skryptowym, prawdopodobnie nie dotyczy optymalizacji.

Kiedy pisałem tę odpowiedź, szukałem tylko w tytule pytanie o <vs <w ogóle, a nie na przykład specyficzna stałej a < 901vs. a <= 900. Wiele kompilatorów zawsze zmniejsza wielkość stałych poprzez konwersję między <i <=, np. Ponieważ operand bezpośredni x86 ma krótsze 1-bajtowe kodowanie dla -128..127.

W przypadku ARM, a zwłaszcza AArch64, możliwość kodowania w trybie natychmiastowym zależy od możliwości obrócenia wąskiego pola w dowolne miejsce w słowie. Więc cmp w0, #0x00f000byłoby encodeable, natomiast cmp w0, #0x00effffnie może być. Zatem reguła make-it-mniejsza dla porównania vs. stała czasowa kompilacji nie zawsze dotyczy AArch64.

<vs. <= ogólnie, w tym dla warunków zmiennych w czasie wykonywania

W języku asemblera na większości maszyn porównanie dla <=ma taki sam koszt jak dla porównania <. Odnosi się to do tego, czy rozgałęziasz się na nim, booleanizujesz go, aby utworzyć liczbę całkowitą 0/1, czy też używasz go jako predykatu dla operacji wybierania bez rozgałęzień (takiej jak x86 CMOV). Pozostałe odpowiedzi dotyczyły tylko tej części pytania.

Ale to pytanie dotyczy operatorów C ++, danych wejściowych do optymalizatora. Zwykle oba są równie wydajne; rada zawarta w książce wydaje się całkowicie nieprawdziwa, ponieważ kompilatory zawsze mogą przekształcić porównania, które implementują w asm. Ale istnieje co najmniej jeden wyjątek, w którym użycie <=może przypadkowo stworzyć coś, czego kompilator nie może zoptymalizować.

Jako stan pętli, istnieją przypadki, gdy <=jest jakościowo różna od <gdy zatrzymuje kompilator dowodzi, że pętla jest nieskończona. Może to mieć dużą różnicę, wyłączając automatyczną wektoryzację.

Niepodpisane przepełnienie jest dobrze zdefiniowane jako zawijanie bazy-2, w przeciwieństwie do podpisanego przepełnienia (UB). Liczniki pętli podpisanych są na ogół bezpieczne przed kompilatorami, które optymalizują się w oparciu o UB z przepełnieniem podpisu: ++i <= sizenie zawsze: w końcu stanie się fałszywy. ( Co każdy programista C powinien wiedzieć o nieokreślonym zachowaniu )

void foo(unsigned size) {
    unsigned upper_bound = size - 1;  // or any calculation that could produce UINT_MAX
    for(unsigned i=0 ; i <= upper_bound ; i++)
        ...

Kompilatory mogą optymalizować tylko w taki sposób, aby zachować (zdefiniowane i prawnie obserwowalne) zachowanie źródła C ++ dla wszystkich możliwych wartości wejściowych , z wyjątkiem tych, które prowadzą do nieokreślonego zachowania.

(Prosty i <= sizerównież stworzyłby problem, ale pomyślałem, że obliczenie górnej granicy było bardziej realistycznym przykładem przypadkowego wprowadzenia możliwości nieskończonej pętli dla danych wejściowych, których nie obchodzi, ale które kompilator musi wziąć pod uwagę.)

W takim przypadku size=0prowadzi do upper_bound=UINT_MAXi i <= UINT_MAXzawsze jest prawdą. Ta pętla jest więc nieskończona size=0, a kompilator musi to szanować, nawet jeśli jako programista prawdopodobnie nigdy nie zamierzasz przekazać size = 0. Jeśli kompilator może wprowadzić tę funkcję do programu wywołującego, w którym może udowodnić, że rozmiar = 0 jest niemożliwy, to świetnie, może zoptymalizować tak, jak mógłby i < size.

Asm like if(!size) skip the loop; do{...}while(--size);to jeden z normalnie wydajnych sposobów optymalizacji for( i<size )pętli, jeśli rzeczywista wartość inie jest potrzebna w pętli ( dlaczego pętle są zawsze kompilowane w stylu „do ... while” (skok z tyłu)? ).

Ale to robi {}, chociaż nie może być nieskończone: jeśli zostanie wprowadzone size==0, otrzymamy 2 ^ iteracje. ( Iteracja po wszystkich liczbach całkowitych bez znaku w pętli for C umożliwia wyrażenie pętli nad wszystkimi liczbami całkowitymi bez znaku, w tym zerem, ale nie jest to łatwe bez flagi przeniesienia tak, jak w asm.)

Ponieważ możliwe jest obejście licznika pętli, nowoczesne kompilatory często po prostu „poddają się” i nie optymalizują prawie tak agresywnie.

Przykład: suma liczb całkowitych od 1 do n

Korzystanie i <= nz rozpoznawania idiomów klanu bez znaku , który optymalizuje sum(1 .. n)pętle z zamkniętą formą opartą na n * (n+1) / 2formule Gaussa .

unsigned sum_1_to_n_finite(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i < n+1 ; ++i)
        total += i;
    return total;
}

x86-64 asm z clang7.0 i gcc8.2 w eksploratorze kompilatorów Godbolt

 # clang7.0 -O3 closed-form
    cmp     edi, -1       # n passed in EDI: x86-64 System V calling convention
    je      .LBB1_1       # if (n == UINT_MAX) return 0;  // C++ loop runs 0 times
          # else fall through into the closed-form calc
    mov     ecx, edi         # zero-extend n into RCX
    lea     eax, [rdi - 1]   # n-1
    imul    rax, rcx         # n * (n-1)             # 64-bit
    shr     rax              # n * (n-1) / 2
    add     eax, edi         # n + (stuff / 2) = n * (n+1) / 2   # truncated to 32-bit
    ret          # computed without possible overflow of the product before right shifting
.LBB1_1:
    xor     eax, eax
    ret

Ale w przypadku wersji naiwnej po prostu dostajemy głupią pętlę od clang.

unsigned sum_1_to_n_naive(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i<=n ; ++i)
        total += i;
    return total;
}

# clang7.0 -O3
sum_1_to_n(unsigned int):
    xor     ecx, ecx           # i = 0
    xor     eax, eax           # retval = 0
.LBB0_1:                       # do {
    add     eax, ecx             # retval += i
    add     ecx, 1               # ++1
    cmp     ecx, edi
    jbe     .LBB0_1            # } while( i<n );
    ret

GCC nie używa formy zamkniętej w żaden sposób, więc wybór warunku pętli tak naprawdę nie zaszkodzi ; automatycznie wektoryzuje z dodaniem liczb całkowitych SIMD, uruchamiając 4 iwartości równolegle w elementach rejestru XMM.

# "naive" inner loop
.L3:
    add     eax, 1       # do {
    paddd   xmm0, xmm1    # vect_total_4.6, vect_vec_iv_.5
    paddd   xmm1, xmm2    # vect_vec_iv_.5, tmp114
    cmp     edx, eax      # bnd.1, ivtmp.14     # bound and induction-variable tmp, I think.
    ja      .L3 #,       # }while( n > i )

 "finite" inner loop
  # before the loop:
  # xmm0 = 0 = totals
  # xmm1 = {0,1,2,3} = i
  # xmm2 = set1_epi32(4)
 .L13:                # do {
    add     eax, 1       # i++
    paddd   xmm0, xmm1    # total[0..3] += i[0..3]
    paddd   xmm1, xmm2    # i[0..3] += 4
    cmp     eax, edx
    jne     .L13      # }while( i != upper_limit );

     then horizontal sum xmm0
     and peeled cleanup for the last n%3 iterations, or something.

Ma również zwykłą pętlę skalarną, która, jak sądzę, wykorzystuje do bardzo małych ni / lub do nieskończonej pętli.

BTW, obie te pętle marnują instrukcję (i kupę w procesorach z rodziny Sandybridge) narzutu pętli. sub eax,1/ jnzzamiast add eax,1/ cmp / jcc byłoby bardziej wydajne. 1 uop zamiast 2 (po makro-fuzji sub / jcc lub cmp / jcc). Kod po obu pętlach bezwarunkowo zapisuje EAX, więc nie używa końcowej wartości licznika pętli.

Tylko jeśli ludzie, którzy stworzyli komputery, mają złe logiki boolowskie. Które nie powinny być.

Każde porównanie ( >= <= > <) można wykonać z tą samą prędkością.

Każde porównanie to tylko odjęcie (różnica) i sprawdzenie, czy jest dodatnie / ujemne.
(Jeśli msbjest ustawiony, liczba jest ujemna)

Jak sprawdzić a >= b? Sub a-b >= 0Sprawdź, czy a-bjest dodatnia.
Jak sprawdzić a <= b? Sub 0 <= b-aSprawdź, czy b-ajest dodatnia.
Jak sprawdzić a < b? Sub a-b < 0Sprawdź, czy a-bjest ujemna.
Jak sprawdzić a > b? Sub 0 > b-aSprawdź, czy b-ajest ujemna.

Mówiąc najprościej, komputer może po prostu zrobić to pod maską dla danej operacji:

a >= b== msb(a-b)==0
a <= b== msb(b-a)==0
a > b== msb(b-a)==1
a < b==msb(a-b)==1

i oczywiście komputer nie będzie faktycznie trzeba zrobić ==0albo ==1albo.
bo ==0może po prostu odwrócić msbobwód.

W każdym razie z pewnością nie a >= bzostałyby obliczone jako a>b || a==blol