Programmoptimierung - Program optimization

In der Informatik ist Programmoptimierung , Codeoptimierung oder Softwareoptimierung der Prozess der Modifizierung eines Softwaresystems, um einen Teil davon effizienter zu machen oder weniger Ressourcen zu verbrauchen. Im Allgemeinen kann ein Computerprogramm so optimiert werden, dass es schneller ausgeführt wird oder mit weniger Speicher oder anderen Ressourcen arbeiten kann oder weniger Strom verbraucht.

Allgemein

Obwohl das Wort "Optimierung" die gleiche Wurzel wie "optimal" hat, ist es selten, dass der Optimierungsprozess ein wirklich optimales System erzeugt. Ein System kann im Allgemeinen nicht absolut optimal gemacht werden, sondern nur in Bezug auf eine gegebene Qualitätsmetrik, die im Gegensatz zu anderen möglichen Metriken stehen kann. Als Ergebnis ist das optimierte System typischerweise nur in einer Anwendung oder für eine Zielgruppe optimal. Man könnte die Zeit, die ein Programm benötigt, um eine Aufgabe auszuführen, auf den Preis reduzieren, dass es mehr Speicher verbraucht. In einer Anwendung, bei der Speicherplatz knapp ist, könnte man bewusst einen langsameren Algorithmus wählen , um weniger Speicher zu verbrauchen. Oft gibt es kein Design „one size fits all“ , die in allen Fällen gut funktioniert, so Ingenieure machen Kompromisse , die Attribute von größtem Interesse zu optimieren. Außerdem ist der Aufwand, um eine Software komplett optimal zu machen, die nicht weiter verbessert werden kann, fast immer höher, als für den daraus resultierenden Nutzen vertretbar ist; so kann der Optimierungsprozess angehalten werden, bevor eine vollständig optimale Lösung erreicht ist. Glücklicherweise kommen die größten Verbesserungen oft schon früh im Prozess.

Selbst bei einer bestimmten Qualitätsmetrik (z. B. Ausführungsgeschwindigkeit) verbessern die meisten Optimierungsmethoden nur das Ergebnis; sie haben nicht den Anspruch, eine optimale Ausgabe zu erzeugen. Superoptimierung ist der Prozess, um wirklich optimale Ergebnisse zu finden.

Optimierungsstufen

Die Optimierung kann auf mehreren Ebenen erfolgen. Normalerweise haben die höheren Ebenen größere Auswirkungen und sind später in einem Projekt schwieriger zu ändern, was erhebliche Änderungen oder eine vollständige Neuschreibung erforderlich macht, wenn sie geändert werden müssen. Somit kann die Optimierung typischerweise über eine Verfeinerung von höher zu niedriger fortschreiten, wobei anfängliche Gewinne größer sind und mit weniger Arbeit erreicht werden und spätere Gewinne kleiner sind und mehr Arbeit erfordern. In einigen Fällen hängt die Gesamtleistung jedoch von der Leistung sehr untergeordneter Teile eines Programms ab, und kleine Änderungen zu einem späteren Zeitpunkt oder eine frühzeitige Berücksichtigung von untergeordneten Details können übergroße Auswirkungen haben. In der Regel wird die Effizienz während eines Projekts berücksichtigt – obwohl dies erheblich variiert –, aber eine größere Optimierung wird oft als Verfeinerung angesehen, die, wenn überhaupt, spät durchgeführt werden sollte. 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 normalerweise eingeschränkt, 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 unbrauchbar langsam ist, ist es nicht geeignet: Ein Videospiel mit 60 Hz (Frames-per-Sekunde) ist akzeptabel, aber 6 Frames-per-Sekunde ist inakzeptabel abgehackt – Leistung ist von Anfang an eine Überlegung, um sicherzustellen, dass das System in der Lage ist, ausreichende Leistung zu liefern, und frühe Prototypen müssen eine ungefähr akzeptable Leistung aufweisen, damit das endgültige System (mit Optimierung) eine akzeptable Leistung erzielen wird. Dies wird manchmal aus der Überzeugung weggelassen, dass eine Optimierung immer später erfolgen kann, was zu viel zu langsamen Prototypsystemen führt – oft um eine Größenordnung oder mehr – und zu Systemen, die letztendlich ausfallen, weil sie ihre Leistungsziele architektonisch nicht erreichen können, wie z als Intel 432 (1981); oder solche, die jahrelange Arbeit benötigen, um eine akzeptable Leistung zu erzielen, wie Java (1995), das nur mit HotSpot (1999) eine akzeptable Leistung erzielte . Das Ausmaß, in dem sich die Leistung zwischen Prototyp und Produktionssystem ändert und wie optimierungsfähig es ist, kann eine erhebliche Unsicherheits- und Risikoquelle darstellen.

