なぜ私の Intel Skylake / Kaby Lake CPU は、単純なハッシュテーブルの実装で不可解な 3 倍の速度低下を起こすのでしょうか? 質問する

Question

まとめ

TLDRは、TLBのすべてのレベルを逃す（したがってページウォークを必要とする）ロードと、住所不明ストアは並列実行できない、つまりロードはシリアル化され、メモリレベルの並列処理（MLP）係数は1に制限されています。実質的に、店舗はフェンス負荷も同様lfenceです。

挿入関数の遅いバージョンではこのシナリオになりますが、他の 2 つではこのシナリオになりません (ストアアドレスが既知)。領域サイズが大きい場合、メモリアクセスパターンが支配的になり、パフォーマンスは MLP にほぼ直接関係します。高速バージョンでは、ロードミスが重複して MLP が約 3 になり、3 倍のスピードアップが実現します (以下で説明する狭い再現ケースでは、10倍Skylake の違い)。

根本的な理由は、Skylakeプロセッサがページテーブルの一貫性これは仕様では必須ではありませんが、ソフトウェアのバグを回避することができます。

詳細

興味のある方のために、何が起こっているのか詳細に掘り下げてみます。

私は Skylake i7-6700HQ マシンですぐに問題を再現することができ、余分な部分を取り除くことで、元のハッシュ挿入ベンチマークを次の単純なループに減らすことができましたが、同じ問題が発生します。

tlb_fencing:

    xor     eax, eax  ; the index pointer
    mov     r9 , [rsi + region.start]

    mov     r8 , [rsi + region.size]  
    sub     r8 , 200                   ; pointer to end of region (plus a bit of buffer)

    mov     r10, [rsi + region.size]
    sub     r10, 1 ; mask

    mov     rsi, r9   ; region start

.top:
    mov     rcx, rax
    and     rcx, r10        ; remap the index into the region via masking
    add     rcx, r9         ; make pointer p into the region
    mov     rdx, [rcx]      ; load 8 bytes at p, always zero
    xor     rcx, rcx        ; no-op
    mov     DWORD [rsi + rdx + 160], 0 ; store zero at p + 160 
    add     rax, (64 * 67)  ; advance a prime number of cache lines slightly larger than a page

    dec     rdi
    jnz     .top

    ret

^{これは、 4}B.sizeの最も内側のループのアクセス (ロード) とB.values[B.size] = 1アクセス (ストア)とほぼ同等です。insert_ok

ループに集中して、ストライドロードと固定ストアを実行します。次に、ロード位置をページサイズ（4 KiB）より少しだけ前方に移動します。重要なのは、ストアアドレスです。依存するロードの結果: アドレス指定式には、ロードされた値¹を保持するレジスタが[rsi + rdx + 160]含まれています。ループ内でアドレスコンポーネントは変更されないため、ストアは常に同じアドレスに対して行われます (したがって、常に L1 キャッシュヒットが予想されます)。rdx

元のハッシュの例では、より多くの作業が行われ、メモリにランダムにアクセスし、ロードと同じ行にストアが行われていましたが、この単純なループでも同じ効果が得られます。

我々はベンチマークの別のバージョンも使用します。これは、xor rcx, rcxロードとストアの間のno-opがに置き換えられていることを除いて同一ですxor rdx, rdx。休憩ロードアドレスとストアアドレス間の依存関係。

単純に考えれば、この依存関係が大きな効果をもたらすとは考えられません。ここにある店舗はファイアアンドフォーゲット:保存された場所から再度読み取ることはありません (少なくとも多くの反復では)。そのため、それらは継承される依存関係チェーンの一部ではありません。小さな領域の場合、ボトルネックは約 8 個の uop を処理することであり、大きな領域の場合、すべてのキャッシュミスを処理する時間が支配的になると予想されます。重要なのは、ロードアドレスは単純な非メモリ uop から独立して計算できるため、多くのミスが並列で処理されると予想されることです。

以下に、4 KiB から 256 MiB までの領域サイズについて、次の 3 つのバリエーションでサイクル単位のパフォーマンスを示します。

2M デップ:上記のループ（ストアアドレスはロードに依存）では、2 MiB の巨大ページ。

4K 解像度:上記のループ (ストアアドレスはロードに依存) は標準の 4 KiB ページです。

4K独立:上記のループのバリエーションですが、ロード結果とストアアドレス間の依存関係を断ち切るために 4 KiB ページを使用してxor rdx, rdx置き換えています。xor rcx, rcx

