プログラミングをしていると、あるいはバックジョンの問題を解いていると、よく二重for文、あるいはそれ以上のネストされた反復文を使わなければならないことがありますが、この時、二重for文をうまく使えないとコードが100倍近く遅くなることがあります。これはC++だけの問題ではなく、全てのプログラミングに適用される話です。
| 100倍以上遅いネストされた反復文
// 1番の方法
for (std::size_t i = 0; i < N; ++i) {
for (std::size_t j = 0; j < M; ++j) {
arr[i][j] *= 2；
}
}
// 2番目の方法
for (std::size_t i = 0; i < M; ++i) {
for (std::size_t j = 0; j < N; ++j) {
arr[j][i] *= 2；
}
}
上のコードを見ると、同じ役割をする二重のfor文がありますが、どちらが正しい方法か考えてみましょう。 1番か2番か、それとも両方か？ 結論から言うと、正しい方法は1番で、ロジックが同じだと仮定すると、1番の方法が2番の方法よりほとんどの状況で(事実上、無条件で)速くなります。
結論を先に言うと、繰り返し文はarr[i][j][k]がある時、右から左方向、つまり、k -> j -> iの順番で回る方が(ループ文の内側に位置する方が)速く、できるだけそう回るように設計しなければなりません。
| 理由
結論だけ知っていればいいのですが、なぜこれが遅いのかについて理由を知るためには少しコンピュータの構造についての知識が必要です。また、予備知識として、基本的にベクターがメモリ上でどのように割り当てられるかについて知っていることを前提とします。
コンピュータの構造とキャッシュメモリの限界
コンピュータの基本的な構成要素を説明する部分なので、この部分について知っていれば、そのまま進めても大丈夫です。
コンピュータの構造
コンピュータの構造を説明する時、中央処理装置(CPU)、主記憶装置(RAM)、補助記憶装置(SSDまたはHDD)で構成されていると言う。CPU、RAM、補助記憶装置で構成されるこの構造は、すべてのコンピュータが共通して持っている基本的な構造である。この構造を設計した人の名前からフォン・ノイマン構造(中央処理装置、記憶装置、プログラム)と呼ぶ。
CPUは演算機械である。与えられた入力とデータに基づいて命令を実行し、数学的な演算を処理する。そのほか、メモリを割り当てて解釈することもCPUの役割である。ちなみに、前者はALU(Arithmetic Logical Unit)、後者はCU(Control Unit)と呼ばれるが、ここでは重要ではない。
RAMは周期記憶装置である。CPUが演算するために必要なデータを保存する。
補助記憶装置はデータを永続的に保存するときに使う。
なぜわざわざ主記憶装置と補助記憶装置を分離したかというと、これは経済的な観点からの問題点である。速度の問題だが、主記憶装置の方がはるかに速い。補助記憶装置の速度にはかなわない。
HDDの速度が200-400MB/sで比較にならないし、通常SSDの書き込み速度が3.5GB/sだとしよう。実際、SATA時代だけでもSSDの読み取り速度は500MB/s程度だった。 ところで、3.5GB/sは非常に速く見えるが、これをRAMのクロックで計算してみると約218MHz程度になる。ちなみに、市販されているDRAMのクロック速度は通常3500-4000MHz程度である。
逆にDRAMの速度をGB/sに変換してみると25.6GB/sが出る。次元が違う速度だ。通常、最も速いNVMe SSDの速度が7GB/sであることを考慮しても、異次元の速度であることが分かります。
この計算はおおよその値であり、実際にはMHzとMB/sは直接的に変換される関係ではないので、正確な値ではありません。
そのため、周期記憶装置は電源を切るとデータが揮発するという欠点にもかかわらず使用するのである。そのため、CPUがすぐに必要としないデータは補助記憶装置に保管し、すぐに演算に必要なデータをRAMから要求する。
キャッシュメモリ
しかし実際には、CPUの飛躍的な発展とその演算速度により、DRAMだけではCPUの演算速度に追いつくことができなくなった。そこで、ボトルネックを防ぐために、DRAMよりも高速なSRAMというものをCPU内部に置く。このSRAMがキャッシュメモリである。
ところが、SRAMがDRAMよりずっと速くて良いのですが、欠点は価格がとても高いです。だから、RAMのように8GB、16GBのように置くことができない。せいぜい64kb、500kb程度のサイズしかない。
実際、キャッシュメモリ内でも、その速度の違いによってL1、L2、L3などのキャッシュで階層を分けている。L1キャッシュが最も速く、そのため最も高価であり、容量も最も少ない。私のWindowsノートパソコンは64kbサイズです。L3は実はないノートパソコンもありますが、私のノートパソコンでは500kbくらいの大きさです。
つまり、画像で表すと下の図のようになります。
レジスタはあのL1キャッシュからメモリを読み込みます。
問題は、この時、レジスタが一度に読み込めるメモリの量に限界がある。したがって、レジスタは少量のメモリチャンク単位でのみメモリを読み出し、もしCUが必要なメモリ(アドレス)がメモリチャンクがない場合、レジスタはそのメモリチャンクをL1で探して再読み込みする。もし、L1に探したいメモリがなければ、L2、L2でもなければ、L3、RAM... まで下りながらメモリを探します。 だから、キャッシュフレンドリーなプログラムを作るためには、できるだけ同じメモリチャンクブロック内でメモリを読むことができるようにする必要があります。
正しい二重for文、間違った二重for文
std::vector<std::vector<int> > arr；
上のような二次元配列(ベクトル)arrを考えてみましょう。STLは形が少し複雑でわかりにくいですが、C-スタイルで書くとint arr[M][N] と似ています。ただ、2次元配列は少し話が違うので、まずベクトルで説明します。
これを図で表現すると
のような形で表現することができます。
// 1番の方法
for (std::size_t i = 0; i < N; ++i) {
for (std::size_t j = 0; j < M; ++j) {
arr[i][j] *= 2；
}
}
先ほどの1番方式のメモリアクセス構造を図で表してみましょう。
すると、とても自然な形でアクセスしていることが分かります。実際、レジスタが一度に赤いブロック分だけメモリチャンクを読むことができると仮定すると、0の後に1,2があるメモリ位置を読むには、同じチャンク内で読めばいいのです。そして、赤いチャンクを離れても、次のメモリを読むのに物理的に遠い距離はありません。
一方、2番方式を図で表現してみましょう。
内側の反復文は青い方向に回っていますが、キャッシュメモリの観点から見ると、かなり不自然な方法で回っていることが分かります。レジスタは赤いメモリ領域を読んでいますが、反復文が要求する次のメモリアドレスは、レジスタが読んでいる領域からかなり離れています。こうなると、新しいメモリを読み込むたびに、CPUはL1キャッシュからそのメモリがある場所にメモリチャンクを読み直さなければならず、それだけ非効率的なI/O時間が発生し、性能低下が起きています。1番方式に比べ、チャンクを毎回移動しなければならないので、どれだけ非効率的なのかが分かります。
実際の性能測定
これが実際どの程度影響があるのか簡単にテストしてみましょう。
#include <chrono>
#include <iostream>
#include <thread>
#include <vector>
void fn1(const std::size_t size) {
const size_t N = size;
const size_t M = size;
std::vector<std::vector<int>> arr(N, std::vector<int>(M, 0));
auto start = std::chrono::system_clock::now();
for (std::size_t i = 0; i < N; i++) {
for (std::size_t j = 0; j < M; j++) {
arr[i][j] = i + j;
arr[i][j] *= 2;
}
}
auto end = std::chrono::system_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "fn1 : " << diff.count() << std::endl;
}
void fn2(const std::size_t size) {
const size_t N = size;
const size_t M = size;
std::vector<std::vector<int>> arr(N, std::vector<int>(M, 0));
auto start = std::chrono::system_clock::now();
for (std::size_t j = 0; j < M; j++) {
for (std::size_t i = 0; i < N; i++) {
arr[i][j] = i + j;
arr[i][j] *= 2;
}
}
auto end = std::chrono::system_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "fn2 : " << diff.count() << std::endl;
}
int main(void) {
constexpr std::size_t size = 20000;
std::jthread t1(fn1, size);
std::jthread t2(fn2, size);
return 0;
}
約2万 * 2万のinteger配列をそれぞれ生成して、実行時間を計測してみましょう。関数fn1は1番方式(正しい方式)、fn2は2番方式(間違った方式)で回っています。反復文の内側から外側へのドーニャの違い以外、ロジックは同じです。実行時間を測定するためにchronoを使用しました。
結果です：
etc-image-5
fn1 : 1.86167
fn2 : 4.38487
秒単位なので大したことないと思うかもしれませんが、なんと42%の差です。実際は、この関数が非常に頻繁に呼び出され、内部で複雑な演算と反復が行われているとしたら？ このようなロジックなのに、単純に繰り返し文の繰り返し順序だけでも性能差が結構発生することが分かります。
だから、反復文を回す時たくさん呼び出される反復文(内側にある反復文)は可能であれば、キャッシュフレンドリーなメモリ構造にするのがいいです。
スタック上の2次元配列の場合
int arr[SIZE][SIZE]；
std::array< <std::array<int>, SIZE>, SIZE> arr2；
上記のように配列が生成される場合も似ていますが、少し違います。実際、ヒープの上に割り当てられるベクトルとは違って、上のようにC-styleやstd::arrayを使ってスタックの上に静的な配列として宣言した場合、2次元のように表現はされますが、実際はコンパイラが1次元の配列を生成してくれるからです。だから、ベクトルのようにそこまでダイナミックな性能差が発生することはありません(基本的にスタック上の配列は最大サイズもずっと小さいので)。
それでも、メモリ上物理的にarr[1][N]とarr[2][N]は距離がNだけ離れていて、arr[N][1], arr[N][2]は物理的な距離が1だけ離れているので、これも性能差が発生するので、ベクトルと同じように右から左方向に繰り返し文を回すのがいいです。
実際は
実際、CVなどの画像処理をする場合、通常は以下のように画像が構成されています。
image[color][x][y]...
for i in range(color)：
for j in range(x)：
for k in range(y)：
# どのような演算
その理由は状況によって異なりますが、通常は色をチャンネルごとに分けて、その内側で(x, y)の演算を行うことが多いからです。 そのため、色は繰り返し文でよく変わらないので、一番外側のループで回し、よく変わるx, yをループの内側で回すのが一般的です。
直接実装することはないかもしれませんが、内部構造がなぜこのような構造なのか気になるなら、このような理由があります。
まとめ
覚えておきましょう！
arr[0][N] ~ arr[1][N] # -> 距離 N
arr[N][0] - arr[N][1] # -> 間隔 1
結論として、繰り返し文を回る時は右から左に移動するように、つまり、一番多く呼び出される内側の繰り返し文にメモリ的に近い要素を配置するのが良いです。意外と性能差が大きく出るので、覚えておきましょう。実は暗記する必要もなく、ベクトルがどのように割り当てられるのか、そしてコンピュータの構造とCPUがどのように動作するのかという軽い知識さえあれば、どのように反復文を回すのが良いか思い浮かべることができるでしょう。