Ich glaube (aus einigen Recherchen), dass das Herunterzählen in for-Schleifen tatsächlich effizienter und schneller in der Laufzeit ist. Mein vollständiger Softwarecode ist C ++
Ich habe momentan folgendes:
%Vor%mein 'i' ist unsigniertes resgister int, auch 'domain' ist unsigned int
in der for-Schleife i wird verwendet, um durch ein Array zu gehen, z.B.
%Vor%dies zu Countdown umwandeln vermasselt die erwartete / korrekte Ausgabe meiner Routine.
Ich kann mir vorstellen, dass die Antwort ziemlich trivial ist, aber ich kann es nicht verstehen.
UPDATE: 'do stuff' hängt nicht von vorherigen oder späteren Iterationen ab. Die Berechnungen innerhalb der for-Schleife sind für diese Iteration von i unabhängig. (Ich hoffe, das macht Sinn).
UPDATE: Um eine Laufzeitbeschleunigung mit meiner for-Schleife zu erreichen, zähle ich runter und wenn ja, entferne den nicht-signierten Teil, wenn ich meinen int dekliniere, oder welche andere Methode?
Bitte helfen Sie.
Ich vermute, dass Ihre Rückwärts-For-Schleife folgendermaßen aussieht:
%Vor% Da i in diesem Fall unsigned ist, ist immer größer oder gleich null. Wenn Sie eine vorzeichenlose Variable dekrementieren, die gleich Null ist, wird sie auf eine sehr große Zahl umbrochen. Die Lösung besteht darin, i signed zu machen oder die Bedingung in der for-Schleife wie folgt zu ändern:
Oder zählen Sie von domain bis 1 statt von domain - 1 bis 0 :
Es gibt nur eine korrekte Methode, um rückwärts mit einem vorzeichenlosen Zähler zu laufen:
%Vor%Es gibt einen Trick hier, für die letzte Schleifeniteration hast du i = 1 am Anfang der Schleife, i-- & gt; 0 besteht, weil 1 & gt; 0, dann ist i = 0 im Schleifenkörper. In der nächsten Iteration i-- & gt; 0 scheitert, weil i == 0, also spielt es keine Rolle, dass das Postfix-Dekrement über den Zähler gerollt ist.
Sehr nicht offensichtlich, ich weiß.
Dies ist keine Antwort auf Ihr Problem, weil Sie anscheinend kein Problem haben.
Diese Art der Optimierung ist völlig irrelevant und sollte dem Compiler überlassen werden (wenn überhaupt).
Haben Sie Ihr Programm so profiliert, dass es prüft, ob Ihre For-Schleife ein Flaschenhals ist? Wenn nicht, dann brauchen Sie sich keine Sorgen zu machen. Mehr noch, "i" als "Register" int zu haben, während Sie schreiben, macht aus Performance-Sicht keinen wirklichen Sinn.
Auch ohne Ihre Problemdomäne zu kennen, kann ich Ihnen garantieren, dass sowohl die umgekehrte Schleife als auch der "register" int-Zähler vernachlässigbare Auswirkungen auf die Leistung Ihres Programms haben werden. Denken Sie daran: "Vorzeitige Optimierung ist die Wurzel allen Übels".
Das heißt, eine bessere Zeit für die Optimierung wäre es, über die gesamte Programmstruktur, die verwendeten Datenstrukturen und Algorithmen, die Ressourcennutzung usw. nachzudenken.
Das Überprüfen, ob eine Zahl Null ist, kann schneller oder effizienter sein als ein Vergleich. Aber das ist die Art von Mikro-Optimierung, um die Sie sich wirklich keine Sorgen machen sollten - einige Taktzyklen werden von fast jedem anderen Perf-Problem stark in den Schatten gestellt.
Auf x86:
%Vor%Anstelle von:
%Vor%Wenn Sie einen anständigen Compiler haben, wird das "Hochzählen" genauso optimiert wie das "Herunterzählen". Probieren Sie ein paar Benchmarks aus und Sie werden sehen.
Sie "lesen" also, dass das Herunterklettern effizienter ist? Ich finde das sehr schwer zu glauben, es sei denn, Sie zeigen mir einige Profiler-Ergebnisse und den Code. Ich kann es unter gewissen Umständen kaufen, aber im allgemeinen Fall, nein. Scheint mir so, als wäre das ein klassischer Fall einer vorzeitigen Optimierung.
Ihr Kommentar zu "register int i" ist ebenfalls sehr aussagekräftig. Heutzutage weiß der Compiler immer besser als Sie, wie Sie Register zuweisen. Verwenden Sie das Schlüsselwort register nicht, es sei denn, Sie haben Ihren Code profiliert.
Es hat nichts damit zu tun, up oder down zu zählen. Was schneller sein kann, ist das Zählen von in Richtung Null . Michaels Antwort zeigt warum - x86 gibt Ihnen einen Vergleich mit Null als Implizite Nebenwirkung vieler Anweisungen, also verzweigen Sie nach der Anpassung Ihres Zählers nur basierend auf dem Ergebnis, anstatt einen expliziten Vergleich durchzuführen. (Vielleicht tun andere Architekturen das auch; ich weiß es nicht.)
Borlands Pascal-Compiler sind berüchtigt dafür, diese Optimierung durchzuführen. Der Compiler wandelt diesen Code um:
%Vor%in eine interne Darstellung, die dem ähnlich ist:
%Vor% (Ich sage berüchtigt, nicht weil die Optimierung das Ergebnis der Schleife beeinflusst, sondern weil der Debugger die Zählervariable falsch anzeigt. Wenn das Programmierer i inspiziert, zeigt der Debugger möglicherweise stattdessen den Wert von tmp an, was zu Nein führt Ende der Verwirrung und Panik für Programmierer, die denken, dass ihre Schleifen rückwärts laufen.)
Die Idee ist, dass selbst mit der zusätzlichen Anweisung Aber beachte, dass die Konvertierung etwas ist, was der Compiler automatisch tun würde , je nachdem, ob es die Transformation als sinnvoll erachtet. Der Compiler ist in der Regel besser darin, Code zu optimieren als Sie selbst. Geben Sie also nicht zu viel Mühe damit auf, damit zu konkurrieren. Wie auch immer, du hast nach C ++ gefragt, nicht nach Pascal. C ++ "for" -Schleifen sind nicht ganz so einfach anzuwenden wie Pascal "for" -Schleifen, weil die Grenzen der Pascalschen Schleifen immer vollständig berechnet werden, bevor die Schleife läuft, während C ++ - Schleifen manchmal von der Stoppbedingung und der Schleife abhängen Inhalt. C ++ - Compiler müssen einige statische Analysen durchführen, um zu bestimmen, ob eine gegebene Schleife die Anforderungen für die Art der Transformation erfüllen kann, für die Pascal-Schleifen bedingungslos qualifiziert sind. Wenn der C ++ - Compiler die Analyse durchführt, könnte es eine ähnliche Transformation durchführen. Es gibt nichts, was Sie davon abhält, Ihre Schleifen auf diese Weise selbst zu schreiben: Wenn Sie machen , wird Ihr Code schneller ausgeführt. Wie ich schon sagte, wirst du es wahrscheinlich nicht bemerken. Die höheren Kosten, die Sie zahlen, wenn Sie Ihre Schleifen manuell so anordnen, ist, dass Ihr Code nicht länger etablierten Idiomen folgt. Ihre Schleife ist eine ganz normale "for" -Schleife, aber sie sieht nicht mehr wie eins aus - sie hat zwei Variablen, sie zählen in entgegengesetzte Richtungen und eine davon wird nicht einmal in der Schleifenkörper - jeder, der Ihren Code liest (einschließlich Sie, eine Woche, einen Monat oder ein Jahr später, wenn Sie die "Optimierung" vergessen haben, die Sie erreichen wollten), muss zusätzliche Anstrengungen unternehmen, um sich selbst das zu beweisen Die Schleife ist in der Tat eine gewöhnliche Schleife in der Verkleidung. (Haben Sie bemerkt, dass mein Code oben keine vorzeichenbehafteten Variablen verwendet hat, ohne dass die Gefahr besteht, dass sie bei Null umschlingen? Die Verwendung von zwei separaten Variablen erlaubt das.) Drei Dinge, die man von all dem wegnehmen kann: Inc oder Dec immer noch ein Nettogewinn in Bezug auf die Laufzeit gegenüber einem expliziten Vergleich erzielt wird. Ob Sie diesen Unterschied tatsächlich bemerken können
Jeremy Ruten wies zu Recht darauf hin, dass die Verwendung eines unsignierten Schleifenzählers gefährlich ist. Es ist auch unnötig, soweit ich das beurteilen kann.
Andere haben auch auf die Gefahren einer vorzeitigen Optimierung hingewiesen. Sie haben absolut Recht.
Hier ist ein Stil, den ich vor vielen Jahren bei der Programmierung von eingebetteten Systemen verwendet habe, als jedes Byte und jeder Zyklus für etwas zählte. Diese Formen waren nützlich für mich auf den speziellen CPUs und Compilern, die ich verwendete, aber Ihre Laufleistung kann variieren.
%Vor% Dieses Formular nutzt das Zustandsflag, das nach arithmetischen Operationen auf einige -Prozessoren gesetzt wird - auf einigen Architekturen können Dekrement und Test für die Verzweigungsbedingung zu einem einzigen Befehl kombiniert werden. Beachten Sie, dass die Verwendung von predecrement ( --i ) hier der Schlüssel ist - die Verwendung von postdecrement ( i-- ) hätte nicht so gut funktioniert.
Alternativ
%Vor% Diese zweite Form nutzt die Pointer- (Adressen-) Arithmetik. Ich sehe selten die Form (pointer - int) in diesen Tagen (aus gutem Grund), aber die Sprache garantiert, dass, wenn Sie ein int von einem Zeiger subtrahieren, der Zeiger um (int * sizeof (*pointer)) dekrementiert wird.
Ich betone noch einmal, dass die Frage, ob diese Formulare ein Gewinn für Sie sind, von der CPU und dem Compiler abhängt, den Sie verwenden. Sie haben mir gut auf Motorola 6809 und 68000 Architekturen gedient.
In einigen späteren Armkernen nimmt das Dekrementieren und Vergleichen nur einen einzigen Befehl an. Dies macht das Dekrementieren von Schleifen effizienter als das Inkrementieren von Einsen.
Ich weiß nicht, warum es auch keine Inkrementvergleichsanweisung gibt.
Ich bin überrascht, dass dieser Beitrag mit -1 bewertet wurde, wenn es ein echtes Problem ist.
Sie können Folgendes versuchen, welcher Compiler sehr effizient optimiert:
%Vor%Jetzt können Sie es verwenden:
%Vor%Sie können in jede Richtung iterieren:
%Vor%Die Schleife
%Vor%erzeugt den folgenden Code:
%Vor%Jeder hier konzentriert sich auf die Leistung. Es gibt tatsächlich einen logischen Grund, in Richtung Null zu iterieren, was zu saubererem Code führen kann.
Das letzte Element zuerst zu durchlaufen, ist praktisch, wenn Sie ungültige Elemente durch Verschieben mit dem Ende des Arrays löschen. Für schlechte Elemente, die nicht an das Ende angrenzen, können wir in die Endposition wechseln, die Endgrenze des Arrays verringern und weiter iterieren. Wenn Sie zum Ende hin iterieren würden, könnte das Tauschen mit dem Ende dazu führen, dass Sie schlecht gegen schlecht tauschen. Durch die Iteration von Ende auf 0 wissen wir, dass sich das Element am Ende des Arrays bereits für diese Iteration als gültig erwiesen hat.
Für weitere Erklärungen ...
Wenn:
Dann natürlich:
Das heißt also:
Also endlich:
Was mehr zählt, als ob Sie Ihren Zähler erhöhen oder verringern, ist, ob Sie Speicher oder Speicher nach unten gehen. Die meisten Caches sind optimiert, um Speicher und nicht den Arbeitsspeicher zu erhöhen. Da die Speicherzugriffszeit der Engpass ist, mit dem die meisten Programme heute konfrontiert sind, bedeutet dies, dass das Ändern Ihres Programms, so dass Sie Speicher nach oben gehen, zu einer Leistungssteigerung führen kann, selbst wenn dies den Vergleich Ihres Zählers mit einem Wert ungleich Null erfordert. In einigen meiner Programme habe ich eine deutliche Leistungsverbesserung gesehen, indem ich meinen Code so geändert habe, dass Speicher statt nach unten verschoben wurde.
Skeptisch? Hier ist die Ausgabe, die ich bekam:
%Vor%vom Ausführen dieses Programms:
%Vor% Sowohl sum_abs_up als auch sum_abs_down machen dasselbe und werden auf die gleiche Weise zeitlich festgelegt, mit dem einzigen Unterschied, dass sum_abs_up Speicher hochgeht, während sum_abs_down Speicher ausfällt. Ich übergebe sogar vec als Referenz, so dass beide Funktionen auf dieselben Speicherplätze zugreifen. Trotzdem ist sum_abs_up konsistent schneller als sum_abs_down . Gib es selbst einen Lauf (ich habe es mit g ++ -O3 kompiliert).
FYI vec_original gibt es für Experimente, um es mir leicht zu machen, sum_abs_up und sum_abs_down so zu ändern, dass sie vec ändern, während diese Änderungen keine Auswirkungen auf zukünftige Zeiten haben.
Es ist wichtig zu beachten, wie tight die Schleife ist, die ich zeitlich plane. Wenn der Körper einer Schleife groß ist, ist es wahrscheinlich egal, ob ihr Iterator nach oben oder nach unten geht, da die Zeit, die zum Ausführen des Körpers der Schleife benötigt wird, wahrscheinlich vollständig dominieren wird. Es ist auch wichtig zu erwähnen, dass mit einigen seltenen Loops der Speicher nach unten manchmal schneller geht als nach oben zu gehen. Aber selbst mit solchen Loops ist es selten der Fall, dass das Hochfahren immer langsamer war als das Heruntergehen (im Gegensatz zu Loops, die Speicher aufladen, die oft immer schneller sind als die entsprechenden Down-Memory Loops; eine kleine Handvoll Male waren sie sogar 40 +% schneller).
Der Punkt ist, als Faustregel, wenn Sie die Option haben, wenn der Körper der Schleife klein ist, und wenn es wenig Unterschied gibt, ob Ihre Schleife Speicher statt runter geht, dann sollten Sie Speicher nach oben gehen.