結果：

すべてのバリアントのパフォーマンスは、小さな領域サイズでは基本的に同じです。256 KiBまでのすべては、ループ内の8つのuopと、4 uops/サイクルのCPU幅少し計算してみると、MLP (メモリレベルの並列処理) が適切であることがわかります。L2 キャッシュヒットのレイテンシは 12 サイクルですが、2 サイクルごとに 1 つ完了するため、これを達成するには平均して 6 回の L1 ミスのレイテンシを重ねる必要があります。

256 KiB から 4096 KiB の間では、L3 ヒットが発生し始めるとパフォーマンスが多少低下しますが、パフォーマンスは良好で MLP は高くなります。

8196 KiBではパフォーマンスが著しく低下し、のみの4K 解像度150サイクルを超えて最終的に約220サイクルで安定します。10回他の2つのケースよりも遅い²。

すでにいくつかの重要な観察結果が示されています。

両方とも200万デップそしてその4K独立ケースは速いので、これはただストア間の依存関係だけでなく、ページングの動作についても説明します。
の200万デップこの場合は最も高速なので、メモリが不足している場合でも依存関係によって根本的な問題が発生しないことがわかります。
スローのパフォーマンス4K 解像度このケースは私のマシンのメモリ遅延と疑わしいほど似ています。

上記で MLP について説明し、観測されたパフォーマンスに基づいて MLP の下限を計算しましたが、Intel CPU では 2 つのパフォーマンスカウンターを使用して MLP を直接測定できます。

l1d_pend_miss.pending

未処理の L1D ミスの期間、つまり、デマンド読み取りに必要な未処理の Fill Buffers (FB) の各サイクル数をカウントします。

l1d_pend_miss.pending_cycles

L1Dロードのサイクル未処理のミス

最初のカウンタは、L1Dからの未処理のリクエスト数を毎サイクルカウントします。つまり、3つのミスが進行中の場合、このカウンタは毎サイクル3ずつ増加します。2番目のカウンタは、少なくとも毎サイクル1ずつ増加します。1つl1d_pend_miss.pending / l1d_pend_miss.pending_cyclesミスが進行中です。これは、サイクルごとに 1 で飽和する最初のカウンターのバージョンとして見ることができます。一定期間にわたるこれらのカウンターの比率は、ミスが未解決の場合の平均 MLP 係数³です。

MLP比率をプロットしてみましょう退去そして独立した4Kベンチマークのバージョン:

問題は非常に明確になります。4096 KiB の領域までは、パフォーマンスは同じで、MLP は高くなります (非常に小さな領域サイズでは、L1D ミスがまったくないため、MLP は「ありません」)。8192 KiB で突然、依存ケースの MLP は 1 に低下してそこに留まりますが、独立ケースでは MLP はほぼ 10 になります。これだけで、基本的に 10 倍のパフォーマンスの違いが説明できます。依存ケースでは、ロードをまったくオーバーラップできません。

なぜでしょうか? 問題は TLB ミスのようです。8192 KiB で何が起こるかというと、ベンチマークが TLB をミスし始めるからです。具体的には、各 Skylake コアには 1536 個の STLB (第 2 レベル TLB) エントリがあり、1536 × 4096 = 6 MiB の 4K ページをカバーできます。したがって、4 MiB と 8 MiB の領域サイズの間で、TLB ミスはに基づいて反復ごとに 1 になりdtlb_load_misses.walk_completed、このほぼ完璧すぎる偽物プロットにつながります。

つまり、次のようなことが起こります。アドレス不明のストアがストアバッファー内にある場合、STLB ミスが発生するロードは重複できません。一度に 1 つずつ実行されます。そのため、アクセスごとにメモリ全体の遅延が発生します。これは、2 MB ページのケースが高速だった理由も説明しています。2 MB ページは 3 GiB のメモリをカバーできるため、これらの領域サイズでは STLB ミス/ページウォークは発生しません。

なぜ

この動作は、Skylakeやその他の初期のIntelプロセッサが実装しているという事実に起因しているようです。ページテーブルの一貫性、x86 プラットフォームでは必須ではありませんが、ページテーブルの一貫性とは、たとえば、アドレスマッピングを変更するストアの場合、再マッピングの影響を受ける仮想アドレスを使用する後続のロードでは、明示的なフラッシュなしで一貫して新しいマッピングが参照されることを意味します。

