Ist es schneller herunterzuzählen als hochzuzählen?

Unser Informatiklehrer hat einmal gesagt, dass es aus irgendeinem Grund effizienter ist, herunterzuzählen als hochzuzählen. Wenn Sie zum Beispiel eine FOR-Schleife verwenden müssen und der Schleifenindex nicht irgendwo verwendet wird (wie das Drucken einer Zeile von N * auf den Bildschirm), meine ich diesen Code wie folgt:

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

ist besser als:

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

Ist es wirklich wahr? Und wenn ja, weiß jemand warum?

Ist es wirklich wahr? und wenn ja, weiß jemand warum?

In alten Zeiten, als Computer noch von Hand aus Quarzglas herausgeschlagen wurden, als 8-Bit-Mikrocontroller die Erde durchstreiften und Ihr Lehrer jung war (oder der Lehrer Ihres Lehrers jung war), gab es eine übliche Maschinenanweisung namens Dekrementieren und Überspringen wenn Null (DSZ). Hotshot-Assembly-Programmierer verwendeten diese Anweisung, um Schleifen zu implementieren. Spätere Maschinen erhielten schickere Anweisungen, aber es gab immer noch einige Prozessoren, bei denen es billiger war, etwas mit Null zu vergleichen, als mit irgendetwas anderem. (Dies gilt sogar für einige moderne RISC-Maschinen wie PPC oder SPARC, die ein ganzes Register so reservieren, dass es immer Null ist.)

NWas könnte also passieren , wenn Sie Ihre Schleifen so manipulieren, dass sie mit Null verglichen werden ?

• Sie können ein Register speichern
• Möglicherweise erhalten Sie eine Vergleichsanweisung mit einer kleineren Binärcodierung
• Wenn eine vorherige Anweisung ein Flag setzt (wahrscheinlich nur auf Computern der x86-Familie), benötigen Sie möglicherweise nicht einmal eine explizite Vergleichsanweisung

Sind diese Unterschiede wahrscheinlich Ergebnis in jeder messbaren Verbesserung auf reale Programmen auf einem modernen Out-of-Order - Prozessor? Sehr unwahrscheinlich. Tatsächlich wäre ich beeindruckt, wenn Sie selbst bei einem Mikrobenchmark eine messbare Verbesserung zeigen könnten.

Zusammenfassung: Ich schlage deinen Lehrer auf den Kopf! Sie sollten keine veralteten Pseudo-Fakten über das Organisieren von Schleifen lernen. Sie sollten lernen, dass das Wichtigste an Schleifen darin besteht, sicherzustellen, dass sie enden , korrekte Antworten liefern und leicht zu lesen sind . Ich wünschte, Ihr Lehrer würde sich auf das Wichtige konzentrieren und nicht auf die Mythologie.

Folgendes kann auf einigen Hardwarekomponenten passieren, je nachdem, was der Compiler über den Bereich der von Ihnen verwendeten Zahlen ableiten kann: Mit der Inkrementierungsschleife müssen Sie i<Njedes Mal die Schleife testen . Bei der dekrementierenden Version kann das Übertragsflag (als Nebeneffekt der Subtraktion gesetzt) ​​automatisch anzeigen, ob i>=0. Das spart einen Test pro Zeit rund um die Schleife.

In der Realität ist dieses Zeug auf moderner Pipeline-Prozessorhardware mit ziemlicher Sicherheit irrelevant, da es keine einfache 1-1-Zuordnung von Anweisungen zu Taktzyklen gibt. (Obwohl ich mir vorstellen könnte, dass es auftauchen würde, wenn Sie beispielsweise zeitlich genau abgestimmte Videosignale von einem Mikrocontroller erzeugen würden. Aber dann würden Sie trotzdem in Assemblersprache schreiben.)

