Was ist wirklich langsam?

Was habt ihr schon optimiert und wieviel hat es gebracht?

Meine Optimierungen waren meistens verschachtelte Schleifen, die nicht ganz so offensichtlich waren. Also in einer Schleife wird eine Methode eines Objekts aufgerufen die wieder ein paar aufruft und irgendwo ist wieder eine Schleife. Z.B. innere Schleife ist Suche auf Liste (oder nach Values von Map) -> ersetzt und Suche in Map/ zweite Map. Hat Rechenvorgang von 2-3 Minuten um ca. eine Minute verkürzt.

hustbaer

Ich hab schon so viel optimiert, den Grossteil davon weiss ich nimmer.
Ein paar Beispiele die mir noch einfallen:

* SQL Cursor + Schleifen gegen Statements getauscht die viele Zeilen auf einmal bearbeiten. Gewinn immens, Laufzeit auf 1/10 und z.T. weniger gesunken.

* Caching von Daten die aus ner Datenbank zusammengeklaubt werden müssen in der Form wie sie die Applikation verarbeitet. Gewinn wieder immens, genau kann ichs nicht sagen aber Gefühlt wieder weit mehr als Faktor 10.

* Caching von Daten die von einem sehr langsamen Datenträger gelesen werden. Gewinn immens.

* Suchen der "best fit" Font-Grösse für Text der nicht grösser als ein gewisses Bound werden darf - binäre Suche statt linearer Suche. Gewinn zwischen nix und ca. Faktor 5 (im realen Einsatz; theoretisch beliebig viel schneller, wenn man den Startwert für die lineare Suche "unpassend" genug wählt).

* 2D "Blitting" Schleife mit einfachem Alpha-Blending optimiert. Einfache lineare Optimierungen wie Array-Lookup statt "if", "schlauere" Alpha-Blending Formel die mit einer Multiplikation auskommt, Bearbeiten von Rot + Blau gleichzeitig etc. Gewinn ca. Faktor 1.5 bis 2.

* Unnötige Flusswechsel (send - receive - send ...) bei TCP/IP Kommunikation zwischen Client und Server eliminiert (z.B. stapelweise bestätigung dass der Server bestimmte Daten weggeschrieben hat statt für jeden Datensatz einzeln). Gewinn Faktor >> 2 (weiss nimmer genau, hat sich aber gewaltig ausgezahlt).

* Redundante Retry-Schleife beim Suchen verschiedener Geräte entfernt. Vorher 3x3 Versuche (3 Versuche in einer höheren Schicht mal je 3 Versuche in der darunterliegenden Schicht), nachher nurmehr 3x1 Versuche. Gewinn fast Faktor 3. (Die Geräte hängen an einer seriellen Verbindung die nicht 100.0% verlässlich ist. Daher Retry nötig. Im Normalfall sind nicht alle Geräte vorhanden, daher läuft das Programm immer in die Retry-Schleife. Daher enormer Gewinn.)

Scheppertreiber

So eine Art Compiler von Basic nach C übertragen - Gewinn: Faktor 2000
(der VPf hatte nicht mehr pflegbaren Spaghetticode verbrochen)

berniebutt

Optimierungsmöglichkeiten gibt es oft viele, müssen sich aber lohnen. Hier einige weitere Hinweise:

1. Schalter (falls vorhanden) des Compilers nutzen (BCB optimiert recht gut)
2. Laufzeitintensive Stellen suchen und nur diese betrachten - Millisekunden lohnen nicht den Aufwand
3. Schleifen, vor allem verschachtelte Schleifen genauer ansehen
-- Mehrfachberechnungen vermeiden
-- Mehrfachindizierte Arrays in der Folge der Speicherung bearbeiten
-- ggfs. inline-Assembler-Code einfügen (falls Compiler das unterstützt)
4. Zeigerarithmetik nutzen
5. x * x ist schneller als pow(x,2)
6. Algorithmen mit Integration trimmen

knivil

Was ist wirklich langsam?

Mein Fahrrad. Etwas Oel hat es um 5% beschleunigt. Natuerlich konnte das Oel nicht beliebig verteilt werden.

Antoras

knivil schrieb:

Was ist wirklich langsam?

