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.