Designebene

Auf der höchsten Ebene kann das Design optimiert werden, um die verfügbaren Ressourcen unter gegebenen Zielen, Einschränkungen und erwarteter Nutzung/Last bestmöglich zu nutzen. Das architektonische Design eines Systems beeinflusst in überwältigendem Maße seine Leistung. Zum Beispiel würde ein System, das an die Netzwerklatenz gebunden ist (wobei die Netzwerklatenz die Haupteinschränkung für die Gesamtleistung ist), optimiert werden, um Netzwerkausflüge zu minimieren, und im Idealfall eine einzelne Anfrage (oder keine Anfragen, wie bei einem Push-Protokoll ) statt mehrerer Anfragen stellen Rundfahrten. Die Wahl des Designs hängt von den Zielen ab: Wenn beim Entwerfen eines Compilers eine schnelle Kompilierung oberste Priorität hat, ist ein Compiler mit einem Durchlauf schneller als ein Compiler mit mehreren Durchläufen (gleiche Arbeit vorausgesetzt), aber wenn die Geschwindigkeit des Ausgabecodes das Ziel ist, ein langsamerer Multi-Pass-Compiler erfüllt das Ziel besser, obwohl er selbst länger dauert. Die Auswahl der Plattform und der Programmiersprache erfolgt auf dieser Ebene, und deren Änderung erfordert häufig ein vollständiges Neuschreiben, obwohl ein modulares System möglicherweise nur das Neuschreiben einiger Komponenten ermöglicht – zum Beispiel kann ein Python-Programm leistungskritische Abschnitte in C neu schreiben System, die Wahl der Architektur ( Client-Server , Peer-to-Peer usw.) erfolgt auf Entwurfsebene und kann schwierig zu ändern sein, insbesondere wenn nicht alle Komponenten synchron ersetzt werden können (z. B. alte Clients).

Algorithmen und Datenstrukturen

Bei einem Gesamtdesign folgt eine gute Auswahl an effizienten Algorithmen und Datenstrukturen und eine effiziente Implementierung dieser Algorithmen und Datenstrukturen. Nach dem Design 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 Einschränkung der konkreten Datenstrukturdefinitionen minimiert werden kann an ein paar Stellen.

Bei Algorithmen besteht dies in erster Linie darin, sicherzustellen, dass Algorithmen konstant O(1), logarithmisch O(log n ), linear O( n ) oder in manchen Fällen log-linear O( n log n ) in der Eingabe sind (beide im Raum und Zeit). Algorithmen mit quadratischer Komplexität O( n 2 ) können nicht skaliert werden, und selbst lineare Algorithmen verursachen Probleme, wenn sie wiederholt aufgerufen werden, und werden normalerweise, wenn möglich, durch Konstante oder Logarithmus ersetzt.

Jenseits der asymptotischen Wachstumsordnung sind die konstanten Faktoren von Bedeutung: Ein asymptotisch langsamerer Algorithmus kann schneller oder kleiner sein (weil einfacher) als ein asymptotisch schnellerer Algorithmus, wenn beide mit kleinen Eingaben konfrontiert sind, was in der Realität der Fall sein kann. Häufig bietet ein Hybridalgorithmus die beste Leistung, da sich dieser Kompromiss mit der Größe ändert.

Eine allgemeine Technik zur Leistungssteigerung besteht darin, Arbeit zu vermeiden. Ein gutes Beispiel ist die Verwendung eines schnellen Pfads für häufige Fälle, der die Leistung verbessert, indem unnötige Arbeit vermieden wird. Wenn Sie beispielsweise einen einfachen Textlayoutalgorithmus für lateinischen Text verwenden, wechseln Sie nur zu einem komplexen Layoutalgorithmus für komplexe Skripte wie Devanagari . Eine weitere wichtige Technik ist das Caching, insbesondere die Memoisierung , die redundante Berechnungen vermeidet. Aufgrund der Bedeutung des Cachings gibt es in einem System oft viele Ebenen des Cachings, was zu Problemen bei der Speichernutzung und Korrektheitsproblemen bei veralteten Caches führen kann.

