Was ist wirklich langsam?

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.

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