Optimierung

Während des Compilierens ist es möglich auf verschiedener Ebene Optimierungen durchzuführen um den erzeugten Code zu beschleunigen. Dabei gibt es verschiedene Möglichkeiten, durch Kürzen von Code, ersetzen durch schnellere arithmetische Operationen, gute Registerverwaltung, verbessern des Speichermanagement usw.
Hier sind einige Optimierungen gesammelt die man in einem Compiler umsetzen sollte. Einige Optimierungen können auch in einer Compiler-Warnung als Information ausgegeben werden, zB. wenn Variabeln oder Codeteile nicht benutzt und deshalb entfernt werden.

Bestimmte Mathematische Funktionen können durch solche ersetzt werden welche im Prozessor schneller berechnet werden können.
Über diese einfachen Optimierungen hinaus ist es prinzipiell möglich durch die Umformung von mathematischen Formeln die mathematische Berechnung selbst zu optimieren. Dies ist aber eine sehr komplexe Sache und deshalb eigentlich Aufgabe des Programmierers.

In der Codestruktur lassen sich Optimierungen durchführen die den Code kürzen oder beschleunigen können.

• Unbenutzte Variablen entfernen: Werden Variabeln zwar deklariert und beschrieben, aber nie gelesen können sie gelöscht werden.
• Unbenutzten Code entfernen: Wenn erkannt wird das Codeteile nie erreicht und ausgeführt werden können, können sie gelöscht werden.
• Variablen mehrfach Beschreibung: Werden Variabelwerte mehrfach geschrieben bevor sie das erste mal gelesen werden, können alle vorangehenden Zuweisungen gelöscht werden.
• Umwandlung von Variable zu Konstante: Wird in einem Code erkannt das eine Variable nur einmal mit einem Konstanten Wert beschrieben wird, kann man diese intern zu einer Konstante umwandeln, da diese schneller berechnet werden als Variablen und nicht in Register kopiert werden müssen.
• Konstantenberechnung: Alle Konstantenberechnungen können bereist in Compiler berechnet und so zu einer Konstante zusammengefaßt werden.
• Inlining: Prozeduren mit nur kurzem Code können über Inline direkt in den Code eingefügt werden. Statt also alle Werte erst im Stack abzulegen und eine Prozedur über Call aufzurufen, werden die in der Prozedur enthaltenen Codes direkt in die aufrufende Prozedur kopiert. Besonders bei sehr kurzen Berechnungen wie zB. einer Pythagoras Dreiecksberechnung die im Code sehr häufig aufgerufen wird kann dies den Code erheblich beschleunigen da eine ganze Reihe Funktionen wegfallen (PUSH POP CALL RET). Inlining kann über ein Schlüsselwort Deklariert oder auch automatisch vom Compiler durchgeführt werden. Am besten beläßt man einerseits die Prozeduren, fügt sie aber da wo es möglich ist direkt in den Code ein, so können Public Prozeduren auch extern noch erreicht werden.
• Zwischenspeichern von Werten: Der Zugriff auf einige Daten kann langsamer sein als auf Standard Daten->Typen die den Prozessor direkt ansprechen kann (zB. Arrays, besonders wenn sie mehrdimensional oder Dynamisch sind.). Wird erkannt das viele Zugriffe in Berechnungen Verwendet werden kann eine schnellere temporäre Variable verwendet werden. Die Werte werden dann zuerst in diese kopiert, de Berechnungen durchgeführt und das Resultat wenn notwendig zurück kopiert.
• Variabeln Verschiebung: Hat der Programmierer übersehen das er innerhalb einer Schleife eine Variabel zuweist, deren Wert sich aber in der Schleiffe nie ändert, kann diese aus der Schleife nach oben verschoben werden.
• Schleiffen Ausfalten: Kurze Schleifen mit wenig Inhalt deren Bereich über Konstanten festgelegt wurden, können ausgefaltet werden. So fallen die Schleifenprüfungen und Sprünge weg. Es muß aber dann auch geprüft werden daß das Laden des Codes nicht mehr Zeit in Anspruch nimmt als der kürzere Schleifencode.
• Schleifenzähler Optimierung: Wird der Schleifenzähler nur mit Ganzzahlen und mit Schrittweite=1 durchläuft, und wird der Schleifenzähler weder Innerhalb, noch nach dem verlassen der Schleife gelesen oder geschrieben, kann eine simple Abzählschleife LOOPECX umgeformt werden die ECX auf 0 Prüft. Dies ist schneller als eine COM Prüfung.
• Verschachtelte Schleifen: In verschachtelten Schleifen ist die Innerste Schleifen diejenige die am häufigsten verwendet wird, Optimierung muß also von innen nach außen durch die Verschachtelung verlaufen.
• Rekursionen zu Iterationen umformen: Rekursive Algorithmen (Prozedur ruft sich selbst auf) sind in der Regel langsamer als solche die iterativ (durch schleifen) gelöst werden können. Ein oft benutztes Beispiel ist das Berechnen einer Fakultät. Werden solche Rekursionen verwendet könnte ein Compiler diese umformen und daraus iterative Lösungen finden. Das hat mehrere forteile, da die Daten nicht über den Stack abgewickelt werden müssen kann der Speicher besser verwaltet werden, Stack-Überlauf ist nicht mehr so gefährlich, und es fallen die Sprung-Funktionen und Parameterübergaben weg. Dies ist allerdings abhängig vom Algorithmus, ein Quicksort zB. läßt sich auf diese weise nicht optimieren. (Aber eigentlich sind solche Optimierungen Sache des Programmierers, denn dies hat mit Algorithmus-Entwicklung zutun.)
• Daten-Typ Optimierung (und Polymorphie Auflösung): Ist es möglich während der Compilierungszeit Datentypen aufzulösen, können diese durch Datan-Typen Änderung beschleunigt werden. Variant kann zu Standard Daten-Typ, Object kann zu Klassename, Fließpunkt kann zu Ganzzahl geändert werden usw. Dabei müssen aber bestimmte Voraussetzungen erfüllt sein.
  • Es muß lückenlos die gesamte Existenz der Variable zur Compilierungszeit aufgelöst werden können. Das heißt die notwendigen Bedingungen für eine Umformung komplett geprüft werden können.
  • Die Umformung sollte nur auf lokal gültige Variabeln angewendet werden.
  • Werden Private Public sichtbare Umformungen durchgeführt (zB. Prozeduren), müssen die gesamten Codes mehrfach erzeugt werden, also eine automatische Überladung durchgeführt werden. Dabei müssen auch alle abhängigen internen Verschachtelnden berücksichtigt werden, die Analyse ist dann also auf Public-Ebene weitaus aufwendiger.
  • Polymorphe (allgemeine vielgestaltige) können zu Explizite Daten-Typen geändert werden, wenn feststeht das der Name immer den gleichen Typ trägt, Varianz also nie verwendet wird.
  • Fließpunkt kann zu Ganzzahl geändert werden: Wenn feststeht das nie eine Bruchzahl gelesen geschrieben oder erzeugt werden kann (nur Ganzzahlen lesen schreiben, nur Operationen "+ - * \ ^", keine "/ Sqr()"). (Ein Beispiel wäre wenn eine Fließpunkt Zahl als Schleifenzähler verwendet wird, der aber nur Ganzzahlen abzählt.)