Quellcode-Ebene

Über allgemeine Algorithmen und deren Implementierung auf einer abstrakten Maschine hinaus können konkrete Entscheidungen auf Quellcodeebene einen signifikanten Unterschied machen. Bei frühen C-Compilern while(1)war es beispielsweise langsamer als for(;;)bei einer unbedingten Schleife, weil while(1)1 ausgewertet wurde und dann einen bedingten Sprung hatte, der prüfte, ob er wahr ist, während for (;;)ein unbedingter Sprung durchgeführt wurde. Einige Optimierungen (wie diese) können heutzutage durch die Optimierung von Compilern durchgeführt werden . Dies hängt von der Quellsprache, der Zielmaschinensprache und dem Compiler ab und kann sowohl schwer zu verstehen oder vorherzusagen sein und sich im Laufe der Zeit ändern. Dies ist ein wichtiger Ort, an dem das Verständnis von Compilern und Maschinencode die Leistung verbessern kann. Schleifeninvariante Codebewegung und Rückgabewertoptimierung sind Beispiele für Optimierungen, die den Bedarf an Hilfsvariablen reduzieren und sogar zu einer schnelleren Leistung führen können, indem Umwegoptimierungen vermieden werden.

Build-Level

Zwischen der Quelle und der Kompilierung Ebene, Richtlinien und Build - Flags können jeweils in der Quellcode und Compiler abzustimmen Leistungsoptionen verwendet werden, wie die Verwendung von Präprozessor definiert zu deaktivieren Sie nicht benötigte Software - Funktionen, die Optimierung für bestimmte Prozessormodelle oder Hardware - Fähigkeiten oder die Vorhersage Verzweigung , zum Beispiel. Quellbasierte Softwareverteilungssysteme wie BSD 's Ports und Gentoo 's Portage können von dieser Form der Optimierung profitieren.

Kompilierungsebene

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

Montageebene

Auf der untersten Ebene kann das Schreiben von Code unter Verwendung einer Assemblersprache , der für eine bestimmte Hardwareplattform entwickelt wurde, den effizientesten und kompaktesten Code erzeugen, wenn der Programmierer das volle Repertoire an Maschinenbefehlen ausnutzt . Viele Betriebssysteme, die auf eingebetteten Systemen verwendet werden, wurden aus diesem Grund traditionell in Assembler-Code geschrieben. Programme (außer sehr kleine Programme) werden aufgrund des damit verbundenen Zeit- und Kostenaufwands selten von Anfang bis Ende in der Assemblierung geschrieben. Die meisten werden von einer Hochsprache bis zur Assemblierung herunterkompiliert und von dort von Hand optimiert. Wenn Effizienz und Größe weniger wichtig sind, können große Teile in einer Hochsprache geschrieben werden.

Mit moderneren Optimierungscompilern und der höheren Komplexität neuerer CPUs ist es schwieriger, effizienteren Code zu schreiben, als der Compiler generiert, und nur wenige Projekte benötigen diesen "ultimativen" Optimierungsschritt.

Viel Code, der heute geschrieben wird, soll auf so vielen Maschinen wie möglich laufen. Infolgedessen nutzen Programmierer und Compiler nicht immer die effizienteren Anweisungen neuerer CPUs oder Eigenheiten älterer Modelle. Außerdem kann ein für einen bestimmten Prozessor abgestimmter Assemblercode ohne Verwendung solcher Befehle auf einem anderen Prozessor immer noch suboptimal sein, da eine andere Abstimmung des Codes erwartet wird.

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

Laufzeit

Just-in-Time- Compiler können auf der Grundlage von Laufzeitdaten auf Kosten des Kompilierungsaufwands benutzerdefinierten Maschinencode erstellen. Diese Technik stammt aus den frühesten Engines für reguläre Ausdrücke und ist mit Java HotSpot und V8 für JavaScript weit verbreitet. In einigen Fällen kann die adaptive Optimierung in der Lage sein, eine Laufzeitoptimierung durchzuführen , die die Fähigkeit von statischen Compilern überschreitet, indem Parameter gemäß der tatsächlichen Eingabe oder anderen Faktoren dynamisch angepasst werden.