この洞察はヘンリー・ウォンの著書から得たもので、ページウォークの一貫性に関する優れた記事これを実現するために、競合または住所不明の店舗散歩中に遭遇する：

予期せぬことに、Intel Core 2 以降のシステムでは、ページテーブルの変更がなかったにもかかわらず、ページウォークの一貫性の誤った推測が発生したかのように動作しました。これらのシステムにはメモリ依存性の予測機能があるため、ロードはストアよりもずっと前に推測的に実行され、データ依存性のチェーンが切断されるはずです。

誤って検出された誤った推測の原因は、まさに初期実行の負荷であることが判明しました。これは、一貫性違反を検出する方法についてのヒントになります。つまり、ページウォークを既知の古いストアアドレス (ストアキュー内?) と比較し、競合または不明なアドレスを持つ古いストアがある場合は一貫性違反であると想定します。

これらのストアはページテーブルを変更しないという点では全く無害ですが、ページテーブル一貫性メカニズムに巻き込まれます。この理論のさらなる証拠は、イベントを見ることで見つけることができますdtlb_load_misses.miss_causes_a_walk。イベントとは異なりwalk_completed、これはすべてのウォークをカウントします。開始正常に完了しない場合でも、次のようになります (ここでも、2M はページウォークをまったく開始しないため表示されません)。

えっ！4K依存の番組二ウォークが開始されましたが、そのうち 1 つだけが正常に完了しました。つまり、ロードごとに 2 つのウォークが行われます。これは、反復 N+1 のロードのページウォークが開始されるが、反復 N のストアがストアバッファーにまだ残っている (反復 N のロードがそのアドレスを提供し、まだ進行中であるため) という理論と一致します。アドレスが不明であるため、Henry が説明したようにページウォークはキャンセルされます。それ以降のページウォークは、ストアアドレスが解決されるまで延期されます。結果として、ロード N+1 のページウォークはロード N の結果を待機する必要があるため、すべてのロードがシリアル化されて完了します。

「悪い」方法と「代替」方法が速い理由

最後に、謎が 1 つ残っています。上記では、元のハッシュアクセスが遅い理由は説明されていますが、他の 2 つが高速である理由は説明されていません。重要なのは、ロードによるデータ依存関係が投機的な制御依存関係に置き換えられているため、高速メソッドの両方にアドレス不明のストアがないことです。

アプローチの内部ループを見てみましょうinsert_bad。

for (size_t i = 0; i < bucket_size; ++i)
{
    if (i == B.size)
    {
        B.keys[i] = k;
        B.values[i] = 1;
        ++B.size;
        ++table_count;
        return;
    }
}

ストアはループインデックスを使用することに注意してください。インデックスがストアから取得される場合とiは異なり、は単にレジスタ内の計算された値です。insert_ok[B.size]ii関連しているロードされた値にB.size最終値が等しいそれに似ていますが、これは推測された制御依存関係である比較によって確立されます。ページウォークのキャンセルでは問題は発生しません。このシナリオでは、ループの終了が予測不可能であるため、予測ミスが多く発生しますが、大規模な領域の場合、これらは実際にはそれほど有害ではありません。これは、通常、不良パスは正常なパスと同じメモリアクセスを行うため (具体的には、挿入される次の値は常に同じ)、メモリアクセスの動作が優先されるためです。

同じことがケースにも当てはまりますalt。書き込むインデックスは、計算された値を使用してi値をロードし、それが特別なマーカー値であるかどうかを確認し、インデックスを使用してその場所に書き込むことによって確立されますi。この場合も、遅延ストアアドレスはなく、すばやく計算されたレジスタ値と推測された制御依存関係のみです。

他のハードウェアについて

質問者と同様に、Skylakeで効果を確認しましたが、Haswellでも同じ動作を確認しました。Ice Lakeでは再現できません。退去そして独立したほぼ同じパフォーマンスを発揮します。

しかし、ユーザーNoahは、タイガーレイクで繁殖できると報告した特定のアラインメントに対して元のベンチマークを使用します。最も可能性の高い原因は、TGL がこのページウォーク動作の影響を受けないことですが、一部のアラインメントではメモリの曖昧さ回避予測子が衝突し、非常によく似た効果が発生します。つまり、プロセッサがストアがロードに転送される可能性があると判断するため、ロードは以前のアドレス不明のストアより先に実行できません。

