地道に解決していくためのパフォーマンスチューニング講座　Vol.3　～演算の改善～

2024年8月15日 19:24

入れ替えただけで！？

システムツー・ワンのテクニカルシステムエンジニアの「じょん（日本人）」です。前回に引き続きパフォーマンスチューニングのお話です。他の回と比べるとぱっとはしないかもしれませんが、シミュレーションや座標計算などで何千何万回と処理をする場合には馬鹿にならないお話です。

そんな本稿、パフォーマンスチューニング講座第3回のテーマは「演算の改善」。

ちょっと復習

パフォーマンスに影響する機器にはこんなのがありました。

何かを処理するときには基本的に主記憶装置（いわゆるメモリ）、キャッシュ、CPUがデータをやり取りしながら処理が進む。

演算とは

本稿ではCPU内での処理の他に、主記憶装置やキャッシュへの読み書きも含めて演算処理と呼ぶ。これはI/Oや通信と比べるとかなり速く、数回程度では差が出づらい。しかし、あからさまに遅くないが故に気が付きづらい遅さの原因になることもある。

演算の実行時間の内訳

細かい処理は置いといて、ざっくり描くとこんな感じ。

レジスタなどCPU内にもつデータ領域は一旦無視すると、CPUはキャッシュにあればキャッシュから、なければ主記憶からデータを取得するような動きをする。

データの取り出し

キャッシュヒット率

取り出し時にはなるべくキャッシュからデータを取得できるようにすると速くなる。キャッシュにデータがあり、主記憶までアクセスする必要がない場合の割合をキャッシュヒット率という。キャッシュヒット率を上げることが重要であり、配列のアクセス方法などに気を付ける必要がある。

例えば下記コードを考える。

final int M = 10000;
final int N = 10000;

int sum = 0;
for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
		sum += values[j][i];
	}
}

※本講座はJavaを用いて例示しています。言語による違いに注意してください。

この処理にかかる時間は1,720msec.である。計1億回も足し算しているとはいえ、高々足し算に少し時間がかかりすぎな印象は受けないだろうか。

この処理は2文字変えるだけで処理時間が約1/40になる。そのコードが下記である。

final int M = 10000;
final int N = 10000;

int sum = 0;
for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
		sum += values[i][j];
	}
}
System.out.println(sum);

違いに気が付くだろうか。ただ、values[j][i]をvalues[i][j]にしただけである。これだけで、処理時間は44msec.となる。
これはJavaの配列のメモリ上の配置がvalues[0][0], values[0][1], …, values[1][0], values[1][1], …のように、右の添え字が先行して回るような形となっているためである。言語仕様によるため、他の言語の場合にどちらが速いのかはよく確認する必要がある。

データの配置箇所

public static void main(String[] args) {
	final int MAX = 1000000000;
	Test test = new Test();

	// 狭いスコープ
	int a = 0;
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			a = i + j;
		}
	}

	// 広いスコープ
	int b = 0;
	int i, j;
	for (i = 0; i < MAX; i++) {
		for (j = 0; j < MAX; j++) {
			b = i + j;
		}
	}
	
	test.run();
	
	Test.staticRun();
}

class Test {
	int i, j;
	static int si, sj;
	
	public void run() {
		final int MAX = 1000000000;

		int a;
		// インスタンス変数
		for (i = 0; i < MAX; i++) {
			for (j = 0; j < MAX; j++) {
				a = i + j;
			}
		}
	}
	
	public static void staticRun() {
		final int MAX = 1000000000;

		int a;
		// static変数
		for (si = 0; si < MAX; si++) {
			for (sj = 0; sj < MAX; sj++) {
				a = si + sj;
			}
		}
	}
	
}

狭いスコープ：4msec.
広いスコープ：4msec.
インスタンス変数：76msec.
static変数：51msec.

ここで注目すべきは、ローカル変数へのアクセスが速いことである。これはヒープ領域よりスタック領域へのアクセスのほうが一般に速いためである。static変数がインスタンス変数より速いのはデータの保存領域やアクセス方法の違いによるものかと思われる。とはいえ、速さを求めるためにstatic変数のようなスコープの広い変数を使うのは、保守性に欠け、そもそも設計を見直したほうが良いと考える。

CPU上での処理

CPU上での処理においては、考えるパターンは多岐にわたる。私的には下記を考えれば大体は問題ないと思っている。

処理の回数
- 処理の回数は減らせないか。
処理の重さ
- 同じことをするにも演算子や関数の違い、使い方次第で処理速度が速くなるもの、方法が無いか。
アルゴリズム
- そもそもアルゴリズムが適切なのか。
値の使いまわし
- 使いまわせる値を何度も計算、生成していないか。

総じて言えるのは、知り、考え、「想像しないで」実測することが大切である。「ここは正しい、ここは関係ない」という思い込みが一番の敵である。

以下に幾つかの速度差が出るパターンを例示する。

演算子による違い

