datchの日記

気がついたら社会人。気になる技術的なことについて少しずつ書いていけたらと思っております。

配列の一次元(リニア)化による高速化とその原理

今回は一次元配列による高速化の話。


主に画像処理をしており、研究室でも一次元化(以降、リニア化と呼称)を行った高速化が行われていた。


それじゃ、なんでリニアにすると実行速度が高速になるのか?


今回はその原理について話したいと思う。



結論から言えば、一次元化による高速化の原理は「CPUのキャッシュ」にある。


CPUは命令の実行段階になると必要なデータを取得しに行く。


参照順番として、


「CPU内【レジスタ→キャッシュ(L1,L2,L3)】→ CPU外【メモリ→仮想メモリ(HDD,外付けUSB,etc)】」
高速 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 低速
容量小 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 容量大


という順番で読みに行く。


ここで、キャッシュ内に必要なデータがない場合、それらをメモリからコピーする必要が出てくる訳だ。


もちろんCPU外のデータを引っ張ってくる為、余計な処理が増える。


このキャッシュ内に必要なデータが無い、という事象を減らせば自然と速くなるわけだ。



なんでリニアにすると速くなるかというと理由は簡単。


メモリからキャッシュ内にデータをコピーする際、ある程度の固まりでデータを取得する。


一次元(前者)と多次元(後者)の典型的な例として以下のふたつのコードを示す。


int* hoge;
hoge = new int[n * m];
hoge[a * m + b];


int** hoge;
hoge = new *int[n];
for(int i = 0; i < n; ++i)
{
    hoge[i] = new int[m];
}
hoge[a][b];




一見、アクセスの仕方は違う物のどちらもメモリ内にデータが密に確保されているように見えなくもない。


が、そんなことはない。


■(mサイズ分のメモリ領域)
□(確保されていないメモリ領域)


前者 @■■...............................■ n個分の■が密に確保されている


後者 @■□..□■□...□■□...□■□...□■ n個分の■が疎に確保されている



前者の場合は密に配置されているため、


hoge[0][m - 1]からhoge[1][0]にメモリ参照先が移っても、

hoge[0][0]にアクセスしたタイミングで移り変わり先のデータが固まりで取得されているので、


既にキャッシュ内にデータが存在しているためにコピーが発生しない。


が、後者は移り変わる時にコピーが発生する。


これがリニア化による高速化の正体です。



高速化を意識すると低レイヤーの知識が必要になるので結構大変ですね。



以上、リニア化による高速化についてでした。




追伸: 初めての「はてぶ」ですが書き方が分からない。あとでググる