プログラムで行列にアクセスする際はアクセス順序を気をつけないといけない話

はじめに

自社開発のエンジニアをやっているものです。
Web開発で２次元配列を全件処理をする機会はそれほどないかもしれないのですが、競技プログラミング等の数理計算？を処理する際にはよく使うと思います。
その際何気なく1行目から順に最終行まで辿るようにアクセスすると思うのですが、1列目~最終列まで処理しても差分はないのかという題材でこの記事を書いていこうと思います。

結論

早速結論ですが基本的には行ごとにアクセスした方が処理速度が早くなるようです。
ただ全てのプログラミング言語がそのような動きにはなっていないようで、MATLABやpythonのnumpyライブラリ等は列毎に処理をした方が早くなるようです。
今回は例としてgo言語で行基準、列基準の速度を見ていきたいと思います。

行毎にアクセスした場合

// 行ごとに行列に値を格納する
func inputMatrix(matrix [][]int) {
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			matrix[i][j] = 1
		}
	}
}

func main() {
	// 10000x10000の行列を作成
	matrix := make([][]int, 10000)
	for i := 0; i < len(matrix); i++ {
		matrix[i] = make([]int, 10000)
	}

	start := time.Now()
	inputMatrix(matrix)

	// 処理時間を計測
	elapsed := time.Since(start)
	elapsedMilli := elapsed.Milliseconds()
	println("実行時間:",elapsedMilli,"ms")
}  

% go run ファイル名
実行時間: 224 ms

列毎にアクセスした場合

// 列ごとに行列に値を格納する
func inputMatrix(matrix [][]int) {
  for i := 0; i < len(matrix); i++ {
    for j := 0; j < len(matrix[i]); j++ {
      matrix[j][i] = 1
		}
	}
}

func main() {
  // 10000x10000の行列を作成
	matrix := make([][]int, 10000)
	for i := 0; i < len(matrix); i++ {
    matrix[i] = make([]int, 10000)
	}

	start := time.Now()
	inputMatrix(matrix)

	// 処理時間を計測
	elapsed := time.Since(start)
	elapsedMilli := elapsed.Milliseconds()
	println("実行時間:",elapsedMilli,"ms")
}

    % go run ファイル名
    実行時間: 866 ms

結果

行毎にアクセスした場合は224msでしたが、列毎にアクセスした場合は866msと約3.8倍ほどに差が出る結果となりました。
どうしてこのような結果になってしまうのか説明しようと思います。

処理速度に差が出る理由

配列を生成した時のメモリ内の配置

イメージとして、5*5の二次元配列を生成した場合に1行1列目、1行2列目、1行2列目・・・5行5列目という順番で配置がされているみたいです。

アドレス1	アドレス2	アドレス3	アドレス4	アドレス5	アドレス6	アドレス7	アドレス8	アドレス9	アドレス10
matlix[0][0]	matlix[0][1]	matlix[0][2]	matlix[0][3]	matlix[0][4]	matlix[1][0]	matlix[1][1]	matlix[1][2]	matlix[1][3]	matlix[1][4]

配列へのアクセスの動き

プログラムが配列にアクセスする場合はまずキャッシュ(I/O速度がより速い)にあるか確認して、ある場合はキャッシュから、なければメモリからアクセスする動きになっているようです。

そして、メモリからアクセスした場合は付近のアドレスもごっそりキャッシュに一時保存をする動きになっているようです。
ですので、matlix[0][0]を取得した際はその付近（例としてmatlix[0][0]~matlix[0][4]）をキャッシュに保存されると次からその範囲の値を取得するときにはキャッシュから取得できるようになります。逆にその範囲外の値を取得しようとすると、メモリから取得するという動きになってしまうので前者よりも速度が劣ってしまいます。

以上のことから行毎でアクセスすると都度キャッシュから取得できる動きになるのに対して、列毎でアクセスするとメモリから取得する動きになり実行速度に差が出るということに繋がってしまいます。

まとめ

言語によって、２次元配列のアクセス方法に気をつけなければいけないことがわかりました。
特に意識する必要はないと思いますが、ハードウェアに近い仕組みを理解することは知識定着を高めてくれると考えているのでこれからも追求し続けていこうと思いました。