Die profilgesteuerte Optimierung ist eine AOT-Kompilierungsoptimierungstechnik basierend auf Laufzeitprofilen und ähnelt einem statischen "Durchschnittsfall"-Analogon der dynamischen Technik der adaptiven Optimierung.

Selbstmodifizierender Code kann sich als Reaktion auf Laufzeitbedingungen ändern, um den Code zu optimieren; Dies war in Assemblerprogrammen üblicher.

Einige CPU-Designs können zur Laufzeit einige Optimierungen durchführen. Einige Beispiele umfassen Ausführung außerhalb der Reihenfolge , spekulative Ausführung , Anweisungspipelines und Verzweigungsprädiktoren . Compiler können dem Programm dabei helfen, diese CPU-Eigenschaften zu nutzen, beispielsweise durch Befehlsplanung .

Plattformabhängige und unabhängige Optimierungen

Codeoptimierung kann auch grob in plattformabhängige und plattformunabhängige Techniken kategorisiert werden. Während letztere auf den meisten oder allen Plattformen wirksam sind, verwenden plattformabhängige Techniken spezifische Eigenschaften einer Plattform oder verlassen sich auf Parameter, die von der einzelnen Plattform oder sogar vom einzelnen Prozessor abhängen. Es kann daher erforderlich sein, verschiedene Versionen desselben Codes für verschiedene Prozessoren zu schreiben oder zu produzieren. Im Fall der Optimierung auf Kompilierungsebene sind plattformunabhängige Techniken beispielsweise generische Techniken (wie Schleifenabrollen , Reduzierung von Funktionsaufrufen, speichereffiziente Routinen, Reduzierung von Bedingungen usw.), die sich in ähnlicher Weise auf die meisten CPU-Architekturen auswirken Weg. Ein gutes Beispiel für plattformunabhängige Optimierung wurde mit der inneren for-Schleife gezeigt, wo beobachtet wurde, dass eine Schleife mit einer inneren for-Schleife mehr Berechnungen pro Zeiteinheit durchführt als eine Schleife ohne sie oder eine mit einer inneren while-Schleife. Im Allgemeinen dienen diese die Gesamt zu reduzieren Anweisung Pfadlänge erforderlich , um das Programm zu beenden und / oder die gesamte Speichernutzung während des Prozesses zu reduzieren. Auf der anderen Seite beinhalten plattformabhängige Techniken Befehlsplanung, Parallelität auf Befehlsebene, Parallelität auf Datenebene, Cache-Optimierungstechniken (dh Parameter, die sich zwischen verschiedenen Plattformen unterscheiden), und die optimale Befehlsplanung kann sogar auf verschiedenen Prozessoren des Systems unterschiedlich sein gleiche Architektur.

Festigkeitsreduzierung

Rechenaufgaben können auf verschiedene Weise mit unterschiedlicher Effizienz durchgeführt werden. Eine effizientere Version mit gleichwertiger Funktionalität wird als Festigkeitsreduzierung bezeichnet . Betrachten Sie beispielsweise das folgende C- Code-Snippet, dessen Absicht darin besteht, die Summe aller ganzen Zahlen von 1 bis N zu erhalten : 

int i, sum = 0;
for (i = 1; i <= N; ++i) {
  sum += i;
}
printf("sum: %d\n", sum);

Dieser Code kann (kein arithmetischer Überlauf vorausgesetzt ) mit einer mathematischen Formel wie folgt umgeschrieben werden: 

int sum = N * (1 + N) / 2;
printf("sum: %d\n", sum);

Die Optimierung, die manchmal automatisch von einem optimierenden Compiler durchgeführt wird, besteht darin, eine Methode ( einen Algorithmus ) auszuwählen, die recheneffizienter ist, während die gleiche Funktionalität beibehalten wird. Siehe algorithmische Effizienz für eine Diskussion einiger dieser Techniken. Eine deutliche Leistungssteigerung kann jedoch oft durch Entfernen von Fremdfunktionen erreicht werden.

