Floyd-Steinberg Dithering

[Amateurprofi]

Zitat von Stevie:

Der Benchmark ist Blödsinn, denn in TestMov wird der erste jle immer genommen, also ist der Branchpredictor ziemlich happy.
Branchy Code, bei dem ein conditional branch immer genommen wird oder nie genommen wird, ist für einen solchen Test Unfug.

Generell gilt: Conditional branches sind ok, wenn sie sehr predictable sind - d.h. es wird meist der eine Branch und selten der andere genommen. Sie funktionieren auch, wenn es immer abwechselnd ist, die Branchpredictors auf modernen CPUs sind ziemlich schlau. Schlimm wird es allerdings, wenn sie nicht vorhersehbar sind - selbst wenn es im Schnitt 50/50 ist aber ob der Sprung genommen wird oder nicht, ist z.B nicht immer abwechselnd, dann wirds schlimm und man ist mit einem cmov besser aufgehoben.

Übrigens schreibt man dec ecx und nicht sub ecx, 1 - dec ist 1 byte instruction, sub benötigt 3 byte

FWIW: https://codereview.stackexchange.com...he-range-0-255

Zu "Übrigens schreibt man dec ecx und nicht sub ecx, 1 - dec ist 1 byte instruction, sub benötigt 3 byte"
Da sind die Hersteller meiner CPU anderer Meinung.
Zitat aus Kapitel 2-12 in "IA-32 Intel® Architecture Optimization Reference Manual" (Siehe Anhang)

Zitat:

The inc and dec instructions should always be avoided. Using add
and sub instructions instead avoids data dependence and improves
performance.

