Wo optimieren Sie?

Es gibt zwei Bereiche, in denen möglicherweise die Geschwindigkeit optimiert werden kann:

• Wo die meiste Zeit verbracht wird
• Der Code, der am häufigsten aufgerufen wird

Welches ist der beste Ort, um mit der Optimierung zu beginnen?

Oft hat der am häufigsten aufgerufene Code bereits niedrige Ausführungszeiten. Optimieren Sie die langsameren, weniger aufgerufenen Bereiche oder verbringen Sie Zeit damit, die schnelleren, stark genutzten Bereiche zu optimieren?

Sie sollten die geringen Wirkungsgrade in 95% der Fälle ignorieren. Lassen Sie es zuerst richtig funktionieren , dann analysieren Sie ...

Dein Design.

Ihre Wahl von Algorithmen auf hoher Ebene kann einen enormen Einfluss auf die Gesamtleistung Ihrer Software haben, bis zu dem Punkt, an dem eine scheinbar triviale Wahl den Unterschied zwischen einer Wartezeit von 20 Minuten auf den Start des Programms und einer schnellen, reaktionsschnellen Benutzeroberfläche bedeuten kann.

Beispiel: In einem 3D-Spiel: Wenn Sie mit einer einfachen flachen Liste von Objekten für Ihr Szenendiagramm beginnen, werden Sie bei einer relativ kleinen Anzahl von Objekten eine äußerst schlechte Leistung feststellen. Wenn Sie jedoch stattdessen eine Volume-Hierarchie (wie ein Octree oder BVH) implementieren und beim Zeichnen Teile des Baums aussortieren, werden Sie einen massiven Leistungsschub feststellen.

Wenn Ihr Design korrekt erscheint, können Sie mit ...

Low-Level-Logik.

Algorithmen auf niedrigerer Ebene können ebenfalls erhebliche Auswirkungen haben. Wenn Sie beispielsweise bei der Bildverarbeitung das Bild in der falschen Reihenfolge lesen, treten massive Verlangsamungen auf, wenn Sie auf ständige L2-Cache-Fehler stoßen. Eine Neuordnung Ihrer Betriebsabläufe kann eine zehnfache Leistungssteigerung bedeuten.

Profilieren und finden Sie an diesem Punkt den Ort, an dem der Großteil der Programmzeit verbracht wird, und finden Sie einen Weg, dies zu beseitigen.

Führen Sie zunächst einen Profiler aus, um herauszufinden, wo Ihr Code seine Zeit verbringt.

Schauen Sie sich dann diese Stellen an, um zu sehen, welche leicht zu optimieren sind.

Suchen Sie nach den einfachsten Lösungen, die zuerst die größten Gewinne erzielen (wählen Sie die niedrig hängenden Früchte). Mach dir nicht zu viele Sorgen darüber, wie wichtig es genau ist. Wenn es einfach ist, beheben Sie es. Es wird sich summieren. 25 einfache Korrekturen sind möglicherweise schneller als eine große Korrektur, und ihre kumulativen Auswirkungen sind möglicherweise größer. Wenn es schwierig ist, machen Sie sich eine Notiz oder reichen Sie einen Fehlerbericht ein, damit Sie ihn später priorisieren können. Sorgen Sie sich an dieser Stelle nicht so sehr um "groß" oder "klein" - tun Sie es einfach, bis Sie zu Funktionen gelangen, die nur sehr wenig Zeit benötigen. Sobald Sie dies getan haben, sollten Sie eine bessere Vorstellung davon haben, welches der anderen Probleme, die Sie aufgedeckt haben, die größten Gewinne bei geringstem Zeitaufwand erzielen kann.

Vergessen Sie nicht, die Profilerstellung nach Ihren Korrekturen als eine Art Regressionstest durchzuführen, um zu überprüfen, ob Ihre Leistungsänderungen die erhofften Auswirkungen hatten. Vergessen Sie auch nicht, Ihre Regressionssuite auszuführen, um sicherzustellen, dass keine Funktionalität beeinträchtigt wurde. Manchmal weist eine schlechte Leistung auf Umgehungen hin, und der Versuch, die Leistung zu beheben, beeinträchtigt die Funktionalität.

