Optimierung: Bilder blenden

[Wolfgang Fellger]

Hallo,
dann wage ich mich mal vor, um hier mein Assemblergekritzel zu zeigen :)

Ich habe folgende Funktion:

procedure AlphaBlendLine(Dest, Src: Pointer; Length: integer; Value: byte);
asm
push EBX
push ESI
mov EBX, Dest
mov ESI, Src
mov DL, Value
mov DH, $FF
sub DH, DL
inc DH
xor AX, AX
@Loop:
mov AL, [EBX]
mul DL
shl EAX, 8
mov AL, [ESI]
mul DH
shr EAX, 8
add AH, AL
mov [EBX], AH
inc EBX
inc ESI
dec ECX
JNZ @Loop
pop ESI
pop EBX
end;

(Wie man sieht der Inline-Assembler von Delphi. Im Orginal steht da noch ein
register; dahinter - Length wird bereits direkt in ECX übergeben.)

Sinn und Zweck ist, zwei Bilder ineinander zu überblenden. Normalerweise würde
man den Wert eines Zielpixels mit
Z = A*T + B*(1-T)
berechnen; um mir die Fließkommaberechnung zu ersparen wird Value hier als
Bruchteil von 256 gesehen. Das Ganze arbeitet auf 24-bit-Bilddaten.

Funktionsweise: Vor Beginn der Schleife berechne ich (256-Value) und speichere
diesen Wert in DH, neben Value selbst in DL. In der Schleife wird dann erst ein
Byte aus Dest geladen und multipliziert. Anschließend schiebe ich EAX 8 bit
nach links, um die hohen 8 bit des Ergebnisses aufzubewahren. Danach folgt noch
die Multiplikation eines Bytes aus Src, und EAX wird wieder zurückgeschoben.
Nun werden die hohen Ergebnisanteile beider Multiplikationen addiert und das
Ergebnis in Dest gespeichert. Auf einen Überlauf wird nicht geprüft, da hier
keiner vorkommen kann (oder hab ich einen Fall übersehen?).

Funktioniert soweit prächtig[*], daher jetzt die Frage ob jemand noch
Möglichkeiten findet dieses zu beschleunigen. Natürlich bin ich auch für
komplett andere Ansätze offen.
Ich hatte über eine Lösung mit MMX nachgedacht, nur scheitert das daran dass es
leider kein PMUL für gepackte Bytes gibt :-|

So. Ich danke schonmal im Voraus für Antworten.

[Jan Bruns]

Post by Wolfgang Fellger
procedure AlphaBlendLine(Dest, Src: Pointer; Length: integer; Value: byte);
asm
...
mov AL, [EBX]
mul DL
shl EAX, 8
mov AL, [ESI]
mul DH
shr EAX, 8
add AH, AL
mov [EBX], AH
inc EBX
inc ESI
dec ECX

Genau dafür wäre die Verwendung vom MMX deutlich besser.
Damit könntest Du 8 Datenelemente, also in diesem Fall 2 oder fast
3 komplette Pixel gleichzeitig bearbeiten, vermutlich sogar ohne
daß die innere Scleife deutlich länger würde.

Post by Wolfgang Fellger
Sinn und Zweck ist, zwei Bilder ineinander zu überblenden. Normalerweise würde
man den Wert eines Zielpixels mit
Z = A*T + B*(1-T)
berechnen; um mir die Fließkommaberechnung zu ersparen wird Value hier als
Bruchteil von 256 gesehen. Das Ganze arbeitet auf 24-bit-Bilddaten.

Naja, ist halt nur etwas unschön, daß dabei "Datenverluste" auftreten.
So ist bspw. der Höchstwert von T <= 255/256.

Mit

A*T + B*(1-T)
= A*T - B*T + B
= T*(A-B) + B


liesse sich die innere Schleife etwa so gestalten:

@m1:
MOVZX EAX,byte ptr[ESI]
MOVZX ECX,byte ptr[EDI]
SHL EAX,20 // *
SHL ECX,20 // *
SUB EAX,ECX
SHR ECX,4 // *
IMUL dword ptr[T] // *
ADD ECX,EDX
BSWAP ECX
MOV byte ptr[EDI],CH
INC ESI
INC EDI
DEC EBX
JNZ @m1

