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ą.
c++
performance
assembly
relational-operators
wścibski
źródło
źródło
<
jest dwa razy szybsze niż pisanie<=
.Odpowiedzi:
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:
test
lubcmp
instrukcja, która ustawiaEFLAGS
Jcc
instrukcja (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
Przykład (edytowany dla zwięzłości) Skompilowany z
$ gcc -m32 -S -masm=intel test.c
Kompiluje do:
I
Kompiluje do:
Tak więc jedyną różnicą między nimi jest instrukcja
jg
kontrajge
instrukcja. 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ść.Wartości dla
Jcc
:z następującym przypisem
Jcc
:Zatem nic w dokumentach Intela nigdy nie traktuje jednej
Jcc
instrukcji 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
double
zamiastint
.)źródło
jg
ijnle
są tą samą instrukcją7F
:-)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.
Teraz, kiedy
A < B
odejmowanie 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.
Tak więc implementacja rozgałęzienia dla
A < B
może być wykonana w jednej instrukcji, ponieważ bit przenoszenia jest wyraźny tylko w tym przypadku, to znaczyAle jeśli chcemy dokonać porównania mniejszego lub równego, musimy wykonać dodatkową kontrolę flagi zerowej, aby uchwycić przypadek równości.
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.
źródło
jge
, które testują zarówno flagę zero, jak i flagi znak / noś.<=
test może być realizowany w jednej instrukcji z wymiany argumentów i testowania dlanot <
(odpowiednik>=
) Jest to pożądane<=
z zamienionych argumentów:cmp B,A; bcs addr
. OtoZakł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).źródło
<
też<=
prędkości, dopóki kompilator nie zdecyduje, jaką prędkość będzie mieć. Jest to bardzo prosta optymalizacja dla kompilatorów, jeśli weźmie się pod uwagę, że generalnie już wykonują optymalizację martwego kodu, optymalizację wywołania ogona, podnoszenie pętli (i czasami rozwijanie), automatyczne równoległe wykonywanie różnych pętli itp. ... Po co marnować czas na rozważanie przedwczesnych optymalizacji ? Uruchom prototyp, profiluj go, aby określić, gdzie leżą najważniejsze optymalizacje, wykonaj te optymalizacje w kolejności według znaczenia i ponownie profiluj po drodze, aby zmierzyć postęp ...(a < C)
na(a <= C-1)
(dla niektórych stałychC
) powoduje,C
że trudniej jest zakodować w zestawie instrukcji. Na przykład, zestaw instrukcji może być w stanie reprezentować podpisane stałe od -127 do 128 w zwartej formie w porównaniu, ale stałe poza tym zakresem muszą być ładowane przy użyciu dłuższego, wolniejszego kodowania lub całkowicie innej instrukcji. Tak więc porównanie(a < -127)
może nie mieć prostej transformacji.a > 127
tego,a > 128
ponieważ nie masz wyboru, korzystasz z tego, czego potrzebujesz. Porównujemya > 127
doa >= 128
, które nie mogą wymagać innego kodowania ani różnych instrukcji, ponieważ mają tę samą tabelę prawdy. Każde kodowanie jednego jest równie kodowaniem drugiego.<=
się<
na stałe”. O ile mi wiadomo, ta transformacja obejmuje zmianę stałej. Np.a <= 42
Jest kompilowany,a < 43
ponieważ<
jest szybszy. W niektórych przypadkach taka transformacja nie byłaby owocna, ponieważ nowa stała może wymagać większej lub wolniejszej instrukcji. Oczywiściea > 127
ia >= 128
są równoważne i kompilator powinien zakodować obie formy w (samo) najszybszy sposób, ale to nie jest sprzeczne z tym, co powiedziałem.Widzę, że żadne nie jest szybsze. Kompilator generuje ten sam kod maszynowy dla każdego warunku z inną wartością.
Mój przykład
if
pochodzi 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.
źródło
if(a <=900)
aby pokazać, że generuje dokładnie taki sam asm :)W przypadku kodu zmiennoprzecinkowego porównanie <= może rzeczywiście być wolniejsze (według jednej instrukcji), nawet w nowoczesnych architekturach. Oto pierwsza funkcja:
W PowerPC najpierw wykonuje porównanie zmiennoprzecinkowe (które aktualizuje
cr
rejestr 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:
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_loose
Wymaga więc pięciu instrukcji, acompare_strict
czterech.Możesz pomyśleć, że kompilator może zoptymalizować drugą funkcję w następujący sposób:
Jednak będzie to niepoprawnie obsługiwać NaN.
NaN1 <= NaN2
iNaN1 > NaN2
musimy zarówno ocenić na fałsz.źródło
fucomip
ustawia ZF i CF.cr
jest równoważny z flagami takimi jakZF
iCF
na x86. (Chociaż CR jest bardziej elastyczny). To, o czym mówi plakat, przenosi wynik do GPR: który przyjmuje dwie instrukcje na PowerPC, ale x86 ma instrukcję warunkowego ruchu.Być może autor tej nienazwanej książki przeczytał, że
a > 0
biegnie szybcieja >= 1
i uważa, że to prawda.Ale dzieje się tak dlatego, że a
0
jest zaangażowane (ponieważCMP
może, w zależności od architektury, zastąpić np.OR
), A nie z powodu<
.źródło
(a >= 1)
aby działał wolniej niż(a > 0)
, ponieważ ten pierwszy może być w prosty sposób przekształcony w drugi przez optymalizator ..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 .
źródło
NOT
jest po prostu wykonany przez inną instrukcję (je
vs.jne
)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.
źródło
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.
źródło
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ódło
Różnica nie powinna być zauważalna, nawet jeśli istnieje. Poza tym w praktyce będziesz musiał wykonać dodatkową akcję
a + 1
luba - 1
sprawić, by warunek się utrzymał, chyba że będziesz używał magicznych stałych, co jest bardzo złą praktyką pod każdym względem.źródło
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.
źródło
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 < 901
vs.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, #0x00f000
byłoby encodeable, natomiastcmp w0, #0x00effff
nie 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 <= size
nie zawsze: w końcu stanie się fałszywy. ( Co każdy programista C powinien wiedzieć o nieokreślonym zachowaniu )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 <= size
ró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=0
prowadzi doupper_bound=UINT_MAX
ii <= UINT_MAX
zawsze jest prawdą. Ta pętla jest więc nieskończonasize=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łbyi < size
.Asm like
if(!size) skip the loop;
do{...}while(--size);
to jeden z normalnie wydajnych sposobów optymalizacjifor( i<size )
pętli, jeśli rzeczywista wartośći
nie 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 <= n
z rozpoznawania idiomów klanu bez znaku , który optymalizujesum(1 .. n)
pętle z zamkniętą formą opartą nan * (n+1) / 2
formule Gaussa .x86-64 asm z clang7.0 i gcc8.2 w eksploratorze kompilatorów Godbolt
Ale w przypadku wersji naiwnej po prostu dostajemy głupią pętlę od clang.
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
i
wartości równolegle w elementach rejestru XMM.Ma również zwykłą pętlę skalarną, która, jak sądzę, wykorzystuje do bardzo małych
n
i / 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
/jnz
zamiastadd 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.źródło
<
lub<=
. Ale na pewnotest ecx,ecx
/bt eax, 3
/jbe
przeskoczy, jeśli ustawiony jest ZF (ecx == 0) lub jeśli ustawiony jest CF (bit 3 EAX == 1), powodując częściowe zatrzymanie flagi na większości procesorów, ponieważ czytane flagi nie wszystkie pochodzą z ostatniej instrukcji, aby napisać dowolne flagi. W przypadku rodziny Sandybridge tak naprawdę nie zwleka, wystarczy wstawić scalający się element.cmp
/test
napisz wszystkie flagi, alebt
pozostawia ZF niezmodyfikowany. felixcloutier.com/x86/btTylko 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
msb
jest ustawiony, liczba jest ujemna)Jak sprawdzić
a >= b
? Suba-b >= 0
Sprawdź, czya-b
jest dodatnia.Jak sprawdzić
a <= b
? Sub0 <= b-a
Sprawdź, czyb-a
jest dodatnia.Jak sprawdzić
a < b
? Suba-b < 0
Sprawdź, czya-b
jest ujemna.Jak sprawdzić
a > b
? Sub0 > b-a
Sprawdź, czyb-a
jest 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ć
==0
albo==1
albo.bo
==0
może po prostu odwrócićmsb
obwód.W każdym razie z pewnością nie
a >= b
zostałyby obliczone jakoa>b || a==b
lolźródło