Merke: Kürzere Instruction bedeutet nicht automatisch "schneller".
Mir ist bewusst, dass bei heutigen Prozessoren (auch bei meinem schon etwas älteren I7 2600K) ein dec/inc und sub 1/add 1 gleich schnell abgearbeitet werden, bei früheren Prozessoren war sub/add (mit #-Werten) deutlich schneller als dec/inc.
Ich benutze trotzdem i.d.R. sub/add weil hier, anders als bei dec/inc, auch das CF Flag gesetzt wird.


Zu "Der Benchmark ist Blödsinn, denn in TestMov wird der erste jle immer genommen"
Nein. Der jle @Z wird nur dann genommen, wenn eax <= 0 ist.
Bei @1 wird edx = -255 gesetzt.
Bei @2 wird edx in eax kopiert und dann eax mit 0 verglichen und gejumpt, wenn eax <= 0 ist.
Bei @N wird edx um 1 erhöht und zu @2 gejumpt, solange edx <= 255 ist.
Bei @2 kann edx und dann eax also Werte im Bereich -255 bis 255 haben.
Merke: Worte wie "Blödsinn" oder"Quatsch" sollte man vermeiden,

Delphi-Quellcode:

PROCEDURE TestMov;
const S:String=' ';
asm
      push 0
      mov edi,0
      mov esi,255
      mov ecx,Count
@1:   mov edx,-255
@2:   mov eax,edx
      cmp eax,0
      jle @Z
      cmp eax,255
      jbe @S
      mov byte[esp],255
      jmp @N
@Z:   xor eax,eax
@S:   mov [esp],al
@N:   add edx,1
      cmp edx,255
      jbe @2
      sub ecx,1
      jne @1
@End: pop ecx
end;

Das mov edi,0 und mov esi,255 ist übrigens überflüssig (resultierte aus copy/paste).

[Stevie]

Zitat von Amateurprofi:

Da sind die Hersteller meiner CPU anderer Meinung.
Zitat aus Kapitel 2-12 in "IA-32 Intel® Architecture Optimization Reference Manual" (Siehe Anhang)

Stand 2006 - sorry, aber das war ja schon zum Release des i7-2600 in 2011 veraltet.
Dass speziell das mit dem dec/inc vs add/sub dort noch zutreffend war, mag ich nicht in Abrede stellen.

Mehr zu der Thematik guckst du hier: https://stackoverflow.com/questions/...does-it-matter

Aber mein Fehler, ich geh in aller Regel davon aus, dass wenn man asm redet, sich zumindest innerhalb derselben Dekade bewegt und nicht im Jahr des Releases von Windows Vista

Und die Aussage zu dem jle war selbstverständlich auch auf die Benchmark von Kas bezogen, die dort nämlich immer den jump genommen hat, damit beweist man nämlich gar nix, außer dass der Branchpredictor gut funktioniert (vermutlich auch 2006 schon)

[Amateurprofi]

Zitat von Stevie:

Zitat von Amateurprofi:

Da sind die Hersteller meiner CPU anderer Meinung.
Zitat aus Kapitel 2-12 in "IA-32 Intel® Architecture Optimization Reference Manual" (Siehe Anhang)

Stand 2006 - sorry, aber das war ja schon zum Release des i7-2600 in 2011 veraltet.
Dass speziell das mit dem dec/inc vs add/sub dort noch zutreffend war, mag ich nicht in Abrede stellen.

Mehr zu der Thematik guckst du hier: https://stackoverflow.com/questions/...does-it-matter

Aber mein Fehler, ich geh in aller Regel davon aus, dass wenn man asm redet, sich zumindest innerhalb derselben Dekade bewegt und nicht im Jahr des Releases von Windows Vista

Und die Aussage zu dem jle war selbstverständlich auch auf die Benchmark von Kas bezogen, die dort nämlich immer den jump genommen hat, damit beweist man nämlich gar nix, außer dass der Branchpredictor gut funktioniert (vermutlich auch 2006 schon)

OK.
Wie wäre es, wenn Du bei einer Antwort (wenn Du nicht den Beitrag zitierst), angibst, auf welchen Beitrag Du Dich beziehst?
Zum Beispiel ein "Zu #25:" würde helfen, Missverständnisse zu vermeiden.
Ist nur eine Anregung.

[Stevie]

Zitat von Amateurprofi:

Nein. Der jle @Z wird nur dann genommen, wenn eax <= 0 ist.
Bei @1 wird edx = -255 gesetzt.
Bei @2 wird edx in eax kopiert und dann eax mit 0 verglichen und gejumpt, wenn eax <= 0 ist.
Bei @N wird edx um 1 erhöht und zu @2 gejumpt, solange edx <= 255 ist.
Bei @2 kann edx und dann eax also Werte im Bereich -255 bis 255 haben.

Delphi-Quellcode:

PROCEDURE TestMov;
const S:String=' ';
asm
      push 0
      mov ecx,Count
@1:   mov edx,-255
@2:   mov eax,edx
      cmp eax,0
      jle @Z
      cmp eax,255
      jbe @S
      mov byte[esp],255
      jmp @N
@Z:   xor eax,eax
@S:   mov [esp],al
@N:   add edx,1
      cmp edx,255
      jbe @2
      sub ecx,1
      jne @1
@End: pop ecx
end;

Ich erkläre nochmal warum diese Funktion für die Messung, ob conditional jumps oder conditional mov besser sind, so nützlich wie nen Abgastest bei VW ist:

Wie du selbst erklärt hast, wird hier von -255 bis 255 gezählt - die ersten 256 mal wird der jle genommen, die nächsten 255 mal nicht. Der folgende jbe wird immer genommen, denn da kommt man überhaupt nie mit nem Wert von über 255 an. Glücklicher kann man die Sprungvorhersage fast gar nicht machen, die liegt vermutlich zu 99% richtig (genaue Zahl kommt auf die CPU an und selbst Intel hat keine genauen Dokumentationen, wie die exakt funktionieren - Matt Godbolt hat vor Jahren mal ein bisschen was gemessen und einige Blog Artikel dazu geschrieben).

Das heißt, um Code wie diesen richtig zu vergleichen, muss man Daten erzeugen, die eine realistische Verteilung haben - ob das nun Daten sind, wie Kas in #34 generiert hat oder ob sie in Realität anders aussehen, kann ich nicht beurteilen, aber ich bin mir sicher, dass sie nicht in der Sequenz -255..255 vorliegen.

[Amateurprofi]

Zitat von Stevie:

Zitat von Amateurprofi:

Nein. Der jle @Z wird nur dann genommen, wenn eax <= 0 ist.
Bei @1 wird edx = -255 gesetzt.
Bei @2 wird edx in eax kopiert und dann eax mit 0 verglichen und gejumpt, wenn eax <= 0 ist.
Bei @N wird edx um 1 erhöht und zu @2 gejumpt, solange edx <= 255 ist.
Bei @2 kann edx und dann eax also Werte im Bereich -255 bis 255 haben.

Delphi-Quellcode:

PROCEDURE TestMov;
const S:String=' ';
asm
      push 0
      mov ecx,Count
@1:   mov edx,-255
@2:   mov eax,edx
      cmp eax,0
      jle @Z
      cmp eax,255
      jbe @S
      mov byte[esp],255
      jmp @N
@Z:   xor eax,eax
@S:   mov [esp],al
@N:   add edx,1
      cmp edx,255
      jbe @2
      sub ecx,1
      jne @1
@End: pop ecx
end;

Ich erkläre nochmal warum diese Funktion für die Messung, ob conditional jumps oder conditional mov besser sind, so nützlich wie nen Abgastest bei VW ist:

Wie du selbst erklärt hast, wird hier von -255 bis 255 gezählt - die ersten 256 mal wird der jle genommen, die nächsten 255 mal nicht. Der folgende jbe wird immer genommen, denn da kommt man überhaupt nie mit nem Wert von über 255 an. Glücklicher kann man die Sprungvorhersage fast gar nicht machen, die liegt vermutlich zu 99% richtig (genaue Zahl kommt auf die CPU an und selbst Intel hat keine genauen Dokumentationen, wie die exakt funktionieren - Matt Godbolt hat vor Jahren mal ein bisschen was gemessen und einige Blog Artikel dazu geschrieben).

Das heißt, um Code wie diesen richtig zu vergleichen, muss man Daten erzeugen, die eine realistische Verteilung haben - ob das nun Daten sind, wie Kas in #34 generiert hat oder ob sie in Realität anders aussehen, kann ich nicht beurteilen, aber ich bin mir sicher, dass sie nicht in der Sequenz -255..255 vorliegen.

Du hast da uneingeschränkt Recht.
Viel schlimmer ist jedoch das:

Delphi-Quellcode:

@N:   add edx,1
      cmp edx,255
      jbe @2

Da wird das jbe nie ausgeführt.
Aber den Fehler hatte ich in alle Testprozeduren gleichermaßen eingebaut.

Was den Wert in EDX betrifft, hab ich noch mal geprüft, welche Werte in Frage kommen.
Dieser wird so ermittelt (am Beispiel des Blau-Anteils) zweier Pixel).