Hab' ich jetzt nicht getestet, und ich bin auch unsicher,
wo * man man die Daten nun am besten hinschiebt.


So dürfte es möglich sein, bspw. folgendes exakt nachzuahmen:


FUNCTION reference_blend(a,b,t : byte) : byte;
VAR tempa,tempb,tempt : float;
BEGIN
tempa := a/255;
tempb := b/255;
tempt := t/255; // nun sind alle temps im Bereich 0.0 .. 1.0

tempt := tempa*tempt + tempb*(1-tempt);
pixel_value := int( 255*( tempt ) );
END;


was vermutlich dein eigentlicher Wunsch ist.

Aber, wie gesagt, wenn Dir kleine Fehlerchen nix ausmachen,
dann kannst auch gut so ähnlich wie bisher vorgehen, aber dann
geht's natürlich mit MMX erst recht noch deutlich schneller.


Gruss

Jan Bruns

[Wolfgang Fellger]

Post by Jan Bruns
Genau dafür wäre die Verwendung vom MMX deutlich besser.
Damit könntest Du 8 Datenelemente, also in diesem Fall 2 oder fast
3 komplette Pixel gleichzeitig bearbeiten, vermutlich sogar ohne
daß die innere Scleife deutlich länger würde.

Gäbe es ein PMULHUB, wäre die Lösung überaus elegant und schon implementiert
:-) Aber wie schon gesagt, hat Intel diesen Befehl leider in einem Anfall von
Sparsamkeit weggelassen.
Es gibt nicht mal ein PMULLUW, bei dem ich immerhin noch 4 Byte auf einmal
bearbeiten könnte, auch wenn ich die Daten dann erst mit UNPACK/PACK in das
passende Format bringen müsste :-|
Mir fehlt es also an einer Idee, wie das mit MMX zu lösen wäre. Vorschläge
willkommen.

Post by Jan Bruns
Mit
A*T + B*(1-T)
= A*T - B*T + B
= T*(A-B) + B
[SNIP]

Sehr schön, danke schonmal. Präzision ist wie gesagt zweitrangig, aber ich
werde diesen Ansatz auf jeden Fall einmal versuchen.

[Jan Bruns]

Post by Wolfgang Fellger

Post by Jan Bruns
Genau dafür wäre die Verwendung vom MMX deutlich besser.
Damit könntest Du 8 Datenelemente, also in diesem Fall 2 oder fast
3 komplette Pixel gleichzeitig bearbeiten, vermutlich sogar ohne
daß die innere Scleife deutlich länger würde.

Gäbe es ein PMULHUB, wäre die Lösung überaus elegant und schon implementiert
:-) Aber wie schon gesagt, hat Intel diesen Befehl leider in einem Anfall von
Sparsamkeit weggelassen.

Oh ja, ärgerlich.

Post by Wolfgang Fellger
Es gibt nicht mal ein PMULLUW, bei dem ich immerhin noch 4 Byte auf einmal
bearbeiten könnte, auch wenn ich die Daten dann erst mit UNPACK/PACK in das
passende Format bringen müsste :-|
Mir fehlt es also an einer Idee, wie das mit MMX zu lösen wäre. Vorschläge
willkommen.

Wie wär's damit (nicht getestet, oder so).


@m0:

MOVQ mm0,[EDI]
MOVQ mm1,mm0
MOVQ mm2,[ESI]
MOVQ mm3,mm2

PUNPCKLBW mm0,[null]
PUNPCKHBW mm1,[null] // mm0,mm1 = stream0 mit words
PUNPCKLBW mm2,[null]
PUNPCKHBW mm3,[null] // mm2,mm3 = stream1 mit words

PSUBW mm0,mm2
PSUBW mm1,mm3

PSLLW mm0,4 // shift, damit die ergebnisbits nach MULH
PSLLW mm1,4 // überhaupt im Highword stehen können

PMULHW mm0,[konstante]
PMULHW mm1,[konstante]

PADDW mm0,mm2
PADDW mm1,mm3

PACKUSWB mm0,mm1

MOVQ [EDI],mm0

