Was ist wirklich langsam?

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.

berniebutt

@Bashar: Richtig, ich hatte Iteration nicht Integration gemeint! War ein fataler Lapsus.
@otze: So trivial mit dem richtigen Algorithmus ist das auch nicht. Selbst wenn er stimmt kann man durch unnötige Dinge noch viel unnütze Rechenzeit verbraten.

Fazit: Optimierungen lohnen nur, wenn es deutlich um Rechenzeit geht. Den Kleinkram kann man getrost dem intelligenten Compiler überlassen. Den Anwender interessiert es nicht, ob er für ein Ergebnis z.B. 200 Millisekunden statt vieleicht erreichbare 100 Millisekunden auf ein Ergebnis wartet. Oder man kitzelt den Zeitgewinn mit viel Aufwand selbst heraus. Also meine Meinung: Alle Bemühungen zur Optimierung nur dort ansetzen, wo es richtig etwas bringen kann. Und das sind nun einmal oft durchlaufene Programmstellen (Schleifen aller Art), Lösungsalgorithmen, und wie zitiert Zugriffe auf eine Datenbank.

Leider kann man ein Programm durch Ölen wie ein Fahrrad selbst nicht schneller machen.

berniebutt schrieb:

Den Anwender interessiert es nicht, ob er für ein Ergebnis z.B. 200 Millisekunden statt vieleicht erreichbare 100 Millisekunden auf ein Ergebnis wartet.

Wenn der "Anwender" ein 100ms-Task ist schon

rüdiger

berniebutt schrieb:

4. Zeigerarithmetik nutzen

Das ist doch eher schlecht wegen des möglichen aliasing.

abc.w

100 Millisekunden

könnten übrigens 10 fps (frames per second) ermöglichen

Meine schönste Optimierung: http://www.c-plusplus.net/forum/viewtopic-var-p-is-1024198.html

tntnet

berniebutt schrieb:

@Bashar: Richtig, ich hatte Iteration nicht Integration gemeint! War ein fataler Lapsus.
@otze: So trivial mit dem richtigen Algorithmus ist das auch nicht. Selbst wenn er stimmt kann man durch unnötige Dinge noch viel unnütze Rechenzeit verbraten.

Fazit: Optimierungen lohnen nur, wenn es deutlich um Rechenzeit geht. Den Kleinkram kann man getrost dem intelligenten Compiler überlassen. Den Anwender interessiert es nicht, ob er für ein Ergebnis z.B. 200 Millisekunden statt vieleicht erreichbare 100 Millisekunden auf ein Ergebnis wartet. Oder man kitzelt den Zeitgewinn mit viel Aufwand selbst heraus. Also meine Meinung: Alle Bemühungen zur Optimierung nur dort ansetzen, wo es richtig etwas bringen kann. Und das sind nun einmal oft durchlaufene Programmstellen (Schleifen aller Art), Lösungsalgorithmen, und wie zitiert Zugriffe auf eine Datenbank.

100 Millisekunden später kann schon mal ein paar millionen Euro ausmachen, wenn es um Tradingsysteme geht. Gerade als C++-Programmierer hat man häufig nicht einfach nur den GUI-Benutzer im Sinn.

Und noch dazu können sich 100 Millisekunden ganz schnell aufaddieren. Bei einem komplexen System können hier und da immer wieder mal 100 Millisekunden verplempert werden, so dass gleich ein paar Sekunden oder noch mehr raus kommen.

hustbaer

berniebutt schrieb:

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.

Ich habe auch "trimmen" noch nie im Zusammenhang mit "Algorithmus" gehört/gelesen, und bezweifle dass das allgemein von Naturwissenschaftlern verstanden wird.

tntnet schrieb:

100 Millisekunden später kann schon mal ein paar millionen Euro ausmachen, wenn es um Tradingsysteme geht.

Damit wäre alles Trading reiner Zufall, weil kein Trader im 100ms Bereich reagiert.

Und noch dazu können sich 100 Millisekunden ganz schnell aufaddieren. Bei einem komplexen System können hier und da immer wieder mal 100 Millisekunden verplempert werden, so dass gleich ein paar Sekunden oder noch mehr raus kommen.