final int MAX = 100000000;
int tmp = 0;

// 足し算
for (int i = 0; i < MAX; i++) {
	tmp = i + i;
}
// 引き算
for (int i = 0; i < MAX; i++) {
	tmp = i - i;
}
// 掛け算
for (int i = 0; i < MAX; i++) {
	tmp = i * i;
}
// 割り算
for (int i = 0; i < MAX; i++) {
	tmp = i / i;
}

足し算：1msec.
引き算：2msec.
掛け算：2msec.
割り算：16msec.

不思議に思うかもしれないが、割り算のひっ算をイメージしてもらえれば、割り算だけ計算量が多くなる理由は何となく納得するのではないだろうか。

固定小数点数と浮動小数点数

final int MAX = 100000000;
int nTmp = 0;
double rTmp = 0.0;

// int
for (int i = 1; i <= MAX; i++) {
	nTmp = i + i;
}

// double
for (double i = 1; i <= MAX; i++) {
	rTmp = i + i;
}

int：2msec.
double：26msec.

もはや誤差だが、浮動小数点のほうが遅い。これらの選択は速度差よりも、doubleに伴う誤差などを考慮するほうが適切な考えであろうかと思う。
※intとlongではintのほうが速いなど、値型同士でも差が出るので興味があったら調べてみてください。

適切な処理の使用

final long MAX = 100000;

// pow
for (long x = 0; x < MAX; x++) {
	for (long y = 0; y < MAX; y++) {
		Math.pow(Math.pow(x, 2) + Math.pow(y, 2), 1.0 / 2.0);
	}
}

// sqrt
for (long x = 0; x < MAX; x++) {
	for (long y = 0; y < MAX; y++) {
		double r = Math.sqrt(x * x + y * y);
	}
}

pow：18494msec.
sqrt：5msec.

これは明確に差があり、気を付けるべき事項である。2乗や1/2乗（√）などの簡易なものにはpowを使うべきではない。
※1.3乗などを計算する場合は仕方がないです。

コレクションの違い

final static int MAX = 10000000;

Integer array[] = new Integer[MAX];
List<Integer> list = new ArrayList<Integer>();
Map<Integer, Integer> map = new HashMap<Integer, Integer>();

int a;
for (int idx = 0; idx < MAX; idx++) {
	a = array[idx];
	a = list.get(idx);
	a = map.get(idx);
}

array：183msec.
list：213msec.
map：349msec.

普通に添え字で参照するのであれば、通常の配列が最速である。

String name;
for (int idx = 0; idx < MAX; idx++) {
	for (Model model: array) {
		if (model.id == idx) {
			name = model.name;
			break;
		}
	}
	for (Model model: list) {
		if (model.id == idx) {
			name = model.name;
			break;
		}
	}
	name = map.get(idx).name;
}

array：8614msec.
list：21645msec.
map：9msec.

打って変わって、引き当て処理は連想配列の得意とする処理である。

データの書き込み

ここでのデータの書き込みはキャッシュやメモリにデータを書き込むことである。とはいえ多くはデータの取り出しと共通している。本項では書き込み特有の処理としてメモリ割り当てに言及する。

変数を宣言する、インスタンスを生成するなど主記憶上にデータ領域を確保する処理（メモリ割り当て）は、単に読み書きするよりも時間のかかる処理である。

最も単純な対策は、インスタンスの生成回数をむやみに増やさないことである。
※とはいえ、保守性の問題から、むやみにインスタンスを使いまわすべきでもない。

下記は配列の生成を1回にしてforで値をリセットする処理と、配列を生成しなおすことで値をリセットする処理である。

final int MAX = 100000;

// forで値をリセット
int a[] = new int[MAX];
for (int i = 0; i < MAX; i++) {
	for (int j = 0; j < MAX; j++) {
		a[j] = 0;
	}
	for (int j = 0; j < MAX; j++) {
		a[j] = j;
	}
}

// 生成しなおすことで値をリセット
int b[];
for (int i = 0; i < MAX; i++) {
	b = new int[MAX];
	for (int j = 0; j < MAX; j++) {
		b[j] = j;
	}
}

forで値をリセット：4804msec.
生成しなおすことで値をリセット：6544msec.

余計なループがある分forで値をリセットするほうが遅くなるように思えるかもしれないが、それを上回るほどメモリ割り当ては遅い処理である。
一般にメモリ割り当ての回数は減らすべきだが、コンストラクタの処理次第では入れ替わるかもしれないので、時間を気にする処理では時間を測って様子を見るしかない。

最後に

演算の改善の観点では様々なことに気を配る必要があるが、一つ一つ知識として頭の片隅においておけば最悪な事態は避けられるかもしれない。ここで教えられるよりも、自分で書いて試してみるほうが実感がわくと思うので、ぜひ自分でも試してみてほしい。次回は非同期や並列化に触れていく予定である。

地道に解決していくためのパフォーマンスチューニング講座 Vol.3 ～演算の改善～