add esi,8
add edi,8
dec ecx
jnz @m0

[Wolfgang Fellger]

Post by Jan Bruns
Wie wär's damit

Nach links schieben damit man PMULHW verwenden kann... genial :-)
Aber was noch wichtiger ist: Ich kann es mir jetzt leisten (Register frei und
ausreichend große Datenportionen), einen dritten Parameter einzuführen, so dass
ich das Originalbild nicht jedesmal zurückkopieren muss.
Insgesamt erreicht die Funktion so eine Geschwindigkeitssteigerung von 180%.

Einen herzlichen Dank für deine Hilfe - wobei das eigentlich zu wenig ist, du
hast ja fast die ganze Arbeit gemacht.
Der Credit für die Funktion geht an dich, ich kann nur nochmal Danke sagen :-)


Für die Nachwelt unten jetzt noch die komplette Funktion.

==

procedure CopyAndAlphaBlendLineMMX(Dest, Src1, Src2: Pointer; Length: longint;
Value: byte); register;
asm
push ESI
push EDI
mov EDI, Dest
mov ESI, Src1
mov EAX, Src2
mov ECX, Length
shr ECX, 3
PXOR mm4, mm4

movzx DX, Value
shl EDX, 16
mov DL, Value
shl EDX, 4
movd mm6, EDX
PSLLQ mm6, 32
movd mm7, EDX
POR mm6, mm7

@Loop:
movq mm0, [EAX]
movq mm1, mm0
movq mm2, [ESI]
movq mm3, mm2
PUNPCKLBW mm0, mm4
PUNPCKHBW mm1, mm4 // mm0,mm1 = stream0 mit words
PUNPCKLBW mm2, mm4
PUNPCKHBW mm3, mm4 // mm2,mm3 = stream1 mit words
PSUBW mm0, mm2
PSUBW mm1, mm3
PSLLW mm0, 4
PSLLW mm1, 4
PMULHW mm0, mm6
PMULHW mm1, mm6
PADDW mm0, mm2
PADDW mm1, mm3
PACKUSWB mm0, mm1
add EAX, 8
add ESI, 8
movq [EDI], mm0
add EDI, 8
dec ECX
JNZ @Loop
EMMS
pop EDI
pop ESI
end;

[Jan Bruns]

Post by Wolfgang Fellger
Insgesamt erreicht die Funktion so eine Geschwindigkeitssteigerung von 180%.

Das lässt sich bestimmt noch etwas verbessern:

- ersetze "movq [],mmx" durch "movntq [],mmx
das bringt oft einige %, weil die CPU dadurch das Wegschreiben
der Ergebnisse verzögern, und daher Blockweise gestalten kann
(vermindert also Bandbreitenverschwendung)

- ersetze alle Speicherreferenzen "[REG]" durch "[REG+8*EBX]"
Pro Referenz wird dadurch zwar die Codierung des Befehls um
1 Byte länger, aber Du sparst Dir die "ADD reg,8", was etwa
3 Byte Codierung entspricht.
Insgesamt dürfte das 4 Byte Codelänge einsparen. Kürzere
Codierungen führen manchmal zu etwas schnellerer Codeausführung.

- Falls EDX = x + ESI, mit x im Bereich etwa 64 < x < 512
könntest Du zwischen den "MULHW" ein "PREFETCHnta [EDX+8*EBX]"
einfügen.


Unglaublich viel wird all das nicht bringen, aber zumindest der
erste Verbesserungsvorschlag ist ja schnell gemacht (o;

Gruss

Jan Bruns



-

[Wolfgang Fellger]

Post by Jan Bruns

Post by Wolfgang Fellger
Insgesamt erreicht die Funktion so eine Geschwindigkeitssteigerung von 180%.

Oh sorry, ich war da etwas ungenau. Die 180% gelten für den praxisnahen
Benchmark. In einem synthetischem Benchmark (also nur die Funktion in einer
Schleife) liegt die Geschwindigkeitssteigerung bei ca. Faktor 8-9.
Die Funktion ist also inzwischen so schnell, dass sie durch ihr Umfeld schon
spürbar ausgebremst wird. Als nächstes muss also dieses optimiert werden.

Post by Jan Bruns
- ersetze "movq [],mmx" durch "movntq [],mmx

Das ist dann aber kein MMX mehr, dieser Befehl kam erst mit SSE :)
Bringt aber tatsächlich gute 10%, das reicht um eine dritte Variante der
Funktion zu rechtfertigen.

