私は基本的なデータ構造について学んでおり、これまでリンクされていないリストを展開しています。私は、各ブロックの要素の数を最大で1つのキャッシュラインのサイズにすると、改善されたメモリのローカリティからより良いキャッシュパフォーマンスを得ることができると私は言います。私はこれについて2つの質問があります。展開されたリンクリストの最適なブロックサイズ
まず、キャッシュラインのサイズに正確にするのが最適か、分割できない小さなサイズですか？
第2に、L1/2/3キャッシュの行サイズが64バイトであることが、thisのポストに見つかりました。私はこれがすべてのモデルi7用であることを確認したかったのですか？私は2014年中頃のMBPを持っていて、私のシステムに最適なアンロールされたリンクリストを作成しようとしています。キャッシュラインサイズを確認するターミナルコマンドはありますか？
アンロールされたリンクリスト内のノードの要素はすべて、非常に高速にアクセスされます。。
キャッシュされた行のバイトはすべて非常に高速にアクセスされます。
ここでの類推を見ることができます。リンクされていないリンクリストは、アイテムをメモリの連続領域に圧縮して、よりキャッシュフレンドリであるようにします。
ノード・サイズをキャッシュ・ラインより大きくするのがなぜ問題になるかを知るには、サイズが1行のキャッシュ（任意の結合性）を持つアーキテクチャを考えてみましょう。S。
ノードサイズがの展開されていないリンクリストも2Sと考えてください。
最後に、ノードの算術平均にノード内の各項目の値を設定するアルゴリズム
For each node N
Let avg = ArithmeticMean(N.items)
For i = 0 To N.numerOfItems - 1
N.items[i] = avg
のキャッシュミスを（完全なノードを想定）を分析することができます。
平均を計算するには、すべての要素を合計する必要があります。最初の要素にアクセスすると、キャッシュ・ロード（+1）がトリガーされます。最初の半分の中で、要素はロードされたばかりのキャッシュラインから読み込まれます。
後半の最初の要素がアクセスされると、別のキャッシュロードが必要になり、古い行がフラッシュされます（+2）。ノードの終わりまで、この第2のロードはすべての将来のアクセスを満たす。
平均値を取得すると、最初の半分に再びキャッシュ負荷（+3）でアクセスし、後半でもう一度すぐに再ロードされる行（+4）を削除します。
このアルゴリズムは、ノードに対して4つのキャッシュ負荷をトリガします。 ノードのサイズをSにして分析を繰り返すと、キャッシュの負荷だけが必要であることがわかります。
ノードをキャッシュ行より小さくすると、一部のノードが同じ行を共有することがありますが、一般的には害はありません。 しかし、これはリスト内の要素の総数と各行がそれ自身のアドレスにあり、必ずしも互いに接近しているわけではないので、より多くの行を使用します。 S = 1の場合、通常のリンクリストがあります。
これまでにないすべてのインテルCPUは、64バイトのキャッシュラインを持っています。
これは非常によく変更することができます。
CPUキャッシュ情報を表示するには、この質問を参照してください。finding L2 cache size in Linux
sudo dmidecode -t cacheを使用します。
おかげアレイは、ランダムアクセスを可能にする要素を格納するために使用されているという事実。
すべてのキャッシュレベルinfact。