配列の一次元(リニア)化による高速化とその原理
今回は一次元配列による高速化の話。
主に画像処理をしており、研究室でも一次元化(以降、リニア化と呼称)を行った高速化が行われていた。
それじゃ、なんでリニアにすると実行速度が高速になるのか?
今回はその原理について話したいと思う。
結論から言えば、一次元化による高速化の原理は「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]にアクセスしたタイミングで移り変わり先のデータが固まりで取得されているので、
既にキャッシュ内にデータが存在しているためにコピーが発生しない。
が、後者は移り変わる時にコピーが発生する。
これがリニア化による高速化の正体です。
高速化を意識すると低レイヤーの知識が必要になるので結構大変ですね。
以上、リニア化による高速化についてでした。
追伸: 初めての「はてぶ」ですが書き方が分からない。あとでググる。