Ansätze gegen eine einheitlich langsame Codebasis

11

Wir arbeiten an einer mittelgroßen C ++ - Codebasis (10Mloc), die durch unsere Optimierungsbemühungen gleichmäßig langsam wird .

Diese Codebasis besteht aus einer Reihe von Bibliotheken, die wir kombinieren, um sie zum Laufen zu bringen. Als der allgemeine Rahmen für die Kommunikation dieser Bibliotheken entwickelt wurde, lag ein gewisser Schwerpunkt auf der Leistung, und später, als weitere Teile hinzugefügt wurden, wurde der allgemeine Rahmen nicht wesentlich geändert. Die Optimierung wurde bei Bedarf und im Zuge der Weiterentwicklung unserer Hardware durchgeführt. Dies machte eine teure frühzeitige Entscheidung erst viel später deutlich. Wir sind jetzt an einem Punkt angelangt, an dem weitere Optimierungen viel teurer sind, da große Teile der Codebasis neu geschrieben werden müssten. Wir nähern uns einem unerwünschten lokalen Minimum, da wir wissen, dass der Code im Prinzip viel schneller ausgeführt werden kann.

Gibt es erfolgreiche Methoden, mit denen entschieden werden kann, wie die Entwicklung einer Codebasis zu einer global optimal funktionierenden Lösung erfolgen soll, die nicht leicht durch einfache Optimierungsmöglichkeiten verwechselt werden kann?

BEARBEITEN

Um die Frage zu beantworten, wie wir uns derzeit profilieren:

Wir haben wirklich nur zwei verschiedene Szenarien, wie dieser Code verwendet werden kann, beide peinlich parallel. Die Profilerstellung erfolgt sowohl mit einer über eine große Stichprobe von Eingaben gemittelten Wanduhrzeit als auch mit detaillierteren Läufen (Anweisungskosten, Fehlvorhersagen für Zweige und Caching-Probleme). Dies funktioniert gut, da wir ausschließlich auf unseren extrem homogenen Maschinen (einem Cluster von ein paar tausend identischen Maschinen) arbeiten. Da wir normalerweise alle unsere Maschinen die meiste Zeit schneller beschäftigen, können wir uns zusätzliche neue Dinge ansehen. Das Problem ist natürlich, dass neue Eingabevariationen, wenn sie auftauchen, möglicherweise zu spät kommen, da wir die offensichtlichsten Mikroineffizienzen für die anderen Anwendungsfälle beseitigt haben, wodurch möglicherweise die Anzahl der "optimal laufenden" Szenarien verringert wird.

Benjamin Bannier
quelle
10
10Mloc ist eigentlich ein riesiges Projekt
BЈовић
1
Es sind 10 Millionen loc (SI-Präfix), gezählt von sloc. Ich habe es "mittelgroß" genannt, weil ich keine Ahnung habe, was hier als "groß" gilt.
Benjamin Bannier
5
Ich bin mir ziemlich sicher, dass 10 Millionen überall mindestens groß sind und wahrscheinlich an den meisten Orten riesig.
Ryathal
1
Super, danke @honk Für 10M LOC klingt es so, als würden Sie auf einem sehr niedrigen Niveau optimieren, fast auf Hardware-Ebene? Herkömmliches OOP (AOS "Array of Structures") ist in Caches schrecklich ineffizient. Haben Sie versucht, Ihre Klassen in SOA (Struktur von Arrays) umzuordnen, damit die Datenpunkte, an denen Ihr Code arbeitet, im Speicher kohärent sind? Bei so vielen Maschinen treten Kommunikationsblockaden oder Synchronisationsprobleme auf? Letzte Frage: Haben Sie es mit großen Mengen an Streaming-Daten zu tun oder ist dies hauptsächlich ein Problem komplexer Vorgänge in Ihren Datensätzen?
Patrick Hughes
1
Wenn Sie so viel Code haben, stehen die Chancen gut, dass es große potenzielle Beschleunigungen der von mir erwähnten nicht-lokalen Art gibt. Es macht keinen Unterschied, ob es Tausende von Threads / Prozessen gibt. Eine zufällige Pause wird sie entweder für Sie fingern oder mir das Gegenteil beweisen.
Mike Dunlavey

Antworten:

9

Ich kenne keinen allgemeinen Ansatz für dieses Problem, aber zwei etwas verwandte Ansätze haben in der Vergangenheit für mich gut funktioniert: Mangels besserer Begriffe habe ich sie Bündelung und horizontale Optimierung genannt .