Im Intel x86-Befehlssatz kann das Erstellen einer Schleife zum Herunterzählen auf Null normalerweise mit weniger Befehlen durchgeführt werden als eine Schleife, die bis zu einer Exit-Bedingung ungleich Null zählt. Insbesondere wird das ECX-Register traditionell als Schleifenzähler in x86 asm verwendet, und der Intel-Befehlssatz verfügt über einen speziellen jcxz-Sprungbefehl, der das ECX-Register auf Null testet und basierend auf dem Testergebnis springt.

Der Leistungsunterschied ist jedoch vernachlässigbar, es sei denn, Ihre Schleife reagiert bereits sehr empfindlich auf Taktzykluszählungen. Das Herunterzählen auf Null kann 4 oder 5 Taktzyklen pro Iteration der Schleife im Vergleich zum Hochzählen verkürzen. Es ist also eher eine Neuheit als eine nützliche Technik.

Außerdem sollte ein guter Optimierungs-Compiler heutzutage in der Lage sein, Ihren Quellcode für Aufwärtsschleifen in Maschinencode von Countdown bis Null umzuwandeln (abhängig davon, wie Sie die Schleifenindexvariable verwenden), sodass es wirklich keinen Grund gibt, Ihre Schleifen einzuschreiben seltsame Wege, um hier und da ein oder zwei Zyklen zu quetschen.

Ja..!!

Das Zählen von N bis 0 ist etwas schneller als das Zählen von 0 bis N in dem Sinne, wie die Hardware den Vergleich handhabt.

Beachten Sie den Vergleich in jeder Schleife

i>=0
i<N

Die meisten Prozessoren haben einen Vergleich mit dem Nullbefehl. Der erste wird also wie folgt in Maschinencode übersetzt:

1. Laden Sie i
2. Vergleichen und springen, wenn kleiner als oder gleich Null ist

Der zweite muss jedoch jedes Mal N aus dem Speicher laden

1. lade i
2. Last N.
3. Sub i und N.
4. Vergleichen und springen, wenn kleiner als oder gleich Null ist

Es liegt also nicht am Countdown oder Up. Aber daran, wie Ihr Code in Maschinencode übersetzt wird.

Das Zählen von 10 bis 100 ist also dasselbe wie das Zählen von Form 100 bis 10. Das
Zählen von i = 100 bis 0 ist jedoch schneller als von i = 0 bis 100 - in den meisten Fällen.
Und das Zählen von i = N bis 0 ist schneller als von i = 0 bis N.

• Beachten Sie, dass heutzutage Compiler diese Optimierung möglicherweise für Sie durchführen (wenn sie intelligent genug ist).
• Beachten Sie auch, dass die Pipeline Beladys anomalieähnlichen Effekt verursachen kann (kann nicht sicher sein, was besser sein wird).
• Endlich: Bitte beachten Sie, dass die 2 für Schleifen, die Sie präsentiert haben, nicht gleichwertig sind. Die ersten drucken noch eine * ....

Verwandte: Warum wird n ++ schneller ausgeführt als n = n + 1?

In C zur Psudo-Montage:

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

verwandelt sich in

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

während:

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

verwandelt sich in

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

Beachten Sie das Fehlen des Vergleichs in der zweiten Psudo-Baugruppe. Auf vielen Architekturen gibt es Flags, die durch arithmatische Operationen (Addieren, Subtrahieren, Multiplizieren, Dividieren, Inkrementieren, Dekrementieren) gesetzt werden und die Sie für Sprünge verwenden können. Diese geben Ihnen oft einen kostenlosen Vergleich des Ergebnisses der Operation mit 0. In der Tat auf vielen Architekturen

x = x - 0

ist semantisch dasselbe wie

compare x, 0

Außerdem könnte der Vergleich mit einer 10 in meinem Beispiel zu einem schlechteren Code führen. 10 müssen möglicherweise in einem Register leben. Wenn sie also knapp sind, kostet dies und kann zu zusätzlichem Code führen, um Dinge zu verschieben oder die 10 jedes Mal durch die Schleife neu zu laden.