Bestimmte Operationen können durch Prozessor-Funktionen oder Assembler Umformungen beschleunigt werden.
Dabei müssen zwei Dinge berücksichtigt werden, nicht nur das die einzelnen Prozessor-Funktionen schneller sind, sondern auch das sie geladen werden müssen. Man kann ein Code auch überoptimieren, in dem man die einzelnen Funktionen zwar beschleunigt, aber der Code als ganzes von der Hardware trotzdem langsamer ausgeführt wird.
Da sich bei einigen Optimierungen die Strukturen verändern können, kann die Fehlersuche ein Problem darstellen da die Position wo ein Fehler aufgetreten ist nicht mehr exakt festgestellt werden kann, oder die Operation selbst ist nicht mehr die selbe. Während der Entwicklung muß es also auch möglich sein alle Optimierungen auszuschalten.
Alle Optimierungen können nur durchgeführt werden wenn der Code zur Compilierungszeit aufgelöst werden kann.

• Register Optimierung: Dabei wird versucht möglichst die Variabeln die am häufigsten verwendet werden in den Registern zu halten, zudem können alle Register für bestimmte Operationen genutzt werden, eine Addition zB. kann auf allen Registern stattfinden, während eine Multiplikation oder ein Speicherzeiger nur auf speziellen Registern stattfinden kann. Auch muß berücksichtigt werden das bestimmte Operationen Register überschreiben können, wie zB. MUL und DIV überschreiben EDX (auch wenn man dies der ASM-Funktion nicht ansehen kann). Noch mehr Optimierung ist bei modernen 64Bit Prozessoren möglich da diese nun 16 Register zur Verfügung stellen.
• Register mehrfach Beschreibung: Durch die Codegenerierung ist es möglich das Register mehrfach beschrieben werden bevor sie das erste mal gelesen werden. Alle vorangehenden Zuweisungen können gelöscht werden.
• Parameter Übergabe an Prozeduren über Register: Normalerweise werden alle Parameter einer Prozeduren in den Stack kopiert und dieser dann so vorbereitet an die Prozedur übergeben. Es ist aber auch möglich Parameter direkt über die Register zu übergeben. Auf diese Weise kann das Umkopieren der Werte in und aus dem Stack beschleunigt werden. (Vorallem sinnvoll wenn sich Inlining nicht lohnt.)
• Register Sicherung: Wenn durch die Operationen Register verändert werden, müssen die enthaltenen Werte die noch benötigt werden gesichert werden. Um dies zu vereinfachen wurden einige Register als flüchtig betrachtet, die aufrufende Prozedur ist also Verantwortlich diese zu sichern. Die nicht flüchtigen Register werden dann meisten in der Prozedur auf den Stack gesichert. Dies kann in die Aufrufende Prozedur verschoben werden, da nur diese weis welche Register sie noch braucht. So können überflüssige Sicherungen vermieden werden.
  Diese Optimierung funktioniert aber nur in einem nach außen Abgeschlossenen Projekt, werden die Prozeduren zB. aus einer DLL extern abgerufen ist es nicht möglich festzustellen welche Regsiter die aufrufende Prozedur sichert, deshalb muß die Sicherung innerhalb der Prozeduren erfolgen.