Der Bündelungsansatz ist ein Versuch, eine große Anzahl kurzer, schneller Vorgänge durch einen einzigen, langsamer laufenden, hochspezialisierten Vorgang zu ersetzen, der letztendlich das gleiche Ergebnis liefert.

Beispiel: Nachdem wir eine besonders langsame Operation unseres visuellen Regel-Editors profiliert hatten, entdeckten wir keine "niedrig hängenden Früchte": Es gab keine einzige Operation, die mehr als 2% der Ausführungszeit in Anspruch nahm, aber die Operation insgesamt fühlte sich träge an. Wir haben jedoch festgestellt, dass der Editor eine große Anzahl kleiner Anforderungen an den Server gesendet hat. Obwohl der Editor die einzelnen Antworten schnell verarbeitete, wirkte sich die Anzahl der Anforderungs- / Antwortinteraktionen multiplikativ aus, sodass die Gesamtdauer des Vorgangs mehrere Sekunden betrug. Nachdem wir die Interaktionen des Editors während dieses lang laufenden Vorgangs sorgfältig katalogisiert hatten, haben wir der Serverschnittstelle einen neuen Befehl hinzugefügt. Der zusätzliche Befehl war spezialisierter, da er die Daten akzeptierte, die zum Ausführen einer Teilmenge von Kurzoperationen erforderlich waren. Untersuchte Datenabhängigkeiten, um den endgültigen Datensatz für die Rückgabe herauszufinden, und lieferte eine Antwort mit den Informationen, die erforderlich sind, um alle einzelnen kleinen Vorgänge in einer einzigen Fahrt zum Server abzuschließen. Dies hat die Verarbeitungszeit in unserem Code nicht verkürzt, aber die Latenz erheblich reduziert, da mehrere teure Client-Server-Roundtrips entfernt wurden.

Die horizontale Optimierung ist eine verwandte Technik, wenn Sie die "Langsamkeit" beseitigen, die unter Verwendung einer bestimmten Funktion Ihrer Ausführungsumgebung dünn auf mehrere Komponenten Ihres Systems verteilt ist.

Beispiel: Nach der Profilerstellung eines lang laufenden Vorgangs haben wir festgestellt, dass wir viele Aufrufe über die Anwendungsdomänengrenze hinweg tätigen (dies ist sehr spezifisch für .NET). Wir konnten keinen der Anrufe eliminieren und wir konnten sie nicht zusammenfassen: Sie kamen zu unterschiedlichen Zeiten aus sehr unterschiedlichen Bereichen unseres Systems, und die von ihnen angeforderten Dinge waren abhängig von den Ergebnissen, die aus früheren Anfragen zurückgegeben wurden. Jeder Aufruf erforderte die Serialisierung und Deserialisierung einer relativ kleinen Datenmenge. Auch hier waren die einzelnen Anrufe von kurzer Dauer, aber sehr zahlreich. Am Ende haben wir ein Schema entworfen, das die Serialisierung fast vollständig vermeidet und es durch das Übergeben eines Zeigers über die App-Domänengrenze ersetzt. Dies war ein großer Gewinn, da viele Anfragen von völlig unabhängigen Klassen durch die Anwendung einer einzelnen Klasse sofort viel schneller wurdenhorizontale Lösung.

dasblinkenlight
quelle
Vielen Dank, dass Sie uns Ihre Erfahrungen mitgeteilt haben. Dies sind nützliche Optimierungen, die Sie berücksichtigen sollten. Da sie problematische Teile an einen bestimmten Ort heben, sind sie in Zukunft viel besser zu kontrollieren. In gewisser Weise setzen sie um, was eigentlich hätte passieren sollen, jetzt nur noch durch harte Daten.
Benjamin Bannier
3

Dies machte eine teure frühzeitige Entscheidung erst viel später deutlich. Wir sind jetzt an einem Punkt angelangt, an dem weitere Optimierungen viel teurer sind, da große Teile der Codebasis neu geschrieben werden müssten.

Wenn Sie mit dem Umschreiben beginnen, müssen Sie verschiedene Dinge unterschiedlich ausführen.

Zuerst. Und das Wichtigste. Stoppen Sie die "Optimierung". "Optimierung" spielt überhaupt keine Rolle. Wie Sie gesehen haben, ist nur das Umschreiben im Großhandel von Bedeutung.

