Optimierung kann auf verschiedenen Ebenen stattfinden. Typischerweise haben die höheren Ebenen größere Auswirkungen und sind später im Projekt schwieriger zu ändern, da sie erhebliche Änderungen oder eine komplette Neuschreibung erfordern, wenn sie geändert werden müssen. Daher kann die Optimierung in der Regel durch eine Verfeinerung von einer höheren zu einer niedrigeren Ebene erfolgen, wobei die anfänglichen Gewinne größer sind und mit weniger Arbeit erreicht werden, während die späteren Gewinne kleiner sind und mehr Arbeit erfordern. In einigen Fällen hängt die Gesamtleistung jedoch von der Leistung sehr kleiner Teile eines Programms ab, und kleine Änderungen in einem späten Stadium oder die frühzeitige Berücksichtigung von Details auf niedriger Ebene können übergroße Auswirkungen haben. Normalerweise wird die Effizienz während des gesamten Projekts berücksichtigt – auch wenn dies sehr unterschiedlich ist -, aber größere Optimierungen werden oft als eine Verfeinerung betrachtet, die, wenn überhaupt, erst spät vorgenommen wird. Bei länger laufenden Projekten gibt es in der Regel Optimierungszyklen, bei denen die Verbesserung eines Bereichs Einschränkungen in einem anderen aufdeckt, und diese werden in der Regel abgebrochen, wenn die Leistung akzeptabel ist oder die Gewinne zu gering oder zu kostspielig werden.

Da die Leistung Teil der Spezifikation eines Programms ist – ein Programm, das ungewöhnlich langsam ist, ist nicht zweckdienlich: ein Videospiel mit 60 Hz (Bildern pro Sekunde) ist akzeptabel, aber 6 Bilder pro Sekunde sind inakzeptabel ruckelig – ist die Leistung von Anfang an eine Überlegung, um sicherzustellen, dass das System in der Lage ist, eine ausreichende Leistung zu liefern, und frühe Prototypen müssen eine annähernd akzeptable Leistung haben, damit man darauf vertrauen kann, dass das endgültige System (mit Optimierung) eine akzeptable Leistung erreichen wird. Dies wird manchmal in dem Glauben unterlassen, dass Optimierungen immer später vorgenommen werden können, was zu Prototypensystemen führt, die viel zu langsam sind – oft um eine Größenordnung oder mehr – und zu Systemen, die letztendlich scheitern, weil sie architektonisch nicht in der Lage sind, ihre Leistungsziele zu erreichen, wie z.B. der Intel 432 (1981); oder zu Systemen, die jahrelange Arbeit benötigen, um eine akzeptable Leistung zu erreichen, wie z.B. Java (1995), das erst mit HotSpot (1999) eine akzeptable Leistung erreichte. Das Ausmaß, in dem sich die Leistung zwischen Prototyp und Produktionssystem ändert, und die Frage, inwieweit sie sich optimieren lässt, kann eine bedeutende Quelle der Unsicherheit und des Risikos sein.

EntwurfsebeneBearbeiten