• Stack-Rahmen: Normalerweise wird in einer Prozedur ein Stack-Rahmen geschaffen um darin Temporäre Variabeln und Register zu sichern. Dieser kann weggelassen werden wenn weder Temp-Variablen noch Register gesichert werden müssen.
• Erweiterte Funktionssätze: Es ist möglich die neuen modernen Funktionssätze wie MMX SSE 3DNow usw. zu benutzen um Berechnungen zu beschleunigen. Dies ist aber in weites Feld und erfordert Codes an verschiedene Hardware Umgebungen anzupassen damit sie auf allen Systemen lauffähig bleiben. Es handelt sich dann meistens um Vektor-Berechnungen in welchen es möglich ist mehrere Operationen gleichzeitig parallel zu berechnen. Das lohnt sich besonders wenn man große Mengen an Daten gleichförmig berechnen muß (zB. Matrizen). Aus dem Grund werden diese Funktionen auch vorallem im Grafik und Sound Bereich benutzt (MMX -> Multi Media Extension).

• Kommutative Optimirung: Der Assembler erlaubt nur Operationen in welchen das Resultat im ersten Operator gespeichert wird. Deshalb muß eine Operation wie
  A = B + C
  zu
  A = B
  A += C
  erweitert werden. Dadurch müssen im Codebaum Zwischenresultate in temporären Variabeln gespeichert werden. Dies kann man aber bei kommutativen (vertauschbaren) Operationen wie + * Add Mul optimieren in dem man die Operanden umkehrt und so die Temporäre Speicherung des Resultats umgeht. "A = C * D + B" ist gleich wie "A = B + C * D".