Compiler können den Code manchmal neu anordnen, um dies auszunutzen. Dies ist jedoch häufig schwierig, da sie häufig nicht sicher sein können, ob das Umkehren der Richtung durch die Schleife semantisch äquivalent ist.

In diesem Fall schneller herunterzählen:

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

weil someObject.getAllObjects.size()am Anfang einmal ausgeführt wird.

Sicher, ein ähnliches Verhalten kann durch Aufrufen size()aus der Schleife erreicht werden, wie Peter erwähnte:

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

Ist es schneller herunterzuzählen als hochzuzählen?

Vielleicht. Aber weit mehr als 99% der Zeit spielt es keine Rolle, also sollten Sie den "vernünftigsten" Test zum Beenden der Schleife verwenden, und mit "vernünftig" meine ich, dass ein Leser die geringste Menge an Gedanken benötigt, um dies herauszufinden was die Schleife tut (einschließlich was sie zum Stoppen bringt). Passen Sie Ihren Code an das mentale (oder dokumentierte) Modell dessen an, was der Code tut.

Wenn die Schleife durch ein Array (oder eine Liste oder was auch immer) funktioniert, passt ein inkrementierender Zähler oft besser dazu, wie der Leser über die Funktionsweise der Schleife nachdenkt - codieren Sie Ihre Schleife auf diese Weise.

Wenn Sie jedoch einen Container mit NElementen durcharbeiten und die Elemente unterwegs entfernen, ist es möglicherweise kognitiver, den Zähler nach unten zu arbeiten.

Ein bisschen mehr Details zum 'Vielleicht' in der Antwort:

Es ist richtig, dass auf den meisten Architekturen das Testen auf eine Berechnung, die zu Null führt (oder von Null nach Negativ geht), keine explizite Testanweisung erfordert - das Ergebnis kann direkt überprüft werden. Wenn Sie testen möchten, ob eine Berechnung zu einer anderen Zahl führt, muss der Anweisungsstrom im Allgemeinen über eine explizite Anweisung verfügen, um diesen Wert zu testen. Insbesondere bei modernen CPUs wird durch diesen Test einem Schleifenkonstrukt normalerweise weniger zusätzliche Zeit als der Rauschpegel hinzugefügt. Insbesondere, wenn diese Schleife E / A ausführt.

Wenn Sie dagegen von Null herunterzählen und den Zähler beispielsweise als Array-Index verwenden, kann es sein, dass der Code gegen die Speicherarchitektur des Systems arbeitet. Speicherlesevorgänge führen häufig dazu, dass ein Cache nach vorne schaut. mehrere Speicherplätze nach dem aktuellen in Erwartung eines sequentiellen Lesens. Wenn Sie rückwärts durch den Speicher arbeiten, erwartet das Caching-System möglicherweise keine Lesevorgänge eines Speicherorts an einer niedrigeren Speicheradresse. In diesem Fall ist es möglich, dass das Zurückschleifen die Leistung beeinträchtigt. Wahrscheinlich würde ich die Schleife jedoch immer noch auf diese Weise codieren (solange die Leistung kein Problem darstellt), da die Korrektheit von größter Bedeutung ist und die Übereinstimmung des Codes mit einem Modell eine hervorragende Möglichkeit ist, die Korrektheit sicherzustellen. Falscher Code ist so unoptimiert wie möglich.

Daher würde ich den Rat des Professors eher vergessen (natürlich nicht bei seinem Test - Sie sollten im Klassenzimmer immer noch pragmatisch sein), es sei denn und bis die Leistung des Codes wirklich wichtig ist.

Auf einigen älteren CPUs gibt es Anweisungen wie DJNZ== "Dekrementieren und Springen, wenn nicht Null". Dies ermöglichte effiziente Schleifen, bei denen Sie einen anfänglichen Zählwert in ein Register geladen haben und dann eine Dekrementierungsschleife mit einem Befehl effektiv verwalten konnten. Wir sprechen hier jedoch von ISAs der 1980er Jahre - Ihr Lehrer ist ernsthaft außer Kontakt, wenn er der Meinung ist, dass diese "Faustregel" für moderne CPUs immer noch gilt.