自分で実行する

上で説明したベンチマークを自分で実行することもできます。これはuarchベンチLinux (または WSL、ただしパフォーマンスカウンターは使用できません) では、次のコマンドを実行して結果を収集できます。

for s in 2M-dep 4K-dep 4K-indep; do ./uarch-bench --timer=perf --test-name="studies/memory/tlb-fencing/*$s" --extra-events=dtlb_load_misses.miss_causes_a_walk#walk_s,dtlb_load_misses.walk_completed#walk_c,l1d_pend_miss.pending#l1d_p,l1d_pend_miss.pending_cycles#l1d_pc; done

一部のシステムでは、使用可能な空きパフォーマンスカウンターが十分にない場合があるため (ハイパースレッディングが有効になっている場合)、毎回異なるカウンターセットを使用して 2 回実行することができます。

¹この場合、rdxは常にゼロ (領域全体がゼロで満たされている) なので、ストアアドレスは、このレジスタがアドレス指定式に含まれていない場合と同じになりますが、CPU はそれを認識しません。

²ここでは、200万デップケースも、4K独立ただし、その差はわずかです。

³「未処理のミスがある場合」という部分に注意してください。MLP をとして計算することもできます。l1d_pend_miss.pending / cyclesこれは、未処理のミスがあるかどうかに関係なく、一定期間の平均 MLP になります。それぞれ独自の方法で役立ちますが、ミスが常に未処理であるこのようなケースでは、ほぼ同じ値が得られます。

⁴はい、この例と元の例には多くの違いがあります。元のループではロード場所の近くに保存されますが、元のループではロード場所の近くに保存されます。ロード場所は反復ごとに変わります。1 ではなく 0 を保存します。B.size大きすぎるかどうかはチェックしません。テストでは、ロードされた値は常に 0 です。バケットがいっぱいになったときの検索ループはありません。アドレスにランダムな値をロードするのではなく、線形ストライドを実行します。ただし、これらは重要ではありません。どちらの場合でも同じ効果が発生し、この単純なケースに到達するまで複雑さを排除して元の例を段階的に変更できます。

Answer 1

まとめ

TLDRは、TLBのすべてのレベルを逃す（したがってページウォークを必要とする）ロードと、住所不明ストアは並列実行できない、つまりロードはシリアル化され、メモリレベルの並列処理（MLP）係数は1に制限されています。実質的に、店舗はフェンス負荷も同様lfenceです。

挿入関数の遅いバージョンではこのシナリオになりますが、他の 2 つではこのシナリオになりません (ストアアドレスが既知)。領域サイズが大きい場合、メモリアクセスパターンが支配的になり、パフォーマンスは MLP にほぼ直接関係します。高速バージョンでは、ロードミスが重複して MLP が約 3 になり、3 倍のスピードアップが実現します (以下で説明する狭い再現ケースでは、10倍Skylake の違い)。

根本的な理由は、Skylakeプロセッサがページテーブルの一貫性これは仕様では必須ではありませんが、ソフトウェアのバグを回避することができます。

詳細

興味のある方のために、何が起こっているのか詳細に掘り下げてみます。

私は Skylake i7-6700HQ マシンですぐに問題を再現することができ、余分な部分を取り除くことで、元のハッシュ挿入ベンチマークを次の単純なループに減らすことができましたが、同じ問題が発生します。

tlb_fencing:

    xor     eax, eax  ; the index pointer
    mov     r9 , [rsi + region.start]

    mov     r8 , [rsi + region.size]  
    sub     r8 , 200                   ; pointer to end of region (plus a bit of buffer)

    mov     r10, [rsi + region.size]
    sub     r10, 1 ; mask

    mov     rsi, r9   ; region start

.top:
    mov     rcx, rax
    and     rcx, r10        ; remap the index into the region via masking
    add     rcx, r9         ; make pointer p into the region
    mov     rdx, [rcx]      ; load 8 bytes at p, always zero
    xor     rcx, rcx        ; no-op
    mov     DWORD [rsi + rdx + 160], 0 ; store zero at p + 160 
    add     rax, (64 * 67)  ; advance a prime number of cache lines slightly larger than a page

    dec     rdi
    jnz     .top

    ret

^{これは、 4}B.sizeの最も内側のループのアクセス (ロード) とB.values[B.size] = 1アクセス (ストア)とほぼ同等です。insert_ok