P1 = Pixel[0,0]
P2 = Pixel[1,0]
OldBlue = P1.Blue
NewBlue = 0 oder 255
Delta = OldBlue - NewBlue; // kann sein -255..255
Offset = (Delta * Faktor) div 16 // kann bei Faktor 7 sein -111..111
NewVal = P2.Blue + Offset // kann sein -111..366
P2.Blue = EnsureRange(NewVal, 0, 255)

Ich hab noch mal getestet, dieses Mal habe ich aber nicht Laufzeiten mit GetTickCount gemessen, sondern die benötigten CPU-Ticks mit TimeStampCounter.
Das ist (meine Meinung) realistischer, weil die CPU mit unterschiedlichen Geschwindigkeiten laufen kann.
Bei GetTickCount werden die Laufzeiten dadurch mal länger, mal kürzer, beim TimeStampCounter (wiederum meine Meinung) nicht.
Hoffentlich nicht wieder dumme Fehler eingebaut.

Aber auch hier ergeben sich unterschiedliche Resultate.

13,917 15,052 3,967,047 CPU-Ticks TestCMovShort
14,246 14,977 83,528 CPU-Ticks TestMov

13,556 14,994 126,734 CPU-Ticks TestCMovShort
13,884 15,276 65,974 CPU-Ticks TestMov

