Geht das noch schneller? - Bitmap-Verrechnung

[samso]

Ich habe einige sehr einfache Änderungen vorgenommen. Bei mir benötigt der Algorithmus dann nur noch die halbe Zeit. Das Ergebnis ist nicht identisch mit dem alten Algorithmus. Die Ursache liegt meiner Meinung nach im Floatingpoint-Rundungsalgorithmus begründet. Das Bild sieht aber nicht offensichtlich falsch aus.

Delphi-Quellcode:

procedure Draw32BitToBitmapSamso(const BitOben: TBitmap; BitUnten: TBitmap);
var
   h, w, i: Integer;
   RGBA_Unten, RGBA_Oben: PRGBQuad;
begin
    for h := 0 to BitUnten.Height-1 do begin
     RGBA_Unten := BitUnten.ScanLine[h];
     RGBA_Oben := BitOben.ScanLine[h];

     For w:= 0 to BitUnten.Width-1 do begin
       if RGBA_Oben^.rgbReserved = 0 then begin
         // unten bleibt
       end else begin
         i := RGBA_Unten^.rgbBlue - (RGBA_Unten^.rgbBlue - RGBA_Oben^.rgbBlue) * RGBA_Oben^.rgbReserved div 256;
         if i < 0 then RGBA_Unten^.rgbBlue := 0 else RGBA_Unten^.rgbBlue := i;

         i := RGBA_Unten^.rgbGreen - (RGBA_Unten^.rgbGreen - RGBA_Oben^.rgbGreen) * RGBA_Oben^.rgbReserved div 256;
         if i < 0 then RGBA_Unten^.rgbGreen := 0 else RGBA_Unten^.rgbGreen := i;

         i := RGBA_Unten^.rgbRed - (RGBA_Unten^.rgbRed - RGBA_Oben^.rgbRed) * RGBA_Oben^.rgbReserved div 256;
         if i < 0 then RGBA_Unten^.rgbRed := 0 else RGBA_Unten^.rgbRed := i;

         RGBA_Unten^.rgbReserved := 255;
       end;
       inc(RGBA_Unten); inc(RGBA_Oben);
    end;
   end;
end;

[Harry Stahl]

Erst mal vielen Dank an Euch fürs mit überlegen, ich finde es echt spannend, hier die anderen Ansätze mal zu sehen. Jede der zuletzt genannten Varianten war immer ein weniger schneller als die Ausgangsfunktion.

Ich habe jetzt einfach mal bei ImageEn nachgesehen, die ich hier lizenziert habe, wie die das machen. Da ist das Bild zwar auch geringfügig unterschiedlich als meine Ausgangsfunktion, aber vielleicht war meine ja auch nicht korrekt.

Jedenfalls in Anlehnung an die ImageEn-Lösung kann man das hier so machen ist das ist dann mit 71 MS die bislang schnellste Lösung und toppt sogar die Parallel-Lösung. Da ist dann irgendwann anscheinend der Zeitbedarf für das Management des Threading größer, als der Zeitgewinn durch den Einsatz mehrerer Kerne. Insofern muss man sich genau ansehen, wann man die Parallelisierung einsetzt. Besserer Code geht also meistens doch noch vor Parallel-Bearbeitung. Wahrscheinlich lohnt sich die Parallelisierung eher bei Prozessen, die eh schon etwas länger dauern.

Delphi-Quellcode:

// Setz vorraus, dass die Bitmaps die gleiche Größe haben!!!
procedure Draw32BitToBitmap(const BitOben: TBitmap; BitUnten: TBitmap);
var
  h,w,i: Integer;
  RGBA_Unten, RGBA_Oben: pRGBALine;