ループに集中して、ストライドロードと固定ストアを実行します。次に、ロード位置をページサイズ（4 KiB）より少しだけ前方に移動します。重要なのは、ストアアドレスです。依存するロードの結果: アドレス指定式には、ロードされた値¹を保持するレジスタが[rsi + rdx + 160]含まれています。ループ内でアドレスコンポーネントは変更されないため、ストアは常に同じアドレスに対して行われます (したがって、常に L1 キャッシュヒットが予想されます)。rdx

元のハッシュの例では、より多くの作業が行われ、メモリにランダムにアクセスし、ロードと同じ行にストアが行われていましたが、この単純なループでも同じ効果が得られます。

我々はベンチマークの別のバージョンも使用します。これは、xor rcx, rcxロードとストアの間のno-opがに置き換えられていることを除いて同一ですxor rdx, rdx。休憩ロードアドレスとストアアドレス間の依存関係。

単純に考えれば、この依存関係が大きな効果をもたらすとは考えられません。ここにある店舗はファイアアンドフォーゲット:保存された場所から再度読み取ることはありません (少なくとも多くの反復では)。そのため、それらは継承される依存関係チェーンの一部ではありません。小さな領域の場合、ボトルネックは約 8 個の uop を処理することであり、大きな領域の場合、すべてのキャッシュミスを処理する時間が支配的になると予想されます。重要なのは、ロードアドレスは単純な非メモリ uop から独立して計算できるため、多くのミスが並列で処理されると予想されることです。

以下に、4 KiB から 256 MiB までの領域サイズについて、次の 3 つのバリエーションでサイクル単位のパフォーマンスを示します。

2M デップ:上記のループ（ストアアドレスはロードに依存）では、2 MiB の巨大ページ。

4K 解像度:上記のループ (ストアアドレスはロードに依存) は標準の 4 KiB ページです。

4K独立:上記のループのバリエーションですが、ロード結果とストアアドレス間の依存関係を断ち切るために 4 KiB ページを使用してxor rdx, rdx置き換えています。xor rcx, rcx

結果：

すべてのバリアントのパフォーマンスは、小さな領域サイズでは基本的に同じです。256 KiBまでのすべては、ループ内の8つのuopと、4 uops/サイクルのCPU幅少し計算してみると、MLP (メモリレベルの並列処理) が適切であることがわかります。L2 キャッシュヒットのレイテンシは 12 サイクルですが、2 サイクルごとに 1 つ完了するため、これを達成するには平均して 6 回の L1 ミスのレイテンシを重ねる必要があります。

256 KiB から 4096 KiB の間では、L3 ヒットが発生し始めるとパフォーマンスが多少低下しますが、パフォーマンスは良好で MLP は高くなります。

8196 KiBではパフォーマンスが著しく低下し、のみの4K 解像度150サイクルを超えて最終的に約220サイクルで安定します。10回他の2つのケースよりも遅い²。

すでにいくつかの重要な観察結果が示されています。

両方とも200万デップそしてその4K独立ケースは速いので、これはただストア間の依存関係だけでなく、ページングの動作についても説明します。
の200万デップこの場合は最も高速なので、メモリが不足している場合でも依存関係によって根本的な問題が発生しないことがわかります。
スローのパフォーマンス4K 解像度このケースは私のマシンのメモリ遅延と疑わしいほど似ています。

上記で MLP について説明し、観測されたパフォーマンスに基づいて MLP の下限を計算しましたが、Intel CPU では 2 つのパフォーマンスカウンターを使用して MLP を直接測定できます。

l1d_pend_miss.pending

未処理の L1D ミスの期間、つまり、デマンド読み取りに必要な未処理の Fill Buffers (FB) の各サイクル数をカウントします。

l1d_pend_miss.pending_cycles

L1Dロードのサイクル未処理のミス

最初のカウンタは、L1Dからの未処理のリクエスト数を毎サイクルカウントします。つまり、3つのミスが進行中の場合、このカウンタは毎サイクル3ずつ増加します。2番目のカウンタは、少なくとも毎サイクル1ずつ増加します。1つl1d_pend_miss.pending / l1d_pend_miss.pending_cyclesミスが進行中です。これは、サイクルごとに 1 で飽和する最初のカウンターのバージョンとして見ることができます。一定期間にわたるこれらのカウンターの比率は、ミスが未解決の場合の平均 MLP 係数³です。

