Floyd-Steinberg Dithering

[Kas Ob.]

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

Thank you very much, i have no idea what i was thinking missing all that.

here revised version of that benchmark with some semi-real data simulation over 1kb repeated million time.

Code:

uses
  System.SysUtils,
  Windows;

const
  Count = 1000000;
  DATA_LEN = 1024;

var
  Data: array[0..DATA_LEN - 1] of Integer;
  CData: array[0..DATA_LEN - 1] of Byte;

procedure TestMov;
asm
        mov     esi, 255
        mov     ecx, Count

@1:     mov     edi, 0

@2:     mov     edx, dword[Data + edi * 4]
        mov     eax, edx
        cmp     eax, 0
        jle     @Z
        cmp     eax, 255
        jbe     @S
        mov     Byte[CData + edi], 255
        jmp     @N

@Z:     xor     eax, eax

@S:     mov     Byte[CData + edi], al

@N:     inc     edi
        cmp     edi, DATA_LEN
        jle     @2
        dec     ecx
        jne     @1
end;

procedure TestCMovShort;
asm
        mov     esi, 255          // High Limit
        mov     ecx, Count

@1:     mov     edi, 0

@2:     mov     edx, dword[Data + edi * 4]
        XOR     eax, eax     // eax is destination value filled with the lowest value
        cmp     edx, esi     // comapare v (edx) with high value
        cmovg   eax, esi     // if bigger then take the highest esi
        cmovbe  eax, edx     // if below or equal we fill value v (edx)
        mov     Byte[CData + edi], al
        inc     edi
        cmp     edi, DATA_LEN
        jl      @2
        dec     ecx
        jne     @1
end;

procedure Test;
var
  T: Cardinal;
  i: Integer;
begin
  Randomize;
  for i := Low(Data) to High(Data) do
    Data[i] := Random(256 * 3) - 256;

  T := GetTickCount;
  TestMov;
  T := GetTickCount - T;
  Writeln('TestMov ' + IntToStr(T));

  T := GetTickCount;
  TestCMovShort;
  T := GetTickCount - T;
  Writeln('TestCMovShort ' + IntToStr(T));

end;

begin
  Test;
  Readln;
end.

and the result

Code:

TestMov 1703
TestCMovShort 969

CMOV is almost twice faster.

[Stevie]

In den Kommentaren verweist Peter Cordes auf einen Trick, der ermöglicht, direkt in eax zu laden und benötigt nicht das wiederholte nullen.

Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:

Code:

procedure TestCMov_Better;
asm
        push   esi
        push   edi

        xor    edx, edx
        mov    esi, 255          // High Limit
        mov    ecx, Count

@1:     mov    edi, 0

@2:     mov    eax, dword[Data + edi * 4]
        cmp    eax, esi    // compare v (eax) with high value
        cmovae eax, edx    // if negative (unsigned check) or 255 we fill 0 (edx)
        cmovge eax, esi    // if greater (signed check) or 255 we fill 255 (esi)
        mov    Byte[CData + edi], al
        inc    edi
        cmp    edi, DATA_LEN
        jl     @2
        dec    ecx
        jne    @1

        pop  edi
        pop  esi
end;

Wenn nicht genügend Register zur Verfügung sind, können wir auch das hier (nur die Stelle mit dem Vergleich) machen - ist ein kleines bisschen langsamer aber immernoch schneller als alles andere:

Code:

        xor    edx, edx
        cmp    eax, 255    // compare v (eax) with high value
        cmovae eax, edx    // if negative or 255 we fill 0 (edx)
        mov    edx, 255
        cmovge eax, edx    // if greater or 255 we fill 255 (edx)

[Amateurprofi]

Zitat von Stevie:

In den Kommentaren verweist Peter Cordes auf einen Trick, der ermöglicht, direkt in eax zu laden und benötigt nicht das wiederholte nullen.

Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:

Code:

procedure TestCMov_Better;
asm
        push   esi
        push   edi

        xor    edx, edx
        mov    esi, 255          // High Limit
        mov    ecx, Count

@1:     mov    edi, 0

@2:     mov    eax, dword[Data + edi * 4]
        cmp    eax, esi    // compare v (eax) with high value
        cmovae eax, edx    // if negative (unsigned check) or 255 we fill 0 (edx)
        cmovge eax, esi    // if greater (signed check) or 255 we fill 255 (esi)
        mov    Byte[CData + edi], al
        inc    edi
        cmp    edi, DATA_LEN
        jl     @2
        dec    ecx
        jne    @1

        pop  edi
        pop  esi
end;