Bob,

Erst wenn Sie Mikrooptimierungen durchführen, haben Sie das Handbuch für Ihre CPU zur Hand. Wenn Sie so etwas tun würden, müssten Sie diese Frage wahrscheinlich sowieso nicht stellen. :-) Aber dein Lehrer unterschreibt diese Idee offensichtlich nicht ....

In Ihrem Schleifenbeispiel sind 4 Dinge zu beachten:

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

• Vergleich

Der Vergleich ist (wie andere haben darauf hingewiesen) relevant zu bestimmten Prozessor - Architekturen . Es gibt mehr Prozessortypen als Windows-Prozessoren. Insbesondere könnte es eine Anweisung geben, die Vergleiche mit 0 vereinfacht und beschleunigt.

• Einstellung

In einigen Fällen ist das Einstellen nach oben oder unten schneller. Normalerweise wird ein guter Compiler es herausfinden und die Schleife wiederholen, wenn es möglich ist. Nicht alle Compiler sind jedoch gut.

• Schleifenkörper

Sie greifen mit putchar auf einen Systemaufruf zu. Das ist massiv langsam. Außerdem rendern Sie (indirekt) auf dem Bildschirm. Das ist noch langsamer. Denken Sie an ein Verhältnis von 1000: 1 oder mehr. In dieser Situation überwiegt der Schleifenkörper die Kosten für die Einstellung / den Vergleich der Schleife vollständig und vollständig.

• Caches

Ein Cache- und Speicherlayout kann einen großen Einfluss auf die Leistung haben. In dieser Situation spielt es keine Rolle. Wenn Sie jedoch auf ein Array zugreifen und eine optimale Leistung benötigen, müssen Sie untersuchen, wie Ihr Compiler und Ihr Prozessor Speicherzugriffe angeordnet haben, und Ihre Software optimieren, um das Beste daraus zu machen. Das Aktienbeispiel ist das in Bezug auf die Matrixmultiplikation angegebene.

Was viel wichtiger ist, als ob Sie Ihren Zähler erhöhen oder verringern, ist, ob Sie den Speicher erhöhen oder verringern. Die meisten Caches sind für die Speichererweiterung und nicht für die Speicherreduzierung optimiert. Da die Speicherzugriffszeit der Engpass ist, mit dem die meisten Programme heutzutage konfrontiert sind, bedeutet dies, dass das Ändern Ihres Programms so, dass Sie mehr Speicher benötigen, zu einer Leistungssteigerung führen kann, selbst wenn dies den Vergleich Ihres Zählers mit einem Wert ungleich Null erfordert. In einigen meiner Programme konnte ich eine deutliche Leistungsverbesserung feststellen, indem ich meinen Code so änderte, dass er den Speicher vergrößerte, anstatt ihn zu verkleinern.

Skeptisch? Schreiben Sie einfach ein Programm in Zeitschleifen, die den Speicher nach oben / unten verschieben. Hier ist die Ausgabe, die ich bekommen habe:

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

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

(wobei "mus" für Mikrosekunden steht) vom Ausführen dieses Programms:

#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;
}

Beide sum_abs_upund sum_abs_downtun dasselbe (summieren den Vektor der Zahlen) und werden auf die gleiche Weise zeitgesteuert, mit dem einzigen Unterschied, dass sum_abs_upder Speicher nach oben geht, während der Speicher sum_abs_downnach unten geht. Ich gehe sogar als vecReferenz durch, damit beide Funktionen auf die gleichen Speicherplätze zugreifen. Trotzdem sum_abs_upist durchweg schneller als sum_abs_down. Probieren Sie es selbst aus (ich habe es mit g ++ -O3 kompiliert).