Kleine Funktionen, die nicht optimiert werden können, aber viel Zeit in Anspruch nehmen, sind möglicherweise immer noch Hinweise darauf, wo sie optimiert werden müssen. Warum wird diese Funktion so oft aufgerufen? Gibt es eine Funktion, die diese kleine Funktion aufruft, die sie nicht so oft verwenden muss? Wird die Arbeit dupliziert oder wird unnötige Arbeit geleistet? Suchen Sie im Stapel nach den Zeiten, zu denen er aufgerufen wird, bis Sie sicher sind, dass er so oft aufgerufen werden sollte, und prüfen Sie, ob Sie eine größere Funktion mit einem ineffizienten Algorithmus finden.

Bearbeitet, um hinzuzufügen: Da Sie über bestimmte Funktionen verfügen, die lange dauern, führen Sie die obigen Schritte aus, wobei nur diese bestimmte Funktion etwa zehnmal ausgeführt wird.

Es ist schwer zu sagen. Dies hängt wirklich davon ab, was der Code tut. Führen Sie einen Leistungstest durch, erstellen Sie ein Leistungsprofil und sehen Sie, wie viel tatsächliche Zeit in verschiedenen Bereichen verbracht wird. Ihre Verallgemeinerungen sind ... Verallgemeinerungen und variieren von Projekt zu Projekt.

Beispielsweise kann der Code, der am häufigsten aufgerufen wird, einfach in einer Datei oder Konsole protokolliert werden. Es macht nicht viel Sinn, dies zu optimieren, wenn es bereits eine oder zwei Codezeilen gibt, die nicht einfacher gestaltet werden können, und es kann sein, dass sich die Bemühungen, so etwas zu optimieren, nicht lohnen, die Kosten für die eigentliche Codierung zu tragen. Der am wenigsten aufgerufene Code könnte eine Abfrage in Monstergröße sein, die in einer schrecklich komplexen Funktion verwendet wird. Die Funktion wird während eines gesamten Ausführungslaufs möglicherweise nur 100 Mal aufgerufen (gegenüber 10000 für die einfache Protokollierungsanweisung). Wenn jedoch für jede ausgeführte Aufrufzeit 20 Sekunden benötigt werden, sollte hier möglicherweise die Optimierung beginnen. Oder es könnte umgekehrt sein, wobei die große Abfrage am häufigsten aufgerufen wird und die Protokollierungsanweisung nur eine pro 100 Abfragen aufruft ...

Ich mache mir normalerweise keine Sorgen über solche Dinge (bis ich die Leistung optimieren muss), es sei denn, ich habe im Voraus eine Vorstellung davon, was passieren wird.

Nun, "wir" optimieren normalerweise erst, wenn ein offensichtlicher Optimierungsbedarf besteht, wenn etwas inakzeptabel langsam ist.

Und wenn sich dieses Bedürfnis manifestiert, bringt es normalerweise gute Hinweise mit sich, was genau Optimierung erfordert.

Die Antwort ist also üblich: "Es kommt darauf an."

Sie sollten einen Profiler für eine Handvoll typischer Läufe verwenden und die Gesamtzeit in jedem Teil des Codes anzeigen, unabhängig davon, wie oder wie oft Sie dort angekommen sind. Die Optimierung dieser Teile sollte immer zu einer Geschwindigkeitssteigerung führen.

Abhängig davon, wie niedrig Ihre Implementierungssprache ist, sollten Sie auch herausfinden, welche Teile die meisten Cache-Fehler verursachen. Hier hilft die Konsolidierung des Aufrufcodes.

Das Problem ist, dass der Ausdruck "wo die meiste Zeit verbracht wird" nicht eindeutig ist.

Wenn es bedeutet "wo der Programmzähler am häufigsten gefunden wird", dann habe ich Programme gesehen, in denen die meiste Zeit für Funktionen zum Vergleichen von Zeichenfolgen, zum Zuweisen von Speicher und für mathematische Bibliotheken aufgewendet wurde. Mit anderen Worten, Funktionen, die der alltägliche Programmierer niemals berühren sollte.

Wenn es bedeutet, "wo im Code des Programmierers Anweisungen ausgeführt werden, die einen großen Teil der Zeit in Anspruch nehmen", ist dies ein nützlicheres Konzept.

Das Problem mit dem Konzept des "Codes, der am häufigsten aufgerufen wird" ist, dass die benötigte Zeit das Produkt davon ist, wie oft er aufgerufen wird und wie viel Zeit er pro Anruf benötigt (einschließlich Anrufer und E / A). Da die benötigte Zeit über mehrere Größenordnungen variieren kann, sagt Ihnen die Häufigkeit des Aufrufs nicht, wie groß das Problem ist. Funktion A kann 10 Mal aufgerufen werden und dauert 0,1 Sekunden, während Funktion B 1000 Mal aufgerufen werden kann und eine Mikrosekunde dauert.

