以前の 2 つの質問、「64 ビット C/インテル アセンブリ プログラムのメモリ パフォーマンス/データ ローカリティを改善する方法」と「 C/インテル アセンブリを使用して」に続いて、128 バイトのメモリ ブロックにすべてゼロが含まれているかどうかをテストする最速の方法は何ですか? 、以下で説明するように、これらの質問で言及されているテスト プログラムの実行時間を 150 秒から 62 秒にさらに短縮しました。
64 ビット プログラムには、5 つの 4 GB ルックアップ テーブル (bytevecM、bytevecD、bytevecC、bytevecL、bytevecX) があります。最後の質問で分析した (膨大な) キャッシュ ミス数を減らすために、ルックアップ テーブルごとに 1 つずつ、5 つの 4 MB ビットマップを追加しました。
元の内部ループは次のとおりです。
psz = (size_t*)&bytevecM[(unsigned int)m7 & 0xffffff80];
if (psz[0] == 0 && psz[1] == 0
&& psz[2] == 0 && psz[3] == 0
&& psz[4] == 0 && psz[5] == 0
&& psz[6] == 0 && psz[7] == 0
&& psz[8] == 0 && psz[9] == 0
&& psz[10] == 0 && psz[11] == 0
&& psz[12] == 0 && psz[13] == 0
&& psz[14] == 0 && psz[15] == 0) continue;
// ... rinse and repeat for bytevecD, bytevecC, bytevecL, bytevecX
// expensive inner loop that scans 128 byte chunks from the 4 GB lookup tables...
この単純な「事前チェック」の背後にある考え方は、128 バイトすべてがゼロの場合にコストのかかる内部ループを回避することでした。ただし、プロファイリングでは、前回説明したように、膨大な数のキャッシュ ミスが原因で、この事前チェックが主要なボトルネックであることが示されました。そこで、事前チェックを行うために 4 MB のビットマップを作成しました。(ところで、128 バイト ブロックの約 36% はゼロであり、前回誤って報告した 98% ではありません)。
以下は、4 GB のルックアップ テーブルから 4 MB のビットマップを作成するために使用したコードです。
// Last chunk index (bitmap size=((LAST_CHUNK_IDX+1)>>3)=4,194,304 bytes)
#define LAST_CHUNK_IDX 33554431
void make_bitmap(
const unsigned char* bytevec, // in: byte vector
unsigned char* bitvec // out: bitmap
)
{
unsigned int uu;
unsigned int ucnt = 0;
unsigned int byte;
unsigned int bit;
const size_t* psz;
for (uu = 0; uu <= LAST_CHUNK_IDX; ++uu)
{
psz = (size_t*)&bytevec[uu << 7];
if (psz[0] == 0 && psz[1] == 0
&& psz[2] == 0 && psz[3] == 0
&& psz[4] == 0 && psz[5] == 0
&& psz[6] == 0 && psz[7] == 0
&& psz[8] == 0 && psz[9] == 0
&& psz[10] == 0 && psz[11] == 0
&& psz[12] == 0 && psz[13] == 0
&& psz[14] == 0 && psz[15] == 0) continue;
++ucnt;
byte = uu >> 3;
bit = (uu & 7);
bitvec[byte] |= (1 << bit);
}
printf("ucnt=%u hits from %u\n", ucnt, LAST_CHUNK_IDX+1);
}
これを行うためのより良い方法の提案は大歓迎です。
上記の関数で作成されたビットマップを使用して、次のように、4 GB のルックアップ テーブルではなく 4 MB のビットマップを使用するように「事前チェック」を変更しました。
if ( (bitvecM[m7 >> 10] & (1 << ((m7 >> 7) & 7))) == 0 ) continue;
// ... rinse and repeat for bitvecD, bitvecC, bitvecL, bitvecX
// expensive inner loop that scans 128 byte chunks from the 4 GB lookup tables...
これは、単純なシングルスレッドの場合、実行時間が 150 秒から 62 秒に短縮されたという点で「成功」しました。ただし、以下に示すように、VTune は依然としてかなり大きな数値を報告します。
異なる範囲で 8 つの同時スレッドを実行する、より現実的なテストのプロファイルを作成しました。ゼロ ブロックの内部ループ チェックの VTune 出力を以下に示します。
> m7 = (unsigned int)( (m6 ^ q7) * H_PRIME );
> if ( (bitvecM[m7 >> 10] & (1 << ((m7 >> 7) & 7))) == 0 ) continue;
0x1400025c7 Block 15:
mov eax, r15d 1.058s
mov edx, ebx 0.109s
xor eax, ecx 0.777s
imul eax, eax, 0xf4243 1.088s
mov r9d, eax 3.369s
shr eax, 0x7 0.123s
and eax, 0x7 1.306s
movzx ecx, al 1.319s
mov eax, r9d 0.156s
shr rax, 0xa 0.248s
shl edx, cl 1.321s
test byte ptr [rax+r10*1], dl 1.832s
jz 0x140007670 2.037s
> d7 = (unsigned int)( (s6.m128i_i32[0] ^ q7) * H_PRIME );
> if ( (bitvecD[d7 >> 10] & (1 << ((d7 >> 7) & 7))) == 0 ) continue;
0x1400025f3 Block 16:
mov eax, dword ptr [rsp+0x30] 104.983s
mov edx, ebx 1.663s
xor eax, r15d 0.062s
imul eax, eax, 0xf4243 0.513s
mov edi, eax 1.172s
shr eax, 0x7 0.140s
and eax, 0x7 0.062s
movzx ecx, al 0.575s
mov eax, edi 0.689s
shr rax, 0xa 0.016s
shl edx, cl 0.108s
test byte ptr [rax+r11*1], dl 1.591s
jz 0x140007670 1.087s
> c7 = (unsigned int)( (s6.m128i_i32[1] ^ q7) * H_PRIME );
> if ( (bitvecC[c7 >> 10] & (1 << ((c7 >> 7) & 7))) == 0 ) continue;
0x14000261f Block 17:
mov eax, dword ptr [rsp+0x34] 75.863s
mov edx, 0x1 1.097s
xor eax, r15d 0.031s
imul eax, eax, 0xf4243 0.265s
mov ebx, eax 0.512s
shr eax, 0x7 0.016s
and eax, 0x7 0.233s
movzx ecx, al 0.233s
mov eax, ebx 0.279s
shl edx, cl 0.109s
mov rcx, qword ptr [rsp+0x58] 0.652s
shr rax, 0xa 0.171s
movzx ecx, byte ptr [rax+rcx*1] 0.126s
test cl, dl 77.918s
jz 0x140007667
> l7 = (unsigned int)( (s6.m128i_i32[2] ^ q7) * H_PRIME );
> if ( (bitvecL[l7 >> 10] & (1 << ((l7 >> 7) & 7))) == 0 ) continue;
0x140002655 Block 18:
mov eax, dword ptr [rsp+0x38] 0.980s
mov edx, 0x1 0.794s
xor eax, r15d 0.062s
imul eax, eax, 0xf4243 0.187s
mov r11d, eax 0.278s
shr eax, 0x7 0.062s
and eax, 0x7 0.218s
movzx ecx, al 0.218s
mov eax, r11d 0.186s
shl edx, cl 0.031s
mov rcx, qword ptr [rsp+0x50] 0.373s
shr rax, 0xa 0.233s
movzx ecx, byte ptr [rax+rcx*1] 0.047s
test cl, dl 55.060s
jz 0x14000765e
それに加えて、（紛らわしいことに）多くの時間がこの行に起因していました。
> for (q6 = 1; q6 < 128; ++q6) {
0x1400075a1 Block 779:
inc edx 0.124s
mov dword ptr [rsp+0x10], edx
cmp edx, 0x80 0.031s
jl 0x140002574
mov ecx, dword ptr [rsp+0x4]
mov ebx, dword ptr [rsp+0x48]
...
0x140007575 Block 772:
mov edx, dword ptr [rsp+0x10] 0.699s
...
0x14000765e Block 789 (note: jz in l7 section above jumps here if zero):
mov edx, dword ptr [rsp+0x10] 1.169s
jmp 0x14000757e 0.791s
0x140007667 Block 790 (note: jz in c7 section above jumps here if zero):
mov edx, dword ptr [rsp+0x10] 2.261s
jmp 0x140007583 1.461s
0x140007670 Block 791 (note: jz in m7/d7 section above jumps here if zero):
mov edx, dword ptr [rsp+0x10] 108.355s
jmp 0x140007588 6.922s
上記の VTune 出力の大きな数字を完全には理解していません。誰かがこれらの数字にもっと光を当てることができれば、私はすべて耳を傾けます.
私の 5 つの 4 MB ビットマップは、私の Core i7 3770 プロセッサが 8 MB の L3 キャッシュに収まるサイズよりも大きく、多くのキャッシュ ミスが発生しているように思えます (ただし、以前よりははるかに少なくなっています)。私の CPU に 30 MB の L3 キャッシュがあれば (今後の Ivy Bridge-E のように)、5 つのビットマップすべてが L3 キャッシュに快適に収まるため、このプログラムははるかに高速に実行されると思います。そうですか？
それに加えて、ビットマップをテストするコードは次のとおりです。
m7 = (unsigned int)( (m6 ^ q7) * H_PRIME );
bitvecM[m7 >> 10] & (1 << ((m7 >> 7) & 7))) == 0
このコードを高速化するための提案は大歓迎です。