Czy odliczanie jest szybsze niż liczenie w górę?

Nasz nauczyciel informatyki powiedział kiedyś, że z jakiegoś powodu skuteczniej jest odliczać niż liczyć w górę. Na przykład, jeśli potrzebujesz użyć pętli FOR, a indeks pętli nie jest gdzieś używany (jak drukowanie linii N * na ekranie), mam na myśli ten kod:

for (i = N; i >= 0; i--)  
  putchar('*');  

jest lepszy niż:

for (i = 0; i < N; i++)  
  putchar('*');  

Czy to prawda? A jeśli tak, to czy ktoś wie dlaczego?

Czy to prawda? a jeśli tak, to czy ktoś wie dlaczego?

W dawnych czasach, kiedy komputery wciąż były ręcznie wyrywane ze stopionej krzemionki, kiedy 8-bitowe mikrokontrolery wędrowały po Ziemi i kiedy twój nauczyciel był młody (lub nauczyciel twojego nauczyciela był młody), istniała powszechna instrukcja maszynowa zwana dekrementacją i pomijaniem jeśli zero (DSZ). Programiści asemblera Hotshot używali tej instrukcji do implementowania pętli. Późniejsze maszyny otrzymały bardziej wymyślne instrukcje, ale wciąż było sporo procesorów, na których taniej było porównać coś z zerem niż porównać z czymkolwiek innym. (Jest to prawdą nawet w przypadku niektórych nowoczesnych maszyn RISC, takich jak PPC lub SPARC, które rezerwują cały rejestr na zawsze zero).

Jeśli więc skonfigurujesz pętle do porównywania z zerem zamiast zerem N, co się stanie?

• Możesz zapisać rejestr
• Możesz otrzymać instrukcję porównania z mniejszym kodowaniem binarnym
• Jeśli poprzednia instrukcja ustawia flagę (prawdopodobnie tylko na komputerach z rodziny x86), możesz nawet nie potrzebować wyraźnej instrukcji porównania

Czy te różnice prawdopodobnie spowodują jakąkolwiek wymierną poprawę w rzeczywistych programach na nowoczesnym, nieczynnym procesorze? Wysoce nieprawdopodobne. W rzeczywistości byłbym pod wrażeniem, gdybyś mógł wykazać wymierną poprawę nawet na mikroznakach.

Podsumowanie: Uderzyłem twojego nauczyciela po głowie! Nie powinieneś uczyć się przestarzałych pseudo-faktów o tym, jak organizować pętle. Powinieneś nauczyć się, że najważniejszą rzeczą w pętlach jest upewnienie się, że się kończą , dają prawidłowe odpowiedzi i są łatwe do odczytania . Chciałbym, żeby twój nauczyciel skupił się na ważnych rzeczach, a nie na mitologii.

Oto, co może się zdarzyć na jakimś sprzęcie, w zależności od tego, co kompilator może wywnioskować na temat zakresu liczb, których używasz: z pętlą inkrementującą musisz testować za i<Nkażdym razem wokół pętli. W przypadku wersji z dekrementacją flaga przeniesienia (ustawiona jako efekt uboczny odejmowania) może automatycznie powiedzieć, czyi>=0 . To oszczędza czas testu w pętli.

W rzeczywistości, na nowoczesnym sprzęcie z procesorami potokowymi, ta kwestia jest prawie na pewno nieistotna, ponieważ nie ma prostego mapowania 1-1 z instrukcji na cykle zegara. (Chociaż mógłbym sobie wyobrazić, że to nadchodzi, gdybyś robił takie rzeczy, jak generowanie precyzyjnie zsynchronizowanych sygnałów wideo z mikrokontrolera. Ale i tak pisałbyś w języku asemblera).

W zestawie instrukcji Intel x86 budowanie pętli do odliczania do zera można zwykle wykonać z mniejszą liczbą instrukcji niż pętla licząca do niezerowego warunku zakończenia. W szczególności rejestr ECX jest tradycyjnie używany jako licznik pętli w asm x86, a zestaw instrukcji Intela zawiera specjalną instrukcję skoku jcxz, która testuje rejestr ECX pod kątem zera i przeskakuje na podstawie wyniku testu.

