Wie können Sie die Komplexität in der Praxis in Ihrem großen Softwareprojekt messen?

11

In unseren Algorithmenkursen lernen wir an der Universität, wie man die Komplexität verschiedener einfacher Algorithmen, die in der Praxis verwendet werden, wie z. B. Hash-Tabellen oder schnelle Sortierung, genau berechnet.

Aber jetzt, in einem großen Softwareprojekt, wenn wir es schneller machen wollen, schauen wir uns nur einzelne Teile an - ein paar verschachtelte Schleifen, die durch eine schnellere Hash-Tabelle ersetzt werden können, eine langsame Suche hier, die beschleunigt werden kann Eine ausgefallenere Technik - aber wir berechnen niemals die Komplexität unserer gesamten Pipeline.

Gibt es eine Möglichkeit, das zu tun? Oder verlassen sich die Menschen in der Praxis nur auf "lokal" mithilfe eines schnellen Algorithmus, um die gesamte Anwendung schneller zu machen, anstatt die Anwendung global als Ganzes zu betrachten?

(Weil es mir nicht trivial erscheint, zu zeigen, dass Sie, wenn Sie eine große Anzahl von Algorithmen stapeln, von denen bekannt ist, dass sie für sich genommen sehr schnell sind, auch eine schnelle Anwendung als Ganzes erhalten.)

Ich frage dies, weil ich die Aufgabe habe, ein großes Projekt zu beschleunigen, das jemand anderes geschrieben hat, in dem viele Algorithmen interagieren und an Eingabedaten arbeiten. Daher ist mir unklar, wie sich die Beschleunigung einzelner Algorithmen auswirkt die ganze Anwendung.

user7088941
quelle
1) Dies erfordert einen Testansatz, um die zu verbessernden Punkte zu finden. Benchmark-Tests, Haltbarkeitstests, dynamische Tests (durch Überwachen der Speicher- / CPU-Metriken jeder Komponente). 2) Nachdem Sie die Punkte gefunden haben, die verbessert werden sollen, finden Sie die Grundursache für diese Punkte. 3) Finden Sie eine Lösung, um die Grundursache zu lösen und die Richtigkeit zu wahren.
Überaustausch
Sie benötigen einige Werkzeuge für diese Tests in Punkt 1 erwähnt
Übertausch
1
Die Big O-Analyse sagt Ihnen nicht, wie ein Algorithmus funktioniert. Hier erfahren Sie, wie sich die Leistung mit zunehmender Leistung skaliertn .
John Wu

Antworten:

5

Große Softwareprojekte bestehen aus vielen verschiedenen Komponenten, und nicht alle sind in der Regel ein Engpass. Im Gegenteil: Für fast jedes Programm in meinem Leben, bei dem eine geringe Leistung ein Problem war, galt das Pareto-Prinzip : Mehr als 80% der Leistungssteigerungen können durch Optimierung von weniger als 20% des Codes erzielt werden (in Wirklichkeit ich denke, die Zahlen waren oft mehr 95% bis 5%).

Daher ist es oft der beste Ansatz, sich einzelne Stücke anzuschauen. Aus diesem Grund ist die Profilerstellung (wie in der Antwort von David Arno erläutert ) in Ordnung, da Sie damit die genannten 5% des Codes identifizieren können, bei denen Sie durch die Optimierung den "größten Gewinn für das Geld" erzielen. Die Optimierung "der gesamten Anwendung" birgt ein gewisses Risiko einer Überentwicklung. Wenn Sie diese 95% sogar um den Faktor 10 optimieren, hat dies häufig keine messbaren Auswirkungen. Beachten Sie auch, dass die Profilerstellung weitaus mehr aussagt als jede hypothetische Algorithmuskomplexitätsschätzung, da ein einfacher Algorithmus, der O (N ^ 3) -Schritte benötigt, immer noch schneller sein kann als ein komplexer Algorithmus, der O (N log (N)) benötigt, solange N. ist klein genug.

Nachdem die Profilerstellung die Hot Spots aufgedeckt hat, kann man sie optimieren. Natürlich kann ein "Hot Spot" größer sein als nur eine oder zwei Codezeilen. Manchmal muss man eine ganze Komponente ersetzen, um sie schneller zu machen, aber das ist normalerweise immer noch ein kleiner Teil der Codebasis in einem größeren Programm .

Typische Optimierungstechniken umfassen

  • Verbesserung der Verwendung von Algorithmen und Datenstrukturen

  • Feinabstimmung des ersteren

  • Mikrooptimierungen an einigen echten Hot Spots

  • Neukodieren kritischer Abschnitte mithilfe von Assemblycode oder CUDA

