Kapitel 1. Ein Überblick über die Optimierung
Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: translation-feedback@oreilly.com
Die Welt hat einen unglaublichen Appetit auf Berechnungen. Egal, ob der Code, den du schreibst, auf einer Uhr, einem Telefon, einem Tablet, einer Workstation, einem Supercomputer oder einem weltumspannenden Netzwerk von Rechenzentren läuft - es gibt viele Programme, die die ganze Zeit über auf Hochtouren laufen müssen. Es reicht also vielleicht nicht aus, die coole Idee in deinem Kopf in Codezeilen umzusetzen. Es reicht vielleicht nicht einmal aus, den Code nach Fehlern zu durchkämmen, bis er immer korrekt läuft. Deine Anwendung ist vielleicht auf der Hardware, die sich deine Kunden leisten können, zu langsam. Dein Hardware-Team hat dir vielleicht einen winzigen Prozessor aufgehalst, um die Stromverbrauchsziele zu erreichen. Vielleicht kämpfst du mit einem Konkurrenten um den Durchsatz oder die Bilder pro Sekunde. Oder du baust auf planetarischer Ebene und hast ein wenig Angst, die Ozeane zum Kochen zu bringen. Hier kommt die Optimierung ins Spiel.
In diesem Buch geht es um Optimierung - genauer gesagt um die Optimierung von C++-Programmen, mit besonderem Augenmerk auf die Verhaltensmuster von C++-Code. Einige der Techniken in diesem Buch sind auch auf andere Programmiersprachen anwendbar, aber ich habe nicht versucht, die Techniken auf universelle Weise zu erklären. Einige Optimierungen, die bei C++-Code wirksam sind, haben keine Wirkung oder sind in anderen Sprachen einfach nicht möglich.
In diesem Buch geht es darum, korrekten Code, der bewährte Methoden des C++-Designs verkörpert, in korrekten Code umzuwandeln, der immer noch gutes C++-Design verkörpert, aber auch schneller läuft und weniger Ressourcen auf so ziemlich jedem Computer verbraucht. Viele Optimierungsmöglichkeiten ergeben sich, weil einige C++-Funktionen bei gelegentlicher Verwendung langsam laufen und viele Ressourcen verbrauchen. Solcher Code ist zwar korrekt, aber unüberlegt, wenn man nur ein wenig Allgemeinwissen über moderne Mikroprozessoren oder ein wenig Nachdenken über die Kosten verschiedener C++-Konstrukte hat. Andere Optimierungen sind möglich, weil C++ die Speicherverwaltung und das Kopieren von Daten genau kontrolliert.
In diesem Buch geht es nicht darum, mühsam Assembler-Unterprogramme zu kodieren, Taktzyklen zu zählen oder zu lernen, wie viele Befehle Intels neuestes Silizium-Styling gleichzeitig ausführen kann. Es gibt Entwickler/innen, die mehrere Jahre lang mit einer einzigen Plattform arbeiten (die Xbox ist ein gutes Beispiel) und die Zeit und das Bedürfnis haben, diese dunklen Künste zu beherrschen. Die große Mehrheit der Entwickler/innen zielt jedoch auf Handys, Tablets oder PCs ab, die eine unendliche Vielfalt an Mikroprozessorchips enthalten - von denen einige noch nicht einmal entwickelt wurden. Entwickler/innen von Software, die in Produkte eingebettet ist, haben es auch mit einer Vielzahl von Prozessoren mit sehr unterschiedlichen Architekturen zu tun. Der Versuch, das Arkanum der Prozessoren zu lernen, wird die meisten Entwickler/innen verrückt machen und sie vor Unentschlossenheit lähmen. Ich empfehle diesen Weg nicht. Eine prozessorabhängige Optimierung ist für die meisten Anwendungen, die per Definition auf verschiedenen Prozessoren laufen müssen, einfach nicht zielführend.
In diesem Buch geht es auch nicht darum, den schnellsten betriebssystemabhängigen Weg zu erlernen, um eine Operation unter Windows, Linux, OS X und jedem eingebetteten Betriebssystem auszuführen. Es geht darum, was du in C++ tun kannst, auch mit der C++ Standardbibliothek. Wenn du aus C++ ausbrichst, um eine Optimierung durchzuführen, kann es für deine Kollegen schwierig werden, den optimierten Code zu prüfen oder zu kommentieren. Das sollte man nicht auf die leichte Schulter nehmen.
In diesem Buch geht es darum zu lernen , wie man optimiert. Jeder statische Katalog von Techniken oder Funktionen ist zum Scheitern verurteilt, wenn neue Algorithmen entdeckt werden und neue Sprachfunktionen verfügbar werden. Stattdessen zeigt dieses Buch anhand von Beispielen, wie der Code schrittweise verbessert werden kann, damit der Leser mit dem Code-Tuning-Prozess vertraut wird und die Einstellung entwickelt, die die Optimierung fruchtbar macht.
In diesem Buch geht es auch um die Optimierung des Kodierungsprozesses. Entwickler/innen, die auf die Laufzeitkosten ihres Codes achten, können von Anfang an effizienten Code schreiben. Mit etwas Übung dauert das Schreiben von schnellem Code in der Regel nicht länger als das Schreiben von langsamem Code.
Schließlich geht es in diesem Buch darum, Wunder zu vollbringen; darum, eine Änderung einzutragen und später einen Kollegen überrascht ausrufen zu hören: "Wow, was ist passiert? Er ist einfach angesprungen. Wer hat da was repariert?" Optimierung ist etwas, das du auch für deinen Status als Entwickler/in und deinen persönlichen Stolz auf dein Handwerk tun kannst.
Optimierung ist Teil der Softwareentwicklung
Optimierung ist eine Kodierungsaktivität. In traditionellen Softwareentwicklungsprozessen findet die Optimierung nach der Fertigstellung des Codes statt, während der Integrations- und Testphase eines Projekts, wenn die Leistung des gesamten Programms beobachtet werden kann. In einem agilen Entwicklungsprozess können ein oder mehrere Sprints der Optimierung gewidmet werden, nachdem eine Funktion mit Leistungszielen kodiert wurde oder wenn dies erforderlich ist, um die Leistungsziele zu erreichen.
Das Ziel der Optimierung ist es, das Verhalten eines korrekten Programms so zu verbessern, dass es auch die Anforderungen der Kunden an Geschwindigkeit, Durchsatz, Speicherplatzbedarf, Stromverbrauch usw. erfüllt. Die Optimierung ist also genauso wichtig für den Entwicklungsprozess wie die Codierung von Funktionen. Eine inakzeptabel schlechte Leistung ist für die Nutzer/innen das gleiche Problem wie Bugs und fehlende Funktionen.
Ein wichtiger Unterschied zwischen Fehlerbehebung und Leistungsoptimierung ist, dass die Leistung eine kontinuierliche Variable ist. Eine Funktion ist entweder kodiert oder nicht. Ein Fehler ist entweder vorhanden oder nicht vorhanden. Die Leistung kann jedoch sehr schlecht oder sehr gut sein oder irgendwo dazwischen liegen. Die Optimierung ist auch ein iterativer Prozess, bei dem jedes Mal, wenn der langsamste Teil des Programms verbessert wird, ein neuer langsamster Teil auftaucht.
Die Optimierung ist eine experimentelle Wissenschaft, die mehr als andere Codierungsaufgaben eine wissenschaftliche Denkweise erfordert. Um bei der Optimierung erfolgreich zu sein, muss man das Verhalten beobachten, auf der Grundlage dieser Beobachtungen überprüfbare Hypothesen aufstellen und Experimente durchführen, die zu Messungen führen, die die Hypothesen entweder bestätigen oder widerlegen. Erfahrene Entwickler/innen glauben oft, dass sie gültige Erfahrungen und Intuitionen über optimalen Code haben. Aber wenn sie ihre Intuitionen nicht häufig testen, werden sie sich häufig irren. Meine persönlichen Erfahrungen beim Schreiben der Testprogramme für dieses Buch brachten mehrere Ergebnisse zutage, die meinen Intuitionen widersprachen. Experimentieren statt Intuition ist ein Thema dieses Buches.
Optimierung ist wirkungsvoll
Für Entwickler ist es schwierig, die Auswirkungen einzelner Programmierentscheidungen auf die Gesamtleistung eines großen Programms zu erkennen. Daher enthalten praktisch alle vollständigen Programme erhebliche Möglichkeiten zur Optimierung. Selbst Code, der von erfahrenen Teams mit viel Zeit erstellt wurde, kann oft um einen Faktor von 30 % bis 100 % beschleunigt werden. Bei eiligeren oder weniger erfahrenen Teams habe ich Leistungsverbesserungen um das 3- bis 10-fache gesehen. Eine Beschleunigung um mehr als das 10-fache durch eine Optimierung des Codes ist weniger wahrscheinlich. Die Wahl eines besseren Algorithmus oder einer besseren Datenstruktur kann jedoch den Unterschied ausmachen, ob eine Funktion eingesetzt werden kann oder unzumutbar langsam ist.
Optimieren ist in Ordnung
Viele Abhandlungen über Optimierung beginnen mit einer ernsten Warnung: Lass es! Optimiere nicht, und wenn du optimieren musst, dann tu es erst am Ende des Projekts und optimiere nicht mehr als nötig. Der berühmte Informatiker Donald Knuth sagte zum Beispiel über die Optimierung:
Wir sollten kleine Effizienzgewinne, sagen wir etwa 97 Prozent der Zeit, vergessen: Vorzeitige Optimierung ist die Wurzel allen Übels.
Donald Knuth, Structured Programming with go to Statements, ACM Computing Surveys 6(4), Dezember 1974, S. 268. CiteSeerX: 10.1.1.103.6084
Oder dies von William A. Wulf:
Im Namen der Effizienz werden mehr Rechensünden begangen (ohne dass diese unbedingt erreicht werden) als aus irgendeinem anderen Grund - einschließlich blinder Dummheit.
"A Case Against the GOTO", Proceedings of the 25th National ACM Conference (1972): 796
Der Ratschlag, nicht zu optimieren, hat sich zu einer Weisheit entwickelt, die selbst von vielen erfahrenen Programmierern nicht hinterfragt wird, die reflexartig zusammenzucken, wenn das Gespräch auf Leistungstuning kommt. Meiner Meinung nach wird dieser Ratschlag zu oft zynisch weitergegeben, um schwache Entwicklungsgewohnheiten zu entschuldigen und den geringen Aufwand an Analyse zu vermeiden, der zu einem wesentlich schnelleren Code führen könnte. Ich glaube auch, dass die unkritische Annahme dieser Ratschläge für viele verschwendete CPU-Zyklen, viele frustrierte Arbeitsstunden und zu viel Zeit für die Überarbeitung von Code verantwortlich ist, der von Anfang an effizienter hätte sein müssen.
Mein Rat ist weniger dogmatisch. Es ist in Ordnung, zu optimieren. Es ist in Ordnung, effiziente Programmier-Idiome zu lernen und sie ständig anzuwenden, auch wenn du nicht weißt, welcher Code leistungsrelevant ist. Diese Idiome sind gutes C++. Du wirst von deinen Mitschülerinnen und Mitschülern nicht beleidigt sein, weil du sie benutzt hast. Wenn dich jemand fragt, warum du nicht etwas "Einfaches" und Ineffizientes geschrieben hast, kannst du sagen: "Es kostet genauso viel Zeit, effizienten Code zu schreiben wie langsamen, verschwenderischen Code. Warum sollte sich jemand absichtlich dafür entscheiden, ineffizienten Code zu schreiben?"
Es ist nicht in Ordnung, wenn du tagelang keine Fortschritte machst, weil du dich nicht entscheiden kannst, welcher Algorithmus besser ist, obwohl du nicht weißt, dass es darauf ankommt. Es ist nicht in Ordnung, wochenlang etwas in Assembler zu programmieren, weil du vermutest, dass es zeitkritisch sein könnte, und dann die ganze Arbeit zu ruinieren, indem du deinen Code als Funktion aufrufst, obwohl der C++-Compiler ihn für dich hätte inlinen können. Nicht in Ordnung ist es, von deinem Team zu verlangen, dass sie die Hälfte ihres Programms in C programmieren, weil "jeder weiß, dass C schneller ist", obwohl du weder weißt, dass C wirklich schneller ist, noch dass C++ nicht schnell ist. Mit anderen Worten: Alle bewährten Methoden der Softwareentwicklung gelten nach wie vor. Optimierung ist keine Ausrede, um die Regeln zu brechen.
Es ist nicht in Ordnung, einen Haufen zusätzlicher Zeit für die Optimierung zu verschwenden, wenn du nicht weißt, wo du Leistungsprobleme hast. In Kapitel 3 wird die 90/10-Regel eingeführt, die besagt, dass nur etwa 10 % des Codes eines Programms leistungsrelevant sind. Es ist also weder notwendig noch hilfreich, jede Zeile eines Programms zu ändern, um die Leistung des Programms zu verbessern. Da nur 10 % des Programms einen signifikanten Einfluss auf die Leistung haben, stehen die Chancen schlecht, dass du zufällig einen guten Startpunkt wählst. In Kapitel 3 findest du Tools, mit denen du herausfinden kannst, wo die Hot Spots im Code liegen.
Als ich an der Uni war, warnten meine Professoren, dass optimale Algorithmen höhere Anlaufkosten haben können als einfache. Sie sollten daher nur für große Datensätze verwendet werden. Auch wenn das für einige esoterische Algorithmen vielleicht zutrifft, habe ich die Erfahrung gemacht, dass optimale Algorithmen für einfache Such- und Sortieraufgaben nur wenig Zeit zum Einrichten benötigen und schon bei kleinen Datensätzen eine Leistungssteigerung bringen.
Mir wurde auch geraten, Programme mit dem Algorithmus zu entwickeln, der am einfachsten zu programmieren ist, und dann zurückzugehen und ihn zu optimieren, wenn das Programm zu langsam läuft. Das ist zwar unbestreitbar ein guter Rat, um weiter voranzukommen, aber wenn du eine optimale Suche oder Sortierung ein paar Mal programmiert hast, ist es nicht schwieriger, sie zum Laufen zu bringen als einen langsameren Algorithmus. Du kannst es auch gleich beim ersten Mal richtig machen und nur einen Algorithmus debuggen.
Der größte Feind von Leistungsverbesserungen ist wahrscheinlich das Allgemeinwissen. So weiß zum Beispiel "jeder", dass ein optimaler Sortieralgorithmus in O(n log n) Zeit läuft, wobei n die Größe des Datensatzes ist (siehe "Zeitkosten von Algorithmen" für einen kurzen Überblick über die Big-O-Notation und die Zeitkosten). Diese Weisheit ist insofern wertvoll, als sie Entwickler/innen davon abhält, zu glauben, dass ihre O(n2)-Einfügungssortierung optimal ist. Sie ist aber nicht so gut, wenn sie sie davon abhält, in der Literatur nachzuschauen, um herauszufinden, dass Radixsort mit O(n logr n) schneller ist (wobei r die Radix oder die Anzahl der Sortierbereiche ist), dass Flashsort bei zufällig verteilten Daten eine noch schnellere O(n)-Leistung hat oder dass Quicksort, das nach der Weisheit als Benchmark für andere Sortierungen gilt, im schlimmsten Fall eine schmerzhaft schlechte O(n2)-Leistung hat. Aristoteles sagte, dass Frauen weniger Zähne haben als Männer(Die Geschichte der Tiere, Buch II, Teil 1). Diese Weisheit hielt sich 1.500 Jahre lang, bis jemand neugierig genug war, die Zähne in ein paar Mündern zu zählen. Das Gegenmittel gegen überlieferte Weisheiten ist die wissenschaftliche Methode in Form von Experimenten. In Kapitel 3 geht es um Instrumente zur Messung der Softwareleistung und um Experimente zur Validierung von Optimierungen.
In der Welt der Softwareentwicklung gibt es auch die Weisheit, dass Optimierung nicht relevant ist. Die Argumentation lautet: Selbst wenn dein Code heute langsam läuft, bringt jedes neue Jahr schnellere Prozessoren, die deine Leistungsprobleme im Laufe der Zeit kostenlos lösen. Wie die meisten überlieferten Weisheiten war auch dieser Gedanke nie wirklich wahr. In den 1980er und 1990er Jahren, als Desktop-Computer und eigenständige Anwendungen die Entwicklungsszene beherrschten und sich die Geschwindigkeit von Single-Core-Prozessoren alle 18 Monate verdoppelte, mag sie wahr gewesen sein. Aber während die heutigen Multicore-Prozessoren insgesamt immer leistungsfähiger werden, verbessert sich die Leistung der einzelnen Kerne nur allmählich oder nimmt manchmal sogar ab. Programme müssen heute auch auf mobilen Plattformen laufen, wo Akkulaufzeit und Wärmeableitung die Befehlsausführungsrate einschränken. Außerdem bringt die Zeit zwar neue Kunden mit schnelleren Computern, aber die Leistung der bestehenden Hardware wird dadurch nicht verbessert. Das einzige, was mit der Zeit zunimmt, sind die Arbeitslasten der bestehenden Kunden. Der einzige Geschwindigkeitszuwachs, den ein bestehender Kunde jemals von deinem Unternehmen erhalten wird, ist die Optimierung der nachfolgenden Versionen. Die Optimierung hält dein Programm frisch.
Eine Nanosekunde hier, eine Nanosekunde dort
Eine Milliarde hier, eine Milliarde da, schon bald geht es um richtiges Geld.
Wird häufig fälschlicherweise Senator Everett Dirkson (1898-1969) zugeschrieben, der behauptet, dies nie gesagt zu haben, obwohl er zugibt, viele ähnliche Dinge gesagt zu haben
Desktop-Computer sind erstaunlich schnell. Sie können jede Nanosekunde (oder besser) einen neuen Befehl senden. Das heißt, alle 10-9 Sekunden! Es ist verführerisch zu glauben, dass Optimierung keine Rolle spielen kann, wenn ein Computer so schnell ist.
Das Problem bei dieser Denkweise ist, dass sich überflüssige Befehle umso schneller anhäufen, je schneller der Prozessor ist. Wenn 50 % der Befehle, die ein Programm ausführt, unnötig sind, kann man das Programm doppelt so schnell machen, indem man sie entfernt, egal wie schnell jeder unnötige Befehl ausgeführt wird.
Deine Kolleginnen und Kollegen, die sagen "Effizienz spielt keine Rolle", meinen vielleicht auch, dass sie für bestimmte Anwendungen, die an menschliche Reaktionen gebunden sind und auf bereits sehr schnellen Desktop-Computern laufen, keine Rolle spielt. Auf kleinen eingebetteten und mobilen Prozessoren mit Speicher-, Leistungs- oder Geschwindigkeitsbeschränkungen ist Effizienz sehr wichtig. Sie ist auch bei Servern wichtig, die auf großen Computern laufen. Man könnte auch sagen, dass Effizienz für jede Anwendung wichtig ist, die um begrenzte Ressourcen (Speicher, Strom, CPU-Zyklen) kämpfen muss. Effizienz ist auch immer dann wichtig, wenn die Arbeitslast so groß ist, dass sie auf mehrere Computer verteilt werden muss. In diesem Fall kann die Effizienz den Unterschied zwischen den Ausgaben für 100 Server oder Cloud-Instanzen und 500 oder 1.000 ausmachen.
In 50 Jahren hat sich die Computerleistung um sechs Größenordnungen verbessert. Und trotzdem reden wir hier über Optimierung. Wenn die Vergangenheit ein Anhaltspunkt ist, wird die Optimierung wahrscheinlich noch lange Zeit relevant bleiben.
Zusammenfassung der Strategien zur Optimierung von C++ Code
Versammle die üblichen Verdächtigen.
Capt. Louis Renault (Claude Rains), Casablanca, 1942
Der Funktionsmix von C++ bietet ein Kontinuum an Implementierungsmöglichkeiten, das von einfacher Automatisierung und Ausdrucksstärke auf der einen Seite bis hin zu einer immer feineren Kontrolle der Leistung auf der anderen Seite reicht. Dieses Maß an Wahlmöglichkeiten macht es möglich, C++-Programme auf die Leistungsanforderungen abzustimmen.
In C++ gibt es die "üblichen Verdächtigen" für Optimierungs-Hotspots, darunter Funktionsaufrufe, Speicherzuweisung und Schleifen. Im Folgenden findest du eine zusammenfassende Liste von Möglichkeiten, die Leistung von C++-Programmen zu verbessern, die auch einen Überblick über dieses Buch gibt. Die Ratschläge sind erschreckend einfach. Alles davon wurde schon einmal veröffentlicht. Aber natürlich steckt der Teufel im Detail. Die Beispiele und Heuristiken in diesem Buch werden dir helfen, Optimierungsmöglichkeiten besser zu erkennen, wenn du sie siehst.
Verwende einen besseren Compiler, verwende deinen Compiler besser
C++-Compiler sind komplexe Software-Artefakte. Jeder Compiler trifft unterschiedliche Entscheidungen darüber, welcher Maschinencode für C++-Anweisungen erzeugt werden soll. Sie sehen unterschiedliche Möglichkeiten zur Optimierung. Sie erzeugen unterschiedliche ausführbare Dateien aus demselben Quellcode. Wenn du das letzte Quäntchen Leistung aus deinem Code herauskitzeln willst, kann es sich lohnen, mehrere Compiler auszuprobieren, um zu sehen, ob einer eine schnellere ausführbare Datei für deinen Code erzeugt.
Der wichtigste Ratschlag für die Wahl des C++-Compilers ist, einen C++11-konformen Compiler zu verwenden. C++11 implementiert rValue-Referenzen und Move-Semantik, die viele Kopiervorgänge eliminieren, die in früheren C++-Versionen unvermeidlich waren. (Die Move-Semantik wird im Abschnitt "Implementierung der Move-Semantik" behandelt).
Manchmal bedeutet die Verwendung eines besseren Compilers , dass du deinen Compiler besser nutzen kannst. Wenn dir deine Anwendung zum Beispiel träge vorkommt, solltest du in den Compiler-Schaltern nachsehen, ob der Optimierer aktiviert ist. Das scheint ganz offensichtlich zu sein, aber ich kann gar nicht zählen, wie oft ich diesen Ratschlag schon Leuten gegeben habe, die anschließend zugaben, dass ihr Code tatsächlich viel schneller lief, wenn die Optimierung eingeschaltet war. In vielen Fällen brauchst du nicht weiter zu gehen. Der Compiler allein kann dein Programm um ein Vielfaches schneller machen, wenn du ihn nett fragst.
Standardmäßig schalten die meisten Compiler keine Optimierungen ein. Die Kompilierzeiten sind ohne den Optimierungspass etwas kürzer. In den 1990er Jahren war das eine große Sache, aber heute sind Compiler und Computer so schnell, dass die zusätzlichen Kosten unbedeutend sind. Auch die Fehlersuche ist einfacher, wenn der Optimierer ausgeschaltet ist, weil der Ausführungsfluss genau dem Quellcode folgt. Der Optimierer kann Code aus Schleifen herausnehmen, einige Funktionsaufrufe entfernen und einige Variablen ganz streichen. Einige Compiler geben überhaupt keine Debugsymbole aus, wenn die Optimierung eingeschaltet ist. Andere Compiler sind großzügiger, aber es kann eine Herausforderung sein, den Ablauf des Programms im Debugger zu beobachten, um zu verstehen, was das Programm macht. Bei vielen Compilern können einzelne Optimierungen in einem Debug-Build ein- und ausgeschaltet werden, ohne dass das Debugging zu sehr beeinträchtigt wird. Allein das Einschalten des Funktions-Inlinings kann erhebliche Auswirkungen auf ein C++-Programm haben, denn zum guten C++-Stil gehört es, viele kleine Mitgliedsfunktionen zu schreiben, um auf die Mitgliedsvariablen jeder Klasse zuzugreifen.
Die Dokumentation eines C++-Compilers enthält eine ausführliche Beschreibung der verfügbaren Optimierungsflags und Pragmas. Diese Dokumentation ist wie das Benutzerhandbuch, das mit einem neuen Auto geliefert wird. Du kannst in dein neues Auto einsteigen und es fahren, ohne das Handbuch zu lesen, aber es enthält viele Informationen, die dir helfen können, dieses große, komplizierte Werkzeug effektiver zu nutzen.
Wenn du das Glück hast, für die x86-Architektur unter Windows oder Linux zu entwickeln, hast du die Wahl zwischen mehreren ausgezeichneten Compilern, die sehr aktiv entwickelt werden. Microsoft hat in den fünf Jahren, bevor dieses Buch geschrieben wurde, drei Versionen von Visual C++ herausgebracht. Der GCC veröffentlicht mehr als eine Version pro Jahr.
Anfang 2016 gab es einen vernünftigen Konsens darüber, dass Intels C++ Compiler sowohl unter Linux als auch unter Windows den engsten Code erzeugt, dass der GNU C++ Compiler GCC zwar weniger leistungsfähig ist, aber die Standards hervorragend einhält, und dass Microsofts Visual C++ dazwischen liegt. Ich würde dir gerne bei der Entscheidungsfindung helfen, indem ich eine kleine Tabelle erstelle, die besagt, dass Intel C++ so und so viele Prozent schneller ist als GCC, aber das hängt von deinem Code ab und davon, wer gerade eine verbesserte Version herausgebracht hat. Intel C++ kostet über tausend Dollar, aber du kannst es 30 Tage lang kostenlos testen. Es gibt kostenlose Express-Versionen von Visual C++. Unter Linux ist der GCC immer kostenlos. Es ist nicht teuer, ein kleines Experiment durchzuführen und jeden Compiler für deinen Code auszuprobieren, um zu sehen, ob einer davon einen Leistungsvorteil bietet.
Bessere Algorithmen verwenden
Der größte Erfolg bei der Optimierung ist die Wahl eines optimalen Algorithmus. Optimierungsmaßnahmen können die Leistung eines Programms dramatisch verbessern. Sie können den Code beschleunigen, der vorher träge schien, so wie ein Upgrade deines PCs die Anwendungen schneller macht. Leider verbessern die meisten Optimierungen die Leistung höchstens um einen konstanten Faktor, genau wie die Aufrüstung deines PCs. Viele Optimierungen bringen eine Verbesserung von 30 % bis 100 %. Wenn du Glück hast, kannst du deine Leistung verdreifachen. Aber ein Quantensprung in der Leistung ist unwahrscheinlich - es sei denn, du kannst einen effizienteren Algorithmus ausfindig machen.
Es ist töricht, heldenhaft zu versuchen, einen schlechten Algorithmus zu optimieren. Das Erlernen und Anwenden optimaler Such- und Sortieralgorithmen ist ein breiter Weg zu optimalem Code. Eine ineffiziente Such- oder Sortierroutine kann die Laufzeit eines Programms komplett dominieren. Eine Optimierung des Codes verkürzt die Laufzeit um einen konstanten Faktor. Der Wechsel zu einem optimalen Algorithmus kann die Laufzeit um einen Faktor verkürzen, der umso größer ist, je größer dein Datensatz ist. Selbst bei kleinen Datensätzen mit einem Dutzend Elementen kann eine optimale Suche oder Sortierung eine Menge Zeit sparen, wenn die Daten häufig durchsucht werden. Kapitel 5, Algorithmen optimieren, enthält einige Hinweise dazu, wie optimale Algorithmen aussehen.
Optimale Algorithmen gibt es in allen Größenordnungen, von kompakten kleinen Berechnungen in geschlossener Form über enge Suchfunktionen für Schlüsselwörter bis hin zu komplexen Datenstrukturen und umfangreichen Programmen. Es gibt viele hervorragende Bücher zu diesem Thema. Ganze Karrieren können damit verbracht werden, es zu studieren. Ich bedaure, dass ich das Thema der optimalen Algorithmen in diesem Buch nur kurz anreißen kann.
"Optimierungsmuster " deckt mehrere wichtige Techniken zur Leistungsverbesserung ab; dazu gehören die Vorberechnung (Verlagerung von Berechnungen von der Laufzeit auf die Link-, Kompilier- oder Entwurfszeit), die träge Berechnung (Verlagerung von Berechnungen auf den Punkt, an dem ein manchmal ungenutztes Ergebnis tatsächlich benötigt wird) und das Zwischenspeichern (Speichern und Wiederverwenden teurer Berechnungen). Kapitel 7, Optimize Hot Statements, enthält viele Beispiele für diese Techniken in der Praxis.
Bessere Bibliotheken nutzen
Die Standard C++ Template- und Laufzeitbibliotheken, die mit einem C++ Compiler geliefert werden, müssen wartbar, allgemein und sehr robust sein. Es mag für Entwickler/innen überraschend sein, dass diese Bibliotheken nicht unbedingt auf Geschwindigkeit getrimmt sind. Noch überraschender ist, dass selbst nach 30 Jahren C++ die Bibliotheken, die mit kommerziellen C++-Compilern geliefert werden, immer noch Fehler enthalten und möglicherweise nicht dem aktuellen C++-Standard oder sogar dem Standard entsprechen, der bei der Veröffentlichung des Compilers in Kraft war. Das erschwert es, Optimierungen zu messen oder zu empfehlen, und macht jede Optimierungserfahrung, die Entwickler/innen zu haben glauben, nicht übertragbar. Kapitel 8, Bessere Bibliotheken verwenden, behandelt diese Themen.
Die Beherrschung der C++ Standardbibliothek ist eine wichtige Fähigkeit für optimierende Entwickler. Dieses Buch enthält Empfehlungen für Algorithmen zum Suchen und Sortieren(Kapitel 9, Optimize Searching and Sorting), optimale Idiome für die Verwendung von Containerklassen(Kapitel 10, Optimize Data Structures), I/O(Kapitel 11, Optimize I/O), Gleichzeitigkeit(Kapitel 12, Optimize Concurrency) und Speicherverwaltung(Kapitel 13, Optimize Memory Management).
Es gibt Open-Source-Bibliotheken für wichtige Funktionen wie die Speicherverwaltung (siehe "High-Performance Memory Manager"), die ausgefeilte Implementierungen bieten, die schneller und leistungsfähiger sein können als die C++-Laufzeitbibliothek eines Herstellers. Der Vorteil dieser alternativen Bibliotheken ist, dass sie einfach in ein bestehendes Projekt integriert werden können und eine sofortige Geschwindigkeitsverbesserung ermöglichen.
Es gibt viele öffentlich verfügbare Bibliotheken, u. a. vom Boost-Projekt und Google Code, die Bibliotheken für Dinge wie I/O, Windowing, String-Handling (siehe "Eine neuartige String-Implementierung übernehmen") und Gleichzeitigkeit (siehe "Gleichzeitigkeits-Bibliotheken") bereitstellen, die die Standardbibliotheken nicht einfach ersetzen, sondern eine bessere Leistung und zusätzliche Funktionen bieten. Diese Bibliotheken erhalten einen Teil ihres Geschwindigkeitsvorteils dadurch, dass sie andere Kompromisse eingehen als die Standardbibliotheken.
Schließlich ist es möglich, eine projektspezifische Bibliothek zu entwickeln, die einige der Sicherheits- und Robustheitsanforderungen der Standardbibliothek aufhebt und dafür einen Geschwindigkeitsvorteil bietet. All diese Themen werden in Kapitel 8, Bessere Bibliotheken verwenden, behandelt.
Funktionsaufrufe sind in mehrfacher Hinsicht teuer (siehe "Kosten der Funktionsaufrufe"). Gute Funktionsbibliotheken stellen Funktionen zur Verfügung, die das Idiom der Verwendung dieser APIs widerspiegeln, damit der Benutzer die grundlegendsten Funktionen nicht unnötig häufig aufrufen muss. Eine API, die Zeichen abruft und nur die Funktion get_char()
zur Verfügung stellt, erfordert zum Beispiel, dass der Benutzer für jedes benötigte Zeichen einen Funktionsaufruf tätigt. Wenn die API auch eine get_buffer()
Funktion bereitstellt, kann sie den Aufwand vermeiden, für jedes Zeichen eine Funktion aufzurufen.
Funktions- und Klassenbibliotheken sind gute Orte, um die Komplexität zu verstecken, die manchmal mit hochentwickelten Programmen einhergeht. Bibliotheken sollten deinem Programm die Kosten für den Aufruf zurückzahlen, indem sie die Arbeit mit maximaler Effizienz erledigen. Bibliotheksfunktionen befinden sich häufig am Ende von tief verschachtelten Aufrufketten, wo der Effekt der verbesserten Leistung besonders groß ist.
Reduziere die Speicherzuweisung und das Kopieren
Die Reduzierung der Aufrufe in den Speichermanager ist eine so effektive Optimierung, dass ein Entwickler ein erfolgreicher Optimierer sein kann, wenn er nur diesen einen Trick kennt. Während die Kosten der meisten C++-Sprachfunktionen höchstens ein paar Anweisungen betragen, werden die Kosten für jeden Aufruf des Speichermanagers in Tausenden von Anweisungen gemessen.
Weil Strings ein so wichtiger (und kostspieliger) Teil vieler C++-Programme sind, habe ich ihnen ein ganzes Kapitel als Fallstudie zur Optimierung gewidmet. Kapitel 4, Optimize String Use: Eine Fallstudie stellt viele Optimierungskonzepte im vertrauten Kontext des Umgangs mit Strings vor und motiviert sie. Kapitel 6, Optimize Dynamically Allocated Variables (Dynamisch zugewiesene Variablen optimieren), widmet sich der Reduzierung der Kosten für die dynamische Speicherzuweisung, ohne auf nützliche C++-Programmieridiome wie Strings und Standardbibliothekscontainer zu verzichten.
Ein einziger Aufruf einer Funktion zum Kopieren von Puffern kann auch Tausende von Zyklen verbrauchen. Weniger Kopiervorgänge sind daher ein offensichtlicher Weg, um deinen Code zu beschleunigen. Ein Großteil der Kopiervorgänge findet in Verbindung mit der Speicherzuweisung statt, so dass die Behebung des einen den anderen oft überflüssig macht. Andere Brennpunkte für Kopiervorgänge sind Konstruktoren und Zuweisungsoperatoren sowie Ein- und Ausgaben. Kapitel 6, Optimize Dynamically Allocated Variables (Dynamisch zugewiesene Variablen optimieren) behandelt dieses Thema.
Berechnung entfernen
Abgesehen von der Zuweisung und den Funktionsaufrufen sind die Kosten für eine einzelne C++-Anweisung in der Regel unbedeutend. Aber wenn man denselben Code eine Million Mal in einer Schleife oder jedes Mal, wenn ein Programm ein Ereignis verarbeitet, ausführt, ist das plötzlich eine große Sache. Die meisten Programme haben eine oder mehrere Hauptschleifen zur Verarbeitung von Ereignissen und eine oder mehrere Funktionen, die Zeichen verarbeiten. Diese Schleifen zu identifizieren und zu optimieren, ist fast immer sinnvoll. In Kapitel 7, Optimize Hot Statements, findest du einige Tipps, wie du häufig ausgeführten Code findest. Du kannst darauf wetten, dass er sich immer in einer Schleife befindet.
Die Optimierungsliteratur enthält eine Fülle von Techniken zur effizienten Nutzung einzelner C++-Anweisungen. Viele Programmierer glauben, dass das Wissen um diese Tricks das A und O der Optimierung ist. Das Problem bei dieser Denkweise ist, dass die Entfernung von ein oder zwei Speicherzugriffen keinen messbaren Unterschied in der Gesamtleistung ausmacht, es sei denn, der Code ist extrem heiß (wird häufig ausgeführt). Kapitel 3, Leistung messen, enthält Techniken, mit denen du herausfinden kannst, welche Teile eines Programms häufig ausgeführt werden, bevor du versuchst, den Rechenaufwand an diesen Stellen zu verringern.
Es ist auch so, dass moderne C++-Compiler diese lokalen Verbesserungen wirklich hervorragend finden. Entwickler sollten daher nicht versuchen, eine große Codebasis zu optimieren, indem sie jedes Vorkommen von i++
in ++i
ändern, alle Schleifen abrollen und jedem Kollegen atemlos erklären, was genau Duffs Gerät ist und warum es so cool ist. Trotzdem werfe ich in Kapitel 7, Optimize Hot Statements, einen kurzen Blick in dieses Füllhorn.
Bessere Datenstrukturen verwenden
Die Auswahl der am besten geeigneten Datenstruktur hat einen großen Einfluss auf die Leistung. Das liegt zum Teil daran, dass die Algorithmen zum Einfügen, Iterieren, Sortieren und Abrufen von Einträgen Laufzeitkosten verursachen, die von der Datenstruktur abhängen. Außerdem nutzen verschiedene Datenstrukturen den Speichermanager unterschiedlich stark aus. Das liegt zum Teil auch daran, dass die Datenstruktur eine gute Cache-Lokalität haben kann, oder auch nicht. In Kapitel 10, Optimize Data Structures (Datenstrukturen optimieren), werden die Leistung, das Verhalten und die Kompromisse der Datenstrukturen in der C++ Standardbibliothek untersucht. In Kapitel 9, Optimize Searching and Sorting, wird die Verwendung von Algorithmen der Standardbibliothek zur Implementierung von tabellarischen Datenstrukturen auf der Grundlage von einfachen Vektoren und C-Arrays erörtert.
Gleichzeitigkeit erhöhen
Die meisten Programme müssen warten, bis Aktivitäten in der lästigen, schwerfälligen Welt der physischen Realität abgeschlossen sind. Sie müssen darauf warten, dass Dateien von mechanischen Festplatten gelesen werden, dass Seiten aus dem Internet zurückgesendet werden oder dass die langsamen Finger der Benutzer mechanische Tasten drücken. Jedes Mal, wenn das Vorankommen eines Programms durch das Warten auf ein solches Ereignis blockiert wird, ist das eine verpasste Gelegenheit, eine andere Berechnung durchzuführen.
Moderne Computer haben mehr als einen Prozessorkern, um Befehle auszuführen. Wenn die Arbeit auf mehrere Prozessoren aufgeteilt wird, kann sie schneller erledigt werden.
Neben der parallelen Ausführung gibt es auch Werkzeuge für die Synchronisierung paralleler Threads, damit sie Daten gemeinsam nutzen können. Diese Werkzeuge können gut oder schlecht genutzt werden. Kapitel 12, Gleichzeitigkeit optimieren, befasst sich mit einigen Überlegungen zur effizienten Synchronisierung von nebenläufigen Kontrollthreads.
Optimiere die Speicherverwaltung
Der Speichermanager, der Teil der C++-Laufzeitbibliothek, der die Zuweisung von dynamischem Speicher verwaltet, ist häufig ausgeführter Code in vielen C++-Programmen. C++ verfügt über eine umfangreiche API für die Speicherverwaltung, obwohl die meisten Entwickler sie noch nie benutzt haben. Kapitel 13, Optimierung der Speicherverwaltung, zeigt einige Techniken zur Verbesserung der Leistung der Speicherverwaltung.
Zusammenfassung
Dieses Buch hilft dem Entwickler, die folgenden Möglichkeiten zur Verbesserung der Codeleistung zu erkennen und zu nutzen:
-
Verwende bessere Compiler und schalte den Optimierer ein.
-
Verwende optimale Algorithmen.
-
Nutze bessere Bibliotheken, und nutze Bibliotheken besser.
-
Reduziere die Speicherzuweisung.
-
Reduziere das Kopieren.
-
Entferne die Berechnungen.
-
Verwende optimale Datenstrukturen.
-
Erhöhe die Gleichzeitigkeit.
-
Optimiere die Speicherverwaltung.
Wie ich schon sagte, der Teufel steckt im Detail. Lass uns weitermachen.
Get Optimiertes C++ now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.