Optimierung ist nicht immer ein offensichtlicher oder intuitiver Prozess. Im obigen Beispiel könnte die "optimierte" Version tatsächlich langsamer sein als die ursprüngliche Version, wenn N ausreichend klein wäre und die spezielle Hardware zufällig viel schneller bei der Durchführung von Additions- und Schleifenoperationen als bei Multiplikation und Division ist.

Kompromisse

In einigen Fällen beruht die Optimierung jedoch auf der Verwendung ausgefeilterer Algorithmen, der Verwendung von „Sonderfällen“ und speziellen „Tricks“ und dem Ausführen komplexer Kompromisse. Ein "voll optimiertes" Programm ist möglicherweise schwieriger zu verstehen und kann daher mehr Fehler enthalten als nicht optimierte Versionen. Abgesehen davon, dass offensichtliche Antimuster eliminiert werden, verringern einige Optimierungen auf Codeebene die Wartbarkeit.

Die Optimierung konzentriert sich im Allgemeinen auf die Verbesserung nur eines oder zweier Leistungsaspekte: Ausführungszeit, Speichernutzung, Speicherplatz, Bandbreite, Stromverbrauch oder andere Ressourcen. Dies erfordert normalerweise einen Kompromiss – bei dem ein Faktor auf Kosten anderer optimiert wird. Beispielsweise verbessert das Erhöhen der Cachegröße die Laufzeitleistung, erhöht aber auch den Speicherverbrauch. Andere häufige Kompromisse sind Codeklarheit und Prägnanz.

Es gibt Fälle, in denen der Programmierer, der die Optimierung durchführt, entscheiden muss, die Software für einige Operationen besser zu machen, aber auf Kosten anderer Operationen weniger effizient. Diese Kompromisse können manchmal nicht technischer Natur sein – etwa wenn ein Wettbewerber ein Benchmark- Ergebnis veröffentlicht hat, das übertroffen werden muss, um den kommerziellen Erfolg zu verbessern, aber möglicherweise mit der Last einhergeht, die normale Nutzung der Software weniger effizient zu machen. Solche Veränderungen werden manchmal scherzhaft als Pessimierungen bezeichnet .

Engpässe

Die Optimierung kann das Auffinden eines Engpasses in einem System beinhalten – einer Komponente, die der begrenzende Faktor für die Leistung ist. In Bezug auf Code ist dies oft ein Hotspot  – ein kritischer Teil des Codes, der der Hauptverbraucher der benötigten Ressource ist – obwohl es ein anderer Faktor sein kann, wie z. B. E/A-Latenz oder Netzwerkbandbreite.

In der Informatik folgt der Ressourcenverbrauch oft einer Form der Potenzgesetzverteilung , und das Pareto-Prinzip kann auf die Ressourcenoptimierung angewendet werden, indem beobachtet wird, dass 80 % der Ressourcen typischerweise von 20 % der Operationen verwendet werden. In der Softwareentwicklung ist es oft eine bessere Näherung, dass 90% der Ausführungszeit eines Computerprogramms mit der Ausführung von 10% des Codes verbracht wird (in diesem Zusammenhang als 90/10-Gesetz bekannt).

Komplexere Algorithmen und Datenstrukturen funktionieren mit vielen Elementen gut, während einfache Algorithmen eher für kleine Datenmengen geeignet sind – die Einrichtung, die Initialisierungszeit und die konstanten Faktoren des komplexeren Algorithmus können den Vorteil aufwiegen, und daher ein hybrider oder adaptiver Algorithmus Algorithmus kann schneller sein als jeder einzelne Algorithmus. Ein Leistungsprofiler kann verwendet werden, um Entscheidungen darüber einzugrenzen, welche Funktionalität zu welchen Bedingungen passt.

In einigen Fällen kann das Hinzufügen von mehr Speicher dazu beitragen, dass ein Programm schneller ausgeführt wird. Zum Beispiel liest ein Filterprogramm normalerweise jede Zeile und filtert und gibt diese Zeile sofort aus. Dadurch wird nur genügend Speicher für eine Zeile verwendet, die Leistung ist jedoch aufgrund der Latenz jedes Datenträgerlesevorgangs in der Regel schlecht. Das Zwischenspeichern des Ergebnisses ist ähnlich effektiv, erfordert jedoch auch einen größeren Speicherverbrauch.

Wann optimieren