MLP比率をプロットしてみましょう退去そして独立した4Kベンチマークのバージョン:

問題は非常に明確になります。4096 KiB の領域までは、パフォーマンスは同じで、MLP は高くなります (非常に小さな領域サイズでは、L1D ミスがまったくないため、MLP は「ありません」)。8192 KiB で突然、依存ケースの MLP は 1 に低下してそこに留まりますが、独立ケースでは MLP はほぼ 10 になります。これだけで、基本的に 10 倍のパフォーマンスの違いが説明できます。依存ケースでは、ロードをまったくオーバーラップできません。

なぜでしょうか? 問題は TLB ミスのようです。8192 KiB で何が起こるかというと、ベンチマークが TLB をミスし始めるからです。具体的には、各 Skylake コアには 1536 個の STLB (第 2 レベル TLB) エントリがあり、1536 × 4096 = 6 MiB の 4K ページをカバーできます。したがって、4 MiB と 8 MiB の領域サイズの間で、TLB ミスはに基づいて反復ごとに 1 になりdtlb_load_misses.walk_completed、このほぼ完璧すぎる偽物プロットにつながります。

つまり、次のようなことが起こります。アドレス不明のストアがストアバッファー内にある場合、STLB ミスが発生するロードは重複できません。一度に 1 つずつ実行されます。そのため、アクセスごとにメモリ全体の遅延が発生します。これは、2 MB ページのケースが高速だった理由も説明しています。2 MB ページは 3 GiB のメモリをカバーできるため、これらの領域サイズでは STLB ミス/ページウォークは発生しません。

なぜ

この動作は、Skylakeやその他の初期のIntelプロセッサが実装しているという事実に起因しているようです。ページテーブルの一貫性、x86 プラットフォームでは必須ではありませんが、ページテーブルの一貫性とは、たとえば、アドレスマッピングを変更するストアの場合、再マッピングの影響を受ける仮想アドレスを使用する後続のロードでは、明示的なフラッシュなしで一貫して新しいマッピングが参照されることを意味します。

この洞察はヘンリー・ウォンの著書から得たもので、ページウォークの一貫性に関する優れた記事これを実現するために、競合または住所不明の店舗散歩中に遭遇する：

予期せぬことに、Intel Core 2 以降のシステムでは、ページテーブルの変更がなかったにもかかわらず、ページウォークの一貫性の誤った推測が発生したかのように動作しました。これらのシステムにはメモリ依存性の予測機能があるため、ロードはストアよりもずっと前に推測的に実行され、データ依存性のチェーンが切断されるはずです。

誤って検出された誤った推測の原因は、まさに初期実行の負荷であることが判明しました。これは、一貫性違反を検出する方法についてのヒントになります。つまり、ページウォークを既知の古いストアアドレス (ストアキュー内?) と比較し、競合または不明なアドレスを持つ古いストアがある場合は一貫性違反であると想定します。

これらのストアはページテーブルを変更しないという点では全く無害ですが、ページテーブル一貫性メカニズムに巻き込まれます。この理論のさらなる証拠は、イベントを見ることで見つけることができますdtlb_load_misses.miss_causes_a_walk。イベントとは異なりwalk_completed、これはすべてのウォークをカウントします。開始正常に完了しない場合でも、次のようになります (ここでも、2M はページウォークをまったく開始しないため表示されません)。

えっ！4K依存の番組二ウォークが開始されましたが、そのうち 1 つだけが正常に完了しました。つまり、ロードごとに 2 つのウォークが行われます。これは、反復 N+1 のロードのページウォークが開始されるが、反復 N のストアがストアバッファーにまだ残っている (反復 N のロードがそのアドレスを提供し、まだ進行中であるため) という理論と一致します。アドレスが不明であるため、Henry が説明したようにページウォークはキャンセルされます。それ以降のページウォークは、ストアアドレスが解決されるまで延期されます。結果として、ロード N+1 のページウォークはロード N の結果を待機する必要があるため、すべてのロードがシリアル化されて完了します。

「悪い」方法と「代替」方法が速い理由

最後に、謎が 1 つ残っています。上記では、元のハッシュアクセスが遅い理由は説明されていますが、他の 2 つが高速である理由は説明されていません。重要なのは、ロードによるデータ依存関係が投機的な制御依存関係に置き換えられているため、高速メソッドの両方にアドレス不明のストアがないことです。

アプローチの内部ループを見てみましょうinsert_bad。

