Intel x86-Assembler-Optimierungstechniken in einer Probe Problem
https://stackoverflow.com/questions/1414911
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich lerne Assembler eine ganze Weile, und ich versuche, ein paar einfache Verfahren \ Funktionen, um es neu zu schreiben Performance-Vorteile zu sehen (falls vorhanden). Mein Hauptentwicklungswerkzeug ist Delphi 2007 und erste Beispiele in dieser Sprache sein, aber sie können leicht auch in andere Sprachen übersetzt werden.
Die Problemstaaten wie:
Wir haben einen vorzeichenlosen Bytewert in dem jedes der acht Bits repräsentiert ein Pixel in einer Zeile eines Bildschirms gegeben. Jedes einzelne Pixel kann Feststoff (1) oder transparent sein (0). Also mit anderen Worten, wir haben 8 Pixel in einem Byte-Wert verpackt. Ich möchte diese Pixel in einen Acht-Byte-Array in der Weise entpacken, die jüngste Pixel (Bit) unter dem niedrigsten Index des Arrays landen wird, und so weiter. Hier ein Beispiel:
One byte value -----------> eight byte array
10011011 -----------------> [1][1][0][1][1][0][0][1]
Array index number -------> 0 1 2 3 4 5 6 7
Im Folgenden werde ich fünf Methoden vorstellen, die das Problem lösen. Als nächstes werde ich ihren Zeitvergleich zeigen und wie ich diese Zeiten messen habe.
Meine Fragen bestehen aus zwei Teilen:
1.
Ich bitte Sie für detaillierte Antwort in Bezug auf Methoden DecodePixels4a und DecodePixels4b. Warum Verfahren 4b ist etwas langsamer als die 4a?
Wenn zum Beispiel es ist langsamer, weil mein Code nicht korrekt dann mir ausgerichtet ist, zeigen, welche Befehle in einem gegebenen Verfahren besser ausgerichtet werden können und wie dies zu tun, um die Methode nicht zu brechen.
Ich mag reale Beispiele hinter der Theorie sehen. Bitte beachten Sie, dass ich Montag lerne und ich möchte Wissen aus Ihren Antworten zu gewinnen, die mich in der Zukunft ermöglicht eine besseren optimiertem Code zu schreiben.
2.
Kann schreiben Sie schneller Routine als DecodePixels4a? Wenn ja, stellen Sie es bitte und Optimierungsschritte beschreiben, die Sie getroffen haben.
Durch schnelle Routine ich meine Routine, die unter allen Routinen in kürzester Zeit in der Testumgebung läuft hier vorgestellt.
Alle Intel-Familie Prozessoren erlaubt sind und diejenigen, die mit ihnen kompatibel sind.
Im Folgenden finden Sie Routinen geschrieben von mir finden:
procedure DecodePixels1(EncPixels: Byte; var DecPixels: TDecodedPixels);
var
i3: Integer;
begin
DecPixels[0] := EncPixels and $01;
for i3 := 1 to 7 do
begin
EncPixels := EncPixels shr 1;
DecPixels[i3] := EncPixels and $01;
//DecPixels[i3] := (EncPixels shr i3) and $01; //this is even slower if you replace above 2 lines with it
end;
end;
//Lets unroll the loop and see if it will be faster.
procedure DecodePixels2(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels[0] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[1] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[2] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[3] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[4] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[5] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[6] := EncPixels and $01;
EncPixels := EncPixels shr 1;
DecPixels[7] := EncPixels and $01;
end;
procedure DecodePixels3(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push eax;
push ebx;
push ecx;
mov bl, al;
and bl, $01;
mov [edx], bl;
mov ecx, $00;
@@Decode:
inc ecx;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + ecx], bl;
cmp ecx, $07;
jnz @@Decode;
pop ecx;
pop ebx;
pop eax;
end;
end;
//Unrolled assembly loop
procedure DecodePixels4a(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push eax;
push ebx;
mov bl, al;
and bl, $01;
mov [edx], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $01], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $02], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $03], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $04], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $05], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $06], bl;
shr al, $01;
mov bl, al;
and bl, $01;
mov [edx + $07], bl;
pop ebx;
pop eax;
end;
end;
// it differs compared to 4a only in switching two instructions (but seven times)
procedure DecodePixels4b(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push eax;
push ebx;
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $01], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $02], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $03], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $04], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $05], bl; //
mov bl, al;
and bl, $01;
shr al, $01; //
mov [edx + $06], bl; //
mov bl, al;
and bl, $01;
mov [edx + $07], bl;
pop ebx;
pop eax;
end;
end;
Und hier ist, wie ich sie testen:
program Test;
{$APPTYPE CONSOLE}
uses
SysUtils, Windows;
type
TDecodedPixels = array[0..7] of Byte;
var
Pixels: TDecodedPixels;
Freq, TimeStart, TimeEnd :Int64;
Time1, Time2, Time3, Time4a, Time4b: Extended;
i, i2: Integer;
begin
if QueryPerformanceFrequency(Freq) then
begin
for i2 := 1 to 100 do
begin
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels1(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time1 := Time1 + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels2(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time2 := Time2 + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels3(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time3 := Time3 + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels4a(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time4a := Time4a + ((TimeEnd - TimeStart) / Freq * 1000);
QueryPerformanceCounter(TimeStart);
for i := 1 to 100000 do
DecodePixels4b(155, Pixels);
QueryPerformanceCounter(TimeEnd);
Time4b := Time4b + ((TimeEnd - TimeStart) / Freq * 1000);
end;
Writeln('Time1 : ' + FloatToStr(Time1 / 100) + ' ms. <- Delphi loop.');
Writeln('Time2 : ' + FloatToStr(Time2 / 100) + ' ms. <- Delphi unrolled loop.');
Writeln('Time3 : ' + FloatToStr(Time3/ 100) + ' ms. <- BASM loop.');
Writeln('Time4a : ' + FloatToStr(Time4a / 100) + ' ms. <- BASM unrolled loop.');
Writeln('Time4b : ' + FloatToStr(Time4b / 100) + ' ms. <- BASM unrolled loop instruction switch.');
end;
Readln;
end.
Hier sind die Ergebnisse von meinem Rechner (Intel® Pentium® E2180 auf Win32 XP):
Time1 : 1,68443549919493 ms. <- Delphi loop.
Time2 : 1,33773024572211 ms. <- Delphi unrolled loop.
Time3 : 1,37015271374424 ms. <- BASM loop.
Time4a : 0,822916962526627 ms. <- BASM unrolled loop.
Time4b : 0,862914462301607 ms. <- BASM unrolled loop instruction switch.
Die Ergebnisse sind ziemlich stabil - mal nur um wenige Prozent zwischen jedem Test variieren ich gemacht habe. Und das war immer wahr: Time1 > Time3 > Time 2 > Time4b > Time4a
Also ich denke, dass de Unterschied zwischen Time4a und Time4b von abhängig, dass die Anweisungen in der Methode DecodePixels4b wechseln. Manchmal ist es 4% ist es manchmal bis zu 10%, aber 4b ist immer langsamer als 4a.
Ich war mit der Nutzung von MMX Anweisungen über eine andere Methode zu denken in den Speicher acht Bytes auf einmal zu schreiben, aber ich kann schnell Art und Weise nicht herausfinden, um Byte in die 64-Bit-Register zu entpacken.
Vielen Dank für Ihre Zeit.
Danke Jungs für Ihre wertvolle Input. Whish ich euch alle zur gleichen Zeit antworten konnte, im Vergleich leider zum modernen CPUs Ich habe nur ein „Rohr“ und kann nur eine Anweisung „Antwort“ zu der Zeit auszuführen ;-) Also werde ich versuchen, einige Dinge hier zusammenzufassen und schreiben weitere Kommentare unter Ihren Antworten.
Zunächst einmal wollte ich sagen, dass meine Frage vor der Veröffentlichung ich mit der Lösung von Wouter van Nifterick präsentiert kam und es war eigentlich Art und Weise langsamer dann mein Assembler-Code. Also habe ich beschlossen, nicht, dass die Routine hier zu posten, aber man kann sehen, dass ich den gleichen Ansatz nahm auch in meiner Schleife Delphi-Version der Routine. Es wird kommentiert, weil es mir worser Ergebnisse gab.
Dies ist ein Rätsel für mich. Ich habe meinen Code noch einmal mit Wouters und Phils Routinen laufen und hier sind die Ergebnisse:
Time1 : 1,66535493194387 ms. <- Delphi loop.
Time2 : 1,29115785420688 ms. <- Delphi unrolled loop.
Time3 : 1,33716934524107 ms. <- BASM loop.
Time4a : 0,795041753757838 ms. <- BASM unrolled loop.
Time4b : 0,843520166815013 ms. <- BASM unrolled loop instruction switch.
Time5 : 1,49457681191307 ms. <- Wouter van Nifterick, Delphi unrolled
Time6 : 0,400587402866258 ms. <- PhiS, table lookup Delphi
Time7 : 0,325472442519827 ms. <- PhiS, table lookup Delphi inline
Time8 : 0,37350491544239 ms. <- PhiS, table lookup BASM
Sehen Sie sich das TIME5 Ergebnis ziemlich seltsam, nicht wahr? Ich glaube, ich verschiedene Delphi-Version habe, da Code meines generierte Assembly von dem von Wouter vorgesehen abweicht.
Die zweite Haupt bearbeiten:
Ich weiß, warum Routine 5 langsamer auf meinem machnie war. Ich hatte geprüft „Range Überprüfung“ und in meinen Compiler-Optionen „Überlauf überprüft“. Ich habe assembler Richtlinie Routine 9 hinzugefügt, um zu sehen, ob es hilft. Es scheint, dass mit dieser Richtlinie Montageverfahren ist so gut wie Delphi Inline-Variante oder sogar etwas besser.
Hier sind die endgültigen Ergebnisse:
Time1 : 1,22508325749317 ms. <- Delphi loop.
Time2 : 1,33004145373084 ms. <- Delphi unrolled loop.
Time3 : 1,1473583622526 ms. <- BASM loop.
Time4a : 0,77322594033463 ms. <- BASM unrolled loop.
Time4b : 0,846033593023372 ms. <- BASM unrolled loop instruction switch.
Time5 : 0,688689382044384 ms. <- Wouter van Nifterick, Delphi unrolled
Time6 : 0,503233741036693 ms. <- PhiS, table lookup Delphi
Time7 : 0,385254722925063 ms. <- PhiS, table lookup Delphi inline
Time8 : 0,432993919452751 ms. <- PhiS, table lookup BASM
Time9 : 0,362680491244212 ms. <- PhiS, table lookup BASM with assembler directive
Third Haupt bearbeiten:
Nach Ansicht @Pascal Cuoq und @j_random_hacker den Unterschied in der Ausführungszeiten zwischen Routinen 4a, 4b und 5 wird durch die Datenabhängigkeit verursacht. Allerdings muss ich widersprechen, dass Stellungnahme zu den weiteren Tests stützen, die ich gemacht habe.
Ich habe auch neue Routine 4c basierend auf 4a erfunden. Hier ist sie:
procedure DecodePixels4c(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
asm
push ebx;
mov bl, al;
and bl, 1;
mov [edx], bl;
mov bl, al;
shr bl, 1;
and bl, 1;
mov [edx + $01], bl;
mov bl, al;
shr bl, 2;
and bl, 1;
mov [edx + $02], bl;
mov bl, al;
shr bl, 3;
and bl, 1;
mov [edx + $03], bl;
mov bl, al;
shr bl, 4;
and bl, 1;
mov [edx + $04], bl;
mov bl, al;
shr bl, 5;
and bl, 1;
mov [edx + $05], bl;
mov bl, al;
shr bl, 6;
and bl, 1;
mov [edx + $06], bl;
shr al, 7;
and al, 1;
mov [edx + $07], al;
pop ebx;
end;
end;
Ich würde sagen, es ist ziemlich Daten abhängig ist.
Und hier sind die Tests und Ergebnisse. Ich habe vier Tests durchgeführt, um sicherzustellen, es ist kein Zufall. Ich habe auch neue Zeiten für die Routinen Vorschlag GJ (Time10a, Time10b).
hinzugefügt Test1 Test2 Test3 Test4
Time1 : 1,211 1,210 1,220 1,213
Time2 : 1,280 1,258 1,253 1,332
Time3 : 1,129 1,138 1,130 1,160
Time4a : 0,690 0,682 0,617 0,635
Time4b : 0,707 0,698 0,706 0,659
Time4c : 0,679 0,685 0,626 0,625
Time5 : 0,715 0,682 0,686 0,679
Time6 : 0,490 0,485 0,522 0,514
Time7 : 0,323 0,333 0,336 0,318
Time8 : 0,407 0,403 0,373 0,354
Time9 : 0,352 0,378 0,355 0,355
Time10a : 1,823 1,812 1,807 1,813
Time10b : 1,113 1,120 1,115 1,118
Time10c : 0,652 0,630 0,653 0,633
Time10d : 0,156 0,155 0,172 0,160 <-- current winner!
Wie Sie die Ergebnisse der 4a sehen kann, 4b, 4c und 5 sind sehr nahe beieinander.
Warum ist das so? Weil ich entfernt aus 4a, 4b (4c bereits hat es nicht) zwei Anweisungen: push eax und pop eax. Da ich weiß, ich irgendwo sonst in meinem Code wird nicht den Wert unter EAX Ich muss es nicht prereserve.
Nun ist mein Code hat nur ein Paar von Push / Pop, um die Routine 5.
Routine 5 prereserves Wert von EAX beacause es zunächst machen Kopie davon unter ECX aber es deson't prereserve ECX.
So ist meine Schlussfolgerung ist, dass: die Zeitdifferenz Ausführung von 5 und 4a und 4b (vor dem dritten edit) betreffen nicht Daten dependecny wurde aber durch zusätzliches Paar von Push / Pop-Anweisungen verursacht .
Ich interessiere mich sehr für Ihre Kommentare.
Nach ein paar Tagen GJ erfunden noch schneller Routine (Time 10d) als PhiS ist. Gute Arbeit GJ!
Lösung
Ihr asm-Code ist Relativität langsam, da die Verwendung Stapelende 8 mal in dem Speicher zu schreiben. Sehen Sie sich diese ein ...
procedure DecodePixels(EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
xor ecx, ecx
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 1
mov [DecPixels + 4], ecx
xor ecx, ecx
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 8
add al, al
rcl ecx, 1
mov [DecPixels], ecx
end;
Vielleicht ist sogar schneller als Code mit Lookup-Tabelle!
Verbesserte Version:
procedure DecodePixelsI(EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
mov ecx, 0 //Faster than: xor ecx, ecx
add al, al
rcl ch, 1
add al, al
rcl cl, 1
ror ecx, 16
add al, al
rcl ch, 1
add al, al
rcl cl, 1
mov [DecPixels + 4], ecx
mov ecx, 0 //Faster than: xor ecx, ecx
add al, al
rcl ch, 1
add al, al
rcl cl, 1
ror ecx, 16
add al, al
rcl ch, 1
add al, al
rcl cl, 1
mov [DecPixels], ecx
end;
Version 3:
procedure DecodePixelsX(EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
add al, al
setc byte ptr[DecPixels + 7]
add al, al
setc byte ptr[DecPixels + 6]
add al, al
setc byte ptr[DecPixels + 5]
add al, al
setc byte ptr[DecPixels + 4]
add al, al
setc byte ptr[DecPixels + 3]
add al, al
setc byte ptr[DecPixels + 2]
add al, al
setc byte ptr[DecPixels + 1]
setnz byte ptr[DecPixels]
end;
Version 4:
const Uint32DecPix : array [0..15] of cardinal = (
$00000000, $00000001, $00000100, $00000101,
$00010000, $00010001, $00010100, $00010101,
$01000000, $01000001, $01000100, $01000101,
$01010000, $01010001, $01010100, $01010101
);
procedure DecodePixelsY(EncPixels: byte; var DecPixels: TDecodedPixels); inline;
begin
pcardinal(@DecPixels)^ := Uint32DecPix[EncPixels and $0F];
pcardinal(cardinal(@DecPixels) + 4)^ := Uint32DecPix[(EncPixels and $F0) shr 4];
end;
Andere Tipps
Im Allgemeinen würde ich persönlich bleiben weg von dem Versuch, den Code zu optimieren, indem Tricks auf Assembler-Ebene verwenden, es sei denn, Sie wirklich brauchen, dass zusätzliche 2 oder 3% der Geschwindigkeit, und Sie sind bereit, zahlen den Preis des Codes, die schwerer zu lesen ist, zu warten und den Hafen.
Um diesen letzten 1% drücken, könnten Sie sogar mehrere Versionen pflegen müssen pro Prozessor optimiert, und wenn neuere Prozessoren und eine verbesserte pascal Compiler zusammen kommt, wirst du nicht davon profitieren.
Der Delphi-Code ist schneller als die schnellste Assembler-Code:
procedure DecodePixels5(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels[0] := (EncPixels shr 0) and $01;
DecPixels[1] := (EncPixels shr 1) and $01;
DecPixels[2] := (EncPixels shr 2) and $01;
DecPixels[3] := (EncPixels shr 3) and $01;
DecPixels[4] := (EncPixels shr 4) and $01;
DecPixels[5] := (EncPixels shr 5) and $01;
DecPixels[6] := (EncPixels shr 6) and $01;
DecPixels[7] := (EncPixels shr 7) and $01;
end;
Results:
Time1 : 1,03096806151283 ms. <- Delphi loop.
Time2 : 0,740308641141395 ms. <- Delphi unrolled loop.
Time3 : 0,996602425688886 ms. <- BASM loop.
Time4a : 0,608267951561275 ms. <- BASM unrolled loop.
Time4b : 0,574162510648039 ms. <- BASM unrolled loop instruction switch.
Time5 : 0,499628206138524 ms. !!! <- Delphi unrolled loop 5.
Es ist schnell, da die Operationen nur mit Registern durchgeführt werden können, anstatt Speicher zu speichern und holen zu brauchen. Moderne Prozessoren führen dies zum Teil parallel (ein neuer Vorgang kann vor der vorhergehenden fertig gestartet werden), weil die Ergebnisse der aufeinanderfolgenden Befehle unabhängig voneinander sind.
Der Maschinencode sieht wie folgt aus:
push ebx;
// DecPixels[0] := (EncPixels shr 0) and 1;
movzx ecx,al
mov ebx,ecx
// shr ebx,$00
and bl,$01
mov [edx],bl
// DecPixels[1] := (EncPixels shr 1) and 1;
mov ebx,ecx
shr ebx,1
and bl,$01
mov [edx+$01],bl
// DecPixels[2] := (EncPixels shr 2) and 1;
mov ebx,ecx
shr ebx,$02
and bl,$01
mov [edx+$02],bl
// DecPixels[3] := (EncPixels shr 3) and 1;
mov ebx,ecx
shr ebx,$03
and bl,$01
mov [edx+$03],bl
// DecPixels[4] := (EncPixels shr 4) and 1;
mov ebx,ecx
shr ebx,$04
and bl,$01
mov [edx+$04],bl
// DecPixels[5] := (EncPixels shr 5) and 1;
mov ebx,ecx
shr ebx,$05
and bl,$01
mov [edx+$05],bl
// DecPixels[6] := (EncPixels shr 6) and 1;
mov ebx,ecx
shr ebx,$06
and bl,$01
mov [edx+$06],bl
// DecPixels[7] := (EncPixels shr 7) and 1;
shr ecx,$07
and cl,$01
mov [edx+$07],cl
pop ebx;
Edit:. Wie bereits angedeutet, eine Lookup-Tabelle ist in der Tat schneller
var
PixelLookup:Array[byte] of TDecodedPixels;
// You could precalculate, but the performance gain would hardly be worth it because you call this once only.
for I := 0 to 255 do
DecodePixels5b(I, PixelLookup[I]);
procedure DecodePixels7(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels := PixelLookup[EncPixels];
end;
Results:
Time1 : 1,03096806151283 ms. <- Delphi loop.
Time2 : 0,740308641141395 ms. <- Delphi unrolled loop.
Time3 : 0,996602425688886 ms. <- BASM loop.
Time4a : 0,608267951561275 ms. <- BASM unrolled loop.
Time4b : 0,574162510648039 ms. <- BASM unrolled loop instruction switch.
Time5 : 0,499628206138524 ms. !!! <- Delphi unrolled loop 5.
Time7 : 0,251533475182096 ms. <- simple table lookup
Die Erweiterung auf Nick D's Antwort, habe ich versucht, die folgende Tabelle-Lookup-basierten Versionen, die alle , die schneller als die Implementierungen Sie geben (und schneller als Wouter van Nifterick Code).
die folgende gepackten Array Gegeben:
const Uint64DecPix : PACKED ARRAY [0..255] OF UINT64 =
( $0000000000000000, $0000000000000001, $0000000000000100, $0000000000000101, $0000000000010000, $0000000000010001, $0000000000010100, $0000000000010101, $0000000001000000, $0000000001000001, $0000000001000100, $0000000001000101, $0000000001010000, $0000000001010001, $0000000001010100, $0000000001010101,
$0000000100000000, $0000000100000001, $0000000100000100, $0000000100000101, $0000000100010000, $0000000100010001, $0000000100010100, $0000000100010101, $0000000101000000, $0000000101000001, $0000000101000100, $0000000101000101, $0000000101010000, $0000000101010001, $0000000101010100, $0000000101010101,
$0000010000000000, $0000010000000001, $0000010000000100, $0000010000000101, $0000010000010000, $0000010000010001, $0000010000010100, $0000010000010101, $0000010001000000, $0000010001000001, $0000010001000100, $0000010001000101, $0000010001010000, $0000010001010001, $0000010001010100, $0000010001010101,
$0000010100000000, $0000010100000001, $0000010100000100, $0000010100000101, $0000010100010000, $0000010100010001, $0000010100010100, $0000010100010101, $0000010101000000, $0000010101000001, $0000010101000100, $0000010101000101, $0000010101010000, $0000010101010001, $0000010101010100, $0000010101010101,
$0001000000000000, $0001000000000001, $0001000000000100, $0001000000000101, $0001000000010000, $0001000000010001, $0001000000010100, $0001000000010101, $0001000001000000, $0001000001000001, $0001000001000100, $0001000001000101, $0001000001010000, $0001000001010001, $0001000001010100, $0001000001010101,
$0001000100000000, $0001000100000001, $0001000100000100, $0001000100000101, $0001000100010000, $0001000100010001, $0001000100010100, $0001000100010101, $0001000101000000, $0001000101000001, $0001000101000100, $0001000101000101, $0001000101010000, $0001000101010001, $0001000101010100, $0001000101010101,
$0001010000000000, $0001010000000001, $0001010000000100, $0001010000000101, $0001010000010000, $0001010000010001, $0001010000010100, $0001010000010101, $0001010001000000, $0001010001000001, $0001010001000100, $0001010001000101, $0001010001010000, $0001010001010001, $0001010001010100, $0001010001010101,
$0001010100000000, $0001010100000001, $0001010100000100, $0001010100000101, $0001010100010000, $0001010100010001, $0001010100010100, $0001010100010101, $0001010101000000, $0001010101000001, $0001010101000100, $0001010101000101, $0001010101010000, $0001010101010001, $0001010101010100, $0001010101010101,
$0100000000000000, $0100000000000001, $0100000000000100, $0100000000000101, $0100000000010000, $0100000000010001, $0100000000010100, $0100000000010101, $0100000001000000, $0100000001000001, $0100000001000100, $0100000001000101, $0100000001010000, $0100000001010001, $0100000001010100, $0100000001010101,
$0100000100000000, $0100000100000001, $0100000100000100, $0100000100000101, $0100000100010000, $0100000100010001, $0100000100010100, $0100000100010101, $0100000101000000, $0100000101000001, $0100000101000100, $0100000101000101, $0100000101010000, $0100000101010001, $0100000101010100, $0100000101010101,
$0100010000000000, $0100010000000001, $0100010000000100, $0100010000000101, $0100010000010000, $0100010000010001, $0100010000010100, $0100010000010101, $0100010001000000, $0100010001000001, $0100010001000100, $0100010001000101, $0100010001010000, $0100010001010001, $0100010001010100, $0100010001010101,
$0100010100000000, $0100010100000001, $0100010100000100, $0100010100000101, $0100010100010000, $0100010100010001, $0100010100010100, $0100010100010101, $0100010101000000, $0100010101000001, $0100010101000100, $0100010101000101, $0100010101010000, $0100010101010001, $0100010101010100, $0100010101010101,
$0101000000000000, $0101000000000001, $0101000000000100, $0101000000000101, $0101000000010000, $0101000000010001, $0101000000010100, $0101000000010101, $0101000001000000, $0101000001000001, $0101000001000100, $0101000001000101, $0101000001010000, $0101000001010001, $0101000001010100, $0101000001010101,
$0101000100000000, $0101000100000001, $0101000100000100, $0101000100000101, $0101000100010000, $0101000100010001, $0101000100010100, $0101000100010101, $0101000101000000, $0101000101000001, $0101000101000100, $0101000101000101, $0101000101010000, $0101000101010001, $0101000101010100, $0101000101010101,
$0101010000000000, $0101010000000001, $0101010000000100, $0101010000000101, $0101010000010000, $0101010000010001, $0101010000010100, $0101010000010101, $0101010001000000, $0101010001000001, $0101010001000100, $0101010001000101, $0101010001010000, $0101010001010001, $0101010001010100, $0101010001010101,
$0101010100000000, $0101010100000001, $0101010100000100, $0101010100000101, $0101010100010000, $0101010100010001, $0101010100010100, $0101010100010101, $0101010101000000, $0101010101000001, $0101010101000100, $0101010101000101, $0101010101010000, $0101010101010001, $0101010101010100, $0101010101010101);
PUint64DecPix : pointer = @Uint64DecPix;
Sie können schreiben Sie Folgendes:
procedure DecodePixelsPS1Pas (EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);
end;
procedure DecodePixelsPS1PasInline (EncPixels: Byte; var DecPixels: TDecodedPixels);
inline;
begin
DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);
end;
procedure DecodePixelsPS1Asm (EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
lea ecx, Uint64DecPix //[<-Added in EDIT 3]
//mov ecx, dword ptr PUint64DecPix - alternative to the above line (slower for me)
movzx eax, al
movq xmm0, [8*eax+ecx] //Using XMM rather than MMX so we don't have to issue emms at the end
movq [edx], xmm0 //use MOVQ because it doesn't need mem alignment
end;
Die Standard PAS und ASM-Implementierungen sind ziemlich ähnlich Geschwindigkeit her, aber die PAS-Implementierung mit „INLINE“ markiert ist die schnellste, weil es aller Anruf- / ret beteiligt in dem Aufruf der Routine entledigt.
- EDIT--: Ich habe vergessen zu sagen: da Sie implizit etwas über das Speicherlayout Ihrer TDecodedPixels Struktur angenommen werden, wäre es besser, wenn man es erklären, wie
PACKED ARRAY [0..7] of byte
- EDIT2--: Hier sind meine Ergebnisse zum Vergleich:
Time1 : 2.51638266874701 ms. <- Delphi loop.
Time2 : 2.11277620479698 ms. <- Delphi unrolled loop.
Time3 : 2.21972066282167 ms. <- BASM loop.
Time4a : 1.34093090043567 ms. <- BASM unrolled loop.
Time4b : 1.52222070123437 ms. <- BASM unrolled loop instruction switch.
Time5 : 1.17106364076999 ms. <- Wouter van Nifterick
TimePS1 : 0.633099318488802 ms. <- PS.Pas
TimePS2 : 0.551617593856202 ms. <- PS.Pas Inline
TimePS3 : 0.70921094720139 ms. <- PS.Asm (speed for version before 3rd EDIT)
Compiler tun sehr gute Arbeit kleine Routinen zu optimieren.
würde ich Ihren Code optimieren, indem eine Nachschlagtabelle verwendet wird.
256 verschiedene Staaten - - Da Sie ein einzelnes Byte zu dekodieren. Sie können 256-Arrays mit den entpackten Werte vorberechnet
Edit: Beachten Sie, dass Pentium-Prozessoren spezifische Befehle parallel ausführen kann ( superskalare Architektur ) wird Pairing genannt.
Reine Software-Lösung
die schöne Technik von Mit dieser Frage , die wiederum von diese Frage wir nur eine große Lösung wie diese mit haben werden eine Zeile Code (ohne Erklärungen)
type TPackedDecodedPixels = record
case integer of
0: (a: TDecodedPixels);
1: (v: Int64);
end;
procedure DecodePixels(EncPixels: byte; var DecPixels: TDecodedPixels); inline;
const
magic = $8040201008040201;
mask = $8080808080808080;
begin
TPackedDecodedPixels(DecPixels).v := SwapEndian(((EncPixels*magic) and mask) shr 7);
end;
Natürlich müssen Sie sicherstellen, dass DecPixels richtig ist 8-Byte ausgerichtet sind, oder Sie können von einer Verlangsamung (oder sogar segfaults auf anderen Architekturen) leiden. Sie können auch die Funktion leicht vektorisiert, um es schneller
Erklärung:
Angenommen, wir das folgende Bitmuster als abcdefgh haben. Wir werden das Ausgangsarray enthalten soll
0000000a 0000000b 0000000c 0000000d 0000000e 0000000f 0000000g 0000000h (1)
zu lesen, die in Little-Endian als 64-Bit-Integer wir %0000000h0000000g0000000f0000000e0000000d0000000c0000000b0000000a bekommen. Wir haben eine magische Zahl zu finden, die die ursprünglichen Bits zu den Positionen verschieben, dass wir die notwendigen Bits extrahieren
Lassen Sie uns den Wert mit der magischen Zahl multiplizieren
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
abcdefgh (1-byte value)
x 1000000001000000001000000001000000001000000001000000001000000001
__________________________________________________________________
= h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
An diesem Punkt alle Pixel Bits wurden zu den höchstwertigen Bits der entsprechenden Bytes bewegt. Da sie bereits an der richtigen Stelle gelogen, müssen wir nur noch die verbleibenden Bits mit and Streifen aus
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
& 1000000010000000100000001000000010000000100000001000000010000000
__________________________________________________________________
= h0000000g0000000f0000000e0000000d0000000c0000000b0000000a0000000 (8-byte array)
Nun werden die Pixel Bits in der höchstwertigen Bits der entsprechenden Bytes, müssen wir um 7 eine logische Verschiebung nach rechts tun sie auf die niedrigstwertigen Position. Da der OP den Wert in umgekehrter Reihenfolge will, müssen wir SwapEndian() das Bytes zu Big-Endian zu konvertieren. Wenn Sie nur wenig Endian möchten, können Sie in diesem Schritt beenden
So ist die magische Zahl ist %1000000001000000001000000001000000001000000001000000001000000001 = $8040201008040201 und die Maske ist %1000000010000000100000001000000010000000100000001000000010000000 = $8080808080808080. Natürlich in Wirklichkeit das Problem zu lösen und diese Werte, die wir tun müssen, um rückwärts vom Endergebnis → multiplizierte Ergebnis → magische Zahl
Aber warum hatte ich das Bytes in Little-Endian bei (1) und muß dann zurück zu Big-Endian-Format konvertieren? Warum organisieren nicht nur die Bytes in Big-Endian-Reihenfolge und die magische Zahl für das finden? Falls Sie sich fragen, darüber dann ist es, weil auf diese Weise nur für höchstens 7 Bits gleichzeitig arbeiten werde. Ich habe auf diese Weise in meiner alten Antwort und müssen ein wenig abspalten es dann später kombinieren zurück
0abcdefg
x 0000000000000010000001000000100000010000001000000100000010000001
__________________________________________________________________
= 00000000abcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefg
& 0000000000000001000000010000000100000001000000010000000100000001
__________________________________________________________________
= 000000000000000a0000000b0000000c0000000d0000000e0000000f0000000g
Hardware-Unterstützung
Dies ist eigentlich ein Spezialfall von Bit mit einer konstanten Maske erweitern . In AVX2 führte Intel die pdep Anweisung in BMI2 Anweisung zu diesem Zweck eingestellt, so dass Sie nur benötigt einen einzigen Befehl das Ergebnis zu erhalten. In anderen Sprachen können Sie dies mit der intrinsischen Funktion _pext_u64 verwenden. AFAIK Free Pascal unterstützt es leider nicht, und Sie haben Montage direkt zu verwenden. Doch der Ausdruck aussehen wird
TPackedDecodedPixels(DecPixels).v := _pext_u64(EncPixels, $0101010101010101);
Richtigkeitsüberprüfung:
Ich habe versucht, die Version des OP Vergleich mit beiden Versionen und kein Problem bisher gefunden hat. Die Kompiliererausgabe wie dies
mov al, dil
mov rbx, rsi
movzx edi, al
movabs rax, 0x8040201008040201
imul rdi, rax
movabs rax, 0x8080808080808080
and rdi, rax
shr rdi, 0x7
call 4016a0 <SYSTEM_$$_SWAPENDIAN$INT64$$INT64>
mov QWORD PTR [rbx], rax
Der FPC-Ausgang ist immer noch suboptimal, da der Compiler nicht weiß, um den Anruf zu ersetzen mit SwapEndian „http://www.felixcloutier.com/x86/BSWAP.html“ rel = "nofollow noreferrer "> BSWAP und kopiert Daten unnötig. Warum mov al, dil; movzx edi, al statt nur movzx edi, dil ?. Wie Sie sehen können, Ausgaben von C und C ++ Compiler sind viel besser
Siehe Erstellen eines Byte von 8 Bool-Werte (und umgekehrt)?
Ich war über den gleichen Algorithmus wie Wouter van Nifterick geben.
Darüber hinaus würde ich die bessere Leistung in Bezug auf den Abhängigkeitsketten erklären. In jeder der Versionen, die Sie vorgeschlagen, wenn Sie Ihre grundlegenden Schleife entrollt, Sie eine Abhängigkeit zwischen zwei aufeinanderfolgenden Iterationen gehalten: jede Ihrer shr al, $ 01; erfordert der vorherige Wert von al berechnet worden zu sein. Wenn Sie Ihre abgerollt Iterationen so organisieren, dass sie parallel ausgeführt werden können, werden sie tatsächlich auf einem modernen Prozessor sein. Lass dich nicht von falschen Abhängigkeiten täuschen, die durch Registerumbenennung unterdrückt werden können.
Jemand wies darauf hin, dass der Pentium zwei Befehle gleichzeitig ausführen kann. Das stimmt, aber moderne Prozessoren (seit dem Pentium Pro, PII, ..., Core Core 2) ausgeführt werden viel mehr als zwei Befehle zur gleichen Zeit, wenn sie die Chance haben - das heißt, wenn es keine Abhängigkeit zwischen den Befehlen ausgeführt wird. Beachten Sie, wie in Wouter van Nifterick Version jede Zeile unabhängig von den anderen ausgeführt werden können.
http://www.agner.org/optimize/ hat alle Informationen, die Sie könnten je brauchen die Architektur moderner Prozessoren und wie nutzen sie.
verstehenWenn Sie nur 80386 unterstützen und über Sie BTCC und SETcc Satz von Anweisungen in dieser Weise verwendet werden:
BT ax,1
SETC [dx]
inc dx
BT ax,2
SETC [dx]
inc dx
etc
Wie wäre es so etwas wie:
/* input byte in eax, address to store result in edx */
and eax, 0xff /* may not be needed */
mov ebx, eax
shl ebx, 7
or eax, ebx
mov ebx, eax
shl ebx, 14
or eax, ebx
mov ebx, eax
and eax, 0x01010101
mov [edx], eax
shr ebx, 4
and ebx, 0x01010101
mov [edx+4], ebx
Der wahrscheinliche Grund, dass 4b schneller als 4a ist, dass es parallelisiert besser. Von 4a:
mov bl, al;
and bl, $01; // data dep (bl)
mov [edx], bl; // data dep (bl)
shr al, $01;
mov bl, al; // data dep (al)
and bl, $01; // data dep (bl)
mov [edx + $01], bl; // data dep (bl)
Anleitung markiert „Daten dep“ kann die Ausführung erst beginnen, wenn der vorherige Befehl abgeschlossen hat, und ich habe die Register geschrieben, die diese Datenabhängigkeit führen. Moderne Prozessoren sind in der Lage eine Anweisung des Startens, bevor die letzte beendet hat, wenn es keine Abhängigkeit ist. Aber die Art und Weise Sie diese Operationen bestellt haben dies verhindert.
In 4b, haben Sie weniger Datenabhängigkeiten:
mov bl, al;
and bl, $01; // data dep (bl)
shr al, $01;
mov [edx], bl;
mov bl, al;
and bl, $01; // data dep (bl)
shr al, $01;
mov [edx + $01], bl;
Mit diesem Befehl Bestellung, weniger der Befehle hängen von der vorherige Anweisung, so gibt es mehr Möglichkeiten für Parallelität.
Ich kann nicht garantieren, dass dies der Grund für die Geschwindigkeitsdifferenz ist, aber es ist ein wahrscheinlicher Kandidat. Leider ist es schwierig, über Antworten als absolute wie die, die kommen, die Sie suchen; Moderne Prozessoren haben Verzweigungsvorhersager, Multi-Level-Caches, Hardware Pre-Fetcher, und alle möglichen anderen Komplexitäten, die es schwierig machen, können die Gründe für die Leistungsunterschiede zu isolieren. Das Beste, was Sie tun können, ist viel zu lesen, Experimente durchführen und mit den Werkzeugen für die guten Messungen vertraut.
I erraten es ist, dass in dem Speicher zu schreiben (eigentlich Cache-Speicher) ist langsamer als mit Registern arbeiten.
So
mov [edx+...], bl
shr al, $01;
mov bl, al;
gibt dem Prozessor einige Zeit bl in den Speicher zu schreiben, bevor das bl Register wieder benötigt wird, während
shr al, $01;
mov [edx], bl;
mov bl, al;
muss bl sofort so der Prozessor zu stoppen hat und warten, bis der Speicher-Schreib abzuschließen.
Dies ist überraschend für mich. Moderne Intel-Prozessoren zu tun verrückt Pipelining und registrieren so meiner Meinung nach der Umbenennung, wenn überhaupt, DecodePixels4b schneller sein sollte, da die Abhängigkeiten jeden Befehl sind weiter zurück. Die oben ist die ganze Erklärung, die ich anbieten kann, abgesehen davon:
x86 ist ein schrecklicher Befehlssatz, und Intel hat erstaunlichen und sehr weit fortgeschritten Hokuspokus, um es effizienter zu machen. Wenn ich Sie wäre, würde ich in etwas anderes suchen. Es gibt sehr wenig Nachfrage nach megaMcOptimised Software für PCs heute. Mein Vorschlag ist freundlich in Prozessoren für mobile Geräte zu sehen (vor allem ARM), weil in mobilen Geräten, Prozessorgeschwindigkeit, Stromverbrauch und die Lebensdauer der Batterie betrifft bedeuten, dass Mikro-optimierte Software ist wichtiger. Und ARM hat eine überlegene Anweisung auf x86.
SIMD
Wenn Sie den Algorithmus zur Verarbeitung von Arrays erweitern, dann SIMD wird eine Optimierungsoption. Hier ist eine SIMD-Version, die 1/3 der Zeit eines optimierten C äquivalent ist:
int main ()
{
const int
size = 0x100000;
unsigned char
*source = new unsigned char [size],
*dest,
*dest1 = new unsigned char [size * 32],
*dest2 = new unsigned char [size * 32];
for (int i = 0 ; i < size ; ++i)
{
source [i] = rand () & 0xff;
}
LARGE_INTEGER
start,
middle,
end;
QueryPerformanceCounter (&start);
dest = dest1;
for (int i = 0 ; i < size ; ++i)
{
unsigned char
v = source [i];
for (int b = 0 ; b < 8 ; ++b)
{
*(dest++) = (v >> b) & 1;
}
}
unsigned char
bits [] = {1,2,4,8,16,32,64,128,1,2,4,8,16,32,64,128},
zero [] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
ones [] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
QueryPerformanceCounter (&middle);
__asm
{
movdqu xmm1,bits
movdqu xmm2,zero
movdqu xmm3,ones
mov ecx,0x100000/4
mov esi,source
mov edi,dest2
l1:
lodsd
movd xmm0,eax
movd xmm4,eax
punpcklbw xmm0,xmm0
punpcklbw xmm4,xmm4
punpcklwd xmm0,xmm0
punpcklwd xmm4,xmm4
punpckldq xmm0,xmm0
punpckhdq xmm4,xmm4
pand xmm0,xmm1
pand xmm4,xmm1
pcmpeqb xmm0,xmm2
pcmpeqb xmm4,xmm2
paddb xmm0,xmm3
paddb xmm4,xmm3
movdqu [edi],xmm0
movdqu [edi+16],xmm4
add edi,32
dec ecx
jnz l1
}
QueryPerformanceCounter (&end);
cout << "Time taken = " << (middle.QuadPart - start.QuadPart) << endl;
cout << "Time taken = " << (end.QuadPart - middle.QuadPart) << endl;
cout << "memcmp = " << memcmp (dest1, dest2, size * 32) << endl;
return 0;
}
Unglaubliche intelligente Lösung Chris , was würden Sie mit dem inversen Problem zu tun: einen Byte aus einem Array von 8 Bytes machen
Nicht optimierte Lösung für das inverse Problem:
BtBld PROC Array:DWORD, Pixels:DWORD
mov eax, [Array]
add eax, 7
mov edx, [Pixels]
mov bx, 0
mov ecx, 8
rpt: or bx, [eax]
dec eax
shl bx, 1
loop rpt
shr bx, 1
mov [edx], bl
ret
BtBld ENDP
Wie man feststellt, wird die Differenz der Geschwindigkeit in 4a und 4b Umsetzung wegen der CPU-Optimierung ist (durch Ausführen mehrere Befehle parallel / Pipelining-Befehl). Aber der Faktor ist, nicht in den Operanden, sondern wegen der Art des Betreibers selbst.
4a Instruction Sequence:
AND - MOV - SHR
4b Instruction Sequence:
AND - SHR - MOV
Beide AND und SHR Nutty registrieren, so dass diese beiden Befehle haben Zustand in ihrer Pipeline warten.
Lesen Sie sie wie folgt:
4a: AND (piped) MOV (piped) SHR
4b: AND (WAIT) SHR (piped) MOV
Fazit:. 4b hat 7 weitere Wartezustand in der Pipeline als es 4a, so ist es langsamer
Josh erwähnt, dass es Datenabhängigkeiten, das heißt:.
mov bl, al;
and bl, $01; // data dep (bl)
, aber es ist nicht ganz richtig, da die beide Anweisung teilweise in paralel in CPU-Ebene ausgeführt werden kann:
mov bl, al -> (A:) read al (B:) write bl => (2 clocks in i386)
and bl, 01 -> (C:) read 01 (D:) write bl => idem
Nacheinander nehmen sie 4 Uhren, aber pipelined sie nur 3 „Uhren“ nehmen (eigentlich der Begriff „clock“ ist in der Pipeline Perspektive nicht ausreichend, aber ich benutzen es in Zusammenhang mit der Einfachheit)
[--A--][--B--]
[--C--]<wait>[---D--]