Es ist wichtig zu beachten, wie eng die Schleife ist, die ich zeitlich festlege. Wenn der Körper einer Schleife groß ist, spielt es wahrscheinlich keine Rolle, ob der Iterator in den Speicher geht oder nicht, da die Zeit, die zum Ausführen des Körpers der Schleife benötigt wird, wahrscheinlich vollständig dominiert. Es ist auch wichtig zu erwähnen, dass bei einigen seltenen Schleifen das Herunterfahren des Speichers manchmal schneller ist als das Hochfahren. Aber selbst bei solchen Schleifen war es nie so, dass das Hochfahren des Speichers immer langsamer war als das Herunterfahren (im Gegensatz zu Schleifen mit kleinem Körper, die den Speicher hochfahren, für die häufig das Gegenteil der Fall ist; tatsächlich für eine kleine Handvoll von Schleifen I ' Nach dem geplanten Zeitpunkt betrug die Leistungssteigerung durch Speicheraufbau 40 +%.

Der Punkt ist, als Faustregel, wenn Sie die Option haben, wenn der Körper der Schleife klein ist und wenn es kaum einen Unterschied gibt, ob Ihre Schleife den Speicher erhöht oder verringert, sollten Sie den Speicher erhöhen.

Zu Ihrer Information vec_originalist zum Experimentieren da, um das Ändern zu vereinfachen sum_abs_upund so sum_abs_downzu gestalten, dass sie sich ändern, vecohne dass sich diese Änderungen auf zukünftige Timings auswirken. Ich empfehle dringend, mit sum_abs_upund zu spielen sum_abs_downund die Ergebnisse zu planen.

Verwenden Sie unabhängig von der Richtung immer das Präfixformular (++ i anstelle von i ++)!

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

oder

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

Erläuterung: http://www.eskimo.com/~scs/cclass/notes/sx7b.html

Außerdem kannst du schreiben

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

Aber ich würde erwarten, dass moderne Compiler genau diese Optimierungen durchführen können.

Es ist eine interessante Frage, aber aus praktischen Gründen halte ich es nicht für wichtig und macht eine Schleife nicht besser als die andere.

Laut dieser Wikipedia-Seite: Schaltsekunde : "... der Sonnentag wird jedes Jahrhundert um 1,7 ms länger, hauptsächlich aufgrund von Gezeitenreibung." Aber wenn Sie Tage bis zu Ihrem Geburtstag zählen, interessiert Sie dieser winzige Zeitunterschied wirklich?

Es ist wichtiger, dass der Quellcode leicht zu lesen und zu verstehen ist. Diese beiden Schleifen sind ein gutes Beispiel dafür, warum Lesbarkeit wichtig ist - sie werden nicht gleich oft wiederholt.

Ich würde wetten, dass die meisten Programmierer lesen (i = 0; i <N; i ++) und sofort verstehen, dass dies N-mal wiederholt wird. Eine Schleife von (i = 1; i <= N; i ++) ist für mich sowieso etwas weniger klar, und mit (i = N; i> 0; i--) muss ich einen Moment darüber nachdenken . Es ist am besten, wenn die Absicht des Codes direkt in das Gehirn gelangt, ohne dass darüber nachgedacht werden muss.

Seltsamerweise scheint es einen Unterschied zu geben. Zumindest in PHP. Betrachten Sie folgenden Benchmark:

<?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);

Ergebnisse sind interessant:

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

Wenn jemand weiß warum, wäre es schön zu wissen :)

BEARBEITEN : Die Ergebnisse sind auch dann gleich, wenn Sie nicht ab 0, sondern mit einem anderen beliebigen Wert zählen. Es gibt also wahrscheinlich nicht nur einen Vergleich mit Null, der einen Unterschied macht?

Es kann schneller sein.

Auf dem NIOS II-Prozessor, mit dem ich gerade arbeite, der traditionellen for-Schleife

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