Die jeweils 3 Werte sind Minimum, Average, Maximum.

Was sich bei vielen Testläufen herauskristallisiert hat, ist, dass TestCMovShort etwas schneller ist.
Bin jetzt überzeugt.

Für Interessierte:

Delphi-Quellcode:

{$IFDEF CPUX86}
procedure TestCMovShort(Count:Integer);
asm
               push   esi           // Save ESI
               push   0             // Memory
               mov    esi,255       // Max-Value
               mov    ecx,eax       // Counter from Count downto 1
@CounterLoop:  mov    edx,-111      // Value from -111 to 366
@ValueLoop:    mov    eax,0         // Min-Value
               cmp    edx,esi       // Value vs. Max-Value
               cmovg  eax,esi       // Load Max-Value if Value > Max-Value
               cmovbe eax,edx       // Load Value if Value <= Max-Value
               mov    [esp],al      // Store New Value
               inc    edx           // Value + 1
               cmp    edx,367       // Value vs. 367
               jne    @ValueLoop    // Loop until Value = 367
               dec    ecx           // Counter - 1
               jne    @CounterLoop  // Loop until Counter = 0
               pop    ecx           // Remove Memory from Stack
               pop    esi           // Restore ESI
end;
{$ENDIF}

Delphi-Quellcode:

{$IFDEF CPUX86}
PROCEDURE TestMov(Count:Integer);
asm
               push     0             // Memory
               mov      ecx,eax       // Counter from Count downto 1
@CounterLoop:  mov      edx,-111      // Value from -111 to 366
@ValueLoop:    mov      eax,edx       // New-Value = Value
               cmp      eax,0         // New-Value vs. 0
               jle      @Zero         // Jump if New-Value <= 0
               cmp      eax,255       // New-Value vs. 255
               jbe      @Store        // Jump if New-Value <= 255
               mov      byte[esp],255 // Store 255 as New Value
               jmp      @NextValue    // Next Value
@Zero:         xor      eax,eax       // New-Value=0
@Store:        mov      [esp],al      // Store New Value
@NextValue:    inc      edx          // Value + 1
               cmp      edx,367       // Value vs. 367
               jne      @ValueLoop    // Loop until Value = 367
               sub      ecx,1         // Counter - 1
               jne      @CounterLoop  // Loop until Counter = 0
               pop      ecx           // Remove Memory from Stack
end;
{$ENDIF}

Delphi-Quellcode:

{$IFDEF CPUX86}
PROCEDURE TestAsm(Count:Integer; var Ticks1,Ticks2:Int64);
asm  // EAX=Count, EDX=@Ticks1, ECX=@Ticks2
    push    eax         // Count
    push    edx         // @Ticks1
    push    ecx         // @Ticks2
    // CPU auf Trab bingen
    mov     ecx,100000