A = B + C * D

[=] +-- (A)
    |
    +-- [+] +-- (B)
            |
            +-- [*] +-- (C)
                    |
                    +-- (D)

Temp1 = C
Temp1 *= D
A = B
A += Temp1



Optimieren durch

A = C * D + B

[=] +-- (A)
    |
    +-- [+] +-- [*] +-- (C)
            |       |
            |       +-- (D)
            |
            +-- (B)

A = C
A *= D
A += B



hier funktioniert diese Optimierung nicht

A = B - C * D
  ist nicht gleich wie
A = C * D - B

• Distanz zwischen Hauptspeicher Prozessor-Cache und Register: Da nicht der gesamte Arbeitsspeicher im Prozessor gehalten werden kann, muß man berücksichtigen das der RAM-Speicher vom Prozessor (räumlich und zeitlich) weiter entfernt ist als der Prozessor-Cache und dieser wiederum weiter weg als die Register. Um den Cache braucht sich der Entwickler eigentlich nicht direkt zu kümmern, aber das Speichermanagement sollte wenn möglich berücksichtigen das Speicherzugriffe von der Hardware optimiert werden kann. Auch das Betriebsystem hat da ein großen Einfluß. Diese Optimierungen sind allerdings recht komplex und erfordern tiefergehende Kenntnisse über Hardware und Betriebssystem.
• Speicher-Defragmentierung (Garbage Collector): Was der Compiler aber optimieren kann ist das sein Speicherbedarf nicht mit der Zeit zu stark fragmentiert, also wie bei einer Harddisk auch Daten die geschrieben und wieder gelöscht werden den Speicher zerteilen. Den genau wie bei der Harddisk wird der Speicher nicht nur ineffizient genutzt, sonder wird auch langsamer eben weil nicht der ganze Arbeitsspeicher im Prozessor liegen kann.
• Flüchtige Daten: Besonders in der Objektorientierten Programmierung werden sehr häufig Objekte nur kurzfristig erzeugt und schnell wieder verworfen. (Temporäre Variablen werden meistens über den Stack Organisiert, bei Objekten allerdings können Datenmengen zu groß für den Stack sein und werden deshalb über den Hauptspeicher Organisiert.) Diese Daten sind um so flüchtiger, je tiefer Prozeduren verschachtelt sind. Kann der Compiler feststellen welche Daten beständig und welche flüchtig sind, kann er diese getrennt voneinander mit unterschiedlichen Strategien organisieren.
• Statische Speicher-Deklaration in Prozeß/Tread: In einem Prozeß oder Tread in welchem sich Strukturen nie überschneiden können (nie gleichzeitig stattfinden), ist es möglich ihren Speicherbedarf für flüchtige Daten fix zu deklarieren. So können sich mehrere Prozeduren den gleichen festen Speicher teilen. (Diese Optimierung ist bei rekursiven Prozeduren nicht möglich.)

Auch der Programmierer selbst muß bei der Entwicklung von Codes und Algorithmen auf Optimierungen achten, da der Compiler nicht alle Möglichkeiten ausschöpfen kann. Ein Programm ist nicht fähig auf einer intelligenten Ebene Codes zu verbessern, sondern nur auf einer relativ niedrigen logischen Ebene. Auch steigt die Compilierungszeit für jede Optimierung, bei einigen sogar dramatisch.
Ein Beispiel wäre das man auf trigonometrische Sin/Cos/Tan Algorithmen verzichtet und durch Punkt/Kreuz-Produkt Algorithmen ersetzt, da die Grundrechenarten (wie + - * /) viel schneller ausgeführt werden als Sin/Cos/Tan.
Dieses Thema gehört deshalb in den allgemeinen Bereich der Programmierung (Code-Optimierung) oder Algorithmus-Entwicklung, und wird nicht hier in der Compilerentwicklung beschrieben.