コードの実行効率の概要(3):キャッシュとローカル性

前の2つの文章では,プログラム性能の2つの側面を議論した.1つはアルゴリズム(一般化されたアルゴリズム,すなわち問題を解決する方法),2つはコンパイラである.この2つの側面を通じて、私が表現したいのは、プログラムの実行効率は、表面的な現象から結論を出すのは難しいということです.少なくともいくつかの簡単な面から、コードの長さなど、ほとんど問題を説明することは難しいということです.そのため、Profilingを行ってこそ、効果的な最適化ができます.今、私たちは2つのプログラムのアルゴリズムが基本的に同じで、コンパイラも簡単な「翻訳」を行うだけだと仮定して、それでは......私たちは「表面」から性能の高さを見ることができますか?
では、最も簡単な例から見てみましょう.仮にDoSomething AとDoSomething Bでやっていることが固定されているとしたら、次の2つの書き方のどちらが性能が良いと思いますか?

for (int i = 0; i < 100; i++)
{
    DoSomethingA();
    DoSomethingB();
}

for (int i = 0; i < 100; i++)
    DoSomethingA();

for (int i = 0; i < 100; i++)
    DoSomethingB();

この2つの論理のアルゴリズムは基本的に完全に同じであり、コンパイラが直接「翻訳」するだけで最適化されない場合、最初の方法はiの累積と条件ジャンプに対して比較的少ないため、「明らか」な最初のコードの実行効率が高いと結論する可能性があります.残念ながら、プログラムのパフォーマンスに影響を与えるもう一つの要因はキャッシュです.
キャッシュはどこにでもあります.CPUでは、最も性能の速い記憶装置が「レジスタ」であるが、レジスタの数は極めて限られていることが知られている.したがって,CPUはいずれもL 1 CacheとL 2 Cacheのマルチレベルキャッシュ機構を持つ.このうち、L 2 Cacheの性能はL 1 Cacheやレジスタよりも遅いが、メモリよりもずっと速い.あるCoreがメモリからデータを取得する必要がある場合、L 1 Cacheからデータを取得します.L 1 Cacheがない場合、複数のコアで共有されているL 2 Cacheから取得し、それ以上ない場合はメモリから取得します.オペレーティングシステムの仮想メモリメカニズムのため、ディスクの交換ページからデータを取得する可能性があります.この場合、パフォーマンスはかなり悪くなります.
レジスタは4バイトのような1文字長のデータしか使用しないが、L 1 CacheがL 2 Cacheからデータを取得する際には常に「1枚1枚」を取得する--このようなブロックは往々にして連続64バイトである.すなわち、CPUが1つのアドレスのデータを読み出した後、他のアドレスのデータを読み出すのは、L 1 Cacheにすでに存在するため、他のアドレスのデータよりも特に速い.1つのプログラムがCPUのこの特性を利用できれば、その性能は往々にしてよりよくなる(自然に他の多くの性能に影響を与える要素がある).
ローカル性(Locality)は,プログラムがキャッシュをうまく利用できるかどうかを記述するための名詞である.プログラムの局所性が優れているといえば,CPUのキャッシュメカニズムをよりよく利用できることを示す.ローカル性は「空間ローカル性」と「時間ローカル性」の2つに分けられ、前者は「1つのアドレスのデータをロードした後、その近くのデータをロードし続ける」ことを意味し、後者は「1つのアドレスのデータをロードした後、短時間でこのデータを再ロードする」ことを意味する.いずれにしても、高速キャッシュからホットデータをロードすることを目的としています.なぜ冷たい起動はいつも遅いのですか?なぜシステムが電源を入れてから走れば走るほど速くなると言われていますか?実は道理はあまり悪くない.
では、上の2つの方法の効率はどちらが高いのか、どちらが低いのかを判断することができます.1つ目のアプローチでは、iの累積回数と条件ジャンプの回数を減らすことができますが、1サイクルで2つのことを行い、DoSomethingBメソッドを実行すると、DoSomethingAメソッドでキャッシュに入ったばかりのデータが冷却され、次回DoSomethingAを実行するときに遅いストレージデバイスからデータが再ロードされる可能性があります.第2のアプローチでは、DoSomething AまたはDoSomething Bの呼び出しを100回「密」に実行しましたが、この間の大量のデータアクセスはL 1 Cacheに集中しており、パフォーマンスの優位性は言うまでもありません.
私の以前の文章《コンピュータのアーキテクチャとプログラムの性能》は第1部の中で局部性がプログラムの性能に対する影響も討論して、もっと具体的に話して、あなたもその中の内容を参考にすることができます.
プログラム命令は実行効率の唯一の要因ではないため,コードの長さからプログラム性能を判断することも非常に頼りにならない.もちろん、どのような独立した観点から性能を判断しても適切ではない可能性があります.例えば、その文章では、プログラムの性能を考慮するためにグローバル変数を使用すべきだと述べています.もちろん、著者もこれは良い設計ではないと考えています.実際には、私たちのさっきの例では、1つのサイクルで複数のことをしても再構築する価値があるかもしれません.グローバル変数を使用すると、push、popなどのコマンドのオーバーヘッドが確実に節約されますが、このようなグローバル変数は、スタックのどこかに格納されている静的変数などです.ローカルな実践ではありません.これに対して、L 1 Cacheの役割により、呼び出しスタック上で「パラメータ」または「ローカル変数」にアクセスするのはアクセスレジスタよりもそれほど遅くないため、push、popのいくつかの命令のオーバーヘッドは大したことではない可能性がある.ましてや、コンパイラ/ランタイムにこの方法が内蔵されていると、push、popなどの命令も現れません.
この前、ある友达が私のブログで「急進的」な言い方を発表したのを覚えています.例えば、「底辺を学ぶのは.NETプログラムを書くのに役に立たないだけです.それを知っていても、C#はアセンブリを埋め込むことができませんから」.私はこの言い方に同意しません.NETプログラムは、コンピュータアーキテクチャの法則に合致して実行されており、実行時のコードの表現をある程度理解することができます.
現在話している「局所性」について言えば、私たちは多くのものを把握することができます.たとえば、各スレッドの呼び出しスタックはデフォルトで1メガサイズであることがわかります.したがって、2つのスレッド呼び出しスタックのデータは同じCacheエントリにほとんど表示されません.また、例えば、「時間的局所性」のため、最近使用するデータがキャッシュに最も出現する可能性が高いため、NET 4.0のパラレル・ライブラリは、プライベート・キューのタスクをスケジュールするときに、新しく作成したタスクを実行する傾向があります.たとえば、一連の座標のx値とy値を表すために2つのint配列を使用しますか、struct Point配列を構築して保存しますか.2つのint配列を使用するとメモリが節約されますが、ローカル性から問題を考えると、同じ座標のx値とy値が一緒に保存されているほうが適切かもしれません.
私のこれらの文章は,コード表面からプログラム性能を判断する「不確実性」を強調している.同様に、アセンブリコード(断片)を目の前に置いても、パフォーマンスの違いを「見る」ことは難しい場合があります.これはProfilingの重要性を側面から説明しています:コードを読むのは静的で、プログラムの実行とProfilingはすべて動的です.前に友達から「最近プロファイラーにハマってるの?」実は私のここのProfilingは一般的に“1種のプログラムの性能の方式を探求します”を指して、ある特定の手段を指すのではありませんて、更にある具体的なツールではありません——でもVSのProfilerを使うのに関わらず、やはり自分で1つのCodeTimerをして、すべて“コードを読みます”より頼りになります.
関連記事

コードの実行効率について簡単に説明する(1):アルゴリズムはキー

である.

コードの実行効率(2):コンパイラの威力

コードの実行効率(3):キャッシュとローカル

コードの実行効率について簡単に説明する(4):アセンブリ最適化