@1: dec     ecx
    jne     @1
    // TestCMovShort
    mov     ecx,[esp+4] // @Ticks1
    rdtsc
    mov     [ecx],eax   // Ticks1.Lo
    mov     [ecx+4],edx // Ticks1.Hi
    mov     eax,[esp+8] // Count
    call    TestCMovShort
    rdtsc
    mov     ecx,[esp+4] // @Ticks1
    sub     eax,[ecx]   // = Ticks1.Lo
    sbb     edx,[ecx+4] // = Ticks1.Hi
    mov     [ecx],eax   // Ticks1.Lo
    mov     [ecx+4],edx // Ticks1.Hi
    // TestMov
    mov     ecx,[esp]   // @Ticks2
    rdtsc
    mov     [ecx],eax   // Ticks2.Lo
    mov     [ecx+4],edx // Ticks2.Hi
    mov     eax,[esp+8] // Count
    call    TestMov
    rdtsc
    mov     ecx,[esp]   // @Ticks2
    sub     eax,[ecx]   // = Ticks2.Lo
    sbb     edx,[ecx+4] // = Ticks2.Hi
    mov     [ecx],eax   // Ticks2.Lo
    mov     [ecx+4],edx // Ticks2.Hi
    add     esp,12
end;
{$ENDIF}

Delphi-Quellcode:

{$IFDEF CPUX86}
PROCEDURE Test;
const Count1=10; Count2=10000;
var I:Integer;
    SaMask,PaMask,TaMask:NativeUInt;
    T1,T2,T1Min,T2Min,T1Max,T2Max,T1Sum,T2Sum,T1Avg,T2Avg:Int64;
begin
   // Thread auf eine CPU fixieren
   GetProcessAffinityMask(GetCurrentProcess,PaMask,SaMask);
   TaMask:=1;
   while TaMask and PaMask=0 do TaMask:=TaMask shl 1;
   SetThreadAffinityMask(GetCurrentThread,TaMask);
   // Laufzeiten von TestCMovShort (T1) und TestMov (T2) ermitteln
   TestAsm(Count1,T1Min,T2Min);
   T1Max:=T1Min;
   T2Max:=T2Min;
   T1Sum:=T1Min;
   T2Sum:=T2Min;
   for I:=1 to Count2 do begin
      TestAsm(Count1,T1,T2);
      T1Min:=Min(T1Min,T1);
      T1Max:=Max(T1Max,T1);
      T2Min:=Min(T2Min,T2);
      T2Max:=Max(T2Max,T2);
      Inc(T1Sum,T1);
      Inc(T2Sum,T2);
   end;
   T1Avg:=T1Sum div (Count2+1);
   T2Avg:=T2Sum div (Count2+1);
   // Thread für alle CPUs freigeben und Priorität auf alten Wert stellen
   SetThreadAffinityMask(GetCurrentThread,PaMask);
   ShowMessage(Format('%.0N  %.0N  %.0N  CPU-Ticks TestCMovShort'#13+
                      '%.0N  %.0N  %.0N  CPU-Ticks TestMov',
                      [T1Min+0.0, T1Avg+0.0, T1Max+0.0,
                       T2Min+0.0, T2Avg+0.0, T2Max+0.0]));
end;
{$ENDIF}

[Stevie]

Ich bin mir nicht sicher, ob du meine Ausführung mit der Sprungvorhersage verstanden hast, wenn du eine aufsteigende Sequenz zwischen x und y testest, ist das witzlos, denn die Daten bei einer reellen Berechnung liegen nicht in dieser Form vor. In den Daten im Test, wo du von -111 bis 366 gehst hast du nun 112 mal jle jump taken, 366 mal non taken, und dann 255 mal jbe jump taken, 111 mal non taken, immer hintereinander, da ist die Sprungvorhersage immernoch fast immer richtig.
Realistische Werte erhälst du nur, wenn du die Werte nicht in auf- oder absteigender Reihenfolge an die Funktion fütterst sondern in einer realistischen Verteilung durchgemischt.

[Amateurprofi]

Zitat von Stevie:

Ich bin mir nicht sicher, ob du meine Ausführung mit der Sprungvorhersage verstanden hast, wenn du eine aufsteigende Sequenz zwischen x und y testest, ist das witzlos, denn die Daten bei einer reellen Berechnung liegen nicht in dieser Form vor. In den Daten im Test, wo du von -111 bis 366 gehst hast du nun 112 mal jle jump taken, 366 mal non taken, und dann 255 mal jbe jump taken, 111 mal non taken, immer hintereinander, da ist die Sprungvorhersage immernoch fast immer richtig.
Realistische Werte erhälst du nur, wenn du die Werte nicht in auf- oder absteigender Reihenfolge an die Funktion fütterst sondern in einer realistischen Verteilung durchgemischt.

