Tips zum Thema Optimierung

Kaum ein anderer Punkt wird beim Programmieren so sehr vernachlässigt wie das Verbessern der Ausführungsgeschwindigkeit. Dies kann leicht dazu führen, daß das Programm niemals wirklich ausprobiert wird oder nur selten Verwendung findet. Es ist ziemlich frustrierend lange zu warten bis eine Textverarbeitung die gewünschte Datei geöffnet hat oder wenn man mit einem Photofilter experimentieren will und dieser unendlich lange rechnet bis er das Ergebnis anzeigt.

Man kann sich zwar auf einen schnelleren Prozessor verlassen, aber einige Routinen können wesentlich beschleunigt werden indem man einige Anweisungen einfach austauscht und/oder umstellt. Außerdem bringt gerade bei der 2D-Ausgabe (also bei der Textausgabe, dem Zeichnen von Kreisen, etc.) ein schnellerer Prozessor nicht unbedingt den erhofften Leistungsschub.
Dabei ist Optimierung nicht unbedingt so schwierig, es erfordert lediglich etwas Mut neue Wege zu gehen und ein bißchen Zeit.
Und das derer nicht soviel benötigt wird kommt daher, daß nur etwa 10% eines üblichen Programmes zeitkritisch sind, und man sich daher auf diese Teile beschränken kann und sollte.

Für komplizierte 3D-Grafik Beschleunigungen und allgemein fortgeschrittene Optimierungsmethoden verweise ich Sie auf das Buch von Michael Abrash welches sehr detailliert ist, allerdings auch Assemblerkenntnisse vorraussetzt um das letzte Bisschen rauszuholen.

Hinweis: Die Begriffe Funktion, Prozedur und Routine werden innerhalb dieses Dokuments als Synonyme verwendet, da sie vom technischen Aspekt her identisch sind.

Welche Arten von Optimierung gibt es?

Allgemein kann man das Optimieren in folgende Bereiche unterteilen:

die Rechengeschwindigkeit, d.h. die Geschwindigkeit mit der Operationen ausgeführt werden
die Größe von Programmen

Diese beiden Arten sind fast immer entgegengesetzt. D.h. will man an Ausführungsgeschwindigkeit gewinnen muß man oft etwas Speicher opfern, da beim Optimieren versucht wird vieles aus Schleifen rauszuziehen und speziellere Lösungen zu finden, die dann mehr Platz brauchen als universellere Lösungen. Doch der Speicher der dadurch "verschenkt" wird, dürfte heutzutage kein ernstes Problem mehr darstellen, bewegt er sich doch oft nur im KByte-Bereich.

Die Geschwindigkeit kann schon mit Hilfe einiger Tricks erhöht werden. Sollten sie jedoch große Zeitgewinne erreichen wollen, finden Sie weiter unten, eine Anleitung zur gezielten Suche nach langsamen Routinen und deren Optimierung.

Allgemeine Tipps:

Tipp 1: Halten Sie Programmschleifen klein

Sie sollten Programschleifen so klein wie möglich halten, da die Anweisungen innerhalb dieser, mehrfach ausgeführt werden.
Versuchen Sie soweit wie möglich zeitintensive Anweisungen vor oder nach der Schleife auszuführen und schreiben Sie wirklich nur das in eine Schleife was notwendig ist.

Öfters scheint eine Schleife schon ziemlich perfekt bzw. so einfach, daß man keinen Weg sieht sie zu optimieren.
Das liegt daran, daß man die Befehle zu abstrakt sieht. Man muß sich klar werden was diese genau tun.
So ist ein Lesen von Daten aus dem Arbeitsspeicher schneller als von der Festplatte.

Ließt man beispielsweise aus einer Datei Zeichen für Zeichen aus um diese zu analysieren ist dies nicht besonders effektiv. Die Festplatte kann größere Datenblöcke schneller lesen, denn bei jedem neuen Lesezugriff muß erst die richtige "Stelle" gefunden, die Platten entsprechend gedreht und der Schreib/Lesearm bewegt werden. Außerdem sind viel mehr Funktionsaufrufe notwendig für die ein riesiger Verwaltungsaufwand anfällt. Denken Sie daran, daß Windows noch viele andere Anwendungen bedienen muß und daher Regeln für die Nutzung der Festplatte einführt, was wieder Zeit kostet.

Es wäre also effektiver einen Block gewisser Größe auf einmal auszulesen und im RAM zu halten um ihn dann dort zu untersuchen anstatt dies Zeichen für Zeichen zu tun.

Ein konkretes Beispiel wie man Schleifen optimiert bietet der nächste Tipp.

