サンプル問題における Intel x86 アセンブリ最適化テクニック
https://stackoverflow.com/questions/1414911
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私はアセンブラをかなりの期間学習しており、パフォーマンス上の利点（ある場合）を確認するために、いくつかの単純なプロシージャや関数をアセンブラに書き直そうとしています。私の主な開発ツールは Delphi 2007 で、最初の例はその言語で書かれていますが、他の言語にも簡単に翻訳できます。
問題には次のように記載されています。
8 ビットのそれぞれが画面の 1 行のピクセルを表す符号なしバイト値を指定しました。それぞれの単一ピクセルは単色 (1) または透明 (0) になります。つまり、1 バイト値に 8 つのピクセルが詰め込まれています。最も若いピクセル（ビット）が配列の最も低いインデックスの下に配置されるなどの方法で、これらのピクセルを8バイト配列に解凍したいと考えています。以下に例を示します。
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
以下に、問題を解決する 5 つの方法を紹介します。次に、それらのタイムの比較と、それらのタイムをどのように測定したかを示します。
私の質問は 2 つの部分で構成されています。
1.
私はあなたにお願いしています 詳しい 方法についての回答 DecodePixels4a そして DecodePixels4b. 。なぜメソッド 4b よりも若干遅いです 4a?
たとえば、コードが正しくアライメントされていないために処理が遅くなっている場合、特定のメソッドのどの命令をより適切にアライメントできるか、およびメソッドを中断しないようにこれを行う方法を示してください。
理論の背後にある実際の例を見てみたいと思います。私はアセンブリを学習中であり、将来的にはより最適化されたコードを作成できるように、あなたの回答から知識を得たいと考えていることを覚えておいてください。
2.
より速いルーチンを書けますか DecodePixels4a?その場合は、それを提示し、実行した最適化手順について説明してください。による より速いルーチン ここで紹介するすべてのルーチンの中で、テスト環境で最も短い時間で実行されるルーチンを意味します。
すべての Intel ファミリ プロセッサと、それらと互換性のあるプロセッサが許可されます。
以下に私が書いたルーチンを示します。
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;
そして、それらをテストする方法は次のとおりです。
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.
私のマシン (Win32 XP 上の Intel® Pentium® E2180) での結果は次のとおりです。
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.
結果はかなり安定しており、実行した各テスト間での時間の変化は数パーセントのみです。そしてそれは常に真実でした。 Time1 > Time3 > Time 2 > Time4b > Time4a
したがって、Time4aとTime4bの違いは、メソッド内の命令スイッチに依存すると思います DecodePixels4b. 。4%の場合もあれば10%までの場合もありますが、 4b は常により遅いです 4a.
MMX 命令を使用して一度に 8 バイトをメモリに書き込む別の方法を考えていましたが、バイトを 64 ビット レジスタにアンパックする高速な方法がわかりません。
お時間をいただきありがとうございます。
貴重なご意見をありがとうございました。残念ながら、現代のCPUと比較して皆さんに同時に答えることができました。私は1つの「パイプ」しかありません。ここに、あなたの答えの下に追加のコメントを書いてください。
まず最初に、質問を投稿する前に、Wouter van Nifterick 氏が提示した解決策を思いつきました、そしてそれは実際にそうであったことを言いたかったのです。 ずっと遅い それから私のアセンブリコード。したがって、そのルーチンをここには投稿しないことにしましたが、ループの Delphi バージョンのルーチンでも同じアプローチをとったことがわかるかもしれません。より悪い結果が得られたため、そこにコメントされています。
これは私にとって謎です。Wouter と PhilS のルーチンを使用してコードをもう一度実行しました。結果は次のとおりです。
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
Time5 の結果を見てください。かなり奇妙ではありませんか?生成されたアセンブリ コードが Wouter によって提供されたものと異なるため、Delphi のバージョンが異なると思われます。
2 番目の大幅な編集:
なぜルーチンなのかはわかっています 5 私の機械では遅かったです。コンパイラオプションで「範囲チェック」と「オーバーフローチェック」をチェックしていました。私は追加しました assembler ルーチンへのディレクティブ 9 それが役立つかどうかを確認してください。このディレクティブを使用すると、アセンブリ手順は Delphi のインライン版と同等か、わずかに優れているようです。
最終結果は次のとおりです。
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
3回目の大規模な編集:
@Pascal Cuoqと@j_random_hackerの意見では、ルーチン間の実行時間の違い 4a, 4b そして 5 データの依存関係によって引き起こされます。しかし、私が行ったさらなるテストに基づいて、私はその意見に同意しなければなりません。
新しいルーティンも考案しました 4c に基づく 4a. 。ここにあります：
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;
かなりデータに依存していると言えます。
そして、これがテストと結果です。事故がないことを確認するために4つのテストを行いました。また、GJ が提案したルーチン (Time10a、Time10b) に新しい時間を追加しました。
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!
結果からわかるように、 4a, 4b, 4c そして 5 お互いにとても近いです。何故ですか？なぜなら私は 削除されました 4a、4b (4c にはすでにありません) からの 2 つの命令: push eax そして pop eax. 。eax の下の値はコード内の他の場所で使用しないことがわかっているので、事前に予約する必要はありません。現在、私のコードにはルーチン 5 のようにプッシュ/ポップのペアが 1 つだけあります。ルーチン 5 は、最初に ecx の下に eax のコピーを作成しますが、ecx を事前予約しないため、eax の値を事前予約します。
したがって、私の結論は次のとおりです。5と4aと4bの実行時間の差（3回目の編集前） データの依存関係は関係ありませんでしたが、追加のプッシュ/ポップ命令のペアが原因でした.
皆さんのコメントにとても興味があります。
数日後、GJ は PhiS よりもさらに高速なルーチン (時間 10 日) を発明しました。頑張れGJ！
解決
スタックエンドを使用してメモリに8回書き込みを行うため、ASMコードは相対性理論が遅くなります。これをチェックしてください...
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;
もしかしたら、ルックアップ テーブルを使用したコードよりもさらに高速になる可能性があります。
改良版:
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;
バージョン 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;
バージョン 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;
他のヒント
一般に、私は個人的には、アセンブラー レベルのトリックを使用してコードを最適化しようとすることは避けたいと考えています。 ない限り 本当に 2 ～ 3% の追加の速度が必要であり、読み取り、保守、移植が困難になるコードの代償を喜んで支払うことになります。
最後の 1% を圧縮するには、プロセッサごとに最適化された複数のバージョンを維持する必要さえあるかもしれません。新しいプロセッサや改良された Pascal コンパイラが登場しても、その恩恵を受けることはできません。
この Delphi コードのほうが高速です 最速のアセンブラ コードよりも:
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.
メモリの格納やフェッチを必要とせず、レジスタだけで操作を実行できるため高速です。最新のプロセッサは、連続する命令の結果が互いに独立しているため、これを部分的に並行して実行します (前の命令が完了する前に新しい演算を開始できます)。
マシンコードは次のようになります。
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;
編集：示唆されているように、テーブル ルックアップは確かに高速です。
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
Nick D の答えを拡張して、次のテーブルルックアップベースのバージョンを試しました。 あなたが提供する実装よりも高速です (そして Wouter van Nifterick のコードよりも高速です)。
次のパックされた配列があるとします。
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;
次のように書くことができます。
procedure DecodePixelsPS1Pas (EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);
end;
プロシージャ DecodePixelsPS1PasInline (EncPixels:バイト;var DecPixels:TDecodedPixels);列をなして;decpixelsを開始：= tdecodedpixels（uint64decpix [encpixels]）;終わり;
プロシージャ DecodePixelsPS1Asm (EncPixels:バイト;var DecPixels:TDecodedPixels);ASM Lea ECX、UINT64DECPIX // [< - 編集3に追加] // MOV ECX、DWORD PTR PUINT64DECPIX-上記のライン（私にとって遅い）に代わるMOVZX EAX、AL MOVQ XMM0、[8*EAX+ECX] // MMXではなくXMMを使用するため、MEMのアライメントエンドは必要ないため、emms bovq [edx]、xmm0 // movqを使用する必要はありません。
標準の PAS 実装と ASM 実装は、速度の点ではかなり似ていますが、「INLINE」とマークされた PAS 実装は、ルーチンの呼び出しに関連する呼び出し/ret をすべて取り除くため、最も高速です。
- 編集 - ：言うのを忘れていました:TDecodedPixels 構造体のメモリ レイアウトについて暗黙的に何かを想定しているため、次のように宣言した方がよいでしょう。
PACKED ARRAY [0..7] of byte
--編集2--:比較のための私の結果は次のとおりです。
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)
コンパイラは、小さなルーチンの最適化において非常に優れた仕事をします。
ルックアップ テーブルを使用してコードを最適化します。
単一バイト (256 個の異なる状態) をデコードするので、アンパックされた値を使用して 256 個の配列を事前計算できます。
編集： Pentium プロセッサは特定の命令を並行して実行できることに注意してください (スーパースカラ アーキテクチャ)、これをペアリングと呼びます。
純粋なソフトウェアソリューション
の美しいテクニックを使用して、 この質問, 、これもまたインスピレーションを受けています この質問 それだけでこのような素晴らしいソリューションが得られます 一行 コードの数 (宣言を除く)
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;
もちろんそれを確認する必要があります DecPixels 適切です 8バイトアライン あるいは、何らかの速度低下 (または他のアーキテクチャではセグメンテーション違反) が発生する可能性があります。関数を簡単にベクトル化して高速化することもできます
説明：
次のようなビットパターンがあると仮定します。 abcdefgh. 。出力配列に次の内容を含める必要があります。
0000000a 0000000b 0000000c 0000000d 0000000e 0000000f 0000000g 0000000h (1)
それを読むと リトルエンディアン 64ビット整数として取得します %0000000h0000000g0000000f0000000e0000000d0000000c0000000b0000000a. 。元のビットを、必要なビットを抽出できる位置に移動する魔法の数を見つける必要があります。
値にマジックナンバーを掛けてみましょう
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
abcdefgh (1-byte value)
x 1000000001000000001000000001000000001000000001000000001000000001
__________________________________________________________________
= h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
この時点で、すべてのピクセルのビットが、対応するバイトの最上位ビットに移動されます。それらはすでに正しい場所に配置されているため、残りのビットを次のように削除するだけです。 and
| b7 || b6 || b4 || b4 || b3 || b2 || b1 || b0 |
h0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh0abcdefgh
& 1000000010000000100000001000000010000000100000001000000010000000
__________________________________________________________________
= h0000000g0000000f0000000e0000000d0000000c0000000b0000000a0000000 (8-byte array)
これでピクセルのビットは 最も重要な 対応するバイトのビットを取得するには、次のことを行う必要があります。 7 による論理右シフト に移動するには 最も重要でない 位置。OP は逆の順序で値を必要とするため、次の必要があります。 SwapEndian() バイトをビッグエンディアンに変換します。リトルエンディアンだけが必要な場合は、このステップで停止できます。
したがって、魔法の数字は次のとおりです %1000000001000000001000000001000000001000000001000000001000000001 = $8040201008040201 そしてマスクは %1000000010000000100000001000000010000000100000001000000010000000 = $8080808080808080. 。もちろん、実際には問題を解決してそれらの値を取得するには、最終結果→乗算結果→マジックナンバーの順に逆算する必要があります。
しかし、なぜ (1) でバイトをリトル エンディアンに置き、その後ビッグ エンディアンに変換し直さなければならなかったのでしょうか?バイトをビッグエンディアン順に並べて、その魔法の数を見つけてみませんか?それについて疑問に思っている方のために言っておきますが、その方法では一度に最大 7 ビットしか機能しないからです。私はそのようにしました 私の古い答えでは 少し分割して、後で結合する必要があります
0abcdefg
x 0000000000000010000001000000100000010000001000000100000010000001
__________________________________________________________________
= 00000000abcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefg
& 0000000000000001000000010000000100000001000000010000000100000001
__________________________________________________________________
= 000000000000000a0000000b0000000c0000000d0000000e0000000f0000000g
ハードウェアサポート
これは実際には特殊なケースです ビット拡張 一定のマスクを使用します。AVX2 では、Intel が導入しました。 pdep 命令 その目的のために BMI2 命令セットが組み込まれているため、結果を取得するには 1 つの命令だけが必要です。他の言語では、これを組み込み関数とともに使用できます。 _pext_u64. 。残念ながら、私の知る限り、Free Pascalはそれをサポートしていないため、アセンブリを直接使用する必要があります。ただし、式は次のようになります
TPackedDecodedPixels(DecPixels).v := _pext_u64(EncPixels, $0101010101010101);
正確性チェック:
私は試した OPのバージョンと私の両方のバージョンを比較する そして今まで何も問題は見つかりませんでした。の コンパイラ出力 こんな感じです
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
コンパイラは呼び出しを置き換えるべきかどうかを認識していないため、FPC 出力は依然として最適ではありません。 SwapEndian と BSWAP, 、不必要にデータがコピーされます。なぜ mov al, dil; movzx edi, al ただの代わりに movzx edi, dil?。ご覧のとおり、C および C++ コンパイラーからの出力は次のようになります。 ずっと良くなりました
私はワウター・ファン・ニフテリックと同じアルゴリズムを教えようとしていた。
さらに、依存関係チェーンの観点からパフォーマンスが向上することについて説明します。あなたが提案した各バージョンでは、基本ループを展開するときに、連続する 2 つの反復間の依存関係を維持しました。それぞれのシュアル、01 ドル。al の前の値が計算されている必要があります。展開された反復を並列実行できるように編成すると、実際には最新のプロセッサ上で実行されます。レジスタ名の変更によって抑制できる誤った依存関係に騙されないでください。
誰かが、Pentium は一度に 2 つの命令を実行できると指摘しました。それは事実ですが、最新のプロセッサ (Pentium Pro、PII、...、Core、Core 2 以降) は、可能性がある場合、つまり依存関係がない場合、2 つよりはるかに多くの命令を同時に実行しています。実行される命令の間。Wouter van Nifterick のバージョンでは、各行が他の行から独立して実行できることに注目してください。
http://www.agner.org/optimize/ 最新のプロセッサのアーキテクチャとその活用方法を理解するために必要な情報がすべて揃っています。
80386 以降のみをサポートする場合は、次の方法で BTcc および SETcc 命令セットを使用できます。
BT ax,1
SETC [dx]
inc dx
BT ax,2
SETC [dx]
inc dx
等
次のようなものはどうでしょうか。
/* 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
4b が 4a より速い理由は、並列化がより優れているためと考えられます。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)
「データ依存」とマークされた命令は、前の命令が完了するまで実行を開始できません。また、このデータ依存関係を引き起こすレジスタを作成しました。最新の CPU は、依存関係がない場合、最後の命令が完了する前に命令を開始できます。しかし、これらの操作を命令した方法により、これが阻止されます。
4b では、データの依存関係が少なくなります。
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;
この命令の順序付けでは、前の命令に依存する命令が少なくなるため、並列処理の可能性が高くなります。
これが速度の違いの理由であるとは保証できませんが、可能性としては考えられます。残念ながら、あなたが探しているような絶対的な答えに出会うことは困難です。最新のプロセッサには、分岐予測機能、マルチレベル キャッシュ、ハードウェア プリフェッチャー、その他あらゆる種類の複雑さがあり、パフォーマンスの違いの原因を特定することが困難になる場合があります。できる最善のことは、たくさん本を読み、実験を行い、適切な測定を行うためのツールに慣れることです。
私 推測 それは、メモリ (実際にはキャッシュ メモリ) への書き込みがレジスタを操作するよりも遅いということです。
それで、
mov [edx+...], bl
shr al, $01;
mov bl, al;
プロセッサに書き込み時間を与える bl 前の記憶に bl 再度登録が必要ですが、
shr al, $01;
mov [edx], bl;
mov bl, al;
ニーズ bl そのため、プロセッサは停止してメモリへの書き込みが完了するまで待つ必要があります。
これは私にとって驚きです。最近の Intel プロセッサはクレイジーなパイプライン処理とレジスタ名の変更を行うため、私の意見では、各命令の依存関係がさらに遡るため、どちらかと言えば DecodePixels4b の方が高速であるはずです。以上が私が提供できる説明のすべてですが、これ以外は次のとおりです。
x86 はひどい命令セットですが、Intel はそれを効率化するために驚くべき非常に高度な処理を行っています。私があなただったら、別のことを検討するでしょう。現在、PC 用の megaMcOptimized ソフトウェアの需要はほとんどありません。私の親切な提案は、モバイル デバイス用のプロセッサ (主に ARM) を検討することです。モバイル デバイスでは、プロセッサの速度、消費電力、バッテリ寿命の懸念から、微細に最適化されたソフトウェアがより重要であるためです。そして、ARM には x86 に優れた命令セットがあります。
SIMD
アルゴリズムを配列の処理に拡張する場合、SIMD が最適化オプションになります。以下は、最適化された C 版の 1/3 の時間の SIMD バージョンです。
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;
}
信じられないほどスマートなソリューション Chris, 、逆問題をどうするか:8バイトの配列からバイトを作成しますか?
逆問題に対する最適化されていない解決策:
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
お気づきのとおり、4a と 4b の実装における速度の違いは、CPU の最適化 (複数の命令の並列実行/命令のパイプライン処理による) によるものです。ただし、この因数はオペランド内にあるのではなく、演算子自体の性質によるものです。
4a Instruction Sequence:
AND - MOV - SHR
4b Instruction Sequence:
AND - SHR - MOV
AND と SHR はどちらも Flags レジスタを使用するため、これら 2 つの命令はパイプライン内で待機状態になります。
次のように読んでください。
4a: AND (piped) MOV (piped) SHR
4b: AND (WAIT) SHR (piped) MOV
結論：4b は 4a よりもパイプライン内の待機状態が 7 つ多いため、速度が遅くなります。
Josh は、データの依存関係があると述べました。つまり、次のとおりです。
mov bl, al;
and bl, $01; // data dep (bl)
ただし、これら 2 つの命令は部分的に CPU レベルで並行して実行できるため、完全に真実というわけではありません。
mov bl, al -> (A:) read al (B:) write bl => (2 clocks in i386)
and bl, 01 -> (C:) read 01 (D:) write bl => idem
シーケンシャルには 4 クロックかかりますが、パイプラインでは 3 「クロック」しかかかりません (実際、「クロック」という用語はパイプラインの観点からは適切ではありませんが、わかりやすくするために使用しました)
[--A--][--B--]
[--C--]<wait>[---D--]