Deshalb.

Zweite. Verstehen Sie die Auswirkungen jeder Datenstruktur und Algorithmusauswahl.

Dritte. Machen Sie die tatsächliche Wahl der Datenstruktur und des Algorithmus zu einer Frage der "späten Bindung". Entwerfen Sie Schnittstellen, für die eine von mehreren Implementierungen hinter der Schnittstelle verwendet werden kann.

Was Sie jetzt tun (Umschreiben), sollte viel, viel weniger schmerzhaft sein, wenn Sie eine Reihe von Schnittstellen definiert haben, mit denen Sie die Datenstruktur oder den Algorithmus umfassend ändern können.

S.Lott
quelle
1
Danke für deine Antwort. Während wir noch optimieren müssen (was für mich unter 1. und 2. fällt), mag ich das organisierte Denken hinter 3. Ich mag es sehr, Datenstruktur, Algorithmus und Zugriff spät und explizit zu definieren, um viele in den Griff zu bekommen Probleme, mit denen wir konfrontiert sind. Vielen Dank, dass Sie es in eine zusammenhängende Sprache gebracht haben.
Benjamin Bannier
Sie müssen eigentlich nicht optimieren. Sobald Sie die richtige Datenstruktur haben, wird die Optimierung als Verschwendung von Aufwand angezeigt. Die Profilerstellung zeigt, wo Sie eine falsche Datenstruktur und einen falschen Algorithmus haben. Das Herumalbern mit dem Leistungsunterschied zwischen ++und +=1ist irrelevant und fast nicht messbar. Es ist das, was Sie dauern müssen .
S.Lott
1
Nicht alle schlechten Algorithmen können durch reines Denken gefunden werden. Hin und wieder muss man sich hinsetzen und profilieren. Dies ist der einzige Weg, um herauszufinden, ob die anfängliche Vermutung richtig war. Nur so können die tatsächlichen Kosten (BigO + const) geschätzt werden.
Benjamin Bannier
Bei der Profilerstellung werden schlechte Algorithmen angezeigt. Völlig richtig. Das ist immer noch keine "Optimierung". Das ist immer noch die Korrektur eines grundlegenden Designfehlers, den ich bei einer Designänderung vorgenommen habe. Optimierungen (Optimierungen, Feinabstimmungen usw.) sind für die Profilerstellung selten sichtbar.
S.Lott
3

Ein guter praktischer Trick besteht darin , Ihre Unit-Test-Suite als Leistungstestsuite zu verwenden .

Der folgende Ansatz hat in meinen Codebasen gut funktioniert:

  1. Stellen Sie sicher, dass Ihre Unit-Test-Abdeckung gut ist (Sie haben dies bereits getan, oder?)
  2. Stellen Sie sicher, dass Ihr Testlauf-Framework die Laufzeit für jeden einzelnen Test meldet . Dies ist wichtig, da Sie herausfinden möchten, wo eine langsame Leistung stattfindet.
  3. Wenn ein Test langsam abläuft, verwenden Sie dies, um in diesen Bereich einzutauchen und eine Optimierung zu erreichen . Die Optimierung vor dem Erkennen eines Leistungsproblems kann als verfrüht angesehen werden. Das Tolle an diesem Ansatz ist daher, dass Sie zuerst konkrete Beweise für eine schlechte Leistung erhalten. Teilen Sie den Test bei Bedarf in kleinere Tests auf, die verschiedene Aspekte vergleichen, damit Sie feststellen können, wo das Grundproblem liegt.
  4. Wenn ein Test extrem schnell ausgeführt wird, ist dies normalerweise gut, obwohl Sie dann möglicherweise in Betracht ziehen, den Test in einer Schleife mit unterschiedlichen Parametern auszuführen. Dies macht es zu einem besseren Leistungstest und erhöht auch Ihre Testabdeckung des Parameterraums.
  5. Schreiben Sie einige zusätzliche Tests, die speziell auf die Leistung abzielen, z. B. End-to-End-Transaktionszeiten oder Zeit zum Abschließen von 1.000 Regelanwendungen. Wenn Sie bestimmte nicht funktionale Leistungsanforderungen haben (z. B. <300 ms Reaktionszeit), schlagen Sie den Test fehl, wenn er zu lange dauert.