Danke Stevie,
tschuldi, dass ich so spät antworte. Ich hatte diesen Text schon vor 2 Wochen geschrieben, mich dann aber um andere Themen gekümmert.

Ich bin mir sicher, dass ich Deine Ausführungen verstanden hatte und ich bin mir auch sicher, dass ich das auch schon vorher wusste.
Ich habe die CMOV-Instruktion immer gemieden, weil sie nicht von allen Prozessoren unterstützt wird, was allerdings eine recht alte Information ist.
Ich habe die Testprozeduren noch einmal überarbeitet.
Die zu vergleichenden Werte kommen jetzt aus einem Daten-Array, das mit Zufallswerten, und bei einem zweiten Testlauf mit aufsteigenden Werten gefüllt ist.
Die Laufzeiten sind immer recht unterschiedlich, typische Werte waren:

Code:

Zufallswerte 
1,360  2,184  3,926  CPU-Ticks TestCMovShort
2,602  4,243  20,340  CPU-Ticks TestMov 
1,242  2,059  16,414  CPU-Ticks Differenz 
Aufsteigende Werte 
1,360  1,501  27,828  CPU-Ticks TestCMovShort 
1,614  1,755  27,457  CPU-Ticks TestMov 
254  254  -371  CPU-Ticks Differenz

Der fragliche Code wird für jedes Pixel der Bitmap 4 Mal ausgeführt.
Ausgehend von dem Gewinn von 1242 CPU-Ticks für 478 Vergleiche, einer Bitmap mit 2.4 MPixel, und einer CPU-Frequenz von 3.4GHz ergibt sich ein Gewinn von
1242/478*2.4M/3.4G*4*1000 = 7.3 ms.
Bei einer Laufzeit von 63 ms für die Umwandlung der Bitmap ist der Gewinn von 7 ms nicht unbedeutend.

Delphi-Quellcode:

var
   Data:Array[0..366+111] of Integer;

Delphi-Quellcode:

procedure TestCMovShort;
const HI=High(Data);
asm
               push     esi               // Save ESI
               push     0                 // Memory
               mov      esi,255           // Max-Value
               mov      ecx,HI            // Index from High(Data) downto 0
@Loop:         mov      edx,[ecx*4+Data]  // Value
               mov      eax,0             // Min-Value
               cmp      edx,esi           // Value vs. Max-Value
               cmovg    eax,esi           // Load Max-Value if Value > Max-Value
               cmovbe   eax,edx           // Load Value if Value <= Max-Value
               mov      [esp],al          // Store New Value
               dec      ecx               // Index - 1
               jns      @Loop             // Loop until Index = 0
               pop      ecx               // Remove Memory from Stack
               pop      esi               // Restore ESI
end;

Delphi-Quellcode:

PROCEDURE TestMov;
const HI=High(Data);
asm
               push     0                 // Memory
               mov      ecx,HI            // Index from High(Data) downto 0
@Loop:         mov      eax,[ecx*4+Data]  // Value
               cmp      eax,0             // Value vs. 0
               jle      @Zero             // Jump if New-Value <= 0
               cmp      eax,255           // Value vs. 255
               jbe      @Store            // Jump if Value <= 255
               mov      byte[esp],255     // Store 255 as New Value
               jmp      @Next             // Next Index
@Zero:         mov      byte[esp],0       // Store 0 as New Value
               jmp      @Next             // Next Index
@Store:        mov      [esp],al          // Store New Value
@Next:         dec      ecx               // Index - 1
               jns      @Loop             // Loop until Index < 0
               pop      ecx               // Remove Memory from Stack
end;