Post by Jan Bruns
- ersetze alle Speicherreferenzen "[REG]" durch "[REG+8*EBX]"

Oha, da staunt der Laie. Ich glaube, ich will dringend nochmal die passenden
Kapitel in Intels Referenz durchlesen :-o Sehr schön, ist eingebaut.

Post by Jan Bruns
- Falls EDX = x + ESI, mit x im Bereich etwa 64 < x < 512

Du meinst EDI, oder?
Wird nicht vorkommen, da die drei Pointer auf Pixel in verschiedenen Bildern
zeigen.

[Jan Bruns]

Post by Wolfgang Fellger

Post by Jan Bruns

Post by Wolfgang Fellger
Insgesamt erreicht die Funktion so eine Geschwindigkeitssteigerung von 180%.

Oh sorry, ich war da etwas ungenau. Die 180% gelten für den praxisnahen
Benchmark. In einem synthetischem Benchmark (also nur die Funktion in einer
Schleife) liegt die Geschwindigkeitssteigerung bei ca. Faktor 8-9.
Die Funktion ist also inzwischen so schnell, dass sie durch ihr Umfeld schon
spürbar ausgebremst wird. Als nächstes muss also dieses optimiert werden.

Immer noch im Vergleich zu der anfangs von Dir angegebenen Funktion?

Ich hätte eher sowas bei 'nem Faktor nahe 4 geschätzt.

Kommt natürlich auch stark auf die verwendete CPU an, und dein
Code sah (optimierungsechnisch) auch etwas haarsträubend aus:

Auf den meisten neueren CPUs sollte man eine Mischung verschiedener
Operandengrössen vermeiden. Das finde ich persönlich eigentlich recht
schade, weil so ein nicht unwesentlicher Anteil der Verbesserungen,
die damals mit der 32-Bit Technik kamen, nun letzlich doch gar nicht
wirklich genutzt werden können, und der schnellster Code nunmehr sehr
oft besonders weit vom "Schaltungstechnischen Minimum" liegt (will
meinen, er (der schnelle Code) lässt sich überhaupt nicht sinnvoll
verwenden, um daraus eine Logikschaltung zu generieren).

Post by Wolfgang Fellger

Post by Jan Bruns
- ersetze "movq [],mmx" durch "movntq [],mmx

Das ist dann aber kein MMX mehr, dieser Befehl kam erst mit SSE :)
Bringt aber tatsächlich gute 10%, das reicht um eine dritte Variante der
Funktion zu rechtfertigen.

Also mag sein, daß movntq auf einem Pentium 1 MMX nicht verfügbar war,
und zeitgléich mit der Einführung von SSE eingeführt wurde.

Ein SSE Befehl ist das aber definitiv nicht!

Es gibt glaube ich auch CPUs, die movntq unterstützen, ohne
SSE-fähig tu sein (ich denke da bpsw. an AMD XP vor der T-Bred
Revision).

Post by Wolfgang Fellger

Post by Jan Bruns
- Falls EDX = x + ESI, mit x im Bereich etwa 64 < x < 512

Du meinst EDI, oder?
Wird nicht vorkommen, da die drei Pointer auf Pixel in verschiedenen Bildern
zeigen.

Nein, ich meinte EDX. Das ist ja noch frei, Du kannst Dir seinen Wert
also selbst festlegen. Wär' halt elegant, um sowas wie

PREFETCHnta [stream1 + x]

zu schreiben. Aber egal, die Prefetch-Befehle bringen eh' meist nicht
den gewünschten Erfolg.


Übrigens, also dieses "nt" in "movntq" und "PREFETCHnta"
legt fest, daß die Speicherzellen momentan entweder nur gelesen,
oder nur geschrieben werden.

Im Falle von movntq auf multi-CPU-Systemen ist das sogar ein
Versprechen, die geschriebenen Daten vorerst nicht zu lesen.

Gruss

Jan Bruns