produziert die Baugruppe:

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

Wenn wir herunterzählen

for(i=100;i--;)

Wir erhalten eine Baugruppe, die 2 Anweisungen weniger benötigt.

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

Wenn wir verschachtelte Schleifen haben, in denen die innere Schleife häufig ausgeführt wird, können wir einen messbaren Unterschied haben:

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

Wenn die innere Schleife wie oben geschrieben ist, beträgt die Ausführungszeit: 0,12199999999999999734 Sekunden. Wenn die innere Schleife auf herkömmliche Weise geschrieben wird, beträgt die Ausführungszeit: 0,17199999999999998623 Sekunden. Der Countdown der Schleife ist also etwa 30% schneller.

Aber: Dieser Test wurde mit deaktivierten GCC-Optimierungen durchgeführt. Wenn wir sie einschalten, ist der Compiler tatsächlich schlauer als diese handliche Optimierung und hält den Wert sogar während der gesamten Schleife in einem Register, und wir würden eine Assembly wie erhalten

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

In diesem speziellen Beispiel bemerkt der Compiler sogar, dass die Variable a nach der Ausführung der Schleife immer 1 ist, und überspringt die Schleifen insgesamt.

Ich habe jedoch festgestellt, dass der Compiler diese Optimierung manchmal nicht durchführen kann, wenn der Schleifenkörper komplex genug ist. Der sicherste Weg, um immer eine schnelle Schleifenausführung zu erhalten, ist das Schreiben von:

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

Dies funktioniert natürlich nur, wenn es keine Rolle spielt, dass die Schleife umgekehrt ausgeführt wird und wie Betamoo sagte, nur wenn Sie bis auf Null herunterzählen.

Was Ihr Lehrer gesagt hat, war eine schräge Aussage ohne viel Klarstellung. Es ist NICHT so, dass das Dekrementieren schneller ist als das Inkrementieren, aber Sie können mit dem Dekrementieren eine viel viel schnellere Schleife erstellen als mit dem Inkrementieren.

Ohne ausführlich darauf einzugehen, ohne einen Schleifenzähler usw. verwenden zu müssen - was unten zählt, ist nur die Geschwindigkeit und die Anzahl der Schleifen (nicht Null).

So implementieren die meisten Leute eine Schleife mit 10 Iterationen:

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

In 99% der Fälle ist dies alles, was man braucht, aber neben PHP, PYTHON und JavaScript gibt es die ganze Welt zeitkritischer Software (normalerweise eingebettet, Betriebssystem, Spiele usw.), in der CPU-Ticks wirklich wichtig sind. Schauen Sie sich also kurz den Assembler-Code an:

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

