Countdown in for-Schleifen

Gibt es nur eine richtige Methode der looping rückwärts über eine vorzeichenlose Zähler:

for( i = n; i-- > 0; )
{
    //Use i as normal here
}

Gibt es einen trick hier, für den letzten loop iteration haben Sie i = 1 an den Anfang der Schleife, ich-- > 0 geht, denn 1 > 0, dann i = 0 in der Schleife. Für die nächste iteration i-- > 0 schlägt fehl, da i == 0, so spielt es keine Rolle, dass die postfix-Dekrement rollte über den Ladentisch.

Nicht sehr offensichtlich, ich weiß.

Überprüfen, um zu sehen, ob eine Zahl null ist, kann schneller und effizienter als ein Vergleich. Aber dies ist die Art von Mikro-Optimierung, die Sie wirklich sollten sich keine sorgen machen - ein paar Taktzyklen wird stark in den Schatten gestellt, die von fast jedem anderen perf Problem.

Auf x86:

dec eax
jnz Foo

Statt:

inc eax
cmp eax, 15
jl Foo

Damit Sie "gelesen", dass couting unten ist effizienter? Ich finde das sehr schwer zu glauben, es sei denn, Sie zeigen mir einige profiler-Ergebnisse und den code. Ich es kaufen kann, unter gewissen Umständen, aber im Allgemeinen Fall nicht. Scheint mir wie ein klassischer Fall von vorzeitiger Optimierung.

Ihren Kommentar zu "register int i" ist auch sehr aufschlussreich. Heute, der compiler weiß immer besser als Sie, wie zu reservieren registriert. Kümmern Sie sich nicht mit mit der register-Schlüsselwort, es sei denn, Sie haben profiliert Ihr code.

Es hat nichts zu tun mit dem zählen bis oder unten. Was kann man schneller zählen gegen null. Michael ' s Antwort zeigt, warum — x86 bietet Ihnen einen Vergleich mit null als eine implizite Nebeneffekt viele Anweisungen, so, nachdem Sie passen Sie Ihre Konter, die Sie gerade Zweig basierend auf dem Ergebnis zu tun, anstatt einen expliziten Vergleich. (Vielleicht sind andere Architekturen auch machen; ich weiß es nicht.)

Borland-Pascal-Compiler sind berüchtigt dafür, dass die Durchführung der Optimierung. Der compiler wandelt diesen code:

for i := x to y do
  foo(i);

in eine interne Repräsentation eher an diese:

tmp := Succ(y - x);
i := x;
while tmp > 0 do begin
  foo(i);
  Inc(i);
  Dec(tmp);
end;

(Sage ich, berüchtigt nicht, weil die Optimierung wirkt sich auf das Ergebnis der Schleife, aber da der debugger zeigt die counter-variable falsch. Wenn der Programmierer prüft i, kann der debugger den Wert anzuzeigen, der tmp statt, verursacht kein Ende der Verwirrung und Panik für die Programmierer, die denken, dass Ihre loops laufen rückwärts.)

Die Idee ist, dass selbst mit dem extra - Inc oder Dec Unterricht, es ist immer noch ein Netto-Gewinn, in Bezug auf die Ausführung der Zeit, über das tun ein expliziter Vergleich. , Ob Sie tatsächlich bemerken, die Differenz steht zur Debatte.

Aber beachten Sie, dass die Umwandlung ist etwas, was der compiler tun würde automatisch, basierend auf, ob Sie es als die transformation lohnt. Ist der compiler in der Regel besser auf das optimieren von code, als Sie sind, so don ' T verbringen zu viel Aufwand konkurrieren mit ihm.

Du sowieso gebeten, über C++, Pascal. C++ "for" - Schleifen sind nicht ganz so leicht anzuwenden, dass die Optimierung als Pascal "for" - Schleifen sind da die Grenzen von Pascal-Schleifen werden immer vollständig berechnet, bevor die Schleife ausgeführt wird, in der Erwägung, dass C++ - Schleifen manchmal hängt die Stopp-Bedingung und die Schleife Inhalt. C++ - Compiler tun müssen, eine gewisse Menge der statischen Analyse, um zu bestimmen, ob ein bestimmtes Schleife passen könnte, die die Anforderungen für die Art der transformation Pascal-Schleifen qualifizieren sich für bedingungslos. Wenn der C++ compiler ist die Analyse, dann könnte es nicht eine ähnliche transformation.

Gibt es nichts hindert Sie schreiben Ihre loops, die Weg auf Ihre eigenen:

for (unsigned i = 0, tmp = domain; tmp > 0; ++i, --tmp)
  array[i] = do stuff

Tun, dass könnte machen Sie Ihren code schneller laufen. Wie ich schon sagte, bevor, obwohl, werden Sie wahrscheinlich nicht bemerken. Die größeren Kosten, die Sie bezahlen, indem Sie manuell anordnen Schleifen wie, dass ist, dass Ihr code nicht mehr folgt etablierten Idiome. Deine Schleife ist eine stinknormale "for" - Schleife, aber es nicht mehr sieht wie — es hat zwei Variablen, Sie laufen in entgegengesetzte Richtungen, und einer von Ihnen ist nicht einmal in der Schleife Körper — also wer Lesen Ihren code (auch Sie, eine Woche, einen Monat oder ein Jahr ab jetzt, wenn Sie vergessen haben, die "Optimierung", die Sie hofften, zu erreichen) verbringen müssen zusätzlichen Aufwand erweist sich, dass die Schleife ist in der Tat eine ordentliche Schleife im Unglück.

