[解決済み] キャッシュフレンドリーコードとは何ですか？

質問

とquotの違いは何ですか？ キャッシュフレンドリーコード "と、" キャッシュフレンドリー "コードは？

キャッシュ効率の良いコードを書くにはどうしたらいいですか？

どのように解決するのですか？

前置き

最近のコンピュータでは、最下位レベルのメモリ構造( レジスター は、1クロックサイクルでデータを移動させることができます。しかし、レジスタは非常に高価であり、ほとんどのコンピュータコアは数十個以下のレジスタしか持っていません。 もう一方のメモリは( DRAM )、メモリが非常に安い(つまり、文字通り 数百万倍安い しかし、データを受信するためには、リクエストの後、数百サイクルが必要です。 この「超高速で高価」と「超低速で安価」の間のギャップを埋めるのが キャッシュメモリ 速度とコストの順にL1、L2、L3と名付けられました。この考え方は、実行中のコードのほとんどは、小さな変数セットに頻繁にアクセスし、残りの変数（より大きな変数セット）には頻繁にアクセスしないというものです。プロセッサは、L1キャッシュでデータが見つからなければ、L2キャッシュを探します。それがなければL3キャッシュ、さらにそれがなければメインメモリを探す。これらの「ミス」の一つひとつが、時間的に高くつく。

(例えるなら、キャッシュメモリはシステムメモリに、システムメモリはハードディスクストレージに相当します。ハードディスクストレージは超安価ですが、非常に遅いです）。

の影響を軽減するための主な手法の1つがキャッシュです。 レイテンシー . Herb Sutterの言葉を借りると（下記リンク参照）。 帯域を広げるのは簡単ですが、レイテンシーを解決する方法は買えません。 .

データは常にメモリ階層（最小==最速から最遅まで）を通して取り出されます。A キャッシュヒット/ミス 通常、CPUの最上位キャッシュのヒット／ミスを指します。最上位というのは、最大＝最下位という意味です。キャッシュが外れるたびに RAM からデータを取得することになるため、キャッシュのヒット率はパフォーマンスにとって非常に重要です。 たくさん の時間（RAMなら数百サイクル、HDDなら数千万サイクル）を必要とします。それに比べ、（最上位）キャッシュからのデータ読み込みは通常、ほんの数サイクルしかかかりません。

現代のコンピュータ・アーキテクチャでは、パフォーマンスのボトルネックはCPUダイから離れることです（例：RAM以上にアクセスする）。これは時間の経過とともに悪化する一方です。プロセッサの周波数を上げることは、現在のところ、性能向上にはもはや関係がありません。 問題はメモリアクセスです。 そのため、現在、CPUのハードウェア設計では、キャッシュ、プリフェッチ、パイプライン、並行処理の最適化に大きな力を注いでいます。例えば、最近のCPUは、約85%をキャッシュに、最大99%をデータの保存・移動に費やしています。

このテーマについては、かなり多くのことが語られています。キャッシュ、メモリ階層、適切なプログラミングに関する素晴らしい参考文献をいくつかご紹介します。

• アグネル・フォッグのページ . 彼の優れたドキュメントでは、アセンブリからC++までの言語をカバーする詳細な例を見つけることができます。
• ビデオに興味があるなら、次のビデオを見ることを強くお勧めします。 ハーブ・サッターのマシン・アーキテクチャに関する講演 (ユーチューブ) (特に12:00以降をチェックしてください！）。
• メモリ最適化に関するスライド（Christer Ericson著 (ソニー技術担当ディレクター）
• LWN.netの記事 " プログラマが知っておくべきメモリに関する知識 "

キャッシュフレンドリーコードの主な考え方

キャッシュフレンドリーコードの非常に重要な側面は、以下のすべてです。 局所性の原則 これは、関連するデータをメモリ内の近くに配置して、効率的にキャッシュできるようにすることを目的としています。CPUキャッシュについては、キャッシュラインを意識して、この仕組みを理解することが重要です。 キャッシュラインはどのように機能するのですか？

キャッシュを最適化するためには、特に以下の点が重要です。

1. 時間的ロケール : あるメモリ位置にいつアクセスしたか、近い将来に再び同じ位置にアクセスする可能性が高い。理想的には、この情報はその時点でもキャッシュされていること。
2. 空間的な局所性 関連するデータを近くに配置することです。キャッシュはCPUだけでなく、さまざまなレベルで行われます。例えば、RAMから読み込む場合、通常、特に要求されたものよりも大きなメモリの塊がフェッチされます。これは、プログラムがそのデータをすぐに必要とすることが非常に多いからです。HDDのキャッシュも、同じような考え方です。特にCPUキャッシュの場合、以下のような考え方があります。 キャッシュライン が重要です。

適切なものを使用する c++ コンテナ

キャッシュフレンドリーかキャッシュアンフレンドリーかの簡単な例を示します。 c++ 's std::vector 対 std::list . の要素 std::vector は連続したメモリに格納されているので、それらにアクセスすることは だいぶ の要素にアクセスするよりも、よりキャッシュフレンドリーです。 std::list そのコンテンツがあちこちに保存されています。これは、空間的な局所性によるものです。

Bjarne Stroustrupは、このことを非常にうまく説明しています。 このYouTubeのクリップ (リンクしてくれたMohammad Ali Baydounに感謝します！）。

データ構造とアルゴリズム設計において、キャッシュを軽視してはいけない

可能な限り、キャッシュを最大限に活用できるようなデータ構造と計算順序を採用するようにします。この点でよく使われるテクニックは キャッシュブロッキング (Archive.org版) これは、ハイパフォーマンス・コンピューティングにおいて極めて重要なことです（例えば アトラス ).

データの暗黙的な構造を知り、利用する

もう一つの簡単な例として、この分野の多くの人が時々忘れてしまうのですが、column-major（例． フォートラン , マトラブ ) vs. 行頭順 (例. c , c++ ) を使って2次元の配列を格納することができます。例えば，次のような行列を考えてみましょう．

1 2
3 4

行メジャー順序の場合、これはメモリに 1 2 3 4 列順の場合は、次のように格納されます。 1 3 2 4 . この順序を利用しない実装は、すぐにキャッシュの問題（簡単に回避できる！）に直面することは容易に想像がつくでしょう。残念ながら、私は次のようなものを目にします。 非常に 私の専門分野（機械学習）ではよくあることです。この例については、@MatteoItalia さんの回答でより詳しく紹介されています。

行列のある要素をメモリからフェッチするとき、その近くの要素も同様にフェッチされ、キャッシュラインに格納されます。この順序を利用すれば、メモリアクセスが少なくなります（後続の計算に必要な次の数個の値がすでにキャッシュラインに格納されているからです）。

簡単のために、キャッシュは2つの行列要素を含むことができる1つのキャッシュラインから構成され、与えられた要素がメモリからフェッチされると、次の要素も同じであると仮定します。上の例の 2x2 行列の全要素の和を取りたいとします（これを M ):

順序を利用する（例：列のインデックスを最初に変更して c++ ):

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

順番を利用しない（例えば c++ ):

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

この単純な例では、順序性を利用することで実行速度が約2倍になります（メモリアクセスは総和の計算よりはるかに多くのサイクルを必要とするため）。実際のところ、この性能差は だいぶ より大きい。

予測不可能な分岐を避ける

最近のアーキテクチャはパイプラインを備えており、コンパイラはメモリアクセスによる遅延を最小にするためにコードを並べ替えることが得意になっています。クリティカルなコードに（予測不可能な）分岐が含まれていると、データのプリフェッチが困難または不可能になります。これは間接的にキャッシュミスを増やすことになります。

これについては 大変 をご覧ください（リンクを貼ってくださった@0x90さんに感謝します）。 なぜソートされた配列の処理は、ソートされていない配列の処理よりも速いのですか？

仮想関数を避ける

の文脈では c++ , virtual メソッドは、キャッシュミスに関して議論のある問題です (性能の観点から可能な限り避けるべきであるという一般的なコンセンサスが存在します)。仮想関数はルックアップの際にキャッシュミスを引き起こす可能性がありますが、これが起こるのは もし 特定の関数が頻繁に呼び出されるわけではない（そうでなければキャッシュされる可能性が高い）ので、これは問題ではないと考える人もいるようです。この問題についての参考は、以下をご覧ください。 C++のクラスで仮想メソッドを持つことによるパフォーマンス上のコストはどの程度ですか？

よくある問題

マルチプロセッサのキャッシュを持つ最近のアーキテクチャでよくある問題は、以下のようなものです。 フォールスシェアリング . これは、個々のプロセッサが別のメモリ領域のデータを使おうとして、それを同じ キャッシュライン . このため、他のプロセッサが使用できるデータを含むキャッシュラインは何度も上書きされることになります。事実上、異なるスレッドはこの状況でキャッシュミスを誘発することによって、お互いを待たせているのです。 参照(リンクをくれた@Mattに感謝)。 キャッシュラインサイズをいつ、どのように揃えるのか？

RAM メモリのキャッシュが不十分な場合の極端な症状として（この文脈ではおそらく意味しませんが）、いわゆる スラッシング . これは、プロセスがディスクアクセスを必要とするページフォルト（例えば、現在のページにないメモリにアクセスすること）を継続的に発生させる場合に起こります。