Die Optimierung kann die Lesbarkeit verringern und Code hinzufügen, der nur zur Verbesserung der Leistung verwendet wird . Dies kann Programme oder Systeme verkomplizieren, wodurch sie schwieriger zu warten und zu debuggen sind. Daher wird häufig am Ende der Entwicklungsphase eine Optimierung oder ein Performance-Tuning durchgeführt .

Donald Knuth hat die folgenden zwei Aussagen zur Optimierung gemacht:

"Wir sollten kleine Effizienzgewinne vergessen, sagen wir in 97% der Fälle: vorzeitige Optimierung ist die Wurzel allen Übels. Aber wir sollten unsere Chancen bei diesen kritischen 3% nicht verpassen."

(Er schrieb das Zitat einige Jahre später auch Tony Hoare zu , obwohl dies ein Fehler gewesen sein könnte, da Hoare bestreitet, den Ausdruck geprägt zu haben.)

"In etablierten Engineering-Disziplinen wird eine leicht zu erreichende Verbesserung von 12% nie als marginal angesehen und ich glaube, dass die gleiche Sichtweise im Software-Engineering vorherrschen sollte."

"Vorzeitige Optimierung" ist ein Ausdruck, der verwendet wird, um eine Situation zu beschreiben, in der ein Programmierer Leistungsüberlegungen das Design eines Codestücks beeinflussen lässt. Dies kann zu einem nicht so sauberen Design oder fehlerhaftem Code führen, da der Code durch die Optimierung kompliziert wird und der Programmierer durch die Optimierung abgelenkt wird.

Bei der Entscheidung, einen bestimmten Teil des Programms zu optimieren, sollte immer das Gesetz von Amdahl berücksichtigt werden: Die Auswirkungen auf das Gesamtprogramm hängen sehr stark davon ab, wie viel Zeit tatsächlich in diesem bestimmten Teil verbracht wird, was aus dem Blick auf den Code nicht immer klar ist ohne Leistungsanalyse .

Ein besserer Ansatz ist daher zunächst zu entwerfen, Code aus dem Design und dann Profil / Benchmark den resultierenden Code zu sehen , welche Teile optimiert werden sollen. Ein einfaches und elegantes Design ist in dieser Phase oft einfacher zu optimieren, und die Profilerstellung kann unerwartete Leistungsprobleme aufdecken, die durch eine vorzeitige Optimierung nicht behoben worden wären.

In der Praxis ist es oft notwendig, beim ersten Entwurf von Software Leistungsziele im Auge zu behalten, aber der Programmierer wägt die Ziele von Entwurf und Optimierung ab.

Moderne Compiler und Betriebssysteme sind so effizient, dass die beabsichtigten Leistungssteigerungen oft ausbleiben. Beispielsweise führt das Zwischenspeichern von Daten auf Anwendungsebene, die wiederum auf Betriebssystemebene zwischengespeichert werden, nicht zu Verbesserungen bei der Ausführung. Trotzdem kommt es selten vor, dass der Programmierer fehlgeschlagene Optimierungen aus dem Produktionscode entfernt. Es stimmt auch, dass Fortschritte in der Hardware in den meisten Fällen potenzielle Verbesserungen zunichte machen werden, aber der verschleiernde Code wird in der Zukunft bestehen bleiben, lange nachdem sein Zweck negiert wurde.

Makros

Die Optimierung während der Codeentwicklung durch Makros nimmt in verschiedenen Sprachen unterschiedliche Formen an.

In einigen prozeduralen Sprachen wie C und C++ werden Makros mithilfe von Token-Ersetzung implementiert. Heutzutage Inline - Funktionen können eingesetzt werden Typ sichere Alternative in vielen Fällen. In beiden Fällen kann der Inline-Funktionsrumpf dann weiteren Kompilierungszeitoptimierungen durch den Compiler unterzogen werden, einschließlich konstanter Faltung , wodurch einige Berechnungen zur Kompilierzeit verschoben werden können.

In vielen funktionalen Programmiersprachen werden Makros unter Verwendung von Parse-Bäumen/abstrakten Syntax-Bäumen zur Parse-Zeit implementiert, wodurch sie sicherer zu verwenden sind. Da in vielen Fällen Interpretation verwendet wird, ist dies ein Weg, um sicherzustellen, dass solche Berechnungen nur zur Analysezeit durchgeführt werden, und manchmal der einzige Weg.