(Haben Sie bemerkt, dass mein code oben verwendet unsigned Variablen ohne Gefahr der Umwicklung bei null? Mit zwei getrennten Variablen erlaubt.)

Drei Dinge zum mitnehmen aus all dem:

1. Lass den optimizer seinen job tun; es ist besser als Sie sind.
2. Machen ordentlichen code Aussehen gewöhnlichen, so dass der spezielle code, der nicht im Wettbewerb um Aufmerksamkeit zu bekommen von Leuten, überprüfung, debugging, oder Sie beibehalten.
3. Nicht etwas Phantasie in den Namen der Leistung, bis die Tests und profiling zeigen, dass es notwendig ist.

Schwer zu sagen, mit Angaben, aber... reverse-array, und der count down?

In einigen später arm-cores, Dekrementieren und vergleichen dauert nur einer einzigen Instruktion. Dies macht Dekrementieren Schleifen effizienter als die Inkrementierung lieben.

Ich weiß nicht, warum es nicht eine Inkrement-compare-Anweisung auch.

Ich bin überrascht, dass dieser post gewählt wurde, -1, wenn es eine echte Frage.

Was zählt viel mehr als die Frage, ob Sie erhöhen oder verringern Sie Ihren counter ist, ob oder nicht Sie gehen, bis Speicher oder down memory. Die meisten caches sind optimiert für Speicher, nicht Arbeitsspeicher. Da der Speicher-Zugriffszeit ist der Engpass, dass die meisten Programme heute Gesicht, dies bedeutet, dass das ändern Sie Ihr Programm so, dass man mit dem Speicher kann zu einer Leistungssteigerung, auch wenn dies erfordert Vergleich der Zähler auf einen nicht-null-Wert. In einigen meiner Programme, ich sah eine signifikante Verbesserung in der Leistung, indem Sie meinen code zu gehen, bis Speicher statt es nach unten.

Skeptisch? Hier ist die Ausgabe, die ich bekam:

sum up   = 705046256
sum down = 705046256
Ave. Up Memory   = 4839 mus
Ave. Down Memory =  5552 mus
sum up   = inf
sum down = inf
Ave. Up Memory   = 18638 mus
Ave. Down Memory =  19053 mus

aus ausführen dieses Programms:

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

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 RAI, class T>
inline void sum_abs_up(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = first;
  do {
    sum += *it;
    it++;
  } while (it != one_past_last);
  total += sum;
}

template<class RAI, class T>
inline void sum_abs_down(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = one_past_last;
  do {
    it--;
    sum += *it;
  } while (it != first);
  total += sum;
}

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

int main() {
  std::size_t num_repititions = 1 << 10;
  {
  typedef int ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  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 << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  std::cout << "Ave. Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Ave. Down Memory =  "<< time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  }
  {
  typedef double ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  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 << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  std::cout << "Ave. Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Ave. Down Memory =  "<< time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  }
  return 0;
}

Beide sum_abs_up und sum_abs_down tun die gleiche Sache und sind zeitgesteuert, Sie gleichen Weg, nur mit dem Unterschied, dass sum_abs_up geht mit dem Speicher, während sum_abs_down geht down memory. Ich selbst pass vec durch Verweis so, dass beide Funktionen greifen auf die gleichen Speicherplätze. Dennoch sum_abs_up ist durchweg schneller als sum_abs_down. Geben Sie einen Lauf selbst (ich kompiliert es mit g++ -O3).

FYI vec_original ist es für Experimente, um es einfach für mich zu ändern sum_abs_up und sum_abs_down in einer Weise, die macht Sie zu verändern vec zwar nicht, dass diese änderungen wirken sich auf zukünftige Zeiten.

Es ist wichtig zu beachten, wie eng die Schleife, dass ich das timing ist. Wenn Sie einen loop, der Körper ist groß, dann ist es vermutlich egal, ob seine iterator geht nach oben oder unten Speicher, da die Zeit, die zum ausführen der schleifenrumpf wird wahrscheinlich komplett zu Dominieren. Es ist auch wichtig zu erwähnen, dass mit einigen seltenen Schleifen, werde sich das Gedächtnis ist manchmal schneller, als sich es. Aber auch mit solchen loops ist es nur selten der Fall, dass going up war immer langsamer als der Abstieg (im Gegensatz zu Schleifen, die gehen bis Speicher, welche sehr Häufig immer schneller als die entsprechende down-memory-loops; eine kleine Handvoll Zeiten waren Sie noch 40+% schneller).

Der Punkt ist, als eine Regel von Daumen, wenn Sie die Möglichkeit haben, wenn der schleifenrumpf ist klein, und wenn es gibt wenig Unterschied zwischen den loop zu gehen mit dem Speicher auf, anstatt nach unten, dann sollten Sie gehen Speicher.