Jednak różnica w wydajności będzie pomijalna, chyba że pętla jest już bardzo wrażliwa na zliczanie cykli zegara. Odliczanie do zera może skrócić o 4 lub 5 cykli zegara każdej iteracji pętli w porównaniu do zliczania w górę, więc jest to bardziej nowość niż użyteczna technika.

Ponadto dobry kompilator optymalizujący w dzisiejszych czasach powinien być w stanie przekonwertować kod źródłowy pętli zliczania w górę na kod maszynowy odliczający do zera (w zależności od tego, jak używasz zmiennej indeksu pętli), więc naprawdę nie ma powodu, aby zapisywać pętle w dziwne sposoby na wyciśnięcie cyklu lub dwóch tu i tam.

Tak..!!

Liczenie od N do 0 jest nieco szybsze niż liczenie od 0 do N w sensie tego, jak sprzęt poradzi sobie z porównaniem.

Zwróć uwagę na porównanie w każdej pętli

i>=0
i<N

Większość procesorów ma porównanie z instrukcją zerową, więc pierwsza z nich zostanie przetłumaczona na kod maszynowy jako:

1. Załaduj i
2. Porównaj i przeskocz, jeśli Mniejsze niż lub Równe zero

Ale drugi musi za każdym razem ładować pamięć z formularza N.

1. załaduj i
2. ładunek N
3. Sub i oraz N
4. Porównaj i przeskocz, jeśli Mniejsze niż lub Równe zero

Więc to nie z powodu odliczania w dół czy w górę ... Ale z powodu tego, jak twój kod zostanie przetłumaczony na kod maszynowy.

Więc liczenie od 10 do 100 to to samo, co liczenie od 100 do 10
Ale liczenie od i = 100 do 0 jest szybsze niż od i = 0 do 100 - w większości przypadków
I liczenie od i = N do 0 jest szybsze niż od i = 0 do N

• Pamiętaj, że obecnie kompilatory mogą wykonać tę optymalizację za Ciebie (jeśli jest wystarczająco inteligentna)
• Zauważ też, że rurociąg może wywołać efekt anomalii Belady'ego (nie można być pewnym, co będzie lepsze)
• Nareszcie: pamiętaj, że 2 pętle for, które przedstawiłeś, nie są równoważne ... pierwsze wypisuje jeszcze jedną * ....

Powiązane: Dlaczego n ++ działa szybciej niż n = n + 1?

W C do montażu psudo:

for (i = 0; i < 10; i++) {
    foo(i);
}

zamienia się w

    clear i
top_of_loop:
    call foo
    increment i
    compare 10, i
    jump_less top_of_loop

podczas:

for (i = 10; i >= 0; i--) {
    foo(i);
}

zamienia się w

    load i, 10
top_of_loop:
    call foo
    decrement i
    jump_not_neg top_of_loop

Zwróć uwagę na brak porównania w drugim montażu psudo. Na wielu architekturach istnieją flagi ustawiane przez operacje arytmatyczne (dodawanie, odejmowanie, mnożenie, dzielenie, zwiększanie, zmniejszanie), których można używać do skoków. Często dają one za darmo porównanie wyniku operacji z 0. W rzeczywistości na wielu architekturach

x = x - 0

jest semantycznie taka sama jak

compare x, 0

Również porównanie z 10 w moim przykładzie może spowodować gorszy kod. 10 może być zmuszonych do życia w rejestrze, więc jeśli ich brakuje, to kosztuje i może skutkować dodatkowym kodem do przenoszenia elementów lub ponownego ładowania 10 za każdym razem przez pętlę.

Kompilatory mogą czasami zmienić kolejność kodu, aby to wykorzystać, ale często jest to trudne, ponieważ często nie mogą mieć pewności, że odwrócenie kierunku w pętli jest semantycznie równoważne.

