Herunterzählen in for-Schleifen

https://stackoverflow.com/questions/804777

c++
for-loop

03-07-2019
|

Frage

Ich glaube, (von einigen Recherchen Lesung), dass in den Countdown for-Schleifen ist tatsächlich effizienter und schneller in der Laufzeit. Mein vollständiger Software-Code ist C ++

Im Moment habe ich dies:

for (i=0; i<domain; ++i) {

meine 'i' ist unsigned int resgister, 'Domain' auch ist unsigned int

in der for-Schleife i für den Gang durch ein Array verwendet wird, z.

array[i] = do stuff

Diese Umwandlung Verwirrungen rückwärts zu zählen, um die erwartete / korrekte Ausgabe meiner Routine.

Ich kann mich vorstellen, die Antwort ganz trivial zu sein, aber ich kann nicht meinen Kopf um es bekommen.

UPDATE: ‚tun Sachen‘ hängt nicht von früheren oder späteren Iteration. Die Berechnungen in der for-Schleife sind unabhängige für diese Iteration i. (Ich hoffe, das macht Sinn).

UPDATE: Um eine Laufzeit Speedup mit meiner for-Schleife zu erreichen, zähle ich nach unten und wenn ja, den unsigned Teil entfernen, wenn delcaring mein int, oder welche andere Methode

Bitte helfen.

Lösung

Ich bin Ihr rückwärts for-Schleife zu erraten sieht wie folgt aus:

for (i = domain - 1; i >= 0; --i) {

In diesem Fall, weil i ist unsigned , wird es immer größer oder gleich Null ist. Wenn Sie eine nicht signierte Variable dekrementieren, die gleich Null ist, wird es zu einer sehr großen Zahl umschlingen. Die Lösung ist entweder zu i unterzeichnet, oder ändern Sie die Bedingung in der for-Schleife wie folgt vor:

for (i = domain - 1; i >= 0 && i < domain; --i) {

Oder von domain zählt eher 1 als von domain - 1 0:

for (i = domain; i >= 1; --i) {
    array[i - 1] = ...; // notice you have to subtract 1 from i inside the loop now
}

Andere Tipps

Es gibt nur eine richtige Methode des Looping rückwärts einen unsigned Zähler mit:

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

Es gibt einen Trick, für die letzte Schleifeniterationslatenzzeit Sie i = 1 an der Spitze der Schleife haben, i--> 0 Pässe weil 1> 0, dann ist i = 0 in der Schleife. Auf der nächsten Iteration i--> 0 schlägt fehl, weil i == 0, so dass es keine Rolle spielt, dass die Postfix Abnahme außerbörslich gerollt.

Sehr nicht klar, ich weiß.

Das ist keine Antwort auf Ihr Problem, weil Sie ein Problem zu haben scheinen nicht.

Diese Art der Optimierung ist es völlig irrelevant und soll an den Compiler gelassen werden (wenn überhaupt getan).

Haben Sie profilieren Ihr Programm zu überprüfen, ob Ihre for-Schleife ein Engpass? Wenn nicht, dann müssen Sie nicht Zeit damit verbringen, über diese besorgniserregend. Umso mehr, mit „i“ als int „registrieren“, wie Sie schreiben, macht keinen wirklichen Sinn von Performance-Gesichtspunkten.

Auch ohne Ihr Problem Domain zu wissen, ich kann Ihnen garantieren, dass sowohl die Reverse-Looping-Verfahren und das „Register“ int Zähler wird vernachlässigbar Einfluss auf die Leistung Ihres Programms. Denken Sie daran, „Vorzeitige Optimierung ist die Wurzel aller Übel“.

Wie gesagt, besser ausgegebene Optimierungszeit auf Nachdenken über die gesamte Programmstruktur wäre, Datenstrukturen und Algorithmen verwendet, Ressourcennutzung usw.

Überprüfen Sie, ob eine Zahl Null ist schneller sein kann oder effizienter als ein Vergleich. Aber das ist die Art von Mikro-Optimierung sollten Sie wirklich keine Sorgen zu machen -. Ein paar Taktzyklen wird stark durch fast jede andere perf Ausgabe den Schatten gestellt werden

Auf x86:

dec eax
jnz Foo

Statt:

inc eax
cmp eax, 15
jl Foo

Wenn Sie einen anständigen Compiler haben, wird es optimieren „Hochzählen“ genauso effektiv wie „Herunterzählen“. Versuchen Sie einfach ein paar Benchmarks und Sie werden sehen.

So Sie „lesen“, dass couting unten effizienter ist? Ich finde das sehr schwer zu glauben, es sei denn, Sie mir einige Profiler Ergebnisse und den Code zeigen. Ich kann es unter Umständen kaufen, aber im allgemeinen Fall nicht. Scheint mir, wie dies ein klassischer Fall der vorzeitigen Optimierung ist.

Ihr Kommentar zu „registrieren int i“ auch sehr aufschlussreich ist. Heute weiß der Compiler immer besser als Sie, wie Register zuzuordnen. Kümmern Sie sich nicht mit mit dem Schlüsselwort register, wenn Sie Ihren Code profiliert haben.

Wenn Sie durch Datenstrukturen jeglicher Art sind Looping, haben Cache-Misses einen weit größeren Einfluss als die Richtung Sie gehen. Beschäftigen Sie sich mit dem größeren Bild von Speicherlayout und Algorithmusstruktur statt trivial Mikro-Optimierungen.

Es hat nichts mit dem Zählen bis oder unten zu tun. Was kann schneller zählt gegen Null . Michaels Antwort zeigt, warum - x86 Sie einen Vergleich mit Null als eine gibt implizite Nebenwirkung von vielen Anweisungen, so, nachdem Sie Ihren Zähler einstellen, die Sie gerade auf dem Ergebnis Zweig basiert, anstatt einen expliziten Vergleich zu tun. (Vielleicht andere Architekturen das auch tun;. Ich weiß nicht)

Borland Pascal Compiler sind berüchtigt für diese Optimierung durchführen. Der Compiler wandelt diesen Code:

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

in eine interne Darstellung eher so aus:

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

(ich sage notorisch nicht, weil die Optimierung der Ergebnisse der Schleife beeinflusst, sondern weil der Debugger die Zählervariable falsch anzeigt. Wenn der Programmierer i prüft, kann der Debugger den Wert von tmp Anzeige statt, so dass kein Ende der Verwirrung und Panik für Programmierer, die ihre Schleifen denken laufen rückwärts.)

Die Idee ist, dass selbst mit den zusätzlichen Inc oder Dec Anweisung, es ist immer noch ein Nettogewinn in Bezug auf die Laufzeit, über einen expliziten Vergleich zu tun. Ob tatsächlich kann Hinweis diese Differenz zur Debatte.

Beachten Sie aber, dass die Umwandlung etwas ist der Compiler tun würde automatisch , je nachdem, ob es die Transformation lohnenswert erachtet. Der Compiler ist in der Regel besser auf Code zu optimieren, als Sie sind, so verbringen Sie nicht zu viel Mühe mit ihm konkurrieren.

Wie auch immer, fragte Sie über C ++, nicht Pascal. C ++ „für“ Schleifen sind nicht ganz so einfach, dass die Optimierung als Pascal anzuwenden „für“ Schleifen sind, weil die Grenzen der Pascals Schleifen sind immer voll, bevor die Schleifendurchläufe berechnet, während C ++ Schleifen hängen manchmal auf dem Stoppzustand und die Schleife Inhalt. C ++ Compiler benötigt eine gewisse Menge an statischer Analyse zu tun, um zu bestimmen, ob eine gegebene Schleife, um die Anforderungen für die Art von Transformation passen könnte Pascal für bedingungslos Schleifen qualifizieren. Wenn der C ++ Compiler die Analyse der Fall ist, dann könnte es eine ähnliche Transformation tun.

Es gibt nichts mehr im Wege stehen zu schreiben Ihre Loops auf diese Weise auf eigene Faust:

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

, das zu tun könnte Code schneller laufen. Wie ich schon sagte, obwohl, werden Sie wahrscheinlich nicht bemerken. Je größer Kosten Sie durch manuelles Anordnen Loops so bezahlen, dass Ihr Code nicht mehr hergestellt Idiome folgt. Ihre Schleife ist ein stinknormale „für“ Schleife, aber es nicht mehr sieht wie ein - es zwei Variablen hat, sind sie in entgegengesetzten Richtungen zu zählen, und einer von ihnen ist nicht einmal in der verwendet Schleifenkörper - so jemand Ihren Code (einschließlich Sie, eine Woche, einen Monat oder ein Jahr ab jetzt, wenn Sie die „Optimierung“ vergessen haben Sie hatten gehofft, zu erreichen) lesen müssen zusätzliche Anstrengungen, um sich zu beweisen verbringen oder sich, dass die Schleife ist in der Tat eine gewöhnliche Schleife in der Verkleidung.

(Haben Sie bemerkt, dass mein Code über unsigned Variablen, ohne die Gefahr von Umwickeln auf Null verwendet? Die Verwendung von zwei separaten Variablen ermöglicht, dass.)

Drei Dinge wegzunehmen all dies:

Lassen Sie den Optimierer seine Arbeit tun; es ist im Großen und Ganzen besser darin, als Sie sind.
Erstellen gewöhnliche Code gewöhnliche aussehen, so dass der spezielle Code nicht zu konkurrieren hat die Aufmerksamkeit von Menschen zu bekommen Überprüfung, Debuggen oder der Unterhaltung.
Sie nichts tun Phantasie im Namen der Leistung bis zur Prüfung und Profilierung als erforderlich sein.

Sie können die folgende versuchen, die Compiler sehr effizient optimieren:

#define for_range(_type, _param, _A1, _B1) \
    for (_type _param = _A1, _finish = _B1,\
    _step = static_cast<_type>(2*(((int)_finish)>(int)_param)-1),\
    _stop = static_cast<_type>(((int)_finish)+(int)_step); _param != _stop; \
_param = static_cast<_type>(((int)_param)+(int)_step))

Jetzt können Sie es verwenden:

for_range (unsigned, i, 10,0)
{
    cout << "backwards i: " << i << endl;
}

for_range (char, c, 'z','a')
{
    cout << c << endl;
}

enum Count { zero, one, two, three }; 

for_range (Count, c, three, zero)
{
    cout << "backwards: " << c << endl;
}

Sie können in jede Richtung durchlaufen:

for_range (Count, c, zero, three)
{
    cout << "forward: " << c << endl;
}

Die Schleife

for_range (unsigned,i,b,a)
{
   // body of the loop
}

produzieren den folgenden Code:

 mov esi,b
L1:
;    body of the loop
   dec esi
   cmp esi,a-1
   jne L1

Hard mit Informationen zu sagen gegeben, aber ... Reverse Array und count down?

Jeremy Ruten Recht darauf hingewiesen, dass eine nicht signierte Schleifenzähler mit gefährlich ist. Es ist auch nicht erforderlich, soweit ich das beurteilen kann.

Andere haben auch die Gefahren der vorzeitigen Optimierung hingewiesen. Sie haben völlig Recht.

Mit dieser sagt, hier ist ein Stil, den ich verwenden, wenn eingebettete Systeme Programmierung vor vielen Jahren, wenn jedes Byte und jeder Zyklus zählen tun etwas. Diese Formen waren , die für mich von der jeweiligen CPUs und Compiler, die ich benutze, aber die Leistung kann variieren.

// Start out pointing to the last elem in array
pointer_to_array_elem_type p = array + (domain - 1);
for (int i = domain - 1; --i >= 0 ; ) {
     *p-- = (... whatever ...)
}

Diese Form Vorteil der Bedingung führt aus, die auf gesetzt sind einige Prozessoren nach arithmetischen Operationen - auf einigen Architekturen können die Abnahme und Prüfung für die Verzweigungsbedingung in einen einzigen Befehl kombiniert werden. Beachten Sie, dass predecrement (--i) verwendet, ist der Schlüssel hier -. Mit postdecrement (i--) hätte auch nicht funktioniert

Alternativ

// Start out pointing *beyond* the last elem in array
pointer_to_array_elem_type p = array + domain;
for (pointer_to_array_type p = array + domain; p - domain > 0 ; ) {
     *(--p) = (... whatever ...)
}

Diese zweite Form nutzt Zeiger (Adresse) Arithmetik. Ich sehe selten die Form (pointer - int) in diesen Tagen (aus gutem Grund), aber die Sprache gewährleistet, dass, wenn Sie einen int von einem Zeiger subtrahieren, der Zeiger um (int * sizeof (*pointer)) verringert wird.

Ich werde noch einmal betonen, dass, ob diese Formen sind ein Gewinn für Sie auf der CPU und Compiler ab, die Sie verwenden. Sie hat mir gute Dienste auf Motorola 6809 und 68000-Architekturen.

In einem späteren Arm Kern, Abnahme- und vergleichen dauert nur eine einzige Anweisung. Dies macht Dekrementieren Schleifen effizienter als diejenigen erhöht wird.

Ich weiß nicht, warum Anweisung gibt keine Erhöhungs-Vergleich ist auch.

Ich bin überrascht, dass dieser Beitrag gewählt wurde -1, wenn es ein wahres Problem ist.

Jeder hier konzentriert sich auf die Leistung. Es gibt tatsächlich einen logischen Grund, gegen Null zu durchlaufen, die in sauberem Code führen kann.

Iterieren über das letzte Element zunächst praktisch, wenn Sie durch den Austausch mit dem Ende des Arrays ungültig Elemente löschen. Für schlechte Elemente nicht bis zum Ende benachbart wir in die Endposition tauschen können, verringern Sie das Ende des Arrays gebunden, und Iterieren halten. Wenn Sie gegen Ende zu durchlaufen wurden dann mit dem Ende tauscht in Swapping schlecht für schlecht führen könnte. Durch Iterieren Ende auf 0 wissen wir, dass das Element am Ende des Arrays ist bereits für diese Iteration gültig nachgewiesen worden.

Zur weiteren Erläuterung ...

If:

Sie schlechte Elemente löschen, indem Sie mit einem Ende des Arrays Swapping und Ändern der Array-Grenzen, die schlechten Elemente auszuschließen.

Dann offensichtlich:

Sie würden tauschen mit einem guten Elemente das heißt eine, die bereits in dieser Iteration getestet wurde.

So bedeutet dies:

Wenn wir von den variablen iterieren weg gebunden haben gut bewährt dann Elemente zwischen den Variablen gebunden und den aktuellen Iteration Zeigern worden. Ob die Iteration Zeiger bekommt ++ oder - keine Rolle spielt. Entscheidend ist, dass wir weg von der Variable sind Iterieren gebunden, so dass wir wissen, dass die Elemente neben ihm gut sind.

So endlich:

Iterieren auf 0 ermöglicht es uns, nur eine Variable zu verwenden, um die Feldgrenzen darzustellen. Ob dies zählt, ist eine persönliche Entscheidung zwischen Ihnen und Ihrem Compiler.

Was als viel mehr zählt, ob Sie erhöhen oder Ihre Zähler abnimmt, ob Sie Speicher oder unten Speicher gehst nach oben. Die meisten Caches werden für steigen Speicher optimiert, nicht nach unten Speicher. Da die Speicherzugriffszeit die Engpass, dass die meisten Programme heute Gesicht ist, bedeutet dies, dass Ihr Programm zu ändern, so dass Sie Speicher steigen auch in einer Leistungssteigerung führen kann, wenn dies Ihren Zähler auf einen Wert ungleich Null erfordert verglichen wird. Speicher zu gehen, anstatt sie von unten in einigen meiner Programme, sah ich eine deutliche Verbesserung der Performance durch meinen Code zu ändern.

Skeptical? Hier ist die Ausgabe, die ich habe:

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

Ausführung von diesem Programm:

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

Sowohl sum_abs_up und sum_abs_down das gleiche tun, und sie sind mit dem einzigen Unterschied gleiche Weise zeitlich gesteuert, dass sum_abs_up ist nach oben gehen Speicher während sum_abs_down Speicher nach unten geht. Ich selbst vec durch Verweis übergeben, so dass beide Funktionen der gleichen Speicherplatz zugreifen. Dennoch ist sum_abs_up konsequent schneller als sum_abs_down. Geben Sie ihm einen Lauf selbst (ich es mit g ++ kompiliert O3).

Zu Ihrer Information ist vec_original es zum Experimentieren, um es einfach für mich sum_abs_up und sum_abs_down in einer Art und Weise zu ändern, die sie verändern vec macht zwar nicht diese Änderungen ermöglichen Zukunft Timings zu beeinflussen.

Es ist wichtig zu beachten, wie eng die Schleife, die ich bin Timing ist. Wenn der Körper eine Schleife groß ist dann wahrscheinlich wird es keine Rolle, ob sein Iterator nach oben oder unten Speichern geht, da die Zeit es braucht, um die Schleife Körper wird wahrscheinlich vollständig dominiert auszuführen. Außerdem ist es wichtig, mit einigen seltenen Schleifen zu erwähnen, dass, Speicher going down ist manchmal schneller, als es nach oben. Aber auch mit solchen Schleifen ist es nur selten der Fall, dass bis zu gehen, war immer langsamer, als ich nach unten (im Gegensatz zu Schleifen, die Speicher steigen, was sehr oft ist immer schneller als die entsprechenden Abwärts Memory Loops, eine kleine Handvoll Zeiten waren sie sogar 40 +% schneller).

Der Punkt ist, als Faustregel gilt, wenn Sie die Möglichkeit haben, wenn die körpereigene Schleife klein ist, und wenn es wenig Unterschied der Schleife Speicher es statt nach unten nach oben zwischen hat, dann sollten Sie Speicher nach oben.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow