Geschwindigkeit von Schleifen

[Dennis07]

Tach zusammen,
aus reinem Interesse wollt ich mal fragen, welche Schleifen schneller ausgeführt werden für welche bedingungen als andere und wieso. Ich meine, ich hätte vor ungefähr nem Jahr schonmal so etwas gelesen, erinnere mich allerdings nicht mehr an den genauen Thread oder Autor. Auf Google habe ich auch nichts gefunden.
Nur zu testen, was schneller ist, wäre erstens ziemlich ungenau, aufwändig und würde mir außerdem keinen verständlichen Grund liefern.
Wäre nett, wenn jemand, der eine Antwort weiß, sie mir sagen könnte :) oder zumindestens weiß, wie man das herausfindet, bzw. wo man es findet.

MFG

[Dejan Vu]

Von welchen Schleifen sprichst Du? Gibt mal Beispiele.

[Dennis07]

na For-To, For-Downto, For-In, While-Do, Repeat-Until, If-Then und Case-Of... :D

[jfheins]

Die Geschwindigkeit von Schleifen ist ein erster Näherung "hinreichend schnell" und in zweiter "egal".

Eine for-in Schleife ist vermutlich einen *Hauch* langsamer, da da einige Funktionsaufrufe versteckt sind.
Es ist sinnvoller, sich auf andere Sachen zu konzentrieren:
1. Die Anweisungen in der Schleife
2. Brauche ich die Schleife? Kann ich eine bessere Datenstruktur einsetzen, die schneller ist und auf die Schleife verzichtet?

P.S.: Schleifen führen Anweisungen 0 bis x fach aus, if-then und case-of sind daher keine Schleifen.

[Dennis07]

Ja, das stimmt natürlich. Ich schrieb ja auch, dass es im Grunde nur eine nice-to-know Frage ist. Ich wollte halt nur wissen, wie die Schleifen vom Compiler ausgewertet werden und was für ein Maschinencode da erzeugt wird.
Natürlich ist es weitestgehend irrelevant für den alltäglichen Gebrauch... ;)

PS: Ja, allerdings wäre es auch nett zu wissen, ob der CASE und IF code ähnlich bzw. identisch ist und ab wievielen Aufrufen CASE wohl schneller ist... :)

[Dejan Vu]

Du solltest das einfach selbst analysieren: Der Maschinencode ist in Delphi sichtbar und wie man Zeitmessungen macht, sollte Dir spätestens nach dem Bemühen der SuFu klar sein.

Los, ran ans Werk!

[Dennis07]

Ja, genau das war ja meine Frage:
Wie kann ich mir den Quelltext, der bei einer For-Schleife beispielsweise erzeugt wird, anzeigen lassen?
:)

[Dejan Vu]

Das Tastenkürzel kenn ich nicht auswendig, aber du solltest einen Breakpoint auf die Schleife setzen und dann im Menü nach 'Assembleransicht' o.ä. schauen.

[himitsu]

Zitat:

Zitat von Dennis07 (Beitrag 1282846)

If-Then und Case-Of... :D

Das sind keine Schleifen!

Und ansonsten ist alles in etwa gleich schnell.
Außerdem wählt man den Typ der Schleife anhand der Aufgabenstelltung aus und nicht wegen der Geschwindigkeit.


Intern bestehen alle Schleifen auch nur aus IF-THEN und GOTO ... nur die Abbruchbedingungen unterscheiden sich.

[Dejan Vu]

Zitat:

Zitat von himitsu (Beitrag 1282856)

Zitat:

Zitat von Dennis07 (Beitrag 1282846)

If-Then und Case-Of... :D

Das sind keine Schleifen!

Och menno.

[Dennis07]

Danke bis hierher schonmal, allerdings könntet ihr mir vielleicht sagen, wie man herausfindet, woraus genauer die von dem Compiler erzeugten Schleifenquelltexte bestehen?
Denn bei der Ausführung des aktuellen Befehls, wird die For-Schleife beispielsweise als solches ausgeführt und es wird nicht zu einem Quelltext gesprungen.

[Zacherl]

Selbst wenn repeat .. until aus irgendeinem Grund schneller sein sollte als for .. do, würde ich hier (ua. aufgrund der Lesbarkeit des Codes) definitiv niemals optimieren. Solche Dinge sind meiner Meinung nach Compilersache!

Wie himitsu schon sagte sind es im Grunde genommen nur "gotos" (Jumps). Du solltest im Assembler Code Mnemonics wie JMP, JNZ, JE, JZ ... sehen (da gibts ne ganze Reihe). Bei for Schleifen wird irgendwo ein INC bzw. DEC zu finden sein und gelegentlich gehört auch noch ein CMP mit dazu. Kann man so generisch gar nicht sagen.

[Der schöne Günther]

Beispielbild im Anhang.

Schau mal unter Ansicht -> Debug-Fenster -> CPU-Ansicht