Mein Fahrrad. Etwas Oel hat es um 5% beschleunigt. Natuerlich konnte das Oel nicht beliebig verteilt werden.

Bei mir hats geholfen die Reifen mal wieder aufzupumpen. Leistungssteigerung: bestimmt 50%

berniebutt

@Knivil, Antoras: Die Hinweise auf eure Fahrräder sind amüsant. Trinkt vorher einen Energy-Drink, dann holt ihr nochmal 5-15% Zeit heraus!

Die Frage ist und bleibt aber durchaus interessant und sollte deswegen seriöser behandelt werden. Es ging um Minuten, nicht um belanglose Millisekunden. Bei z.B. technisch-wissenschaftlichen Aufgaben kommt das schon mal vor und jede Optimierung kann dann grosse Vorteile bringen!

hustbaer

berniebutt schrieb:

4. Zeigerarithmetik nutzen

was soll das schneller machen?

6. Algorithmen mit Integration trimmen

kannst du das nochmal auf verständlich schreiben?

Die Schalker Abwehr

Jockelx

Das kann man sich ja Heute fast gar nicht mehr vorstellen:
Auf'm C64 hat bei meinem Fussballmanager der Basic-Bubblesort zur Tabellenberechnung (2x18 Mannschaften) unerträglich lange gedauert.
Der Performancegewinn durch Assembler war gigantisch und eines meiner schönsten Programmiererlebnisse.
Ach ja, Programmieren hat schonmal mehr spass gemacht...

Bashar

Ich hab mal ein Matlabscript um 2 Größenordnungen beschleunigt, das war schon was Von 1 Stunde auf <1 Minute.

SeppJ

Eines meiner ersten Programme: Anstatt Dateien immer wieder zu öffnen und zu schließen, habe ich sie die ganze Zeit offen gehalten. War hinterher 25x schneller.

Etwas weniger lang her (und daher etwas schwerer zu verstehen): Eine Lösung mit statischer Polymorphie geschrieben, die ungefähr so aussah:

Zeitkritische Schleife
{
  Unterschleife Typ1
  {
    Zeitkritische Berechnungen auf Container vom Typ1
  }
  Unterschleife Typ2
  {
    Zeitkritische Berechnungen auf Container vom Typ2
  }
  Unterschleife Typ3
  {
    Zeitkritische Berechnungen auf Container vom Typ3
  }
  // Und so weiter, je nach benötigter Anzahl Typen
}

Performanceanalyse hat ergeben, dass dies schlecht skalierte mit der Anzahl der Typen, da die Containergröße häufig sehr klein war. Daher war relativ viel Overhead durch die Unterschleifen vorhanden. dies habe ich daher umgeschrieben zu:

Zeitkritische Schleife
{
  Unterschleife
  {
    Zeitkritische Operationen auf Container mit Basisklassenzeigern, benutzt virtuelle Funktionen
  }
}

Ergebnis: Trotz virtual nicht messbar langsamer als die statische Variante für 1 Typ, dabei aber immer gleich schnell unabhängig von der Anzahl der beteiligten Klassen. Fand ich sehr gut, weil man das wirklich wunderbar im Profiler sehen konnte, dass die Schleifen selbst der Overhead waren und weil das Programm am Ende auch viel einfacher zu warten ist. Und man muss noch sagen: Die ursprüngliche Entscheidung zu statischer Polymorphie war ganz klar premature optimization und wie man sieht war sie tatsächlich the root of all evil.

edit: Und noch einer zu Interpreter vs. Compiler: Ein Datenanlysescript von Python auf C++ umgeschrieben. Das gab einen Geschwindigkeitsgewinn von etwa 5-10. Geschätzt, nicht gemessen. Es war jedenfalls gewaltig viel schneller. Hab mir vorgenommen in Zukunft solche Sachen häufiger in C++ zu schreiben, so viel länger dauert die Entwicklungszeit dort auch nicht, wenn man erstmal einen Grundstock an guten Klassen hat.

DerBaer

ganz Klasisch: von VB auf Java / C umgestiegen. Das erste mal dachte ich, ich hab micch vertippt, weil ich 100 mal sooft mein Prog laufen lassen hab, um überhaupt eine Zeit > 0 zu messen xD.