Merkst du was der Unterschied zwischen premature Optimization und optimieren an der richtigen Stelle ist. Mit dem Addieren der Zeit kommst du zu dem was berniebutt schreibt.

blue-tec

Wenn man das Geld/Zeit hat würde ich immer versuchen zu optimieren. Viele sagen bei z.B GUI lohnt das nicht, das sehe ich anders. Wenn du eine Arbeitsfläche mit z.B. 50 UML-Elementen hast, die per GUI-Framework gezeichnet werden, macht es schon einen großen Unterschied ab das Zeichnen und Verwalten 100ms oder nur 10ms-50ms dauert.

Was ich bis jetzt gelernt und gelesen habe optimiert der Compiler zwar so einiges aber es wird nie so gut sein können um eine Implementierung einfach von Grund aus anders angehen zu können, siehe Volkards Paradebeispiel.

Meiner Meinung nach brauch man nicht Alles zu optimieren, aber die Haltung von heute so gut wie gar nicht zu optimieren finde ich auch nicht richtig denn das ist Ressourcen- und damit Energieverschwendung. Aber ich kann auch verstehen wenn es wirtschaftlich keinen Sinn macht zu optimieren.

Gruß Blue-Tec

blue-tec schrieb:

Wenn man das Geld/Zeit hat würde ich immer versuchen zu optimieren. Viele sagen bei z.B GUI lohnt das nicht, das sehe ich anders. Wenn du eine Arbeitsfläche mit z.B. 50 UML-Elementen hast, die per GUI-Framework gezeichnet werden, macht es schon einen großen Unterschied ab das Zeichnen und Verwalten 100ms oder nur 10ms-50ms dauert.

Was ich bis jetzt gelernt und gelesen habe optimiert der Compiler zwar so einiges aber es wird nie so gut sein können um eine Implementierung einfach von Grund aus anders angehen zu können, siehe Volkards Paradebeispiel.

Meiner Meinung nach brauch man nicht Alles zu optimieren, aber die Haltung von heute so gut wie gar nicht zu optimieren finde ich auch nicht richtig denn das ist Ressourcen- und damit Energieverschwendung. Aber ich kann auch verstehen wenn es wirtschaftlich keinen Sinn macht zu optimieren.

Die Haltung von heute ist auch nicht, Programme gar nicht zu optimieren, sondern nur das, was messbar zu langsam ist. Man schreibt nur nicht von Anfang an total komplizierten, "optimierten" und kryptischen Code, in der Hoffnung, dass man hier und da 3 Operationen spart. Man überlegt sich besser, welche Algorithmen die richtigen sind und wie ein sauberes Design aussieht, dass man das Programm einfach warten und erweitern kann. Dann kann man auch einfach einen zu langsamen Algorithmus austauschen oder optimieren, ohne das ganze Programm anpassen zu müssen. Das Beispiel von volkard ist eben kein Paradebeispiel, weil es viel zu klein ist. Große Programme die von vielen Leuten geschrieben werden, sind viel zu komplex, um einfach sagen zu können, was viel Zeit brauchen wird. Ich glaub es gibt irgend einen Spruch, dass man Programme erst mal zum laufen bekommen soll, dann stabil und dann schnell. Nur für den letzen Teil hat man heute nur noch sehr wenig Zeit (oft auch schon für die ersten beiden Teile), weil irgendwelche Manager das Zeug auf den Markt werfen wollen, wenn es halbwegs stabil läuft.

blue-tec

Ich teile auch die Meinung zuerst die Funktion dann die Optimierung, aber zu komplex kann keine Ausrede sein. Komplexe Software wird auch unterteilt und wenn nicht der Mensch erkennt wo der Flaschenhals ist dann sind es Unit-Tests oder Profiler die da helfen können. Das Design der Software muss dafür natürlich ausgelegt sein.

Meine Rede war auch nicht jedes feuchtes Lüftchen auf eine ns zu untersuchen, sondern die Stellen die stark frequentiert werden zu analysieren.