begin
  For h := 0 to BitUnten.Height-1 do begin
    RGBA_Unten := BitUnten.ScanLine[h];
    RGBA_Oben := BitOben.ScanLine[h];

    For w:= 0 to BitUnten.Width-1 do begin
      if RGBA_Oben^[w].rgbReserved = 0 then begin
        // unten bleibt
      end else begin
        (* Das war die Ausgangslösung
        i := Round (RGBA_Unten^[w].rgbBlue - ((RGBA_Unten^[w].rgbBlue - RGBA_Oben^[w].rgbBlue) / 255 * RGBA_Oben^[w].rgbReserved));
        if i < 0 then RGBA_Unten^[w].rgbBlue := 0 else if i > 255 then RGBA_Unten^[w].rgbBlue := 255 else RGBA_Unten^[w].rgbBlue := i;

        i := Round (RGBA_Unten^[w].rgbGreen - ((RGBA_Unten^[w].rgbGreen - RGBA_Oben^[w].rgbGreen) / 255 *  RGBA_Oben^[w].rgbReserved));
        if i < 0 then RGBA_Unten^[w].rgbGreen := 0 else if i > 255 then RGBA_Unten^[w].rgbGreen := 255 else RGBA_Unten^[w].rgbGreen := i;

        i := Round (RGBA_Unten^[w].rgbRed - ((RGBA_Unten^[w].rgbRed - RGBA_Oben^[w].rgbRed) / 255 * RGBA_Oben^[w].rgbReserved));
        if i < 0 then RGBA_Unten^[w].rgbRed := 0 else if i > 255 then RGBA_Unten^[w].rgbRed := 255 else RGBA_Unten^[w].rgbRed := i;
        *)

        RGBA_Unten^[w].rgbred := (RGBA_Oben^[w].rgbReserved * (RGBA_Oben^[w].rgbred - RGBA_Unten^[w].rgbred) shr 8 + RGBA_Unten^[w].rgbred);
        RGBA_Unten^[w].rgbGreen := (RGBA_Oben^[w].rgbReserved * (RGBA_Oben^[w].rgbgreen - RGBA_Unten^[w].rgbGreen) shr 8 + RGBA_Unten^[w].rgbGreen);
        RGBA_Unten^[w].rgbBlue := (RGBA_Oben^[w].rgbReserved * (RGBA_Oben^[w].rgbBlue - RGBA_Unten^[w].rgbBlue) shr 8 + RGBA_Unten^[w].rgbBlue);

        RGBA_Unten^[w].rgbReserved := 255;
      end;
   end;
  end;
end;

[mensch72]

super... das war eigentlich exakt das was ich dir gerade als "Berechnungslösung" vorschlagen wollte, denn auch wenn ich das vor Jahren woanders her kopiert habe... das sieht einfach schön klar aus

Ich würde aber eine zusätzliche Sicherheitsklammerung einführen, damit auch wirklich erst multipliziert wird und erst dann dividiert(shr 8) wird... das sollte genauer sein, wenn hier bicht absichtlich mit den BitUmschlag im Shift gerechnet wird.

RGBA_Unten^[w].rgbred := ((RGBA_Oben^[w].rgbReserved * (RGBA_Oben^[w].rgbred - RGBA_Unten^[w].rgbred)) shr 8 + RGBA_Unten^[w].rgbred);
RGBA_Unten^[w].rgbGreen := ((RGBA_Oben^[w].rgbReserved * (RGBA_Oben^[w].rgbgreen - RGBA_Unten^[w].rgbGreen)) shr 8 + RGBA_Unten^[w].rgbGreen);
RGBA_Unten^[w].rgbBlue := ((RGBA_Oben^[w].rgbReserved * (RGBA_Oben^[w].rgbBlue - RGBA_Unten^[w].rgbBlue)) shr 8 + RGBA_Unten^[w].rgbBlue);

Einen Versuch wäre es wert

[Dejan Vu]

Zitat von mensch72:

Ich würde aber eine zusätzliche Sicherheitsklammerung einführen, damit auch wirklich erst multipliziert wird und erst dann dividiert(shr 8) wird...

Wie kann ich mir das vorstellen? Ohne Sicherheitsklammerung wird erst multipliziert und dann dividiert, aber *mit* Sicherheits(!)klammerung wird wirklich erst multipliziert und erst dann dividiert, richtig? Woran erkennt man den Unterschied? Ist das eine Ergebnis richtig, aber das andere voll korrekt?

Im Ernst: Mit Sicherheitsklammerung wird ein Programm nicht besser, nur der WTF-Faktor* erhöht sich. Nun ist es aber gerade erstrebenswert, den WTF-Faktor auf 0 zu setzen.

(*) WTF-Faktor: WTF-Shouts / LoC.

PS: Muldiv hat eingebaute Sicherheitsklammerung.

[mensch72]