Odliczaj szybciej w takim przypadku:

for (i = someObject.getAllObjects.size(); i >= 0; i--) {…}

dlatego someObject.getAllObjects.size() wykonuje się raz na początku.

Jasne, podobne zachowanie można osiągnąć, wywołując size()pętlę, jak wspomniał Piotr:

size = someObject.getAllObjects.size();
for (i = 0; i < size; i++) {…}

Czy odliczanie jest szybsze niż w górę?

Może. Ale znacznie więcej niż 99% czasu nie ma to znaczenia, więc powinieneś użyć najbardziej `` rozsądnego '' testu na zakończenie pętli, a przez rozsądny rozumiem, że potrzeba najmniejszej ilości myśli czytelnika, aby dowiedzieć się co robi pętla (w tym co ją zatrzymuje). Dopasuj swój kod do mentalnego (lub udokumentowanego) modelu tego, co robi kod.

Jeśli pętla działa, przechodzi przez tablicę (lub listę lub cokolwiek innego), licznik zwiększający się często lepiej pasuje do tego, jak czytelnik może myśleć o tym, co robi pętla - zakoduj pętlę w ten sposób.

Ale jeśli pracujesz z kontenerem, który zawiera Nelementy, i usuwasz je po drodze, może mieć większy sens poznawczy, aby zmniejszyć licznik.

Nieco więcej szczegółów na temat „może” w odpowiedzi:

Prawdą jest, że na większości architektur testowanie obliczeń dających zero (lub przechodzące od zera do ujemnego) nie wymaga wyraźnej instrukcji testowej - wynik można sprawdzić bezpośrednio. Jeśli chcesz sprawdzić, czy wynikiem obliczenia jest jakaś inna liczba, strumień instrukcji będzie zazwyczaj musiał mieć jawną instrukcję do sprawdzenia tej wartości. Jednak, zwłaszcza w przypadku nowoczesnych procesorów, test ten zwykle dodaje mniej niż poziom szumu dodatkowego czasu do konstrukcji pętli. Szczególnie jeśli ta pętla wykonuje operacje we / wy.

Z drugiej strony, jeśli odliczasz od zera i używasz licznika jako indeksu tablicy, na przykład możesz znaleźć kod działający wbrew architekturze pamięci systemu - odczyty pamięci często powodują, że pamięć podręczna `` patrzy w przyszłość '' kilka miejsc pamięci poza bieżącą w oczekiwaniu na odczyt sekwencyjny. Jeśli pracujesz wstecz w pamięci, system buforowania może nie przewidzieć odczytów lokalizacji pamięci pod niższym adresem pamięci. W takim przypadku możliwe jest, że zapętlenie „do tyłu” może zaszkodzić wydajności. Jednak prawdopodobnie zakodowałbym pętlę w ten sposób (o ile wydajność nie stałaby się problemem), ponieważ poprawność jest najważniejsza, a dopasowanie kodu do modelu jest świetnym sposobem na zapewnienie poprawności. Nieprawidłowy kod jest tak niezoptymalizowany, jak tylko możesz.

Więc miałbym tendencję do zapominania o radach profesora (oczywiście nie na jego teście - w klasie nadal powinieneś być pragmatyczny), chyba że i dopóki wykonanie kodu naprawdę nie będzie miało znaczenia.

Na niektórych starszych procesorach są / były instrukcje takie jak DJNZ== "zmniejszaj i skacz, jeśli nie zero". Pozwoliło to na wydajne pętle, w których załadowano początkową wartość licznika do rejestru, a następnie można było efektywnie zarządzać pętlą dekrementacji za pomocą jednej instrukcji. Mówimy tu jednak o ISA z lat 80-tych - twój nauczyciel jest poważnie oderwany od kontaktu, jeśli uważa, że ​​ta „praktyczna zasada” nadal obowiązuje w przypadku nowoczesnych procesorów.

Pion,