Tipp 2: Vermeiden Sie Zuweisungen in Programmschleifen

Eigenschaften unterscheiden sich dem Anschein nach nicht von Variablen. Aber Eigenschaften werden über Methoden, was einen viel größeren Aufwand erfordert, angesprochen, hingegen Variablen direkt und somit schneller. Deswegen sollte man, wenn ein Eigenschaftswert häufig benötigt wird, ihn in einer Variablen speichern und dann mit dieser weiterarbeiten.
Gerade in Schleifen verstärkt sich dieser Effekt sehr stark.

schlecht

for i := 1 to 10 do
begin
  ListBox1.Items.Add(Edit1.Text);
end;

besser

S := Edit1.Text;
for i := 1 to 10 do
begin
  ListBox1.Items.Add(S);
end;

schlecht

for i := 0 to ListBox1.Items.Count - 1 do
begin
 Edit1.Text := Edit1.Text + Chr(13) + Chr(10) + ListBox1.Items[i]; 
end;

besser

for i := 0 to ListBox1.Items.Count - 1 do
begin
  Temp := Temp + Chr(13) + Chr(10) + ListBox1.Items[i];
end;
Edit1.Text := Temp;

Achtung: Falls sich die Werte der Eigenschaften innerhalb der Schleife ändern, sollten Sie natürlich trotzdem die Eigenschaften verwenden.

Tipp 3: Speichern Sie Rückgabewerte von Funktionen

Für Funktionen gilt dasselbe wie für Eigenschaften. Es kann je nachdem wie komplex eine Funktion aufgebaut ist sehr viel schneller sein das Ergebnis zu speichern. Speziell für häufig verwendete, komplexe Funktionen kann es sinnvoll sein eine Wertetabelle anzulegen die beim Programmstart mit den nötigen Werten gefüllt wird.
Sie sehen alles läuft darauf hinaus unnötige Wiederholungen zu vermeiden.

Tipp 4: with...do-Blöcke

Wenn mehrere Eigenschaften bzw. Methoden eines Objektes verwendet werden ist es sinnvoll sie von einen with...do-Block einzurahmen.
Denn für jede aufgerufene Methode oder gelesene/geschriebene Eigenschaft eines Objekts muß zuerst der ganze "Vererbungsbaum" durchlaufen werden. Je komplexer die "Verwandschaft" einer Methode ist, sie also auf "Vorfahr"-Methoden zugreift, desto langsamer.
Innerhalb eines with...do-Block muß der Vererbungsbaum allerdings nur einmal durchlaufen werden.

Beispiel

with Form1 do
begin
  Top := 10;
  Width := 100;
  Height := Width;
  Color := clRed;
  ...
end;

Tipp 5: Minimieren Sie die Funktions- bzw. Prozedurenaufrufe

Modularisierung trägt sicherlich zu der Übersichtlichkeit eines Programmes bei. Aber in zeitkritischen Teilen sollten Sie diese nicht zu weit treiben, da für jeden Prozedurenaufruf Verwaltungsaufwand betrieben werden muß. In Schleifen ist es gegebenfalls besser die Anweisungen der Funktion/Prozedur direkt in die Schleife einzubauen.

C++ bietet mit inline die Möglichkeit den Komfort von Funktionsaufrufen mit der Leistungsfähigkeit der direkten Implementierung zu kombinieren. Dabei ersetzt der C++-Compiler in der EXE-Datei die Funktionsaufrufe durch die in der Funktion enthaltenen Anweisungen, so als ob sie direkt an Stelle des Funktionsaufrufs eingegeben wurden.

Tipp 6: Maximal 3 Argumente

Delphi benutzt standardmäßig bei den Funktions- und Prozeduraufrufen die register-Konvention. Diese ist besonders schnell, da die Register des Prozessors verwendet werden und somit keine langsamen Hauptspeicherzugriffe(RAM) notwendig sind. Die Ergebnisse bleiben einfach im Prozessor(den Registern) und können dort direkt weiterverarbeitet werden.

Die Anzahl der Register ist allerdings beschränkt. EAX, ECX, EDX werden für alle Typen, mit 4 Byte Größe, inklusive Pointern verwendet. Nur Gleitkommatypen (Single, Double, Extended, Comp, ...) werden über den Co-Prozessor-Register ST übergeben.

Im Register EBX wird bei Methoden die Instanz einer Klasse übergeben, damit man auf die Felder(= Eigenschaften und Methoden) eines Objektes zugreifen kann und ist deshalb bei Methoden nicht nutzbar.