Wenn nicht genügend Register zur Verfügung sind, können wir auch das hier (nur die Stelle mit dem Vergleich) machen - ist ein kleines bisschen langsamer aber immernoch schneller als alles andere:

Code:

        xor    edx, edx
        cmp    eax, 255    // compare v (eax) with high value
        cmovae eax, edx    // if negative or 255 we fill 0 (edx)
        mov    edx, 255
        cmovge eax, edx    // if greater or 255 we fill 255 (edx)

Danke, Stevie
Zwei Fragen hätte ich:
1) Was ist "Data"?
Bei mir kommt der Wert, der ggfs. auf 0 oder 255 zu ändern ist, aus EDX (ist -255..255) und der (ggfs. geänderte Wert wird in [esp] gespeichert.

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"
Ich mache

Delphi-Quellcode:

push     edi
push     esi
...
...
pop      esi
pop      edi

Du machst

Delphi-Quellcode:

push   esi
push   edi
...
...
pop  edi
pop  esi

Was ist daran korrekter?

[Kas Ob.]

Zitat von Amateurprofi:

1) Was ist "Data"?
Bei mir kommt der Wert, der ggfs. auf 0 oder 255 zu ändern ist, aus EDX (ist -255..255) und der (ggfs. geänderte Wert wird in [esp] gespeichert.

Data comes from my earlier test

Code:

const
  Count = 1000000;
  DATA_LEN = 1024;

var
  Data: array[0..DATA_LEN - 1] of Integer;
  CData: array[0..DATA_LEN - 1] of Byte;
....
begin
  Randomize;
  for i := Low(Data) to High(Data) do
    Data[i] := Random(256 * 3) - 256;

Data is filled with arbitrary values bigger than 255 and lower than 0.

Zitat von Amateurprofi:

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"

no difference at all, both are correct, storing registers on stack by push and pop should be planned as First-In-Last-Out FILO, (same as Last-In-First-Out LIFO).

[Amateurprofi]

Zitat von Kas Ob.:

Zitat von Amateurprofi:

1) Was ist "Data"?
Bei mir kommt der Wert, der ggfs. auf 0 oder 255 zu ändern ist, aus EDX (ist -255..255) und der (ggfs. geänderte Wert wird in [esp] gespeichert.

Data comes from my earlier test

Code:

const
  Count = 1000000;
  DATA_LEN = 1024;

var
  Data: array[0..DATA_LEN - 1] of Integer;
  CData: array[0..DATA_LEN - 1] of Byte;
....
begin
  Randomize;
  for i := Low(Data) to High(Data) do
    Data[i] := Random(256 * 3) - 256;

Data is filled with arbitrary values bigger than 255 and lower than 0.

Zitat von Amateurprofi:

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"

no difference at all, both are correct, storing registers on stack by push and pop should be planned as First-In-Last-Out FILO, (same as Last-In-First-Out LIFO).

Thanks for clarification.

[Stevie]

Zitat von Amateurprofi:

1) Was ist "Data"?

Siehe Post #29

Zitat von Amateurprofi:

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"...

Das war auch auf Post #29 bezogen, wo die Benchmark routinen die Register nutzen, aber nicht gesichert haben.

[Amateurprofi]

Zitat von Stevie:

Zitat von Amateurprofi:

1) Was ist "Data"?

Siehe Post #29

Zitat von Amateurprofi:

2) zu "Ich war auch mal so frei, die non-volatilen Register korrekt zu sichern:"...

Das war auch auf Post #29 bezogen, wo die Benchmark routinen die Register nutzen, aber nicht gesichert haben.

Oh, das habe ich missverstanden. Tschuldi.

[Kas Ob.]

@Stevie, nice !

I was going to more generic reusable one like this:

Code:

{$ALIGN 16}
procedure TestCMovShort;
const
  LOWER_LIMIT = 0;
  HIGHER_LIMIT = 255;
asm
        mov     esi, HIGHER_LIMIT          // High Limit
        mov     ecx, Count
        db      $48, $48

@1:     mov     edi, 0
        db      $48, $48, $48

@2:     mov     edx, dword[Data + edi * 4]
        mov     eax, LOWER_LIMIT
        //XOR     eax, eax     // eax is destination value filled with the lowest value
        cmp     edx, esi     // comapare v (edx) with high value
        cmovg   eax, esi     // if bigger then take the highest esi
        cmovbe  eax, edx     // if below or equal we fill value v (edx)
        mov     Byte[CData + edi], al
        inc     edi
        cmp     edi, DATA_LEN
        jl      @2
        dec     ecx
        jne     @1
end;

But it is little slower than xor , and for sure slower then using cmovae and cmovge.

[Kas Ob.]

And of course i forgot about pop and push