=> solange alles es in der Wertebereich der Operatoren passt, bei Ganzzahl-Arithmetik IMMER erst "vergrößern" (also addieren oder multiplizieren oder "shl") und dann verkleinern(also subtrahieren, dividieren oder "shr")

=> weil Pascal hier nicht immer das mach was ich will oder ich auch oft zu nur faul zum Nachzudenken, was der Kompiler draus macht, gebe ich es lieber vor), klammere da lieber einmal zuviel wie zu wenig, außerdem merkt so ein anderer welcher das liest, das man hier besonderen Wert auf die Rechenreihefolge gelegt hat und kommt nicht auf die Idee, weil's eventuell schöner "aussieht" aus "100 * 128 div 256" etwa "128 div 256 * 100" zu machen... mit "WTF" hat dies also nix zu tun!

=> Mein Vertrauen in die math. & logische Hierarchie der Operatoren von Pascal ist leider etwas getrübt, denn wenn man von C/C++ kommt ist das in Pascal bei AND & OR ständig nötige Klammern, weil hier kein "And vor Or" gilt sehr lästig... für mich echt vergleichbar dem wenn der Compiler nicht Punkt vor Strich rechnen könnte... daher klammere ich zur Sicherheit in Pascal eben da wo es mir drauf ankommt noch etwas mehr wie in C/C++.


Hier im Fall wird es nicht "richtiger", sondern WorstCase falsch, auch wenn mathematisch oder mit Fließkomma es an sich hier völlig egal ist ob man erst multipliziert oder erst dividiert.

Bei Ganzzahl-Arithmetik spielt es eben doch eine Rolle, denn wir haben in diesem Fall einen begrenzten Rechenwertebereich von 32Bit, jeder Operator hat einen Wertebereich von zum Glück nur 8Bit, das heißt dann hier im Detail für ein mathematisch eigentlich identisches Beispiel:

128 div 256 * 100 = !0! weil (128 div 256) * 100 = !0!
aber
128*100 div 256 = !50! weil (128*100) div 256 = !50!

Und da finde ich die sicherheitsgeklammerte Schreibweise sehr sinnvoll, weil wenn das keine kurzen Zahlen sondern lange Variablennamen in einer Kette von Operatoren sind, erschließt sich ohne Klammern die Konsequenz falscher Rechenreihenfolge nicht mehr jedem Codebetrachter sofort.

[Dejan Vu]

Es wird von links nach rechts ausgewertet, da werden keine Klammern benötigt. So einfach kann die Sinnlosigkeit der 'Sicherheitsklammern' zusammenfassen. Der Compiler macht das so. Genau so. Jedes mal. Bei C(++) mögen deine Sicherheitsklammern ja sinnvoll sein, aber bei Delphi nicht.

Dein fehlendes Vertrauen könntest Du durch einmaliges Ausprobieren aufbauen, aber dazu bist Du ja leider zu faul (deine Worte). Daher meine Bitte: Verbreite aber deine Faulheit und deine dadurch bedingte Unsicherheit nicht weiter, insbesondere nicht durch Tipps, wie 'Sicherheitsklammern'. Klammen sind entweder sinnvoll oder sinnlos. 'Zur Sicherheit' werden diese nicht benötigt. Zur Lesbarkeit: Jeder mathematisch halbwegs versierte Programmierer wird hier WTF rufen, denn alles, was überflüssig ist, ist eben 'falsch' (weil überflüssig). Lies mal Bücher über sauberes Programmieren, und was genau den Unterschied zwischen einem sauberen Programm und Schrottcode ausmacht (nämlich genau der WTF-Faktor).

Was Du natürlich in deiner Freizeit und privat auf deinem Rechner machst, bleibt Dir überlassen. Klammere ruhig zu viel als zu wenig. Wie wäre es noch mit Sicherheitsblöcken à la "Begin End" (man kann ja nie wissen)? Oder doppelte Zuweisungen, damit es richtig hält.

[Daniel]

... Grundgütiger - was für eine schroffe Zurechtweisung. War die in dieser Schärfe tatsächlich nötig?
Sei Dir bitte bewusst, dass es sich hier um Deine Meinung handelt - ich beispielsweise finde sehr wohl, dass sinnvoll gesetzte Klammern zur Lesbarkeit beitragen können, selbst wenn sie mathematisch nicht erforderlich sind.