12

CPU のキャッシュを利用するより良いコードを書く方法を学びたいです。連続したメモリで作業することは、理想的な状況のようです。そうは言っても、連続していないメモリで行うことができる同様の改善があるかどうか、私は興味がありますが、次のようなポインターの配列を使用します。

struct Position {
    int32_t x,y,z;
}
...
std::vector<Position*> posPointers;
...
updatePosition () {
    for (uint32_t i = 0; i < posPointers.size(); i++) {
        Position& nextPos = *posPointers[i];
        nextPos.x++;
        nextPos.y++;
        nextPos.z++;
    }
}

これは大まかなモックアップ コードにすぎません。これを適切に学習するために、すべての Position 構造体がヒープ全体でランダムに作成されたとだけ言っておきましょう。

Intel の i7 などの最新のスマートなプロセッサは、先を見越して、X_ptrすぐに のデータが必要になることを認識できますか? 次のコード行は役に立ちますか?

... // for loop
Position& nextPos1 = *posPointers[i];
Position& nextPos2 = *posPointers[i+1];
Position& nextPos3 = *posPointers[i+2];
Position& nextPos4 = *posPointers[i+3];
... // Work on data here

このようなコードがプロセッサに一部のデータをプリフェッチさせることを示しているように見えるプレゼンテーション スライドをいくつか読みました。本当？のようなプリフェッチを呼び出す非標準のプラットフォーム固有の方法があることは承知していますが__builtin_prefetch、それをいたるところに投げることは、醜い時期尚早の最適化のように思えます。無意識のうちにキャッシュ効率の良いコードを書く方法を探しています。

4

2 に答える 2

6

あなたが尋ねていないことは知っています (キャッシュの適切な扱いについての説教はおそらく必要ありませんが、とにかく私は 2 セントを寄付すると思いました. これはすべてホットコードにのみ適用されることに注意してください. 時期尚早の最適化は諸悪の根源。

コメントで指摘されているように、最善の方法は、実際のデータのコンテナーを用意することです。一般的に言えば、一部のデータを複製したり、データ構造のサイズ変更/移動/最適化に代償を払ったりする必要がある場合でも、「ポインタースパゲッティ」よりもフラットなデータ構造の方がはるかに適しています。

ご存知のように、フラットなデータ構造 (データの配列など) は、ほとんどの場合、直線的かつ連続的にアクセスする場合にのみ効果があります。

ただし、この戦略は常に使用できるとは限りません。実際の線形データの代わりに、プール アロケーターを採用したり、ポインターを保持するベクトルではなく、プール自体を反復処理したりするなど、他の戦略を使用できます。もちろん、これには独自の欠点があり、もう少し複雑になる可能性があります。

これはもうご存知だと思いますが、キャッシュを最大限に活用するための最も効果的な手法の 1 つは、データを小さくすることです。上記のコードで、 のint16_t代わりに を使用できる場合int32_tは、必ずそうする必要があります。多くの s とフラグと列挙型をビット フィールドにパックboolし、ポインターの代わりにインデックスを使用し (特に 64 ビット システムでは)、文字列の代わりにデータ構造で固定サイズのハッシュ値を使用するなどの必要があります。

さて、あなたの主な質問について、プロセッサがランダムなポインターをたどって、必要になる前にデータをキャッシュに入れることができるかどうかということです。非常に限られた範囲で、これは起こります。おそらくご存じのとおり、最新の CPU は速度を上げる (つまり、命令のリタイア率を上げる) ために多くのトリックを採用しています。ストア バッファー、アウトオブオーダー実行、スーパースカラー パイプライン、あらゆる種類の複数の機能ユニット、分岐などのトリックほとんどの場合、これらのトリックはすべて、CPU が命令を実行し続けるのを助けるだけです。、現在の命令が停止したり、終了するのに時間がかかりすぎたりしても。メモリ ロード (データがキャッシュにない場合は最も低速) の場合、これは、CPU ができるだけ早く命令に到達し、アドレスを計算し、メモリ コントローラーからデータを要求する必要があることを意味します。ただし、メモリ コントローラが保持できる未処理のリクエストの数は非常に限られています (最近は通常 2 つですが、よくわかりません)。ベクトルの要素posPointers) であり、これらがコードが必要とする新しいデータのアドレスであると推測すると、メモリ コントローラーが保留中の要求を非常に多くしか持てないため、コードはそれほど先に進むことができませんでした。

いずれにせよ、私の知る限り、CPUがまだ実際にそうしているとは思いません。ランダムに分散されたメモリ位置のアドレス自体がメモリ内にあるため (レジスタ内にある、またはレジスタの内容から計算可能であるのとは対照的に)、これは難しいケースであることに注意してください。とにかく、メモリインターフェイスの制限により、それだけの効果があります。

あなたが言及したプリフェッチ手法は私には有効であるように思われ、それが使用されているのを見てきましたが、将来のデータが到着するのを待っている間にCPUが何かをしている場合にのみ顕著な効果が得られます. 3 つの整数をインクリメントするのは、メモリから 12 バイトをロードする (実際には 1 つのキャッシュ ラインをロードする) よりもはるかに短い時間で済むため、実行時間にはあまり意味がありません。しかし、メモリ プリフェッチの上に重ねる価値のある、より重量のあるもの (たとえば、メモリからのデータを必要としない複雑な関数の計算!) があれば、非常に高速化される可能性があります。ご覧のとおり、上記のループを通過する時間は、基本的にすべてのキャッシュ ミスの時間の合計です。座標の増分とループの簿記を無料で取得しています。したがって、無料のものがもっと価値があれば、もっと勝っていただろう!

于 2013-03-02T18:42:57.983 に答える
4

最新のプロセッサにはハードウェア プリフェッチ メカニズムがあります: Intel ハードウェア プリフェッチャー。それらは、メモリへのストライド アクセス パターンを推測し、近い将来アクセスされる可能性が高いメモリ位置をプリフェッチします。

ただし、完全にランダムなポインタ追跡の場合、このような手法は役に立ちません。プロセッサは、実行中のプログラムがポインタ追跡を実行していることを認識しないため、それに応じてプリフェッチできません。このような場合、ハードウェア メカニズムは、使用される可能性が低い値をプリフェッチするため、パフォーマンスに悪影響を及ぼします。

最善の方法は、メモリの連続した部分にアクセスする可能性が高くなるように、メモリ内のデータ構造を整理することです。

于 2013-03-02T05:00:35.470 に答える