for (size_t i = 0; i < bucket_size; ++i)
{
    if (i == B.size)
    {
        B.keys[i] = k;
        B.values[i] = 1;
        ++B.size;
        ++table_count;
        return;
    }
}

ストアはループインデックスを使用することに注意してください。インデックスがストアから取得される場合とiは異なり、は単にレジスタ内の計算された値です。insert_ok[B.size]ii関連しているロードされた値にB.size最終値が等しいそれに似ていますが、これは推測された制御依存関係である比較によって確立されます。ページウォークのキャンセルでは問題は発生しません。このシナリオでは、ループの終了が予測不可能であるため、予測ミスが多く発生しますが、大規模な領域の場合、これらは実際にはそれほど有害ではありません。これは、通常、不良パスは正常なパスと同じメモリアクセスを行うため (具体的には、挿入される次の値は常に同じ)、メモリアクセスの動作が優先されるためです。

同じことがケースにも当てはまりますalt。書き込むインデックスは、計算された値を使用してi値をロードし、それが特別なマーカー値であるかどうかを確認し、インデックスを使用してその場所に書き込むことによって確立されますi。この場合も、遅延ストアアドレスはなく、すばやく計算されたレジスタ値と推測された制御依存関係のみです。

他のハードウェアについて

質問者と同様に、Skylakeで効果を確認しましたが、Haswellでも同じ動作を確認しました。Ice Lakeでは再現できません。退去そして独立したほぼ同じパフォーマンスを発揮します。

しかし、ユーザーNoahは、タイガーレイクで繁殖できると報告した特定のアラインメントに対して元のベンチマークを使用します。最も可能性の高い原因は、TGL がこのページウォーク動作の影響を受けないことですが、一部のアラインメントではメモリの曖昧さ回避予測子が衝突し、非常によく似た効果が発生します。つまり、プロセッサがストアがロードに転送される可能性があると判断するため、ロードは以前のアドレス不明のストアより先に実行できません。

自分で実行する

上で説明したベンチマークを自分で実行することもできます。これはuarchベンチLinux (または WSL、ただしパフォーマンスカウンターは使用できません) では、次のコマンドを実行して結果を収集できます。

for s in 2M-dep 4K-dep 4K-indep; do ./uarch-bench --timer=perf --test-name="studies/memory/tlb-fencing/*$s" --extra-events=dtlb_load_misses.miss_causes_a_walk#walk_s,dtlb_load_misses.walk_completed#walk_c,l1d_pend_miss.pending#l1d_p,l1d_pend_miss.pending_cycles#l1d_pc; done

一部のシステムでは、使用可能な空きパフォーマンスカウンターが十分にない場合があるため (ハイパースレッディングが有効になっている場合)、毎回異なるカウンターセットを使用して 2 回実行することができます。

¹この場合、rdxは常にゼロ (領域全体がゼロで満たされている) なので、ストアアドレスは、このレジスタがアドレス指定式に含まれていない場合と同じになりますが、CPU はそれを認識しません。

²ここでは、200万デップケースも、4K独立ただし、その差はわずかです。

³「未処理のミスがある場合」という部分に注意してください。MLP をとして計算することもできます。l1d_pend_miss.pending / cyclesこれは、未処理のミスがあるかどうかに関係なく、一定期間の平均 MLP になります。それぞれ独自の方法で役立ちますが、ミスが常に未処理であるこのようなケースでは、ほぼ同じ値が得られます。

⁴はい、この例と元の例には多くの違いがあります。元のループではロード場所の近くに保存されますが、元のループではロード場所の近くに保存されます。ロード場所は反復ごとに変わります。1 ではなく 0 を保存します。B.size大きすぎるかどうかはチェックしません。テストでは、ロードされた値は常に 0 です。バケットがいっぱいになったときの検索ループはありません。アドレスにランダムな値をロードするのではなく、線形ストライドを実行します。ただし、これらは重要ではありません。どちらの場合でも同じ効果が発生し、この単純なケースに到達するまで複雑さを排除して元の例を段階的に変更できます。

なぜ私の Intel Skylake / Kaby Lake CPU は、単純なハッシュテーブルの実装で不可解な 3 倍の速度低下を起こすのでしょうか? 質問する

ベストアンサー1

まとめ

詳細

なぜ

「悪い」方法と「代替」方法が速い理由

他のハードウェアについて

自分で実行する

おすすめ記事