Beachten Sie, dass diese Techniken auf verschiedenen Abstraktionsebenen arbeiten. Einige von ihnen betrachten eine Komponente "als Ganzes" mehr als andere. Es kommt also darauf an, was Sie unter "Alles, was wir tun, ist, einzelne Teile zu betrachten" verstehen. Wenn Sie nur Mikrooptimierungen im Auge hatten, bin ich nicht der Meinung, dass "wir" nur daran arbeiten. Wenn Sie jedoch diese umfassenden Optimierungen auf einzelne Teile oder Komponenten anwenden möchten, arbeiten "wir" wahrscheinlich an den richtigen Teilen, und Sie sollten Ihre Erwartungen in Frage stellen.

Doc Brown
quelle
13

Die bewährte Standardmethode ist das Profilieren des Codes . Sie führen eine dynamische Analyse des laufenden Systems durch, um das Timing, die Speichernutzung usw. zu messen. Anschließend analysieren Sie die Ergebnisse, um Leistungsengpässe zu ermitteln.

Diese Engpässe werden dann experimentell umgeschrieben und das Ergebnis erneut profiliert, um festzustellen, dass eine Geschwindigkeitssteigerung, eine Verringerung der Speichernutzung usw. erreicht wurde. Dieser Vorgang wird dann wiederholt, bis ein akzeptabler Leistungsgewinn erreicht ist.

David Arno
quelle
1
Dies löst das Leistungsproblem, weshalb wir es tun, aber die ursprüngliche Frage nicht beantworten. Ich denke, dass im schlimmsten Fall die Komplexität von Zeit oder Raum am besten mit einem statischen Programmanalysetool ermittelt werden kann, das möglicherweise fehlt. Leistungstests eignen sich hervorragend für bestimmte Szenarien, sagen jedoch nicht viel über die schlimmsten Situationen aus.
Frank Hileman
3
@FrankHileman Ich denke, der Punkt hier ist, dass Leistung ein praktisches Anliegen ist und nur praktisch gemessen werden kann. Sie verwenden keine Mathematik, um den Engpass Ihrer Software zu ermitteln, selbst wenn Sie ihn möglicherweise mithilfe von Mathematik (Algorithmen) lösen.
Wildcard
In der alten Diashow-Präsentation (Glasdias) gab es eine vorgetäuschte Technologie, mit der die durchschnittliche Dichte einer Laternenrutsche sorgfältig mathematisch berechnet werden kann, um die Helligkeit des zu verwendenden Lichts zu bestimmen. Völlig nutzlos: Wenn das Bild nicht gut angezeigt wird, erhalten Sie ein helleres Licht!
Wildcard
@Wildcard Während die Leistung nur zur Laufzeit gemessen werden kann, kann sie statisch vorhergesagt werden. Eine schlechte Auswahl einer Datenstruktur kann in Leistungstests in Bezug auf die Leistung gut aussehen, in Randfällen, die in einer statischen Analyse vorhergesagt werden könnten, kläglich scheitern. Dies ist der gleiche Grund, warum wir uns die Worst-Case-Komplexitätsanalysen für Datenstrukturen im Allgemeinen ansehen.
Frank Hileman
@Wildcard: Sie haben Recht, aber Frank ist auch sehr richtig, dass dieser Beitrag die Frage nicht beantwortet.
Doc Brown
3

Obwohl die anderen Antworten richtig sind und eine Anleitung geben, denke ich, dass sie einen Schritt verpassen. In einem komplexen System, mit dem Sie gerade arbeiten, ist das Verständnis der verschiedenen Komponenten des Systems der Schlüssel zum Verständnis, warum etwas langsam ist.

Mein erster Schritt wäre, ein detailliertes Architekturdiagramm in die Hände zu bekommen oder selbst eines zu erstellen. Finden Sie heraus, welche Schritte von welchen Komponenten in der Software ausgeführt werden und wie lange jeder Schritt dauert.

Stellen Sie außerdem fest, wie die Komponenten miteinander interagieren. Dies kann den Unterschied ausmachen.

Ich habe beispielsweise Code in C # gesehen, bei dem die Schnittstelle zwischen zwei Komponenten eine von der ersten Komponente erstellte IEnumerable übergeben hat, die dann von der zweiten Komponente aufgelistet wurde. In C # erfordert dies eine Kontextumschaltung, die unter bestimmten Umständen kostspielig sein kann. Das Lösen hat keine Auswirkungen auf den Algorithmus. Eine einfache .ToList () stellt sicher, dass das Ergebnis erfasst wird, bevor der nächste Schritt dieses Problem löst.

Eine weitere zu berücksichtigende Sache ist die Auswirkung auf das System, auf dem Sie den Code ausführen. Hardware-Interaktionen können offensichtlich ein Faktor in komplexen Systemen sein. Suchen Sie nach Festplatten-E / A, großen Speicherzuordnungen und Netzwerk-E / A. Manchmal können diese Probleme effizienter gelöst werden, indem das System optimiert oder sogar die Hardware ausgetauscht wird.

Jonathan van de Veen
quelle