Strategien zur Leistungsoptimierung als letztes Mittel

Question

Es gibt bereits viele Fragen zur Leistung auf dieser Website, aber mir fällt auf, dass fast alle sehr problemspezifisch und ziemlich eng sind. Und fast alle wiederholen den Rat, eine vorzeitige Optimierung zu vermeiden.

Nehmen wir an:

• der Code funktioniert bereits korrekt
• die gewählten Algorithmen sind bereits optimal für die Gegebenheiten des Problems
• der Code wurde gemessen und die fehlerhaften Routinen wurden isoliert
• alle Optimierungsversuche werden auch gemessen, um sicherzustellen, dass sie die Situation nicht verschlimmern

Was ich hier suche, sind Strategien und Tricks, um in einem kritischen Algorithmus bis zu den letzten paar Prozent herauszuholen, wenn nichts anderes übrig bleibt, als alles zu tun.

Versuchen Sie, die Antworten möglichst sprachunabhängig zu gestalten, und geben Sie gegebenenfalls die Nachteile der vorgeschlagenen Strategien an.

Ich werde eine Antwort mit meinen eigenen ersten Vorschlägen hinzufügen und freue mich auf alles, was der Stack Overflow-Community sonst noch einfällt.

Answer 1

OK, Sie definieren das Problem so, dass es nicht mehr viel Spielraum für Verbesserungen zu geben scheint. Meiner Erfahrung nach ist das eher selten der Fall. Ich habe versucht, dies in einem Artikel von Dr. Dobbs im November 1993 zu erklären, indem ich von einem konventionell gut entworfenen, nicht-trivialen Programm ohne offensichtliche Verschwendung ausging und es einer Reihe von Optimierungen unterzog, bis seine Wanduhrzeit von 48 Sekunden auf 1,1 Sekunden reduziert und die Größe des Quellcodes um den Faktor 4 verringert wurde. Mein Diagnoseinstrument war dies . Die Reihenfolge der Änderungen war wie folgt:

• Das erste gefundene Problem war die Verwendung von Listenclustern (jetzt "Iteratoren" und "Containerklassen" genannt), die mehr als die Hälfte der Zeit ausmachten. Diese wurden durch relativ einfachen Code ersetzt, wodurch die Zeit auf 20 Sekunden gesenkt werden konnte.

• Der größte Zeitfresser ist jetzt der Aufbau von Listen. Der prozentuale Anteil war vorher nicht so groß, aber jetzt ist er es, weil das größere Problem beseitigt wurde. Ich habe einen Weg gefunden, es zu beschleunigen, und die Zeit ist auf 17 Sekunden gesunken.

• Jetzt ist es schwieriger, offensichtliche Schuldige zu finden, aber es gibt ein paar kleinere, gegen die ich etwas tun kann, und die Zeit sinkt auf 13 Sekunden.

Jetzt scheine ich gegen eine Mauer zu stoßen. Die Proben sagen mir genau, was sie tun, aber ich kann nichts finden, was ich verbessern könnte. Dann denke ich über den grundlegenden Aufbau des Programms nach, über seine transaktionsgesteuerte Struktur, und frage mich, ob all die Listensuche, die es durchführt, tatsächlich durch die Anforderungen des Problems vorgeschrieben ist.

Dann stieß ich auf einen neuen Entwurf, bei dem der Programmcode tatsächlich (über Präprozessormakros) aus einer kleineren Menge von Quellen generiert wird und bei dem das Programm nicht ständig Dinge herausfinden muss, von denen der Programmierer weiß, dass sie ziemlich vorhersehbar sind. Mit anderen Worten, "interpretieren" Sie nicht die Abfolge der zu erledigenden Dinge, sondern "kompilieren" Sie sie.

• Nach dieser Umgestaltung ist der Quellcode um den Faktor 4 geschrumpft, und die Zeit wurde auf 10 Sekunden reduziert.

Da es so schnell geht, ist es schwer, eine Stichprobe zu machen, also gebe ich ihm die 10-fache Menge an Arbeit, aber die folgenden Zeiten basieren auf der ursprünglichen Arbeitsbelastung.