Lisp hat diesen Makrostil hervorgebracht, und solche Makros werden oft als "Lisp-ähnliche Makros" bezeichnet. Ein ähnlicher Effekt kann durch die Verwendung von Template-Metaprogrammierung in C++ erzielt werden .

In beiden Fällen wird die Arbeit in die Kompilierzeit verschoben. Der Unterschied zwischen C- Makros auf der einen Seite und Lisp-ähnlichen Makros und C++- Template-Metaprogrammierung auf der anderen Seite besteht darin, dass die letzteren Tools die Durchführung beliebiger Berechnungen zur Kompilierzeit/Parse-Zeit ermöglichen, während die Erweiterung von C- Makros keine ausführt Berechnung und verlässt sich auf die Fähigkeit des Optimierers, sie auszuführen. Darüber hinaus unterstützen C- Makros Rekursion oder Iteration nicht direkt , sind also nicht Turing abgeschlossen .

Wie bei jeder Optimierung ist es jedoch oft schwierig vorherzusagen, wo solche Tools die größte Wirkung haben, bevor ein Projekt abgeschlossen ist.

Automatisierte und manuelle Optimierung

Hauptartikel: Compiler optimieren

Siehe auch Kategorie:Compileroptimierungen

Die Optimierung kann von Compilern automatisiert oder von Programmierern durchgeführt werden. Die Gewinne sind normalerweise für lokale Optimierungen begrenzt und für globale Optimierungen größer. Normalerweise besteht die mächtigste Optimierung darin, einen überlegenen Algorithmus zu finden .

Die Optimierung eines ganzen Systems wird normalerweise von Programmierern durchgeführt, da sie für automatisierte Optimierer zu komplex ist. In dieser Situation ändern Programmierer oder Systemadministratoren explizit Code, damit das Gesamtsystem besser funktioniert. Obwohl es eine bessere Effizienz erzielen kann, ist es weitaus teurer als automatisierte Optimierungen. Da viele Parameter die Programmleistung beeinflussen, ist der Programmoptimierungsraum groß. Metaheuristiken und maschinelles Lernen werden verwendet, um die Komplexität der Programmoptimierung zu adressieren.

Verwenden Sie einen Profiler (oder Leistungsanalysator ), um die Abschnitte des Programms zu finden, die die meisten Ressourcen beanspruchen – den Engpass . Programmierer glauben manchmal, dass sie eine klare Vorstellung davon haben, wo der Engpass liegt, aber die Intuition ist häufig falsch. Die Optimierung eines unwichtigen Codeabschnitts trägt normalerweise wenig zur Verbesserung der Gesamtleistung bei.

Wenn der Engpass lokalisiert ist, beginnt die Optimierung normalerweise mit einem Überdenken des im Programm verwendeten Algorithmus. In den meisten Fällen kann ein bestimmter Algorithmus speziell auf ein bestimmtes Problem zugeschnitten werden, was eine bessere Leistung als ein generischer Algorithmus ergibt. Zum Beispiel wird das Sortieren einer riesigen Liste von Elementen normalerweise mit einer Quicksort- Routine erledigt, die einer der effizientesten generischen Algorithmen ist. Wenn jedoch ein Merkmal der Artikel verwertbar ist (z. B. sind sie bereits in einer bestimmten Reihenfolge angeordnet), kann eine andere Methode oder sogar eine maßgeschneiderte Sortierroutine verwendet werden.

Nachdem der Programmierer einigermaßen sicher ist, dass der beste Algorithmus ausgewählt ist, kann die Codeoptimierung beginnen. Schleifen können entrollt werden (für einen geringeren Schleifen-Overhead, obwohl dies oft zu einer geringeren Geschwindigkeit führen kann, wenn es den CPU-Cache überlastet ), können möglichst kleine Datentypen verwendet werden, kann Integer-Arithmetik anstelle von Gleitkomma verwendet werden, und so weiter . (Siehe Artikel zur algorithmischen Effizienz für diese und andere Techniken.)