Wir sehen dass eine for-downto-Schleife in Assembler irgendwie anders (kürzer) ist als eine for-to.

[Zacherl]

Habs auch mal schnell ausprobiert.

[p80286]

Zitat:

Zitat von jfheins (Beitrag 1282847)

Die Geschwindigkeit von Schleifen ist ein erster Näherung "hinreichend schnell" und in zweiter "egal".

Eine for-in Schleife ist vermutlich einen *Hauch* langsamer, da da einige Funktionsaufrufe versteckt sind.
Es ist sinnvoller, sich auf andere Sachen zu konzentrieren:
1. Die Anweisungen in der Schleife
2. Brauche ich die Schleife? Kann ich eine bessere Datenstruktur einsetzen, die schneller ist und auf die Schleife verzichtet?

P.S.: Schleifen führen Anweisungen 0 bis x fach aus, if-then und case-of sind daher keine Schleifen.

das kann ich auch nur unterschreiben.
Zu seligen TP-Zeiten war es so, daß

Delphi-Quellcode:

for to

Schneller war als

Delphi-Quellcode:

while

und

Delphi-Quellcode:

repeat

.
Diese beiden waren gleich schnell, den Unterschied machte die Abfrage der Abbruchbedingung aus, was aber nur relevant ist, wenn man um die Millisekunde feilschen muß.

Das

Delphi-Quellcode:

if

und

Delphi-Quellcode:

case

nichts mit Schleifen zu tun haben, wurde ja schon geschrieben - warum ist dieser Blödsinn eigentlich nicht auszurotten?.

Delphi-Quellcode:

Case

wäre theoretisch schneller, wenn es mit einer Sprungtabelle realisiert würde, das ist allerdings nicht der Fall (soweit ich weiß), somit ist es letztlich für den Compiler egal was eingesetzt wird. Im Sourcecode bevorzuge ich

Delphi-Quellcode:

case

, da dies doch etwas übersichtlicher ist als ellenlange

Delphi-Quellcode:

if..then..else

-Konstrukte.


Gruß
K-H

P.S.
@Schönster Mann von allen
Ich glaube Du hast Dich verguckt, die Schleife ist in beiden Fällen gleich lang/groß:mrgreen:
(inc cmp jnz)
Und was schneller ist,

Delphi-Quellcode:

dec

oder

Delphi-Quellcode:

inc

dazu hab ich auf die Schnelle nichts gefunden

[Dennis07]

Ah, danke, genau das habe ich gesucht ;) Entschuldigt bitte, dass mir die Disassembly-Anzeige-Funktionalität nicht geläufig war :)
Dass eine For-Downto schneller ist als eine For-To, war mir ja schon klar, da ja eine For-To eh immer eine invertierte For-Downto ist.

[Zacherl]

Zitat:

Zitat von Dennis07 (Beitrag 1282874)

Dass eine For-Downto schneller ist als eine For-To, war mir ja schon klar

Woraus hast du denn diese Aussage jetzt geschlussfolgert? Ist nämlich Blödsinn :P Wie auf meinem Screenshot zu sehen besteht sowohl die for .. to, als auch die for .. downto Schleife aus den exakt gleichen Instruktionen MOV, INC/DEC, CMP, JNE.

repeat .. until sieht auf den ersten Blick kompakter aus, als die anderen Schleifen (es fehlt das INC/DEC), aber man muss bedenken, dass die Zählervariable hier manuell im Schleifenkörper gesetzt werden muss. Demnach würde hier zumindest noch eine weitere Instruktion hinzukommen.

while .. true hat den größten Overhead, da vor Begin der eigentlichen Schleife nochmal dediziert geprüft wird, ob die Bedingung überhaupt erfüllt ist. Dieser Check (hier: CMP, JG) wird allerdings nur ein einziges Mal ausgeführt und beeinflusst daher die eigentliche Laufzeit der Schleife nicht.

Fazit:
In dem von mir getesteten Fall (lokale Funktion mit lokaler Zählervariable) sind alle Schleifen gleich performant.

[Neutral General]

Es kann da auch keinen großen Performanceunterschied geben. Letzendlich ist entweder nur die Syntax in Delphi anders und der Code Assemblercode ist der gleiche oder die Assemblerbefehle tauchen ggf. in einer minimal anderen Reihenfolge auf. Letztendlich läuft es immer auf eine bestimmte Kombination von cmp/inc/jmp hinaus.

[himitsu]

Daß

Delphi-Quellcode:

for i := irgendwas downto 0 do

oftmals schneller ist, als ein

Delphi-Quellcode:

for i := 0 to irgendwas do

,
liegt nicht an der Richtung, sondern meistens nur daran, daß das Ende hartecodet werden kann und keine Variable zwischengespeichert/ausgewertet werden muß.

Denn bei

Delphi-Quellcode:

for i := -irgendwas to 0 do

und

Delphi-Quellcode:

for i := 0 downto -irgendwas do

wäre es praktisch andersrum.


PS: Ohne Optimierung entspricht diese For-Schleife

Delphi-Quellcode:

for i := 0 to xxx do begin
  ...
end;

intern jender While-Schleife.

Delphi-Quellcode:

i := 0;
Ende := xxx;  // Dieses hier ist auch der Grund, warum man Löschen besser rückwärts erledigt.
while xxx <= Ende do begin
  ...
  Inc(i);
end;

Nja, eigentlich eher dem

Delphi-Quellcode:

i := 0;
Ende := xxx;  // Dieses hier ist auch der Grund, warum man Löschen besser rückwärts erledigt.
if i <= Ende then
  repeat
    ...
    Inc(i);
  until xxx = Ende;  // = und nicht >=

Aber das fällt kaum auf, außer man manipuliert an der Schleifenvariable, um z.B. etwas ala

Delphi-Quellcode:

for i := 0 to 9 step 3 do

basteln, denn bei

Delphi-Quellcode:

0 to 10

landet man quasi in einer Endlosschleife, da die 10 übersprungen wird. :angel2:

[Dejan Vu]

War da nicht mal was, dass der Vergleich auf 0 schneller ist, als der Vergleich auf '<Variable>'? Aber egal, das sind eh Peanuts.

Wichtig sind doch eh die inneren Werte (der Schleife).

[himitsu]

Bei Schleifen mit sehr vielen Durchläufen und mit sehr wenig Code darin, fällt das schon auf, aber sonst sollte man sich bei Schleifen einfach auf deren Funktion/Verwendung beziehen.

[p80286]

Zitat:

Zitat von Dejan Vu (Beitrag 1282907)

War da nicht mal was, dass der Vergleich auf 0 schneller ist, als der Vergleich auf '<Variable>'?

Jain, beim Vergleich auf null kannst Du das Register gleich mit 0 vorbelegen und mußt Dir nicht erst einen Wert aus dem Speicher angeln.

Aber wenn mann nicht Zeitkritisch arbeitet ist das zu vernachlässigen.

Gruß
K-H

[Stevie]

Interessant wirds eh erst dann, wenn man betrachtet, was innerhalb der Schleife geschieht.
Denn das entscheidet darüber wie ein Compiler entsprechende Optimierungen (z.B. loop unrolling) durchführen kann.

[Insider2004]

Verfalle nicht in den Optimierungswahn. Du verlierst Zeit ganz woanders. Z.B. in schwachsinnigen Programmstrukturen.

[WM_CLOSE]

Man sollte auch nicht ganz vergessen, dass der Prozessor selbst auch noch eine Rolle spielt. Eine Assembleranweisung hat ja bei modernen Mikroprozessoren nicht immer die selbe Ausführungsgeschwindigkeit. Stichworte sind Pipelining, Out-of-order execution, Branch Prediction und Caching.
Der Vergleich mit 0 ist üblicherweise deshalb schneller, weil man keine Variable zusätzlich ins Register laden muss.

Einige Schlüsse kann man auch aus diesem Wikipedia Eintrag ziehen.

Insgesamt kann man aber sagen, dass eine Optimierung auf Assemblerebene oder die Auswahl der "schnellsten" Schleife heute kaum noch nenneswerte Vorteile bringt.
Für rechenintensive Dinge ist heute eher Multithreading oder GPU processing angesagt. Für andere Dinge vielleicht ein intelligentes Caching oder ganz allgemeine Ablauf-Optimierungen.

PS: Solltet ihr neben den Intel Prozessoren auch andere targets haben, müsstet ihr die Optimierung sowieso für jeden Prozessortyp einzeln planen.

[OlafSt]

Das betrifft nicht nur den Unterschied zwischen Intel- und AMD-CPU. Bereits innerhalb der CPUs gibt es gravierende Unterschiede. So war damals z.B. der Aufschrei riesengroß, als die etablierte Pipelining-Technik des 80486 durch die veränderte Out-of-Order- und BP-Technik des Pentium ersetzt wurde.

Konsequenz daraus war, das manche Programme auf dem Pentium - trotz höherer Taktrate - langsamer liefen als auf einem 486. Die 486-Optimierung lief dem Design des Pentium schlicht "gegen den Strich".

[TRomano]

In hochoptimierten Routinen (purer Assembler in mathematischen Berechnungen mit millionenfacher Wiederholung z.B. Videokomprimierung o.ä.) macht das vielleicht Unterschiede, auch hier spielen unterschiedliche Implementierungen der Prozessorbefehle eine Rolle, aber auch nur, wenn man die einzelnen Takte zählt ... In einem Standard-Programm hat das nicht zu suchen, denn entscheidend ist was und wieviel in der Schleife passiert. Da ist (immer) Optimierungspotential vorhanden, vielleicht nicht bei zwei Additionen in einer Zeile ...