• Eine genauere Diagnose zeigt, dass er Zeit mit der Verwaltung von Warteschlangen verbringt. Durch das Inlining wird diese Zeit auf 7 Sekunden reduziert.

• Ein großer Zeitfresser ist jetzt das diagnostische Drucken, das ich gemacht habe. Spülen Sie das - 4 Sekunden.

• Die größten Zeitfresser sind jetzt Anrufe bei malloc y kostenlos . Objekte recyceln - 2,6 Sekunden.

• Wenn ich die Stichprobe fortsetze, finde ich immer noch Vorgänge, die nicht unbedingt notwendig sind - 1,1 Sekunden.

Gesamtbeschleunigungsfaktor: 43.6

Kein Programm ist wie das andere, aber bei Software, die kein Spielzeug ist, habe ich immer einen solchen Verlauf gesehen. Zuerst bekommt man die einfachen Sachen, dann die schwierigeren, bis man an einen Punkt kommt, an dem der Nutzen nachlässt. Dann können die gewonnenen Erkenntnisse zu einem neuen Entwurf führen, der eine neue Runde der Beschleunigung einläutet, bis man wieder auf abnehmende Erträge stößt. Das ist der Punkt, an dem man sich fragen kann, ob es sinnvoll ist ++i o i++ o for(;;) o while(1) schneller sind: die Art von Fragen, die ich so oft auf Stack Overflow sehe.

P.S. Sie werden sich vielleicht fragen, warum ich keinen Profiler verwendet habe. Die Antwort ist, dass es sich bei fast jedem dieser "Probleme" um einen Funktionsaufruf handelte, den Stack-Proben aufspüren. Profiler haben sich auch heute noch kaum mit der Idee angefreundet, dass Anweisungen und Aufrufe wichtiger zu lokalisieren und leichter zu beheben sind als ganze Funktionen.

Ich habe dafür einen Profiler gebaut, aber wenn man wirklich genau wissen will, was der Code macht, gibt es keinen Ersatz dafür, die Finger mitten drin zu haben. Es ist kein Problem, dass die Anzahl der Beispiele klein ist, denn keines der gefundenen Probleme ist so winzig, dass es leicht übersehen werden könnte.

ADDED: jerryjvl bat um einige Beispiele. Hier ist das erste Problem. Es besteht aus einer kleinen Anzahl von separaten Codezeilen, die zusammen mehr als die Hälfte der Zeit beanspruchen:

 /* IF ALL TASKS DONE, SEND ITC_ACKOP, AND DELETE OP */