Dopiero gdy wykonasz mikrooptymalizacje, w którym to momencie będziesz mieć pod ręką instrukcję obsługi swojego procesora. Co więcej, gdybyś robił takie rzeczy, prawdopodobnie i tak nie musiałbyś zadawać tego pytania. :-) Ale twój nauczyciel najwyraźniej nie zgadza się z tym pomysłem ....

W przykładzie pętli należy wziąć pod uwagę 4 kwestie:

for (i=N; 
 i>=0;             //thing 1
 i--)             //thing 2
{
  putchar('*');   //thing 3
}

• Porównanie

Porównanie jest (jak wskazywali inni) istotne dla poszczególnych architektur procesorów . Istnieje więcej typów procesorów niż te z systemem Windows. W szczególności może istnieć instrukcja, która upraszcza i przyspiesza porównania z 0.

• Dostosowanie

W niektórych przypadkach szybsza jest regulacja w górę lub w dół. Zwykle dobry kompilator to rozgryzie i jeśli to możliwe, powtórzy pętlę. Jednak nie wszystkie kompilatory są dobre.

• Pętla Body

Uzyskujesz dostęp do wywołania systemowego za pomocą putchar. To jest bardzo powolne. Dodatkowo renderujesz na ekranie (pośrednio). To jest jeszcze wolniejsze. Pomyśl o stosunku 1000: 1 lub więcej. W tej sytuacji, korpus pętli całkowicie i całkowicie przewyższa koszt dostosowania / porównania pętli.

• Pamięci podręczne

Pamięć podręczna i układ pamięci mogą mieć duży wpływ na wydajność. W tej sytuacji nie ma to znaczenia. Jeśli jednak korzystasz z macierzy i potrzebujesz optymalnej wydajności, należałoby zbadać, w jaki sposób Twój kompilator i procesor zapewniają dostęp do pamięci, i dostroić oprogramowanie, aby jak najlepiej to wykorzystać. Przykładem giełdy jest ten podany w odniesieniu do mnożenia macierzy.

O wiele ważniejsze niż to, czy zwiększasz, czy zmniejszasz licznik, jest to, czy zwiększasz lub zmniejszasz pamięć. Większość pamięci podręcznych jest zoptymalizowana pod kątem zwiększania pamięci, a nie jej wyłączania. Ponieważ czas dostępu do pamięci jest wąskim gardłem, z którym boryka się większość dzisiejszych programów, oznacza to, że zmiana programu w celu zwiększenia ilości pamięci może spowodować wzrost wydajności, nawet jeśli wymaga to porównania licznika z wartością niezerową. W niektórych moich programach zauważyłem znaczną poprawę wydajności, zmieniając kod tak, aby zwiększał pamięć, a nie ją zmniejszał.

Sceptyczny? Po prostu napisz program do pętli czasowych przechodzących w górę / w dół pamięci. Oto wynik, który otrzymałem:

Average Up Memory   = 4839 mus
Average Down Memory = 5552 mus

Average Up Memory   = 18638 mus
Average Down Memory = 19053 mus

(gdzie „mus” oznacza mikrosekundy) od uruchomienia tego programu:

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

//Sum all numbers going up memory.
template<class Iterator, class T>
inline void sum_abs_up(Iterator first, Iterator one_past_last, T &total) {
  T sum = 0;
  auto it = first;
  do {
    sum += *it;
    it++;
  } while (it != one_past_last);
  total += sum;
}

//Sum all numbers going down memory.
template<class Iterator, class T>
inline void sum_abs_down(Iterator first, Iterator one_past_last, T &total) {
  T sum = 0;
  auto it = one_past_last;
  do {
    it--;
    sum += *it;
  } while (it != first);
  total += sum;
}

