ここには素晴らしいアイデアがたくさんありますが、議論の中でそれらを見つけるのは難しくなっています. この回答を使用して、最終的な解決策とそのタイミングを提供しましょう。この投稿を自由に編集し、タイミングに合わせて独自の投稿を追加してください。タイミングが不明な場合は、下部のコードに貼り付けてください。測定します。x64 アセンブリが最適です。喜んで C をコンパイルしますが、このレベルの最適化では、多くの微調整なしで良い結果が得られることはめったにありません。
概要
質問を適切なコンテキストに言い換える: 目標は、「Varint-GB」(または Group Varint) で知られる整数圧縮形式を迅速にデコードすることです。Daniel Lemire と Leo Boytsov による論文で説明されています。. 私は標準的な「明らかに著者はばかだ」スタイルのこの論文の最初のバージョンについてコメントし、Daniel (この論文の主な著者であり、それほどばかではない) は、フォローアップのためのコード作成を助けるために狡猾に私を巻き込んだ.
標準の Varint (別名 VByte) には、各バイトの先頭に整数の末尾かどうかを判断するフラグがありますが、これは解析に時間がかかります。このバージョンには、1 バイトの「キー」と、ペイロードの 4 つの圧縮された整数があります。キーは 4 つの 2 ビット フィールドで構成され、それぞれが後続の圧縮された整数のバイト長を表します。それぞれ、1 バイト (00)、2 バイト (01)、3 バイト (10)、または 4 バイト (11) にすることができます。したがって、各「チャンク」は 5 ～ 17 バイトの長さですが、常に同じ数 (4) の 32 ビット符号なし整数をエンコードします。
Sample Chunk:
Key: 01 01 10 00
Data: [A: two bytes] [B: two bytes] [C: three bytes] [D: one byte]
Decodes to: 00 00 AA AA 00 00 BB BB 00 CC CC CC 00 00 00 DD
キーは、16 バイトのシャッフル パターンのテーブルへのインデックスであり、実際のデコードは、PSHUFB を使用してデータ バイトを正しい間隔にシャッフルすることによって行われます。
vec_t Data = *input
vec_t ShuffleKey = decodeTable[key]
VEC_SHUFFLE(Data, ShuffleKey) // PSHUFB
*out = Data
実際には、通常、元の整数は通常、整数自体ではなく整数間の「デルタ」(差) を圧縮することによって小さくされているため、通常は「デルタ復号化」ステップもあります。ただし、デコード ルーチンのレイテンシは、次の反復がそれに依存しないため、通常は問題になりません。
問題の再掲
ここで指定されている問題は、ある「キー」から次のキーにホップすることです。ここでは、デコードされたデータには依存関係がないため (キーのみ)、実際のデコードは無視して、キーを読み取るループに集中します。この関数は、キーへのポインタとカウント n を取り、n 番目のキーを返します。
11サイクル
「基本的な」アプローチは、キーをインデックスとして「事前」オフセットのルックアップ テーブルを使用することです。offsetTable 内の 256 個のキーのいずれかを検索して、事前に計算された (合計 + 1) オフセットを取得します。それを現在の入力位置に追加し、次のキーを読み取ります。Intel の IACA によると、このループは Sandy Bridge で 11 サイクルかかります (Sandy Bridge でも 1 サイクルはそれ以下にカウントされます)。
uint32_t decodeBasic(uint8_t *in, size_t count) {
uint64_t key, advance;
for (size_t i = count; i > 0; i--) {
key = *in;
advance = offsetTable[key];
in += advance;
}
return key;
}
0000000000000000 <decodeBasic>:
0: test %rsi,%rsi
3: je 19 <decodeBasic+0x19>
5: nopl (%rax)
8: movzbl (%rdi),%eax
b: add 0x0(,%rax,8),%rdi
13: sub $0x1,%rsi
17: jne 8 <decodeBasic+0x8>
19: repz retq
Block Throughput: 11.00 Cycles Throughput Bottleneck: InterIteration
0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | |
--------------------------------------------------------------
| | | 1.0 1.0 | | | | CP | movzx eax, byte ptr [rdi]
| 0.3 | 0.3 | | 1.0 1.0 | | 0.3 | CP | add rdi, qword ptr [rax*8]
| | | | | | 1.0 | | sub rsi, 0x1
| | | | | | | | jnz 0xffffffffffffffe7
10サイクル
そこから、入力ポインターの更新を追加し、同時に次のキーの読み込みを開始するようにループを再配置することで、10 サイクルまで下げることができます。インライン アセンブリを使用して、コンパイラが必要な出力を生成するように「奨励」しなければならなかったことに気付くかもしれません。外側のループも (通常は) 同じままなので、削除し始めます。
key = *in;
advance = offsetTable[key];
for (size_t i = count; i > 0; i--) {
key = *(in + advance);
ASM_LEA_ADD_BASE(in, advance);
advance = offsetTable[key];
}
Block Throughput: 10.00 Cycles Throughput Bottleneck: InterIteration
| 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | |
------------------------------------------------------------
| | | 1.0 1.0 | | | | CP | movzx eax, byte ptr [rdi+rdx*1]
| 0.5 | 0.5 | | | | | | lea rdi, ptr [rdi+rdx*1]
| | | | 1.0 1.0 | | | CP | mov rdx, qword ptr [rax*8]
| | | | | | 1.0 | | sub rsi, 0x1
| | | | | | | | jnz 0xffffffffffffffe2
9サイクル
以前に POPCNT を使用しようとしましたが、Ira と AShelly からの提案、ヒント、およびアイデアがなければ、うまくいきませんでした。しかし、ピースをまとめると、9 サイクルでループを実行するものがあると思います。実際のデコーダーに入れてみましたが、Ints/s の数はこれと一致しているようです。このループは本質的にアセンブリにあります。複数のコンパイラは別として、他の方法では望んでいたことをコンパイラに実行させることができなかったからです。
[編集: AShelly によるコメントごとに余分な MOV を削除]
uint64_t key1 = *in;
uint64_t key2 = *in;
for (size_t i = count; i > 0; i--) {
uint64_t advance1, advance2;
ASM_POPCOUNT(advance1, key1);
ASM_AND(key2, 0xAA);
ASM_POPCOUNT(advance2, key2);
in += advance1;
ASM_MOVE_BYTE(key1, *(in + advance2 + 4));
ASM_LOAD_BASE_OFFSET_INDEX_MUL(key2, in, 4, advance2, 1);
in += advance2;
}
Block Throughput: 9.00 Cycles Throughput Bottleneck: InterIteration
| 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | |
------------------------------------------------------------
| | 1.0 | | | | | CP | popcnt r8, rax
| 1.0 | | | | | | CP | and rdx, 0xaa
| | | | | | 1.0 | CP | add r8, rdi
| | 1.0 | | | | | CP | popcnt rcx, rdx
| | | 1.0 1.0 | | | | CP | movzx rax, byte ptr [rcx+r8*1+0x4]
| | | | 1.0 1.0 | | | CP | mov rdx, qword ptr [r8+rcx*1+0x4]
| 1.0 | | | | | | | lea rdi, ptr [rcx+r8*1]
| | | | | | 1.0 | | dec rsi
| | | | | | | | jnz 0xffffffffffffffd0
最新のプロセッサーの可動部分の複雑さを示すものとして、私はこのルーチンのバリエーションで興味深い経験をしました。と ( ) でメモリの場所を指定mov raxして 2 行目を結合すると、30% 実行するために実行が不安定なルーチンになってしまいました。これは、ループに至るまでの初期条件によって、load/and の「and」マイクロ操作がループ全体の POPCNT の前に実行されることがあるからだと思います。and rax, 0xaamov rax, 0xAA; and rax, qword ptr [r8+rcx*1+0x4]
8サイクル
誰？
エフゲニー
これは、エフゲニーのソリューションを実装する私の試みです。少なくとも IACA の Sandy Bridge のモデル (これまでのところ正確です) については、まだ 9 サイクルまで下げることができませんでした。問題は、ROR のレイテンシは 1 ですが、P1 または P5 で 2 つのマイクロオペレーションが必要になることだと思います。レイテンシを 1 にするには、両方が利用可能である必要があります。AND、ADD、および MOV は P0、P1、または P5 で発行できますが、SHR は P1 で発行できません。ADD と AND が SHR または ROR を置き換えるのを防ぐ余分なジャンク操作を追加することで、10 サイクルに近づけることができますが、10 を下回る方法はわかりません。
Block Throughput: 10.55 Cycles Throughput Bottleneck: InterIteration
| 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | |
------------------------------------------------------------
| | | 1.0 1.0 | | | | CP | movzx eax, byte ptr [esi+0x5]
| | | | 1.0 1.0 | | | CP | movzx ebx, byte ptr [esi+0x5]
| 0.2 | 0.6 | | | | 0.3 | | add esi, 0x5
| 0.3 | 0.3 | | | | 0.3 | | mov ecx, 0x3
| 0.2 | 0.2 | | | | 0.6 | | mov edx, 0x3
| 1.4 | | | | | 0.6 | CP | ror al, 0x4
| 0.1 | 0.7 | | | | 0.2 | CP | and ecx, ebx
| 0.6 | | | | | 0.4 | CP | shr ebx, 0x6
| 0.1 | 0.7 | | | | 0.2 | CP | add ebx, ecx
| 0.3 | 0.4 | | | | 0.3 | CP | and edx, eax
| 0.6 | | | | | 0.3 | CP | shr eax, 0x6
| 0.1 | 0.7 | | | | 0.2 | CP | add eax, edx
| 0.3 | 0.3 | | | | 0.3 | CP | add esi, ebx
| 0.2 | 0.2 | | | | 0.6 | CP | add esi, eax