if (ptop->current_task >= ILST_LENGTH(ptop->tasklist){
. . .
/* FOR EACH OPERATION REQUEST */
for ( ptop = ILST_FIRST(oplist); ptop != NULL; ptop = ILST_NEXT(oplist, ptop)){
. . .
/* GET CURRENT TASK */
ptask = ILST_NTH(ptop->tasklist, ptop->current_task)

Dabei wurde der Listencluster ILST (ähnlich einer Listenklasse) verwendet. Sie sind auf die übliche Weise implementiert, wobei "Information Hiding" bedeutet, dass die Benutzer der Klasse sich nicht darum kümmern sollten, wie sie implementiert wurden. Als diese Zeilen geschrieben wurden (von etwa 800 Zeilen Code), wurde nicht daran gedacht, dass sie einen "Flaschenhals" darstellen könnten (ich hasse dieses Wort). Sie sind einfach der empfohlene Weg, Dinge zu tun. Es ist leicht zu sagen im Nachhinein betrachtet dass diese vermieden werden sollten, aber meiner Erfahrung nach alle Leistungsprobleme sind so eine Sache. Im Allgemeinen ist es gut, Leistungsprobleme zu vermeiden. Noch besser ist es, die entstandenen Probleme zu finden und zu beheben, auch wenn sie (im Nachhinein) "hätten vermieden werden müssen". Ich hoffe, dass dies ein wenig den Geschmack widerspiegelt.

Hier ist das zweite Problem, in zwei separaten Zeilen:

 /* ADD TASK TO TASK LIST */
ILST_APPEND(ptop->tasklist, ptask)
. . .
/* ADD TRANSACTION TO TRANSACTION QUEUE */
ILST_APPEND(trnque, ptrn)

Diese bauen Listen auf, indem sie Elemente an ihre Enden anhängen. (Die Lösung war, die Elemente in Arrays zu sammeln und die Listen auf einmal zu erstellen). Interessant ist, dass diese Anweisungen nur 3/48 der ursprünglichen Zeit kosteten (d.h. auf dem Aufrufstapel lagen), so dass sie eigentlich kein großes Problem darstellten zu Beginn . Nachdem jedoch das erste Problem beseitigt war, kosteten sie 3/20 der Zeit und waren damit ein "größerer Fisch". Im Allgemeinen ist das so.

Ich möchte hinzufügen, dass dieses Projekt aus einem echten Projekt, an dem ich mitgearbeitet habe, destilliert wurde. Bei diesem Projekt waren die Leistungsprobleme weitaus dramatischer (ebenso wie die Geschwindigkeitssteigerungen), z. B. der Aufruf einer Datenbankzugriffsroutine innerhalb einer inneren Schleife, um festzustellen, ob eine Aufgabe abgeschlossen war.

REFERENZ HINZUGEFÜGT: Der Quellcode, sowohl der ursprüngliche als auch der umgestaltete, ist zu finden unter www.ddj.com für 1993 in der Datei 9311.zip, den Dateien slug.asc und slug.zip.

BEARBEITEN 2011/11/26: Es gibt jetzt eine SourceForge-Projekt mit Quellcode in Visual C++ und einer detaillierten Beschreibung, wie er abgestimmt wurde. Es wird nur die erste Hälfte des oben beschriebenen Szenarios durchlaufen, und es folgt nicht genau der gleichen Sequenz, aber es wird immer noch eine Beschleunigung um 2-3 Größenordnungen erreicht.

Answer 2

Vorschläge:

• Vorausberechnung statt Neuberechnung Bei allen Schleifen oder wiederholten Aufrufen, die Berechnungen mit einem relativ begrenzten Bereich von Eingaben enthalten, sollten Sie ein Nachschlagewerk (Array oder Wörterbuch) erstellen, das das Ergebnis dieser Berechnung für alle Werte im gültigen Bereich der Eingaben enthält. Verwenden Sie dann stattdessen ein einfaches Nachschlagewerk innerhalb des Algorithmus.
  Schattenseiten Wenn nur wenige der vorberechneten Werte tatsächlich verwendet werden, kann dies die Situation verschlimmern, außerdem kann die Suche viel Speicherplatz beanspruchen.
• Verwenden Sie keine Bibliotheksmethoden : Die meisten Bibliotheken müssen so geschrieben werden, dass sie unter einer Vielzahl von Szenarien korrekt funktionieren und Parameter auf Null prüfen usw. Durch die Neuimplementierung einer Methode können Sie möglicherweise eine Menge Logik entfernen, die unter den genauen Umständen, unter denen Sie sie verwenden, nicht anwendbar ist.
  Schattenseiten : Das Schreiben von zusätzlichem Code bedeutet mehr Angriffsfläche für Fehler.
• Verwenden Sie Bibliotheksmethoden : um mir selbst zu widersprechen, Sprachbibliotheken werden von Leuten geschrieben, die viel klüger sind als Sie oder ich; die Chancen stehen gut, dass sie es besser und schneller gemacht haben. Implementieren Sie es nicht selbst, es sei denn, Sie können es tatsächlich schneller machen (d.h.: immer messen!)
• Betrug In manchen Fällen ist eine exakte Berechnung für Ihr Problem zwar möglich, aber nicht notwendig. Manchmal ist eine Annäherung "gut genug" und viel schneller. Fragen Sie sich selbst, ob es wirklich wichtig ist, dass die Antwort um 1% abweicht? 5%? sogar 10%?
  Schattenseiten : Nun... die Antwort wird nicht genau sein.

Answer 3

Wenn Sie die Leistung nicht mehr verbessern können, schauen Sie, ob Sie die wahrgenommen Leistung statt.

Vielleicht können Sie Ihren fooCalc-Algorithmus nicht schneller machen, aber oft gibt es Möglichkeiten, Ihre Anwendung für den Benutzer reaktionsschneller zu machen.

Hier ein paar Beispiele:

• Antizipieren, was der Nutzer vorhat und mit der Arbeit daran beginnen bevor dann
• Anzeige der Ergebnisse als sie eintreffen, anstatt alle auf einmal am Ende
• Genaue Fortschrittsanzeige

Dadurch wird Ihr Programm zwar nicht schneller, aber Ihre Benutzer sind vielleicht zufriedener mit der Geschwindigkeit, die Sie haben.

Answer 4

Ich verbringe die meiste Zeit meines Lebens an genau diesem Ort. In groben Zügen geht es darum, den Profiler laufen zu lassen und ihn zum Aufzeichnen zu bringen:

• Cache verfehlt . Der Datencache ist in den meisten Programmen die Hauptursache für Verzögerungen. Verbessern Sie die Cache-Trefferrate, indem Sie störende Datenstrukturen reorganisieren, um eine bessere Lokalisierung zu erreichen; packen Sie Strukturen und numerische Typen zusammen, um vergeudete Bytes (und damit vergeudete Cache-Fetches) zu eliminieren; holen Sie Daten vor, wo immer es möglich ist, um Stalls zu reduzieren.
• Lastaufnahmemittel . Compiler-Annahmen über Zeiger-Aliasing und Fälle, in denen Daten zwischen nicht verbundenen Registersätzen über den Speicher verschoben werden, können ein bestimmtes pathologisches Verhalten verursachen, das dazu führt, dass die gesamte CPU-Pipeline bei einer Ladeoperation gelöscht wird. Finden Sie die Stellen, an denen Floats, Vektoren und Ints ineinander gecastet werden, und beseitigen Sie sie. Verwenden Sie . __restrict frei, um dem Compiler Aliasing zu versprechen.
• Mikrokodierte Operationen . Die meisten Prozessoren verfügen über einige Operationen, die nicht in einer Pipeline verarbeitet werden können, sondern ein winziges, im ROM gespeichertes Unterprogramm ausführen. Beispiele auf dem PowerPC sind Integer-Multiplikation, Dividieren und Verschieben um einen variablen Betrag. Das Problem ist, dass die gesamte Pipeline stillsteht, während diese Operationen ausgeführt werden. Versuchen Sie, diese Operationen nicht mehr zu verwenden oder sie zumindest in die einzelnen Pipeline-Operationen aufzuteilen, damit Sie die Vorteile der superskalaren Abfertigung für den Rest Ihres Programms nutzen können.
• Branche sagt falsch voraus . Auch diese leeren die Pipeline. Finden Sie die Fälle, in denen die CPU viel Zeit damit verbringt, die Pipeline nach einer Verzweigung wieder aufzufüllen, und verwenden Sie Verzweigungshinweise, falls verfügbar, um sie dazu zu bringen, häufiger korrekt vorherzusagen. Oder noch besser: Ersetzen Sie Verzweigungen durch bedingte Bewegungen, wo immer dies möglich ist, insbesondere nach Fließkomma-Operationen, da ihre Pipe in der Regel tiefer ist und das Lesen der Bedingungsflags nach fcmp zu einer Blockierung führen kann.
• Sequentielle Gleitkommaoperationen . Machen Sie diese SIMD.

Und noch eine Sache, die ich gerne mache:

• Stellen Sie Ihren Compiler so ein, dass er Assembler-Listings ausgibt und sehen Sie sich an, was es für die Hotspot-Funktionen in Ihrem Code ausgibt. All diese cleveren Optimierungen, die "ein guter Compiler automatisch für Sie erledigen können sollte"? Die Chancen stehen gut, dass Ihr aktueller Compiler sie nicht durchführt. Ich habe gesehen, dass GCC wirklich WTF-Code ausgibt.

Answer 5

Wirf mehr Hardware drauf!