Es ergibt sich also folgende Regel

Verwenden Sie wenn möglich, nicht mehr als 3 Argumente (+ eventuell 1 Gleitkommaargument). Bei Funktionen und Prozeduren die nicht Teil eines Objekts sind können sie 4 Argumente (+ eventuell 1 Gleitkommaargument) verwenden.
Versuchen Sie Routinen zu spezialisieren, dann fallen meistens einige Argumente weg.
Gerade bei langsamen Programmteilen sind Speziallösungen sehr wirksam, da viele Fallunterscheidungen wegfallen.

Tipp 7: Setzen Sie die richtigen Typen ein

Ganzahlen- und Gleitkommaarithmetik sind sich heutzutage von der Geschwindigkeit ungefähr gleich.
Früher hat man immer empfohlen Festkommaoperationen zu verwenden. In der Zwischenzeit wurden die Gleitkommaoperationen des Coprozessors aber soweit optimiert, daß Festkommaopertionen sogar teilweise langsamer sind.
Auf jeden Fall sollten Sie auf den Variant-Typen verzichten wenn sie ihn ersetzen können, denn er ist durch seine Kombination von verschiedenen Typen mit Verwaltungsaufwand belastet und daher sehr langsam.

Mit der Umstellung auf die 32-Bit-Systeme hat sich ein größerer Wertebereich ergeben der nicht immer benötigt wird. Sie sollten allerdings, zu Gunsten der Leistung häufig 32-Bit Typen verwenden, da die Prozessorbefehle auf 32-Bit optimiert wurden. Dies bezieht sich auch auf Schleifenzähler und boolesche Variablen. Entsprechendes gilt für 64-Bit Prozessoren, d.h. verwenden sie möglichst immer die Datentypbreite auf die der Prozessor ausgelegt ist.
Für Gleitkommatypen sollten Sie am Besten Single oder Double einsetzen aber auf keinen Fall den 6-Byte-Real von Delphi, da er nicht direkt vom Coprozessor unterstützt wird. Extended (in C++ Long Double) ist zwar der native Coprozessordatentyp aber er wird nicht von allen Sprachen korrekt implementiert.

Tipp 8: Richten Sie ihre Daten im Speicher aus

Aus dem gleichen Grund wie in dem vorhergehenden Tipp sollten Sie ihre Daten an 4 Byte-Grenzen ausrichten.
Meißtens wird dies von aktuellen Programmiersprachen durch eine spezielle Compiler-Option unterstützt, die auch fast immer aktiviert ist. Unter Delphi finden Sie diese Option indem Sie im Menü Projekt|Projektoptionen klicken, den Reiter "Compiler" aktivieren und ein Häckchen bei "Ausgerichtete Record-Felder" setzen.

Tipp 9: Schreiben Sie keine zu universellen Routinen

Zwar ist es immer schön wenn man eine Funktion hat die flexibel ist, doch sind diese oft viel schwieriger zu programmieren und auch langsamer. Allgemein gilt je weniger Schritte man durchführen muß, desto schneller ist man. Deckt eine Prozedur aber nun unzählige verschiedene Möglichkeiten ab, so wird sie unübersichtlich und wegen der vielen Fälle auch langsam.
Trotzdem sollte man jetzt nicht alles nach diesem Prinzip machen. Es ist besser es dort aufzuteilen, wo es zu komplex und zu langsam wird und es anderen Falls auf die einfachste, verständlichste Weise umzusetzen.

Tipp 10: Mathematische Terme beschleunigen durch Umschreiben

Der mathematisch vereinfachte Term ist nicht unbedingt der schnellste, da nicht jede Operation gleich schnell ausgeführt wird. So kann es sinnvoll sein einen Term "auseinanderzuziehen" um Multiplikationen zu vermeiden.
Zuerst noch einige Erklärungen, dann folgt ein Beispiel.
Die Geschwindigkeit nimmt bei den Grundrechenarten von + nach / ab. (+, -, *, / ). Dies gilt auch für die entsprechenden Gleitkommaoperationen.
Um solche Terme zu vereinfachen sollte man über eine Tabelle mit Taktzahlen verfügen, die einem aufschlüsselt welche Befehle wie schnell verarbeitet werden.
Hier eine kleine Tabelle für die 4 Grundrechenarten :

Werte gelten für den Pentium, Taktzahlen sind je nach Art der Operanden verschieden, d.h. 4+4 und 4+a (also Addition mit Konstante und Addition mit Variable) werden verschieden schnell verarbeitet, deshalb werden keine genauen Taktangaben gemacht. Bitte verstehen Sie, daß ich nicht detaillierter darauf eingehen kann, denn sonst müßte ich Assemblerkentnisse vorraussetzen. Siehe dazu die Buchempfehlungen:

Befehl	Takte
Addition(+)	1 bis 3
Subtraktion(-)	1 bis 3
Multiplikation(*)	10 bis 11
Division(/)	17 bis 41

Diese Tabelle bietet zwar nur einen groben Überblick reicht jedoch in diesem Fall völlig aus. Wie sie klar erkennen, sind Additon und Subtraktion gleich schnell, die Multiplikation benötigt etwa 3 mal soviel Zeit und die Division im Schnitt das 10-Fache.

Beispiel: Zeichnen von Geraden

Sie folgen der Gleichung y = m * x + b, wobei m die Steigung der Geraden und b ihr y-Achsenabschnitt ist.
Zum Zeichnen der Geraden wollen wir Funktionswerte mit immer gleichen Abständen berechnen. Man muß also eine Schrittweite delta und einen Startwert x₀ festlegen. Um den nächsten x-Wert zu berechnen addiert man einfach delta zum aktuellen x-Wert dazu: x_n+1 = x_n + delta

Nun zur Berechnung der y-Werte. Der y-Startwert wird nach der bekannter Methode berechnet y₀ = m * x₀ + b.
Für y₁ ergibt sich dann y₁ = m * x₁ + b, was nach dem oben gesagten aber auch so geschrieben werden kann:
y₁ = m * (x₀ + delta) + b.
Nun multipliziert man die Klammer aus und erhält y₁ = m*x₀ + m*delta + b. Und jetzt kommt's! Ordnet man den Term etwas um erhält man y₁ = m * x₀ + b + m * delta und kann m * x₀ + b durch y₀ ersetzten.
Schließlich erhält man: y₁ = y₀ + m * delta oder allgemein: y_n+1 = y_n + m * delta.
Das bedeutet das man nur noch für den Startwert y₀ = m * x₀ + b die ursprüngliche Funktion verwenden und einmal die Konstante m * delta ermitteln muß. Alle folgenden Funktionswerte ergeben sich durch eine Additon dieser Konstanten zu ihrem vorhergehenden y-Wert.

Fazit: Wir haben die Multiplikation durch eine Addition ersetzt und haben damit eine rund 3 mal höhere Geschwindigkeit erreicht.

(Übrigens: So ungefähr arbeitet auch der Algorithmus zum Zeichnen von Linien und ist deshalb auch unter anderem schneller als das einfache hintereinandersetzen von Punkten. Es kommen natürlich noch andere Faktoren dazu, wie das direkte Bearbeiten des Grafikkartenspeichers der das Monitorbild enthält. Dabei werden die Punkte zuerst berechnet und dann in einem Aufwasch in den Grafik-Speicher geschrieben, so daß man sich die häufigen Aufrufe einer Punktsetz-Funktion sparen kann.
Dies geht allerdings nur unter DOS, DirectX oder mittels eines Treibers)

Gezielte Suche nach verlangsamenden Anweisungen:

Falls dies nicht genügt, muß man das Problem gezielter angehen:

1. langsame Rountinen identifizieren

Der erste Schritt beim Optimieren ist in einer Routine diejenigen Anweisungen zu finden die die meißte Zeit benötigen.
Verwenden Sie dazu am besten

Spezielle Delphi-Optimierungen hervorheben: inc, dec, include, insert, is, ..., verweis auf www.optimize.com, präzisierung/hervorhebung der Werttabelle, Optimierung von Graphik!!! ScanLine, Bitmap, Bitmap-Switching, Flackern, ... vielleicht eigene Seite dazu

Noch ein Tipp: Verfallen Sie nicht in den Wahn Routinen direkt in Assembler zu schreiben. Versuchen Sie zuerst die Konzepte Ihres Algorithmus zu überdenken und in einer Hochsprache zu realisieren bevor Sie sich an das "Feintuning" in Assembler wagen.
Weiterhin hat das Optimieren in Assembler nur einen Sinn wenn für Sie die Prozessorunabhängigkeit keine große Rolle spielt, da Sie sonst über präzise Kentnisse für mehrere Prozessoren verfügen müssen. Trotz alledem kann Assembler, gezielt eingesetzt, sehr nützlich sein, auch unter Windows(alle Versionen). Hierzu gibt es ein sehr gutes Buch von Trutz Eyke Podschun welches beschreibt wie man Assembler sinnvoll zusammen mit Hochsprachen einsetzt und außerdem Assembler von Beginn an erklärt.