Nach der Kompilierung (ohne Optimierung) kann die kompilierte Version folgendermaßen aussehen (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:

Die gesamte Schleife besteht aus 8 Befehlen (26 Bytes). Darin - es gibt tatsächlich 6 Anweisungen (17 Bytes) mit 2 Zweigen. Ja, ja, ich weiß, dass es besser geht (es ist nur ein Beispiel).

Betrachten Sie nun dieses häufige Konstrukt, das häufig von eingebetteten Entwicklern geschrieben wird:

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

Es iteriert auch 10 Mal (ja, ich weiß, dass der Wert anders ist als der für for-Schleife gezeigte, aber wir kümmern uns hier um die Anzahl der Iterationen). Dies kann wie folgt zusammengefasst werden:

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 Anweisungen (18 Bytes) und nur ein Zweig. Tatsächlich gibt es 4 Befehle in der Schleife (11 Bytes).

Das Beste ist, dass einige CPUs (einschließlich x86 / x64-kompatibel) Anweisungen haben, die ein Register dekrementieren, das Ergebnis später mit Null vergleichen und eine Verzweigung durchführen können, wenn das Ergebnis von Null abweicht. Praktisch ALLE PC-CPUs implementieren diese Anweisung. Wenn Sie es verwenden, ist die Schleife eigentlich nur eine (ja eine) 2-Byte-Anweisung:

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

Muss ich erklären, was schneller ist?

Selbst wenn eine bestimmte CPU den obigen Befehl nicht implementiert, ist nur ein Dekrement gefolgt von einem bedingten Sprung erforderlich, wenn das Ergebnis des vorherigen Befehls zufällig Null ist.

Unabhängig von einigen Fällen, in denen Sie als Kommentar darauf hinweisen können, warum ich falsch liege usw. usw. Ich betone - JA, es ist von Vorteil, nach unten zu springen, wenn Sie wissen, wie, warum und wann.

PS. Ja, ich weiß, dass der kluge Compiler (mit der entsprechenden Optimierungsstufe) die Schleife (mit aufsteigendem Schleifenzähler) in do umschreibt, während sie für konstante Schleifeniterationen äquivalent ist ... (oder sie entrollt) ...

Nein, das stimmt nicht wirklich. Eine Situation, in der es schneller sein könnte, ist, wenn Sie andernfalls eine Funktion aufrufen würden, um die Grenzen während jeder Iteration einer Schleife zu überprüfen.

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

Aber wenn es weniger klar ist, es so zu machen, lohnt es sich nicht. In modernen Sprachen sollten Sie nach Möglichkeit ohnehin eine foreach-Schleife verwenden. Sie erwähnen ausdrücklich den Fall, in dem Sie eine foreach-Schleife verwenden sollten - wenn Sie den Index nicht benötigen.

Der Punkt ist, dass Sie beim Countdown nicht i >= 0separat zum Dekrementieren prüfen müssen i. Beobachten:

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

Sowohl der Vergleich als auch die Dekrementierung ikönnen in einem Ausdruck durchgeführt werden.

In anderen Antworten erfahren Sie, warum dies auf weniger x86-Anweisungen hinausläuft.

Ob es einen bedeutenden Unterschied in Ihrer Anwendung macht, hängt wohl davon ab, wie viele Schleifen Sie haben und wie tief sie verschachtelt sind. Aber für mich ist es genauso lesbar, es so zu machen, also mache ich es trotzdem.

Nun, ich denke du hattest genug Montagevorträge :) Ich möchte dir einen weiteren Grund für den Top-> Down-Ansatz vorstellen.

Der Grund, von oben zu gehen, ist sehr einfach. Im Hauptteil der Schleife können Sie versehentlich die Grenze ändern, was zu einem falschen Verhalten oder sogar zu einer nicht terminierenden Schleife führen kann.

Schauen Sie sich diesen kleinen Teil des Java-Codes an (die Sprache spielt aus diesem Grund keine Rolle):

    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);
    }

Mein Punkt ist also, dass Sie es vorziehen sollten, von oben nach unten zu gehen oder eine Konstante als Grenze zu haben.

Auf Assembler-Ebene ist eine Schleife, die bis Null herunterzählt, im Allgemeinen etwas schneller als eine Schleife, die bis zu einem bestimmten Wert zählt. Wenn das Ergebnis einer Berechnung gleich Null ist, setzen die meisten Prozessoren ein Null-Flag. Wenn das Subtrahieren von Eins einen Berechnungsumbruch nach Null bewirkt, ändert dies normalerweise das Übertragsflag (auf einigen Prozessoren wird es auf anderen gesetzt, es wird gelöscht), so dass der Vergleich mit Null im Wesentlichen kostenlos ist.

Dies gilt umso mehr, wenn die Anzahl der Iterationen keine Konstante, sondern eine Variable ist.

In trivialen Fällen kann der Compiler möglicherweise die Zählrichtung einer Schleife automatisch optimieren, in komplexeren Fällen kann es jedoch sein, dass der Programmierer weiß, dass die Richtung der Schleife für das Gesamtverhalten irrelevant ist, der Compiler dies jedoch nicht beweisen kann.