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

[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:

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

Delphi-Quellcode:

ListBox.Items.BeginUpdate

und

Delphi-Quellcode:

ListBox.Items.EndUpdate

einwerfen, was sich auf das Neuzeichnen von grafischen Komponenten bezieht.

Zitat:

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:

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:

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

Delphi-Quellcode:

Image.Colors[X, Y].Red

, womit ich nur auf einen Farbkanal (Rot) eines Pixel zugreife, wenn ich mich nicht irre. Als ich das durch

Delphi-Quellcode:

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:

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:

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

Delphi-Quellcode:

Inc()

und

Delphi-Quellcode:

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:

Zitat von Gausi

"Wenn man so einen Code auf

Delphi-Quellcode:

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:

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:

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.

[Incocnito]

Zitat:

Zitat von Delphi.Narium (Beitrag 1497915)

...

Delphi-Quellcode:

    z     := x * x - y + y + 2 * a;  // x² - y² + 2a

...

Hehe ... das wäre auch nicht richtig ;-)

[Sinspin]

Zitat:

Zitat von Truther (Beitrag 1497938)

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.

[Delphi.Narium]

Zitat:

Zitat von Incocnito (Beitrag 1497952)

Zitat:

Zitat von Delphi.Narium (Beitrag 1497915)

...

Delphi-Quellcode:

    z     := x * x - y + y + 2 * a;  // x² - y² + 2a

...

Hehe ... das wäre auch nicht richtig ;-)

Upps, das ist ein Schreibfehler, der nur hier im Forum auftaucht. Im Original kann ich ihn nicht finden. Was ist denn da nur wieder in meinem Schreibfehlerchaos passiert?
Natürlich muss es

Delphi-Quellcode:

z     := x * x - y * y + 2 * a;  // x² - y² + 2a

heißen:pale:

[Andreas13]

Zitat:

Zitat von Delphi.Narium (Beitrag 1497915)

...Natürlich muss es

Delphi-Quellcode:

z     := x * x - y * y + 2 * a;  // x² - y² + 2a

heißen:pale:

Wahrscheinlich wäre noch eine Mikrosekunde Ersparnis dabei, wenn man anstelle von

Delphi-Quellcode:

2*a

besser

Delphi-Quellcode:

a + a

schreibt...:-D
Gruß, Adreas

[himitsu]

Beim Integer ist Mal schneller, weil ja "nur" ein Shift.

Aber hätte gedacht, dass es beim Float auch zutrifft.

[Truther]

Ich bin hier auf diese Seite gestoßen, die sich mit Optimierung von Code befasst.

Link: http://www.rinneberg.de/programming/opti.htm

Was sind eure Meinungen dazu? Vielleicht könnte man auf jeden einzelnen Punkt davon eingehen und näher erläutern, sofern das nicht auf der Seite selbst geschehen ist.
Möglicherweise könnte man diese Liste eben auch erweitern.

Nachtrag: In einem Artikel zu Fast direct pixel gibt es einen Punkt zu Pointer. Dort steht:

Zitat:

With use of pointers we can eliminate much of pixel address addition and multiplication by Pixels property access. Only fast increment operation is performed.

Link: https://wiki.lazarus.freepascal.org/...ccess#Pointers

Warum ist das Nutzen von Pointer in dem Fall schneller? Das würde sich auf die Implementierungsfrage beziehen, wie oben an dem Beispiel von

Delphi-Quellcode:

ScanLine

.
Könnte man sagen, dass das Nutzen von Pointern in der Regel schneller ist?