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

Sie sollten wahrscheinlich die "Google-Perspektive" in Betracht ziehen, d. h. herausfinden, wie Ihre Anwendung weitgehend parallelisiert und nebenläufig werden kann, was zwangsläufig auch bedeutet, dass Sie sich irgendwann mit der Verteilung Ihrer Anwendung auf verschiedene Maschinen und Netzwerke befassen müssen, so dass sie im Idealfall fast linear mit der Hardware skalieren kann, die Sie ihr zur Verfügung stellen.

Andererseits sind die Google-Leute auch dafür bekannt, dass sie viel Arbeitskraft und Ressourcen in die Lösung einiger Probleme in den von ihnen verwendeten Projekten, Tools und Infrastrukturen stecken, wie zum Beispiel Optimierung des gesamten Programms für gcc indem ein engagiertes Team von Ingenieuren die Interna des gcc hackt, um ihn für Google-typische Anwendungsszenarien vorzubereiten.

Ebenso bedeutet das Profiling einer Anwendung nicht mehr nur, den Programmcode zu profilieren, sondern auch alle umgebenden Systeme und die Infrastruktur (z.B. Netzwerke, Switches, Server, RAID-Arrays), um Redundanzen und Optimierungspotenziale aus Systemsicht zu identifizieren.

Answer 2

• Inline-Routinen (Abschaffung von Call/Return und Parameter Pushing)
• Versuchen Sie, Tests/Switches mit Tabellen-Look-ups zu eliminieren (wenn sie schneller sind)
• Schleifen (Duff's device) so weit abrollen, dass sie gerade noch in den CPU-Cache passen
• Speicherzugriff lokalisieren, um den Cache nicht zu sprengen
• Zusammenhängende Berechnungen lokalisieren, wenn der Optimierer dies nicht bereits tut
• Beseitigung von Schleifeninvarianten, wenn der Optimierer dies nicht bereits tut

Answer 3

• Wenn Sie den Punkt erreicht haben, an dem Sie effiziente Algorithmen verwenden, stellt sich die Frage, was Sie mehr brauchen Geschwindigkeit oder Speicher . Nutzen Sie die Zwischenspeicherung, um im Speicher für mehr Geschwindigkeit zu "bezahlen", oder verwenden Sie Berechnungen, um den Speicherbedarf zu verringern.
• Wenn möglich (und kostengünstiger) das Problem mit Hardware bekämpfen - Eine schnellere CPU, mehr Speicher oder eine Festplatte könnten das Problem schneller lösen als der Versuch, es zu codieren.
• Parallelisierung verwenden wenn möglich - einen Teil des Codes auf mehreren Threads laufen lassen.
• Verwenden Sie das richtige Werkzeug für die Aufgabe . einige Programmiersprachen erzeugen effizienteren Code, die Verwendung von verwaltetem Code (z.B. Java/.NET) beschleunigt die Entwicklung, aber native Programmiersprachen erzeugen schneller laufenden Code.
• Mikro optimieren . Nur dort, wo es anwendbar ist, können Sie optimierte Assembler verwenden, um kleine Teile des Codes zu beschleunigen; die Verwendung von SSE/Vektor-Optimierungen an den richtigen Stellen kann die Leistung erheblich steigern.

Answer 4

Aufteilen und erobern

Wenn der zu verarbeitende Datensatz zu groß ist, wird eine Schleife über Teile des Datensatzes gezogen. Wenn Sie Ihren Code richtig gemacht haben, sollte die Implementierung einfach sein. Wenn Sie ein monolithisches Programm haben, wissen Sie es jetzt besser.

Answer 5

Wie bereits in mehreren früheren Antworten erwähnt, sollten Sie zunächst herausfinden, was Ihre Leistung beeinträchtigt - ist es der Speicher, der Prozessor, das Netzwerk, die Datenbank oder etwas anderes? Je nach dem...

• ...wenn es am Gedächtnis liegt - finden Sie eines der Bücher, die vor langer Zeit von Knuth geschrieben wurden, eines aus der Reihe "The Art of Computer Programming". Höchstwahrscheinlich ist es eines über Sortierung und Suche - wenn ich mich falsch erinnere, dann müssen Sie es herausfinden, in dem er darüber spricht, wie man mit langsamer Banddatenspeicherung umgeht. Verwandeln Sie gedanklich seine Speicher/Band Paar in Ihr Paar Cache/Hauptspeicher (bzw. in das Paar L1/L2-Cache). Studieren Sie alle Tricks, die er beschreibt - wenn Sie nichts finden, was Ihr Problem löst, beauftragen Sie einen professionellen Informatiker mit der Durchführung einer professionellen Untersuchung. Wenn Ihr Speicherproblem zufällig mit der FFT zusammenhängt (Cache-Misses bei bitumgekehrten Indizes bei Radix-2-Butterflies), dann engagieren Sie keinen Wissenschaftler - optimieren Sie stattdessen manuell einen Durchlauf nach dem anderen, bis Sie entweder gewonnen haben oder in eine Sackgasse geraten sind. Sie erwähnten bis auf die letzten Prozent ausquetschen oder? Wenn es wenige In der Tat werden Sie höchstwahrscheinlich gewinnen.

• ...wenn es ein Prozessor ist - auf Assembler umstellen. Prozessor-Spezifikation studieren - was Zecken braucht VLIW, SIMD. Funktionsaufrufe sind höchstwahrscheinlich austauschbare Zeckenfresser. Lernen Sie Schleifentransformationen - Pipeline, Unroll. Multiplikationen und Divisionen können durch Bitverschiebungen ersetzt/interpoliert werden (Multiplikationen mit kleinen ganzen Zahlen können durch Additionen ersetzt werden). Probieren Sie Tricks mit kürzeren Daten aus - wenn Sie Glück haben, kann eine Anweisung mit 64 Bits durch zwei mit 32 oder sogar 4 mit 16 oder 8 mit 8 Bits ersetzt werden - stellen Sie sich vor. Versuchen Sie auch länger Daten - z.B. können Ihre Fließkommaberechnungen bei einem bestimmten Prozessor langsamer ausfallen als Doppelkommaberechnungen. Wenn Sie trigonometrisches Material haben, bekämpfen Sie es mit vorberechneten Tabellen; denken Sie auch daran, dass der Sinus eines kleinen Wertes durch diesen Wert ersetzt werden könnte, wenn der Verlust an Genauigkeit innerhalb der zulässigen Grenzen liegt.

• ...wenn es sich um ein Netzwerk handelt - denken Sie an die Komprimierung der Daten, die Sie über das Netzwerk übertragen. Ersetzen Sie die XML-Übertragung durch Binärdaten. Studieren Sie Protokolle. Versuchen Sie UDP anstelle von TCP, wenn Sie irgendwie mit Datenverlust umgehen können.

• ...wenn es um Datenbanken geht, dann gehen Sie in ein beliebiges Datenbankforum und fragen Sie um Rat. In-Memory-Daten-Grid, Optimierung der Abfrageplan etc etc etc.

HTH :)