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

[Truther]

Moinsen Leute,

ich habe versucht ein Programm mit Lazarus zu schreiben, welches Bilder auf Ähnlichkeit prüft, nur um dann festzustellen, dass mein Programm extrem langsam ist und selbst nach meinen Optimierungsversuchen es nicht wirklich besser wurde, weshalb ich auf eine vorhandene Bibliothek (OpenCV) versuche, zurzückzugreifen.
Mit der Installation habe ich meine Probleme und warte, bis es auf GetIt veröffentlicht wird. Hier geht es zum entsprechenden Thread: https://www.delphipraxis.net/209296-...y-edition.html

Das nur so nebenbei.

Dann stellte ich mir die Frage: Gibt es generelle Möglichkeiten, die Laufzeit von Code zu verbessern/optimieren, ohne ein Informatikstudium absolviert zu haben? Gibt es Literatur oder Videos dazu, die auch ein Laie versteht?

Ich habe zum Beispiel das hier gefunden: Ein Vortrag von Prof. Dr. Nikolaus Wulff mit dem Thema "Systementwicklung" http://www.lab4inf.fh-muenster.de/la...erung-SS12.pdf

Darin geht es überwiegend um die Potenzierungsfunktion und wie man diese optimieren kann.

Ich bin sehr gespannt auf eure Antworten!

Truther

[Delphi.Narium]

Mal ein Beispiel aus meinem Fraktalgenerator:

Zuerst das Original:

Delphi-Quellcode:

FUNCTION Formel101(a         : Extended;
                   b         : Extended;
                   Faktor    : Extended;
                   Iteration : Longint;
                   Art       : Integer  ):LongInt;
VAR x,y,z  : Extended;
    Farbe  : INTEGER;
BEGIN  (* Apfelmann mit Spitze nach links *)
  x     := 0;
  y     := 0;
  Farbe := 0;
  REPEAT
    z     := x * x - y + y + 2 * a;  // x² - y² + 2a
    y     := 2 * x * y + 3 * b;  // 2 * x * y + 3b
    x     := z;
    Farbe := Farbe + 1;
  UNTIL (Farbe = Iteration) OR (x * x + y * y > Faktor);
  Formel101 := GetFarbe(Farbe,x * x,y * y,x * y,Iteration,art);
END;

und dann die schnellere Methode:

Delphi-Quellcode:

FUNCTION Formel101(a         : Extended;
                   b         : Extended;
                   Faktor    : Extended;
                   Iteration : Longint;
                   Art       : Integer  ):LongInt;
VAR x,y,z  : Extended;
    aa, bb : Extended;
    xx,yy  : Extended;
    xy     : Extended;
    Farbe  : INTEGER;
BEGIN  (* Apfelmann mit Spitze nach links *)
  x     := 0;
  y     := 0;
  Farbe := 0;
  aa    := a + a;
  bb    := b + b + b;
  xx    := 0;
  yy    := 0;
  REPEAT
    z     := xx - yy + aa;  // x² - y² + 2a
    xy    := x * y;
    y     := xy + xy + bb;  // 2 * x * y + 3b
    x     := z;
    xx    := x * x;
    yy    := y * y;
    Farbe := Farbe + 1;
  UNTIL (Farbe = Iteration) OR (xx + yy > Faktor);
  Formel101 := GetFarbe(Farbe,xx,yy,xy,Iteration,art);
END;

Wenn's um Rechnerei geht, kann man eigentlich recht pauschal sagen:

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.

Der Geschwindigkeitsvorteil kann dann schonmal (je nach Komplexität) um die 25% (wenn man Glück hat aber auch deutlich mehr) betragen.

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 langsamste bei der Grafikbearbeitung ist halt die Darstellung auf dem Bildschirm.

[Gausi]

Es gibt da generell zwei Ansätze:

Der erste wäre der, einen Algorithmus zu verwenden, der "prinzipiell schneller" ist. Der erste Schritt dazu ist, die sogenannte Komplexität des vorhandenen Algorithmus abzuschätzen. Das ist ein Teil, den man im Theorie-Teil des Informatik-Studiums lernt. Allerdings könnten die Grundlagen dazu auch schon in der Schule gelehrt werden, imho.

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.
Möglichkeit 1: du schaust dir jedes einzelne Element der Liste an und vergleichst es mit X. Dabei nutzt du die Sortierung der Liste aber nicht aus.
Möglichkeit 2: Du nutzt die Sortierung der Liste: Dazu schaust du dir zuerst das Element in der Mitte der Liste an. Ist das gesuchte X größer, brauchst du die ganze erste Hälfte der Liste nicht mehr zu checken - dort kann es nicht sein. Im anderen Fall kannst du die zweite Hälfte weglassen. Und dann suchst du mit dem gleichen Verfahren nur in dem interessanten Teil weiter.

Der wesentliche Unterschied zwischen den beiden Verfahren ist, dass die Binärsuche konzeptionell schneller ist: Die suche ist nach grob Log(n)-vielen Schritten abgeschlossen (n ist die Anzahl der Elemente in der Liste), bei dem ersten Verfahren benötigt man grob n viele Schritte.

Mit etwas mehr Mathematik liest sich das dann so: https://de.wikipedia.org/wiki/Landau-Symbole, dort findest du auch einige Beispiele zu "effizienten" und nicht ganz so effizienten Algorithmen für einfache klassische Probleme, z.B. für das Sortieren von Zahlen.

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

Bei der Bildverarbeitung ist z.B. ein Klassiker für sehr, sehr langsamen Code die Verwendung von Bitmap.Canvas.Pixels[] , um die RGB-Werte eines Pixels im Bild zu bestimmen. 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.

[Redeemer]

Zitat von Delphi.Narium:

Delphi-Quellcode:

FUNCTION Formel101(a         : Extended;
                   b         : Extended;
                   Faktor    : Extended;
                   Iteration : Longint;
                   Art       : Integer  ):LongInt;
VAR x,y,z  : Extended;
    aa, bb : Extended;
    xx,yy  : Extended;
    xy     : Extended;
    Farbe  : INTEGER;
BEGIN  (* Apfelmann mit Spitze nach links *)
  x     := 0;
  y     := 0;
  Farbe := 0;
  aa    := a + a;
  bb    := b + b + b;
  xx    := 0;
  yy    := 0;
  REPEAT
    z     := xx - yy + aa;  // x² - y² + 2a
    xy    := x * y;
    y     := xy + xy + bb;  // 2 * x * y + 3b
    x     := z;
    xx    := x * x;
    yy    := y * y;
    Farbe := Farbe + 1;
  UNTIL (Farbe = Iteration) OR (xx + yy > Faktor);
  Formel101 := GetFarbe(Farbe,xx,yy,xy,Iteration,art);
END;

Kein gutes Beispiel, denn:

• Farbe := Farbe + 1; schreibt man nicht, man schreibt Inc(Farbe); . Macht auch ein bisschen was aus.
• Bei a + a würde ich vermuten, dass hier eine Multiplikation besser wäre, da im Prinzip der Exponent inkrementiert wird, wenn Compiler/CPU so intelligent sind. Unter Win32 (allerdings sonst nirgendwo) könnte man eventuell auch ein PWord auf @Extended setzen und PWord^ inkrementieren, aber Endianness macht das kompliziert. Wird aber eh nur einmal ausgefühlt.
• Wenn ich nicht komplett auf dem Schlauch stehe, hat die Variable z überhaupt keine Funktion und man kann man das noch weiter kürzen:
  
  Delphi-Quellcode:

    REPEAT
      xy    := x * y;
      y     := xy + xy + bb;  // 2 * x * y + 3b
      x     := xx - yy + aa;  // x² - y² + 2a
      xx    := x * x;
      yy    := y * y;
      Inc(Farbe);
    UNTIL (Farbe = Iteration) OR (xx + yy > Faktor);

[Uwe Raabe]

Zitat von Redeemer:

Farbe := Farbe + 1; schreibt man nicht, man schreibt Inc(Farbe); . Macht auch ein bisschen was aus.

Das ist aber wohl eher ein Mythos. So sieht der mit Delphi 11 Win32 ohne Overflow-Checking erzeugte Code aus:

Delphi-Quellcode:

Project861.dpr.8: Farbe := 0;
0040A104 33C0             xor eax,eax
0040A106 A388F54000       mov [$0040f588],eax
Project861.dpr.9: Farbe := Farbe + 1;
0040A10B FF0588F54000     inc dword ptr [$0040f588]
Project861.dpr.10: Inc(Farbe);
0040A111 FF0588F54000     inc dword ptr [$0040f588]
Project861.dpr.11: end.
0040A117 E8B0BBFFFF       call @Halt0

[Redeemer]

Zitat von Uwe Raabe:

Zitat von Redeemer:

Farbe := Farbe + 1; schreibt man nicht, man schreibt Inc(Farbe); . Macht auch ein bisschen was aus.

Das ist aber wohl eher ein Mythos. So sieht der mit Delphi 11 Win32 ohne Overflow-Checking erzeugte Code aus:

Delphi-Quellcode:

Project861.dpr.8: Farbe := 0;
0040A104 33C0             xor eax,eax
0040A106 A388F54000       mov [$0040f588],eax
Project861.dpr.9: Farbe := Farbe + 1;
0040A10B FF0588F54000     inc dword ptr [$0040f588]
Project861.dpr.10: Inc(Farbe);
0040A111 FF0588F54000     inc dword ptr [$0040f588]
Project861.dpr.11: end.
0040A117 E8B0BBFFFF       call @Halt0

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.

[Delphi.Narium]

@Redeemer

Schön, dass Du es besser weißt.

Aber diese Methode ist durch ausprobieren entstanden und dabei hat sich gezeigt, das bei vielen tausenden Berechnungen a + a schneller als 2 * a ist und das Farbe := Farbe + 1 schneller als Inc(Farbe) ist, auch wenn immer wieder behauptet wird, Inc sei schneller. (Wobei man hier vermutlich deutlich zwischen dem Inc von Pascal und dem Inc im erzeugten Maschinencode unterscheiden muss, bei 'nem intelligenten Compiler dürfte / sollte da der gleiche Maschinencode rauskommen. - siehe Uwes Beispiel )

Und es ist nicht auszuschließen, dass sich identischer Quelltext unter einem anderen Compiler (in Bezug auf die Ausführungsgeschwindigkeit) vollkommen anders verhält, einfach weil anderer Maschinencode daraus kommt.

Die Routine wurde halt nur von Turbo-Pascal 5 bis Delphi 7 in der Form genutzt. Vielleicht gehen neuere Delphicompiler oder Lazarus und FreePascal damit vollkommen anders um.

Sprich: Es kommt nicht darauf an, ob Farbe := Farbe + 1 schneller als Inc(Farbe) ist, sondern darauf, wie der Compiler das letztlich umsetzt. Und dann nimmt man jeweils die schneller Variante Die wesentliche Zeitersparnis liegt eh in der Reduzierung der Multiplikationen, die fressen die Zeit

Außerdem war nach Ideen gefragt und nicht nach ultimativ immer richtigen Vorgehensweisen Derweil: Die gibt es (vermutlich) nicht.

Und ja: Die Berechnung in der Schleife kann man in der Tat noch ein bisserl optimieren.

[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".