うなぎのタレで学ぶキャッシュ

うなぎのタレで学ぶキャッシュ @Msprzk #3 低レイヤーズさっぽろ

自己紹介 名前 : 宮本直幸 X: @Msprzk 所属: 北海道情報大学 趣味: ゲーム配信を見たりする

きっかけ

空間局所性とは あるデータにアクセスした直後に、その近くのデータにアクセスする 傾向のこと。 キャッシュでは、この性質を利用して、近くのデータを先にキャッシ ュに読み込んでおく。

これって、うなぎのタレとうなぎの関係に 似ているよね？

例としてCの2次元配列を考える Cの多次元配列はメモリ上の連続した領域に格納される。 Cでは、配列の要素は行優先（row-major order）で格納され る。 つまり、同じ行の要素が連続してメモリに配置される。

int[][] array = {...}; // は配列の長さだと仮定 十分に大きな2次元配列 // N for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { // [i][j] } } にアクセスする for (j = 0; j < N; j++) { for (i = 0; i < N; i++) { // [i][j] } } にアクセスする

まとめ 空間局所性は、近くのデータにアクセスする傾向のこと。 うなぎのタレとうなぎの関係に似ている。 Cの2次元配列の行優先配置により、行優先のアクセスパターン は空間局所性を活かせる。 列優先のアクセスパターンは空間局所性を活かせず、キャッシ ュミスが増える。