Wenn Sie dies alles weiterhin tun, sollte sich die durchschnittliche Leistung Ihrer Codebasis im Laufe der Zeit organisch verbessern.

Es wäre auch möglich, historische Testzeiten zu verfolgen und Leistungsdiagramme zu zeichnen und Regressionen im Zeitverlauf bei der durchschnittlichen Leistung zu erkennen. Ich habe mich nie darum gekümmert, hauptsächlich, weil es etwas schwierig ist, sicherzustellen, dass Sie beim Ändern und Hinzufügen neuer Tests Gleiches mit Gleichem vergleichen, aber es könnte eine interessante Übung sein, wenn die Leistung für Sie ausreichend wichtig ist.

mikera
quelle
Ich mag die Technik - klug - aber dies ist eine Mikrooptimierung und wird auf ein lokales Minimum verbessert - sie wird keine Architekturprobleme lösen, die es Ihnen ermöglichen, globale Minima zu erreichen
Jason
@ Jasonk - du hast absolut recht. Obwohl ich hinzufügen möchte, dass es Ihnen manchmal die Beweise geben kann, die Sie benötigen, um zu demonstrieren, warum eine bestimmte architektonische Änderung gerechtfertigt ist .....
mikera
1

Die Antwort von @dasblinkenlight weist auf ein sehr häufiges Problem hin, insbesondere bei großen Codebasen (meiner Erfahrung nach). Möglicherweise gibt es schwerwiegende Leistungsprobleme, die jedoch nicht lokalisiert sind . Wenn Sie einen Profiler ausführen, gibt es keine Routinen, die alleine genug Zeit benötigen, um Aufmerksamkeit zu erregen. (Angenommen, Sie betrachten den Prozentsatz der inklusive Zeit, der Callees enthält. Kümmern Sie sich nicht einmal um die "Selbstzeit".)

In diesem Fall wurde das eigentliche Problem nicht durch Profilerstellung, sondern durch glückliche Einsicht gefunden.

Ich habe eine Fallstudie, für die es eine kurze PDF-Diashow gibt , in der dieses Problem detailliert dargestellt wird und wie man damit umgeht. Der grundlegende Punkt ist, da der Code viel langsamer ist als er sein könnte, dass (per Definition) die überschüssige Zeit für etwas aufgewendet wird, das entfernt werden könnte.

Wenn Sie sich einige zufällige Stichproben des Programmstatus ansehen würden, würden Sie aufgrund des prozentualen Zeitaufwands nur sehen, dass es die entfernbare Aktivität ausführt. Es ist durchaus möglich, dass die entfernbare Aktivität nicht auf eine Funktion oder sogar viele Funktionen beschränkt ist. Es lokalisiert nicht so.

Es ist kein "Hot Spot".

Es ist eine Beschreibung, die Sie von dem machen, was Sie sehen, die in einem großen Prozentsatz der Zeit wahr ist. Das macht es einfach zu entdecken, aber ob es leicht zu beheben ist, hängt davon ab, wie viel Umschreiben erforderlich ist.

(Es wird häufig kritisiert, dass die Anzahl der Stichproben für die statistische Validität zu gering ist. Dies wird auf Folie 13 des PDF beantwortet. Kurz gesagt: Ja, es besteht eine hohe Unsicherheit bei der "Messung" potenzieller Einsparungen, aber 1) Der erwartete Wert dieser potenziellen Einsparungen bleibt im Wesentlichen unberührt, und 2) wenn die potenziellen Einsparungen von $ x $ in ein Beschleunigungsverhältnis von $ 1 / (1-x) $ umgerechnet werden, ist er stark auf hohe (vorteilhafte) Faktoren ausgerichtet.)

Mike Dunlavey
quelle
Danke für deine Antwort. Wir glauben nicht an statistische Stichproben und verwenden Instrumente mit Valgrind. Dies gibt uns gute Schätzungen sowohl der "Selbst" - als auch der "Inklusiv" -Kosten der meisten Dinge, die wir tun.
Benjamin Bannier
@honk: Richtig. Leider hat die Instrumentierung immer noch die Idee, dass Leistungsprobleme lokalisiert sind und daher durch Messen des Bruchteils der Zeit, die in Routinen usw. verbracht wird, gefunden werden können. Sie können Valgrind usw. ausführen, aber wenn Sie einen echten Einblick in die Leistung wünschen, schauen Sie sich diese Diashow an .
Mike Dunlavey