Leistungsengpässe können eher auf Sprachbeschränkungen als auf im Programm verwendete Algorithmen oder Datenstrukturen zurückzuführen sein. Manchmal kann ein kritischer Teil des Programms in einer anderen Programmiersprache neu geschrieben werden , die einen direkteren Zugriff auf die zugrunde liegende Maschine ermöglicht. Beispielsweise ist es bei sehr hohen Sprachen wie Python üblich , Module in C geschrieben zu haben, um eine höhere Geschwindigkeit zu erzielen. Programme, die bereits in C geschrieben wurden, können Module enthalten, die in Assembler geschrieben wurden . In D geschriebene Programme können den Inline-Assembler verwenden .

Das Umschreiben von Abschnitten "lohnt sich" unter diesen Umständen aufgrund einer allgemeinen " Faustregel ", die als 90/ 10-Gesetz bekannt ist und besagt, dass 90% der Zeit für 10% des Codes und nur für 10% der Zeit aufgewendet wird in den restlichen 90 % des Codes. Wenn also nur ein kleiner Teil des Programms intellektuell optimiert wird, kann dies einen großen Einfluss auf die Gesamtgeschwindigkeit haben – wenn der/die richtige(n) Teil(e) gefunden werden kann.

Die manuelle Optimierung hat manchmal den Nebeneffekt, dass die Lesbarkeit beeinträchtigt wird. Daher sollten Codeoptimierungen sorgfältig dokumentiert werden (vorzugsweise mithilfe von Inline-Kommentaren) und ihre Auswirkungen auf die zukünftige Entwicklung bewertet werden.

Das Programm, das eine automatisierte Optimierung durchführt, wird als Optimierer bezeichnet . Die meisten Optimierer sind in Compiler eingebettet und arbeiten während der Kompilierung. Optimierer können den generierten Code oft an bestimmte Prozessoren anpassen.

Heute beschränken sich automatisierte Optimierungen fast ausschließlich auf die Compiler-Optimierung . Da Compileroptimierungen jedoch normalerweise auf einen festen Satz eher allgemeiner Optimierungen beschränkt sind, besteht eine beträchtliche Nachfrage nach Optimierern, die Beschreibungen von Problem- und sprachspezifischen Optimierungen akzeptieren können, was es einem Ingenieur ermöglicht, benutzerdefinierte Optimierungen zu spezifizieren. Werkzeuge, die Optimierungsbeschreibungen akzeptieren, werden als Programmtransformationssysteme bezeichnet und beginnen, auf reale Softwaresysteme wie C++ angewendet zu werden.

Einige Hochsprachen ( Eiffel , Esterel ) optimieren ihre Programme durch die Verwendung einer Zwischensprache .

Grid Computing oder Distributed Computing zielt darauf ab, das gesamte System zu optimieren, indem Aufgaben von Computern mit hoher Auslastung auf Computer mit Leerlaufzeit verschoben werden.

Zeitaufwand für die Optimierung

Manchmal kann die Zeit, die benötigt wird, um darin eine Optimierung vorzunehmen, ein Problem sein.

Durch die Optimierung von bestehendem Code werden normalerweise keine neuen Funktionen hinzugefügt, und schlimmer noch, es können neue Fehler in zuvor funktionierendem Code hinzugefügt werden (wie es bei jeder Änderung der Fall sein könnte). Da manuell optimierter Code manchmal weniger „Lesbarkeit“ als nicht optimierter Code aufweisen kann, kann sich die Optimierung auch auf die Wartbarkeit auswirken. Optimierung hat ihren Preis und es ist wichtig sicherzustellen, dass sich die Investition lohnt.

Ein automatischer Optimierer (oder optimierender Compiler , ein Programm, das Code-Optimierung durchführt) muss möglicherweise selbst optimiert werden, entweder um die Effizienz seiner Zielprogramme weiter zu verbessern oder seinen eigenen Betrieb zu beschleunigen. Eine Kompilierung mit "eingeschalteter" Optimierung dauert in der Regel länger, obwohl dies meist nur bei größeren Programmen ein Problem darstellt.

Insbesondere für Just-in-Time-Compiler ist die Leistung der Laufzeitkompilierungskomponente , die zusammen mit ihrem Zielcode ausgeführt wird, der Schlüssel zur Verbesserung der Gesamtausführungsgeschwindigkeit.

Verweise

  • Jon Bentley : Effiziente Programme schreiben , ISBN  0-13-970251-2 .
  • Donald Knuth : Die Kunst der Computerprogrammierung

Externe Links