Eine Sache, die Ihnen sagt, wo Sie suchen müssen, ist folgende: Immer wenn eine Codezeile Zeit verbraucht , befindet sie sich auf dem Stapel . Zum Beispiel, wenn eine Codezeile ein Hot Spot ist oder wenn es sich um einen Aufruf einer Bibliotheksfunktion handelt oder wenn es sich um den 20. Aufruf in einem 30-Ebenen-Aufrufbaum handelt, wenn sie für 20% der Zeit verantwortlich ist , dann ist es 20% der Zeit auf dem Stapel. Zufällige Stichproben des Stapels haben jeweils eine 20% ige Chance, ihn anzuzeigen. Wenn während der E / A Proben entnommen werden können, zeigen sie Ihnen, welche Faktoren für die E / A verantwortlich sind. Dies kann genauso oder verschwenderischer sein als verschwendete CPU-Zyklen.

Und dies ist völlig unabhängig davon, wie oft es aufgerufen wird.

Optimieren Sie, wo die meiste Zeit verbracht wird, es sei denn, es gibt einen bestimmten Grund, dies nicht zu tun (dh die meiste Zeit wird für die asynchrone Verarbeitung aufgewendet, die den Menschen egal ist, ob sie in 5 Minuten oder 10 Minuten abgeschlossen ist). Der Code, der am häufigsten genannt wird, macht natürlich einen relativ großen Teil der insgesamt verstrichenen Zeit aus, nur weil sich selbst kurze Ausführungszeiten summieren, wenn Sie dies tausende Male tun.

Sie müssen an dem Code arbeiten, der die meiste Zeit in Anspruch nimmt. Wenn Sie Code verbessern, der nur einige Prozent der Laufzeit ausmacht, können Sie nur eine kleine Verbesserung erzielen.

Haben Sie Messungen durchgeführt, um zu wissen, welcher Code am meisten Zeit in Anspruch nimmt?

Früher habe ich Benchmarking und Marketing für einen Supercomputer-Anbieter durchgeführt, daher war es nicht das Wichtigste, die Konkurrenz schnell zu schlagen, sondern das EINZIGE. Für diese Art von Ergebnis war es erforderlich, dass Sie eine Kombination aus gutem Algorithmus und einer Datenstruktur verwenden, die es den CPU-intensivsten Teilen ermöglicht, einen Peak effizient auszuführen. Das bedeutete, dass Sie eine ziemlich gute Vorstellung davon haben mussten, was die rechenintensivsten Operationen sein würden und welche Arten von Datenstrukturen es ihnen ermöglichen würden, am schnellsten zu laufen. Dann ging es darum, die Anwendung um diese optimierten Kernel / Datenstrukturen herum aufzubauen.

Im allgemeineren Sinne das typische nachträgliche Tuning. Sie profilieren, sehen sich die Hot Spots an und die Hot Spots, von denen Sie glauben, dass Sie sie beschleunigen können, sind diejenigen, an denen Sie arbeiten. Mit diesem Ansatz erhalten Sie jedoch selten etwas, das der schnellstmöglichen Implementierung nahe kommt.

Im Allgemeinen muss man bei modernen Maschinen denken (algorithmische Fehler nicht aushalten), dass die Leistung durch drei Dinge bestimmt wird: Datenzugriff, Datenzugriff und Datenzugriff! Erfahren Sie mehr über die Speicherhierarchie (Register, Caches, TLBs, Seiten usw.) und entwerfen Sie Ihre Datenstrukturen so, dass sie so gut wie möglich genutzt werden. Im Allgemeinen bedeutet dies, dass Schleifen innerhalb eines kompakten Speicherbedarfs ausgeführt werden sollen. Wenn Sie stattdessen nur eine Anwendung schreiben (oder erhalten) und dann versuchen, sie zu optimieren, werden Sie normalerweise mit Datenstrukturen belastet, die die Speicherhierarchie schlecht nutzen, und das Ändern der Datenstrukturen erfordert normalerweise eine umfangreiche Refactoring-Übung oft stecken.

Wenn Sie Ihre Optimierungsbemühungen zurückzahlen möchten, müssen Sie sich den Code ansehen, der am meisten Zeit in Anspruch nimmt. Mein allgemeines Ziel ist etwas, das mindestens 80% der Zeit in Anspruch nimmt. Ich strebe im Allgemeinen einen 10-fachen Leistungsgewinn an. Dies erfordert manchmal eine wesentliche Änderung in der Gestaltung dieses Codes. Mit dieser Art von Änderung erhalten Sie etwas, das ungefähr viermal schneller läuft.