//Time how long it takes to make num_repititions identical calls to sum_abs_down().
//We will divide this time by num_repitions to get the average time.
template<class T>
std::chrono::nanoseconds TimeDown(std::vector<T> &vec, const std::vector<T> &vec_original,
                                  std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_down(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

template<class T>
std::chrono::nanoseconds TimeUp(std::vector<T> &vec, const std::vector<T> &vec_original,
                                std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_up(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
  std::random_device rnd_device;
  std::mt19937 generator(rnd_device());
  std::uniform_int_distribution<T> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class Iterator>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) {
  std::random_device rnd_device;
  std::mt19937_64 generator(rnd_device());
  std::uniform_real_distribution<double> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class ValueType>
void TimeFunctions(std::size_t num_repititions, std::size_t vec_size = (1u << 24)) {
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(vec_size);

  FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
  const auto vec_original = vec;
  ValueType sum_up = 0, sum_down = 0;

  auto time_up   = TimeUp(vec, vec_original, num_repititions, sum_up).count();
  auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
  std::cout << "Average Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Average Down Memory = " << time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  return ;
}

int main() {
  std::size_t num_repititions = 1 << 10;
  TimeFunctions<int>(num_repititions);
  std::cout << '\n';
  TimeFunctions<double>(num_repititions);
  return 0;
}

Oba sum_abs_upi sum_abs_downrobią to samo (sumują wektor liczb) i są mierzone w ten sam sposób, z jedyną różnicą, że sum_abs_upzwiększa się pamięć, a sum_abs_downzmniejsza pamięć. Przechodzę nawet vecprzez odniesienie, aby obie funkcje miały dostęp do tych samych lokalizacji pamięci. Niemniej jednak sum_abs_upjest konsekwentnie szybszy niżsum_abs_down . Zrób to sam (skompilowałem to z g ++ -O3).

Ważne jest, aby zwrócić uwagę na to, jak ścisła jest pętla, którą mierzę. Jeśli ciało pętli jest duże, prawdopodobnie nie będzie miało znaczenia, czy jej iterator zwiększy, czy zmniejszy pamięć, ponieważ czas potrzebny do wykonania pętli prawdopodobnie całkowicie zdominuje. Należy również wspomnieć, że w przypadku niektórych rzadkich pętli, zmniejszenie pamięci jest czasami szybsze niż zwiększenie jej. Ale nawet przy takich pętlach nigdy nie było tak, że zwiększanie pamięci było zawsze wolniejsze niż schodzenie w dół (w przeciwieństwie do małych pętli, które przechodzą w górę pamięci, dla których często jest odwrotnie; w rzeczywistości dla małej garstki pętli I ' w określonym czasie wzrost wydajności poprzez zwiększenie pamięci wyniósł 40 +%).

Zasadniczo chodzi o to, że jeśli masz taką opcję, jeśli korpus pętli jest mały i jeśli istnieje niewielka różnica między wprowadzaniem pętli w górę pamięci, a nie w jej dół, powinieneś iść w górę pamięci.

FYI vec_originaljest po to, aby eksperymentować, aby ułatwić zmianę sum_abs_upi sum_abs_downw sposób, który sprawia, że ​​zmieniają się vec, nie pozwalając tym zmianom wpływać na przyszłe czasy. Gorąco polecam zabawy z sum_abs_upa sum_abs_downi rozrządu wyniki.

niezależnie od kierunku zawsze używaj prefiksu (++ i zamiast i ++)!

for (i=N; i>=0; --i)  

lub

for (i=0; i<N; ++i) 

Wyjaśnienie: http://www.eskimo.com/~scs/cclass/notes/sx7b.html

Ponadto możesz pisać

for (i=N; i; --i)  

Ale spodziewałbym się, że nowoczesne kompilatory będą w stanie wykonać dokładnie te optymalizacje.

To interesujące pytanie, ale ze względów praktycznych nie uważam, że jest ważne i nie czyni jednej pętli lepszej od drugiej.

Według tej strony Wikipedii: Sekunda przestępna , „... dzień słoneczny wydłuża się o 1,7 ms każdego stulecia, głównie z powodu tarcia pływowego”. Ale jeśli liczysz dni do swoich urodzin, czy naprawdę zależy ci na tej niewielkiej różnicy w czasie?

Ważniejsze jest, aby kod źródłowy był łatwy do odczytania i zrozumienia. Te dwie pętle są dobrym przykładem tego, dlaczego czytelność jest ważna - nie zapętlają się tyle samo razy.

Założę się, że większość programistów czyta (i = 0; i <N; i ++) i od razu rozumie, że to zapętla się N razy. Pętla (i = 1; i <= N; i ++), zresztą dla mnie, jest trochę mniej wyraźna, a przy (i = N; i> 0; i--) muszę się nad tym chwilę zastanowić . Najlepiej, jeśli intencja kodu trafi bezpośrednio do mózgu bez konieczności myślenia.

O dziwo, wygląda na to, że JEST różnica. Przynajmniej w PHP. Rozważ następujący punkt odniesienia:

<?php

print "<br>".PHP_VERSION;
$iter = 100000000;
$i=$t1=$t2=0;

$t1 = microtime(true);
for($i=0;$i<$iter;$i++){}
$t2 = microtime(true);
print '<br>$i++ : '.($t2-$t1);

$t1 = microtime(true);
for($i=$iter;$i>0;$i--){}
$t2 = microtime(true);
print '<br>$i-- : '.($t2-$t1);

$t1 = microtime(true);
for($i=0;$i<$iter;++$i){}
$t2 = microtime(true);
print '<br>++$i : '.($t2-$t1);

$t1 = microtime(true);
for($i=$iter;$i>0;--$i){}
$t2 = microtime(true);
print '<br>--$i : '.($t2-$t1);

Wyniki są interesujące:

PHP 5.2.13
$i++ : 8.8842368125916
$i-- : 8.1797409057617
++$i : 8.0271911621094
--$i : 7.1027431488037


PHP 5.3.1
$i++ : 8.9625310897827
$i-- : 8.5790238380432
++$i : 5.9647901058197
--$i : 5.4021768569946

Jeśli ktoś wie dlaczego, dobrze by było wiedzieć :)

EDYCJA : Wyniki są takie same, nawet jeśli nie zaczynasz liczyć od 0, ale innej arbitralnej wartości. Więc prawdopodobnie istnieje nie tylko porównanie do zera, które robi różnicę?

To może być szybciej.

Na procesorze NIOS II, z którym obecnie pracuję, tradycyjna pętla for

for(i=0;i<100;i++)

produkuje montaż:

ldw r2,-3340(fp) %load i to r2
addi r2,r2,1     %increase i by 1
stw r2,-3340(fp) %save value of i
ldw r2,-3340(fp) %load value again (???)
cmplti r2,r2,100 %compare if less than equal 100
bne r2,zero,0xa018 %jump

Jeśli odliczamy

for(i=100;i--;)

otrzymujemy zestaw, który potrzebuje 2 instrukcji mniej.

ldw r2,-3340(fp)
addi r3,r2,-1
stw r3,-3340(fp)
bne r2,zero,0xa01c

Jeśli mamy zagnieżdżone pętle, w których wewnętrzna pętla jest często wykonywana, możemy mieć wymierną różnicę:

int i,j,a=0;
for(i=100;i--;){
    for(j=10000;j--;){
        a = j+1;
    }
}

Jeśli pętla wewnętrzna jest zapisana jak powyżej, czas wykonania wynosi: 0,12199999999999999734 sekundy. Jeśli pętla wewnętrzna jest zapisana w tradycyjny sposób, czas wykonania wynosi: 0,17199999999999998623 sekundy. Tak więc odliczanie pętli jest około 30% szybsze.

Ale: ten test został wykonany z wyłączonymi wszystkimi optymalizacjami GCC. Jeśli je włączymy, kompilator jest w rzeczywistości mądrzejszy niż ta ręczna optymalizacja, a nawet zachowuje wartość w rejestrze przez całą pętlę i otrzymalibyśmy asembler podobny do

addi r2,r2,-1
bne r2,zero,0xa01c

W tym konkretnym przykładzie kompilator nawet zauważa, że ​​zmienna a zawsze będzie wynosić 1 po wykonaniu pętli i całkowicie pomija pętle.

Jednak doświadczyłem, że czasami, jeśli treść pętli jest wystarczająco złożona, kompilator nie jest w stanie wykonać tej optymalizacji, więc najbezpieczniejszym sposobem uzyskania szybkiego wykonania pętli jest napisanie:

register int i;
for(i=10000;i--;)
{ ... }

Oczywiście działa to tylko wtedy, gdy nie ma znaczenia, że ​​pętla jest wykonywana w odwrotnej kolejności i jak powiedział Betamoo, tylko wtedy , gdy liczysz do zera.

To, co powiedział twój nauczyciel, było jakimś ukośnym stwierdzeniem, bez większego wyjaśnienia. To NIE jest tak, że dekrementacja jest szybsza niż inkrementacja, ale możesz stworzyć dużo szybszą pętlę z dekrementacją niż z przyrostem.

Nie wdając się w to zbyt długo, bez potrzeby używania licznika pętli itp. - poniżej liczy się tylko prędkość i liczba pętli (niezerowa).

Oto jak większość ludzi implementuje pętlę z 10 iteracjami:

int i;
for (i = 0; i < 10; i++)
{
    //something here
}

W 99% przypadków jest to wszystko, czego możesz potrzebować, ale wraz z PHP, PYTHON, JavaScript istnieje cały świat oprogramowania krytycznego czasowo (zwykle wbudowane, system operacyjny, gry itp.), W których znaczniki procesora naprawdę mają znaczenie, więc spójrz krótko na kod asemblera:

int i;
for (i = 0; i < 10; i++)
{
    //something here
}

po kompilacji (bez optymalizacji) wersja skompilowana może wyglądać następująco (VS2015):

-------- C7 45 B0 00 00 00 00  mov         dword ptr [i],0  
-------- EB 09                 jmp         labelB 
labelA   8B 45 B0              mov         eax,dword ptr [i]  
-------- 83 C0 01              add         eax,1  
-------- 89 45 B0              mov         dword ptr [i],eax  
labelB   83 7D B0 0A           cmp         dword ptr [i],0Ah  
-------- 7D 02                 jge         out1 
-------- EB EF                 jmp         labelA  
out1:

Cała pętla to 8 instrukcji (26 bajtów). W nim - faktycznie jest 6 instrukcji (17 bajtów) z 2 gałęziami. Tak tak, wiem, że można to zrobić lepiej (to tylko przykład).

Rozważmy teraz tę częstą konstrukcję, którą często można znaleźć napisaną przez programistę embedded:

i = 10;
do
{
    //something here
} while (--i);

Iteruje również 10 razy (tak, wiem, że wartość i jest inna niż pokazana pętla for, ale tutaj zależy nam na liczbie iteracji). Można to skompilować w następujący sposób:

00074EBC C7 45 B0 01 00 00 00 mov         dword ptr [i],1  
00074EC3 8B 45 B0             mov         eax,dword ptr [i]  
00074EC6 83 E8 01             sub         eax,1  
00074EC9 89 45 B0             mov         dword ptr [i],eax  
00074ECC 75 F5                jne         main+0C3h (074EC3h)  

5 instrukcji (18 bajtów) i tylko jedna gałąź. Właściwie w pętli są 4 instrukcje (11 bajtów).

Najlepsze jest to, że niektóre procesory (w tym kompatybilne z x86 / x64) mają instrukcję, która może zmniejszyć rejestr, później porównać wynik z zerem i wykonać rozgałęzienie, jeśli wynik jest różny od zera. Praktycznie WSZYSTKIE procesory PC realizują tę instrukcję. Używając go, pętla jest w rzeczywistości tylko jedną (tak) 2-bajtową instrukcją:

00144ECE B9 0A 00 00 00       mov         ecx,0Ah  
label:
                          // something here
00144ED3 E2 FE                loop        label (0144ED3h)  // decrement ecx and jump to label if not zero

Czy muszę wyjaśniać, co jest szybsze?

Teraz, nawet jeśli dany procesor nie implementuje powyższej instrukcji, wszystko, czego wymaga do emulacji, jest to dekrementacja, po której następuje skok warunkowy, jeśli wynik poprzedniej instrukcji wynosi zero.

Więc niezależnie od niektórych przypadków, które możesz wskazać w komentarzu, dlaczego się mylę itp. PODKREŚLAJ - TAK, KORZYSTNE JEST PĘTLA W DÓŁ, ​​jeśli wiesz jak, dlaczego i kiedy.

PS. Tak, wiem, że mądry kompilator (z odpowiednim poziomem optymalizacji) przepisze pętlę for (z licznikiem pętli rosnącej) na do.., podczas gdy odpowiednik dla iteracji w pętli stałej ...

Nie, to nieprawda. Jedną z sytuacji, w której mogłoby to być szybsze, jest wywołanie funkcji w celu sprawdzenia granic podczas każdej iteracji pętli.

for(int i=myCollection.size(); i >= 0; i--)
{
   ...
}

Ale jeśli jest mniej jasne, aby zrobić to w ten sposób, nie warto. W nowoczesnych językach i tak powinieneś używać pętli foreach, jeśli to możliwe. W szczególności wspomina się o przypadku, w którym należy użyć pętli foreach - kiedy nie jest potrzebny indeks.

Chodzi o to, że podczas odliczania nie trzeba i >= 0osobno sprawdzać odliczania i. Przestrzegać:

for (i = 5; i--;) {
  alert(i);  // alert boxes showing 4, 3, 2, 1, 0
}

W ijednym wyrażeniu można wykonać zarówno porównanie, jak i dekrementację .

Zobacz inne odpowiedzi, dlaczego sprowadza się to do mniejszej liczby instrukcji x86.

Jeśli chodzi o to, czy robi to znaczącą różnicę w twojej aplikacji, myślę, że zależy to od tego, ile masz pętli i jak głęboko są one zagnieżdżone. Ale dla mnie robienie tego w ten sposób jest równie czytelne, więc i tak to robię.

Myślę, że miałeś dość wykładów montażowych :) Chciałbym przedstawić kolejny powód do podejścia odgórnego.

Powód, dla którego warto iść z góry jest bardzo prosty. W treści pętli możesz przypadkowo zmienić granicę, co może zakończyć się nieprawidłowym zachowaniem lub nawet niekończącą pętlą.

Spójrz na tę małą część kodu Javy (język nie ma znaczenia z tego powodu):

    System.out.println("top->down");
    int n = 999;
    for (int i = n; i >= 0; i--) {
        n++;
        System.out.println("i = " + i + "\t n = " + n);
    }
    System.out.println("bottom->up");
    n = 1;
    for (int i = 0; i < n; i++) {
        n++;
        System.out.println("i = " + i + "\t n = " + n);
    }

Chodzi mi więc o to, że powinieneś rozważyć preferowanie przechodzenia z góry na dół lub posiadanie stałej jako granicy.

Na poziomie asemblera pętla odliczająca do zera jest generalnie nieco szybsza niż pętla zliczająca do podanej wartości. Jeśli wynik obliczenia jest równy zero, większość procesorów ustawi flagę zero. Jeśli odjęcie jednego powoduje zawinięcie obliczenia wokół zera, zwykle zmienia flagę przeniesienia (na niektórych procesorach ustawi ją na innych, usuwając ją), więc porównanie z zerem jest zasadniczo bezpłatne.

Jest to jeszcze bardziej prawdziwe, gdy liczba iteracji nie jest stała, ale zmienna.

W trywialnych przypadkach kompilator może być w stanie automatycznie zoptymalizować kierunek zliczania pętli, ale w bardziej złożonych przypadkach może się zdarzyć, że programista wie, że kierunek pętli nie ma znaczenia dla ogólnego zachowania, ale kompilator nie może tego udowodnić.