ansonsten: richtigen Algorithmus verwenden. Ich denke mir öfters: Naja Bubblesort wird ja wohl reichen. Aber langsam verwende ich den gar nicht mehr, weil Quicksort deutlich schneller ist und sogar einfacher zu schreiben^^

auch hilfreich: erstmal in standardlibraries suchen obs die Funktienen nicht schon gibt. Die sind irgendwie trotzdem immer schnell er als eigener Code (trotz gleichem algorythmus xD)

berniebutt schrieb:

3. Schleifen, vor allem verschachtelte Schleifen genauer ansehen
-- Mehrfachberechnungen vermeiden

Klingt simpel, passiert aber schnell. Bei Datenbankzugriffen die durch allgemeine Schnittstellen abstrahiert sind, liest man oft viel mehr aus, als durch eine spezielle Abfrage.

DerBaer schrieb:

Ich denke mir öfters: Naja Bubblesort wird ja wohl reichen. Aber langsam verwende ich den gar nicht mehr, weil Quicksort deutlich schneller ist und sogar einfacher zu schreiben^^

Ich denke mir öfters: wozu selber schreiben, wenn doch jede brauchbare bibliothek gut implementierte sortierroutinen mitbringt?

Bashar schrieb:

Ich hab mal ein Matlabscript um 2 Größenordnungen beschleunigt, das war schon was Von 1 Stunde auf <1 Minute.

Also von Schleifen-Matlab auf Matlab umgeschrieben?

Ich hab schon öfters (kleinere) Simulink-Simulationen entweder als reinen (und ordentlichen) Matlab-Code oder gleich als Mex-Funktion umgeschrieben. Da holt man sehr leicht Faktor 50-100 raus. Lohnt sich dann schon wenn man die Dinger mehrere hundert/tausend mal durchsimuliert.

Blue-Tiger

Von elendslangsamen Datenbank dazu uebergegangen, die Daten von Hand zu parsen. Parser in C++ geschrieben, Rest des Programms in R gelassen. Ausfuehrungszeit ging von ~6 Tagen runter auf knapp 12 Stunden

EDIT: Daten dann nochmal umzurechnen und in Binaerformat abzuspeichern brachte nochmal Faktor 10

berniebutt

hustbaer schrieb:

Algorithmen mit Integration trimmen. Kannst du das nochmal auf verständlich schreiben?

Naturwissenschaftlern und Ingenieueren ist das hinreichend verständlich. Oft sind Aufgaben nicht durch eine feste Formel oder durch ein einfaches lineares Gleichungssystem genau genug lösbar. Dann braucht man eine 'Schrittweise Annäherung = Iteration' mit einem bekannten Kriterium für die Genauigkeit einer Zielgrösse (Konvergenzkriterium).

Stelle dir vor, du brauchst für jeden einzelnen Iterationsschritt ein grösseres lineares Gleichungssystem (z.B. 1000 x 1000). Dessen Lösung braucht Rechenzeit. Es kommt also entscheidend darauf an, wieviele Iterationsschritte man bis zum Ziel benöntigt (10 oder gar 1000). Das Finden einer passenden Startbedingung und die Verbesserung bei jedem neuen Iterationsschritt sind dann das 'Trimmen des Algorithmus', um die Anzahl der erforderlichen Iterationen möglichst gering zu halten.

Bashar

berniebutt schrieb:

hustbaer schrieb:

Algorithmen mit Integration trimmen. Kannst du das nochmal auf verständlich schreiben?

Naturwissenschaftlern und Ingenieueren ist das hinreichend verständlich.[Schnipp]

Du hast eine seltsam umständliche Art, "Sorry, ich meinte Iteration, nicht Integration" zu sagen.

otze

berniebutt schrieb:

hustbaer schrieb:

Algorithmen mit Integration trimmen. Kannst du das nochmal auf verständlich schreiben?

Naturwissenschaftlern und Ingenieueren ist das hinreichend verständlich.

Nein.

Der Rest deines Posts liest sich wie "den richtigen Algorithmus für das Problem verwenden". Obwohl diese Aussage relativ trivial anmutet, muss man sie doch als Korrekt anerkennen.