Mein bester Leistungsgewinn aller Zeiten ist die Reduzierung der Laufzeit von 3 Tagen auf 9 Minuten. Der von mir optimierte Code ging von 3 Tagen auf 3 Minuten. Die Anwendung, die diese Anwendung ersetzte, reduzierte diese auf 9 Sekunden, dies erforderte jedoch eine Änderung der Sprache und ein vollständiges Umschreiben.

Die Optimierung einer bereits schnellen Anwendung kann ein Kinderspiel sein. Ich würde immer noch das Gebiet anvisieren, das die meiste Zeit in Anspruch nimmt. Wenn Sie in 10% der Fälle etwas brauchen, um sofort zurückzukehren, benötigen Sie immer noch 90% der Zeit. Sie haben schnell die Regel der sinkenden Rendite getroffen.

Je nachdem, was Sie für die Regel optimieren, gilt dies weiterhin. Suchen Sie nach den wichtigsten Ressourcenbenutzern und optimieren Sie sie. Wenn die Ressource, die Sie optimieren, der Systemengpass ist, müssen Sie möglicherweise nur den Engpass in eine andere Ressource ändern.

In der Regel handelt es sich in den meisten Fällen um fleischigere Funktionen, nicht um Funktionen, die in einer Schleife milliardenfach aufgerufen werden.

Wenn Sie eine beispielbasierte Profilerstellung durchführen (mit einem Tool oder von Hand), befinden sich die größten Hotspots häufig in winzigen Blattaufrufen, die einfache Aufgaben ausführen, z. B. eine Funktion zum Vergleichen von zwei Ganzzahlen.

Diese Funktion wird oft nicht von viel, wenn überhaupt, Optimierung profitieren. Zumindest haben diese granularen Hotspots selten oberste Priorität. Es ist die Funktion, die diese Blattfunktion aufruft, die möglicherweise den Fehler verursacht, oder die Funktion, die die Funktion aufruft, die die Funktion aufruft, wie ein suboptimaler Sortieralgorithmus. Mit guten Tools können Sie einen Drilldown vom Angerufenen zum Anrufer durchführen und auch sehen, wer am meisten Zeit damit verbringt, den Angerufenen anzurufen.

Es ist oft ein Fehler, von Callees besessen zu sein und Anrufer in einer Profilerstellungssitzung nicht im Anrufdiagramm zu betrachten, es sei denn, Sie erledigen die Dinge auf Mikroebene sehr ineffizient. Andernfalls könnten Sie die kleinen Dinge übermäßig schwitzen und das große Ganze aus den Augen verlieren. Nur einen Profiler in der Hand zu haben, schützt Sie nicht vor Besessenheit über triviale Dinge. Es ist nur ein erster Schritt in die richtige Richtung.

Außerdem müssen Sie sicherstellen, dass Sie Profiling-Vorgänge ausführen, die auf die Dinge abgestimmt sind, die die Benutzer tatsächlich ausführen möchten. Andernfalls ist es wertlos, bei Ihren Messungen und Benchmarks absolut diszipliniert und wissenschaftlich zu sein, da sie nicht mit dem übereinstimmen, was die Kunden mit dem Produkt tun. Ich hatte einmal einen Kollegen, der die Hölle aus einem Unterteilungsalgorithmus herausgestimmt hat, um einen Würfel in eine Milliarde Facetten zu unterteilen, und er war sehr stolz darauf ... außer, dass Benutzer einfache 6-Polygon-Würfel nicht in eine Milliarde unterteilen Facetten. Das Ganze verlangsamte sich zu einem Kriechen, als es versuchte, auf einem Serienautomodell mit über 100.000 zu unterteilenden Polygonen zu laufen. Zu diesem Zeitpunkt konnte es nicht einmal zwei oder drei Unterteilungsebenen ausführen, ohne sich zu einem Kriechen zu verlangsamen. Einfach gesagt, schrieb er Code, der für unrealistisch kleine Eingabegrößen optimiert war, die es nicht taten.

Sie müssen reale Anwendungsfälle optimieren, die auf die Interessen Ihrer Benutzer abgestimmt sind, oder es ist schlimmer als wertlos, da all jene Optimierungen, die die Wartbarkeit von Code zumindest etwas beeinträchtigen, nur einen geringen Nutzen für den Benutzer haben und nur all diese Nachteile für die Codebasis.