Möglichkeiten Code zu optimieren (z.B. Laufzeit verringern)

[Uwe Raabe]

Zitat von Redeemer:

Hatte das aus der Doku geschlossen:

Zitat:

Auf manchen Plattformen erzeugt Inc u. U. hochoptimierten Maschinencode, der sich besonders für enge Schleifen eignet.

Ist dann wohl falsch.

Für Win32 offenbar, wobei der Compiler für jede Plattform nur wenig intelligent sein muss, um für Farbe := Farbe + 1 den gleichen Code wie für Inc(Farbe) auszugeben. Andere Plattformen kommen wegen Extended aber auch wohl nicht in Frage.

[jbg]

Zitat von Redeemer:

Zitat:

Auf manchen Plattformen erzeugt Inc u. U. hochoptimierten Maschinencode, der sich besonders für enge Schleifen eignet.

Ist dann wohl falsch.

So als historischer Hintergrund: Bis TurboPASCAL 5.5 war Inc() schneller. Seit TurboPASCAL 5.5 hat der Compiler gelernt, dass "A := A + 1" dasselbe wie "Inc(A)" ist. Der Doku-Satz wurde wohl aus älteren Handbüchern übernommen. Selbst der wirklich schlecht optimierende Win64 Delphi Compiler kennt diese Optimierung. Und die "LLVM Backend" Compiler haben damit überhaupt kein Problem.

[Gausi]

Diese Diskussion, wie man den Code so schreibt, dass man noch ein paar Takte sparen kann, ist sicherlich interessant. Aber ich denke, dass die hier nicht zielführend ist.

Wenn ich Truther richtig verstehe, dann hat er keine High-Performance-Situation, wo es wichtig ist, dass man noch die letzten paar Mikro- oder gar Nanosekunden einspart. Ich denke eher, dass sein Programm "spürbar" zu lange dauert. Ob das in dem Fall nun ein paar Sekunden sind, oder evtl. sogar in den Minutenbereich geht, kann ich nicht abschätzen. Da liegt der Flaschenhals mit ziemlicher Sicherheit nicht bei "inc vs. x+1", sondern ganz woanders.

Bei "Bilder auf Ähnlichkeit prüfen" würde ich wie gesagt ganz stark auf "Canvas.Pixels" tippen, oder generell auf ein Verfahren mit kubischer Laufzeit (also 3-fach ineinander geschachtelte Schleife o.ä.), für das es ggf. sinnvollere Alternativen gibt.

Wirklich konkret kann man aber ohne weitere Details zur Aufgabe und dem vorhandenen Code nicht werden. Denn wie in den verlinkten Folien in der Zusammenfassung schön zitiert: "Algorithmen zu optimieren ist eine Kunst".

[jaenicke]

Mich wundert, dass noch kein Profiler angesprochen wurde. Es gibt Tools, die analysieren welcher Teil des Codes wie lange benötigt. Daraus kann man dann ableiten wo man optimieren sollte, wenn möglich.

Die wirklich guten Profiler sind nicht gerade billig, aber dieser hier ist für den Anfang ganz gut:
https://yavfast.github.io/dbg-spider/
Quelltext:
https://github.com/yavfast/dbg-spider

[Truther]

Zitat von Delphi.Narium:

"Alle Berechnungen, deren Ergebnis mehr als einmal benötigt wird, wird nur einmal berechnet und das Ergebnis in einer Variabel gespeichert. Danach wird statt der Berechnung die Variabel genommen."

"Bei Grafikbearbeitung ist es hilfreich, für die Zeit der Berechnung alle Bildschirmaktuallisierungen zu deaktivieren. Ggfls. das Programm zu Beginn der Berechnung minimieren und am Ende der Berechnung wieder auf die normale Größe bringen."

Das sind auf jeden Fall schon mal hilfreiche Sachen. Da würde ich noch ListBox.Items.BeginUpdate und ListBox.Items.EndUpdate einwerfen, was sich auf das Neuzeichnen von grafischen Komponenten bezieht.

Zitat von Gausi:

"Der erste Schritt dazu ist, die sogenannte Komplexität des vorhandenen Algorithmus abzuschätzen."

Man kommt also nicht drum herum, sich mit dieser Thematik genauer zu beschäftigen? Falls nicht, könnte jemand z.B. Bücher dazu empfehlen oder reicht schon eine Suche im Netz?
... Okay, offenbar gibt es gute Videos auf z.B. YouTube, die das gut erklären (siehe unten).

Zitat von Gausi:

"Zur Verdeutlichung ein ganz einfaches Beispiel: Du hast eine sortierte Liste mit Zahlen gegeben, und möchtest wissen, an welcher Stelle dieser Liste eine Zahl X steht."

Für mich ist dieses Beispiel zu konkret auf ein Fallbeispiel. Ich hatte da eher an allgemeinere Sachen gedacht, unabhängig davon, welchen Algorithmus man programmiert, wie eben das Beispiel, dass man manche Berechnungen nicht andauernd wiederholt, sondern die Ergebnisse in eine Variable packt und dann auf diese zugreift, sofern diese nur einmal berechnet werden müssen, versteht sich.

Zitat von Gausi:

"Der zweite Ansatz ist, den Algorithmus generell so zu belassen, aber die Ausführungsgeschwindigkeit dadurch zu verbessern, dass man das Verfahren geschickter implementiert."

Das klingt für mich eher nach dem, was ich suche. Ich hatte bei meinem Projekt den Aufruf Image.Colors[X, Y].Red , womit ich nur auf einen Farbkanal (Rot) eines Pixel zugreife, wenn ich mich nicht irre. Als ich das durch ScanLine ersetzt hatte, war es deutlich schneller, auch wenn ich nicht weiß, warum es an sich schneller ist.