Auf der höchsten Ebene kann der Entwurf optimiert werden, um die verfügbaren Ressourcen unter Berücksichtigung der Ziele, Einschränkungen und der erwarteten Nutzung/Last bestmöglich zu nutzen. Das architektonische Design eines Systems hat einen überwältigenden Einfluss auf seine Leistung. Ein System, das an die Netzwerklatenz gebunden ist (wobei die Netzwerklatenz die wichtigste Einschränkung für die Gesamtleistung darstellt), würde beispielsweise so optimiert, dass es möglichst wenige Netzwerkreisen durchführt und im Idealfall nur eine einzige Anfrage (oder gar keine Anfragen, wie bei einem Push-Protokoll) stellt und nicht mehrere Hin- und Rückreisen. Die Wahl des Designs hängt von den Zielen ab: Wenn bei der Entwicklung eines Compilers die schnelle Kompilierung im Vordergrund steht, ist ein One-Pass-Compiler schneller als ein Multi-Pass-Compiler (bei gleichem Arbeitsaufwand), aber wenn die Geschwindigkeit des ausgegebenen Codes das Ziel ist, erfüllt ein langsamerer Multi-Pass-Compiler dieses Ziel besser, auch wenn er selbst länger braucht. Die Wahl der Plattform und der Programmiersprache erfolgt auf dieser Ebene, und ihre Änderung erfordert häufig eine vollständige Neuschreibung, obwohl ein modulares System möglicherweise nur die Neuschreibung einiger Komponenten erlaubt – ein Python-Programm kann beispielsweise leistungsrelevante Abschnitte in C umschreiben. In einem verteilten System erfolgt die Wahl der Architektur (Client-Server, Peer-to-Peer usw.) auf der Entwurfsebene und kann schwer zu ändern sein, insbesondere wenn nicht alle Komponenten synchron ersetzt werden können (z. B,

Algorithmen und DatenstrukturenBearbeiten

Aufgrund eines Gesamtentwurfs ist eine gute Auswahl effizienter Algorithmen und Datenstrukturen sowie eine effiziente Implementierung dieser Algorithmen und Datenstrukturen der nächste Schritt. Nach dem Entwurf beeinflusst die Wahl der Algorithmen und Datenstrukturen die Effizienz mehr als jeder andere Aspekt des Programms. Im Allgemeinen sind Datenstrukturen schwieriger zu ändern als Algorithmen, da eine Datenstrukturannahme und ihre Leistungsannahmen im gesamten Programm verwendet werden, obwohl dies durch die Verwendung abstrakter Datentypen in Funktionsdefinitionen und die Beschränkung der konkreten Datenstrukturdefinitionen auf wenige Stellen minimiert werden kann.

Bei Algorithmen besteht dies in erster Linie darin, sicherzustellen, dass Algorithmen konstant O(1), logarithmisch O(log n), linear O(n) oder in einigen Fällen log-linear O(n log n) in der Eingabe sind (sowohl in Raum als auch in Zeit). Algorithmen mit quadratischer Komplexität O(n2) skalieren nicht, und selbst lineare Algorithmen verursachen Probleme, wenn sie wiederholt aufgerufen werden, und werden in der Regel durch konstante oder logarithmische Algorithmen ersetzt, wenn dies möglich ist.

Abgesehen von der asymptotischen Wachstumsordnung spielen die konstanten Faktoren eine Rolle: Ein asymptotisch langsamerer Algorithmus kann schneller oder kleiner (weil einfacher) sein als ein asymptotisch schnellerer Algorithmus, wenn beide mit kleinen Eingaben konfrontiert sind, was in der Realität der Fall sein kann. Oft wird ein hybrider Algorithmus die beste Leistung erbringen, da sich dieser Kompromiss mit der Größe ändert.

Eine allgemeine Technik zur Verbesserung der Leistung ist die Vermeidung von Arbeit. Ein gutes Beispiel ist die Verwendung eines schnellen Pfads für häufige Fälle, der die Leistung durch Vermeidung unnötiger Arbeit verbessert. So wird beispielsweise für lateinischen Text ein einfacher Textlayout-Algorithmus verwendet und erst bei komplexen Schriften wie Devanagari zu einem komplexen Layout-Algorithmus gewechselt. Eine weitere wichtige Technik ist die Zwischenspeicherung, insbesondere die Memoisierung, die redundante Berechnungen vermeidet. Wegen der Bedeutung der Zwischenspeicherung gibt es in einem System oft viele Ebenen der Zwischenspeicherung, was zu Problemen bei der Speichernutzung und bei der Korrektheit aufgrund veralteter Zwischenspeicher führen kann.

QuelltextebeneBearbeiten

Neben den allgemeinen Algorithmen und ihrer Implementierung auf einer abstrakten Maschine können konkrete Entscheidungen auf Quelltextebene einen erheblichen Unterschied ausmachen. Auf frühen C-Compilern war z. B. while(1) für eine unbedingte Schleife langsamer als for(;;), weil while(1) 1 auswertete und dann einen bedingten Sprung hatte, der prüfte, ob er wahr war, während for (;;) einen unbedingten Sprung hatte. Einige Optimierungen (wie diese) können heutzutage von optimierenden Compilern durchgeführt werden. Dies hängt von der Quellsprache, der Ziel-Maschinensprache und dem Compiler ab und kann sowohl schwer zu verstehen oder vorherzusagen sein als auch sich im Laufe der Zeit ändern; dies ist ein Schlüsselbereich, in dem das Verständnis von Compilern und Maschinencode die Leistung verbessern kann. Schleifeninvariante Code-Bewegung und Rückgabewert-Optimierung sind Beispiele für Optimierungen, die den Bedarf an Hilfsvariablen verringern und sogar zu einer schnelleren Leistung führen können, indem sie Umweg-Optimierungen vermeiden.

Build-EbeneBearbeiten

Zwischen der Quellcode- und der Kompilierebene können Direktiven und Build-Flags verwendet werden, um die Leistungsoptionen im Quellcode bzw. im Compiler zu optimieren, wie z. B. die Verwendung von Präprozessor-Definitionen zur Deaktivierung nicht benötigter Softwarefunktionen, die Optimierung für bestimmte Prozessormodelle oder Hardwarefunktionen oder die Vorhersage von Verzweigungen. Quellcode-basierte Software-Distributionssysteme wie BSD’s Ports und Gentoo’s Portage können diese Form der Optimierung nutzen.

Compile levelEdit

Die Verwendung eines optimierenden Compilers stellt in der Regel sicher, dass das ausführbare Programm mindestens so weit optimiert ist, wie der Compiler vorhersagen kann.

Assembler-EbeneBearbeiten

Auf der untersten Ebene kann das Schreiben von Code in einer Assemblersprache, die für eine bestimmte Hardwareplattform entwickelt wurde, den effizientesten und kompaktesten Code ergeben, wenn der Programmierer das gesamte Repertoire an Maschinenbefehlen nutzt. Viele Betriebssysteme, die auf eingebetteten Systemen eingesetzt werden, wurden aus diesem Grund traditionell in Assembler-Code geschrieben. Programme (mit Ausnahme sehr kleiner Programme) werden aus Zeit- und Kostengründen nur selten von Anfang bis Ende in Assembler geschrieben. Die meisten werden von einer Hochsprache in Assembler kompiliert und von dort aus von Hand optimiert. Wenn Effizienz und Größe weniger wichtig sind, können große Teile in einer Hochsprache geschrieben werden.

Mit moderneren optimierenden Compilern und der größeren Komplexität aktueller CPUs ist es schwieriger, effizienteren Code zu schreiben als den, den der Compiler erzeugt, und nur wenige Projekte benötigen diesen „ultimativen“ Optimierungsschritt.

Ein Großteil des heute geschriebenen Codes soll auf so vielen Maschinen wie möglich laufen. Infolgedessen nutzen Programmierer und Compiler nicht immer die Vorteile der effizienteren Befehle neuerer CPUs oder die Eigenheiten älterer Modelle. Außerdem kann Assembler-Code, der für einen bestimmten Prozessor ohne solche Anweisungen optimiert wurde, auf einem anderen Prozessor immer noch suboptimal sein, was eine andere Optimierung des Codes voraussetzt.

Anstatt in Assemblersprache zu schreiben, verwenden Programmierer heute typischerweise einen Disassembler, um die Ausgabe eines Compilers zu analysieren und den High-Level-Quellcode so zu ändern, dass er effizienter kompiliert werden kann, oder zu verstehen, warum er ineffizient ist.

LaufzeitBearbeiten

Just-in-Time-Compiler können auf der Grundlage von Laufzeitdaten angepassten Maschinencode erzeugen, was mit einem Kompilierungs-Overhead verbunden ist. Diese Technik geht auf die frühesten Engines mit regulären Ausdrücken zurück und hat sich mit Java HotSpot und V8 für JavaScript weit verbreitet. In einigen Fällen kann die adaptive Optimierung eine Laufzeitoptimierung durchführen, die über die Möglichkeiten statischer Compiler hinausgeht, indem sie die Parameter dynamisch an die tatsächliche Eingabe oder andere Faktoren anpasst.

Die profilgeführte Optimierung ist eine AOT-Kompilierungsoptimierungstechnik, die auf Laufzeitprofilen basiert und einem statischen „Durchschnittsfall“ analog zur dynamischen Technik der adaptiven Optimierung ähnelt.

Selbstmodifizierender Code kann sich als Reaktion auf Laufzeitbedingungen selbst verändern, um den Code zu optimieren; dies war bei Assembler-Programmen üblicher.

Einige CPU-Designs können einige Optimierungen zur Laufzeit durchführen. Einige Beispiele sind Out-of-Order-Ausführung, spekulative Ausführung, Befehlspipelines und Verzweigungsvorhersagen. Compiler können dem Programm helfen, diese CPU-Funktionen zu nutzen, zum Beispiel durch Befehlsplanung.

Plattformabhängige und -unabhängige OptimierungenBearbeiten

Die Code-Optimierung kann auch allgemein in plattformabhängige und plattformunabhängige Techniken eingeteilt werden. Während letztere auf den meisten oder allen Plattformen wirksam sind, nutzen plattformabhängige Techniken spezifische Eigenschaften einer Plattform oder sind auf Parameter angewiesen, die von der einzelnen Plattform oder sogar vom einzelnen Prozessor abhängen. Daher kann es erforderlich sein, verschiedene Versionen desselben Codes für verschiedene Prozessoren zu schreiben oder zu erstellen. Im Falle der Optimierung auf Kompilierungsebene sind plattformunabhängige Techniken generische Techniken (wie z. B. Schleifenabrollung, Reduzierung von Funktionsaufrufen, speichereffiziente Routinen, Reduzierung von Bedingungen usw.), die sich auf die meisten CPU-Architekturen in ähnlicher Weise auswirken. Ein gutes Beispiel für eine plattformunabhängige Optimierung ist die innere for-Schleife, bei der beobachtet wurde, dass eine Schleife mit einer inneren for-Schleife mehr Berechnungen pro Zeiteinheit durchführt als eine Schleife ohne diese oder eine mit einer inneren while-Schleife. Im Allgemeinen dienen diese dazu, die Gesamtlänge des Anweisungspfads zu reduzieren, der für die Fertigstellung des Programms erforderlich ist, und/oder den gesamten Speicherverbrauch während des Prozesses zu verringern. Andererseits beinhalten plattformabhängige Techniken Befehlsplanung, Parallelität auf Befehlsebene, Parallelität auf Datenebene, Cache-Optimierungstechniken (d.h. Parameter, die sich zwischen verschiedenen Plattformen unterscheiden), und die optimale Befehlsplanung kann sogar auf verschiedenen Prozessoren derselben Architektur unterschiedlich sein.