Auszug aus einem Wikipedia-Artikel zum Thema "Overhead":

Zitat von Wikipedia:

"Overhead wird aber auch ganz allgemein als Zusatzarbeit übersetzt, die z. B. durch Schleifen oft und unnötig durchgeführt werden muss, erst recht, wenn ein Abbruch-Kriterium schon erreicht war."

Sowas z.B. wäre auch etwas Allgemeines, was die Laufzeit optimieren würde.

Zitat von
Algorithmen und Datenstrukturen (YouTube-Kanal):

"Multiplizieren länger dauert als Addieren."

Video mit Zeitstempel (ab ca. Minute 4): https://youtu.be/D8n5qnyFIKc?t=244

Solche Sachen wären auch interessant zu wissen. Aber da es auch mitunter von der Programmiersprache abhängt (Aussage aus dem Video), kann man das nicht so sagen, das Addieren schneller als Multiplizieren ist.
Das wäre dann in etwa gleichzusetzen mit der Problematik oben zu Inc() und i := i + 1 .

Wenn ich asymptotische Laufzeit richtig verstanden habe, bedeutet das, dass man grob sagen kann, wie die Laufzeit wäre (z.B linear oder quadratisch), aber nicht exakt bestimmen kann, wie der exakte Verlauf der Kurve ist, richtig?

Zitat von Gausi:

"Wenn man so einen Code auf Scanline umschreibt, wird der Code um ein vielfaches schneller, auch wenn der zugrundeliegende Algorithmus die gleiche asymptotische Zeitkomplexität hat."

Also ist es dann eher eine Frage der Implementierung anstatt einer schnelleren asymptotischer Laufzeit?

Zitat von Gausi:

"Wenn ich Truther richtig verstehe, dann hat er keine High-Performance-Situation, wo es wichtig ist, dass man noch die letzten paar Mikro- oder gar Nanosekunden einspart. Ich denke eher, dass sein Programm "spürbar" zu lange dauert."

Naja, wenn ich z.B. Millionen von Pixel vergleichen muss, um mal das Beispiel von meinem gescheiterten Bildvergleichsprogramm aufzugreifen, und das von mehreren tausenden Bildern, dann macht das schon was aus.

Zitat:

"Algorithmen zu optimieren ist eine Kunst".

Aber es muss doch Methoden geben, um diese Kunst zu erlernen.

Bei der Speicherreservierung (Allokation) bspw. für dynamische Arrays habe ich gelesen, dass es sinnvoll ist, wenn, sobald man mehr Elemente eines solchen Arrays hinzufügen möchte, die Länge des Arrays jeweils verdoppelt.

Artikel dazu: http://delphiblog.twodesk.com/dynami...ow-to-use-them

Zitat von delphiblog.twodesk.com:

"When the time comes to reallocate the array, double its size: SetLength(arr, Length(arr) * 2). Research shows that this strikes the ideal balance between time and space for most cases."

Auch hatte ich mal aufgeschnappt, dass das Arbeiten mit Pointern die Laufzeiten auch verbessern können. Ob das stimmt, weiß ich nicht. Ich wüsste auch nicht, wie da der Zusammenhang wäre.

@jaenicke Das werde ich mir mal ansehen, auch wenn vielleicht nicht für Delphi sondern für Lazarus. Für Lazarus gibt es wohl auch solch Profiler. (https://wiki.freepascal.org/LazProfiler)

[dummzeuch]

Scanline zu verwenden ist schonmal ein guter Ansatz, allerdings ist auch jeder Scanline-Aufruf ziemlich langsam (zumindest in Delphi, keine Ahnung, ob das bei Lazarus auch so ist). Da lohnt es sich, die einzelnen Zeilen selbst per Pointer-Artithmetik zu ermitteln.

[himitsu]

Bei so kleinen Schleifen, die sehr oft schnell durchlaufen werden, funktionieren die Profiler auch nicht unbedingt sehr gut,

aber ansonsten sind die schon ganz praktisch.


Bezüglich Scanline: Man kann das auch einmal am Anfang in ein Array auslesen
oder nur den Anfang (eigentlich das Ende) sich holen, in einen Pointer, und dann Zeilen/Spalten entsprechend daraus berechen.

[Sinspin]

Zitat von Truther:

Naja, wenn ich z.B. Millionen von Pixel vergleichen muss, um mal das Beispiel von meinem gescheiterten Bildvergleichsprogramm aufzugreifen, und das von mehreren tausenden Bildern, dann macht das schon was aus.

Klar, gerade als Anfänger ist man da schnell überfordert, aber das macht es doch erst richtig interessant wenn es klemmt einen Weg zu finden das es weniger klemmt
Dank des Internets sind da draußen umglaubliche massen an Beispielen wie man dies oder jenes Problem angehen kann, und selber experimentieren ist schon immer der beste Weg gewesen etwas neues zu erfinden.

[TSchnuckenbock]

Zitat von jaenicke:

Mich wundert, dass noch kein Profiler angesprochen wurde. Es gibt Tools, die analysieren welcher Teil des Codes wie lange benötigt. Daraus kann man dann ableiten wo man optimieren sollte, wenn möglich.

Die wirklich guten Profiler sind nicht gerade billig, aber dieser hier ist für den Anfang ganz gut:
https://yavfast.github.io/dbg-spider/
Quelltext:
https://github.com/yavfast/dbg-spider

Ich hab mir das Spider-Projekt mal kompiliert. Nur jetzt weiß ich nicht, wie ich genau was damit machen kann. Gibt es dazu irgendwie/irgendwo eine Anleitung? Muß die Dll irgendwie ins zu analysierende Projekt eingebunden werden?
Ich hab noch nie mit so Profilern gearbeitet.