稼ぐ電子工作

趣味の電子工作をするために電子工作で稼ぐブログ。

組み込みC高速化 最適化促進

前回はソフトウェアの設計で高速化できないか検討しました。

pkeisrebpys.hatenablog.com

今回はコードの記述を改め,最適化に使える情報をコンパイラに提供することで, 最適化を促進して演算時間を短縮します。

ループ最適化

何度も処理が繰り返されるループは最適化の効果が出やすいので, コンパイラはあらゆる手を尽くしてくれます。 ただし,最適化に使える情報をコードで与えるのは処理の目的を知っている人間の仕事です。 (時々,よかれと思って加えた情報がむしろ最適化を邪魔する場合があるので注意。)

  • ループ回数を固定にする
  • ループ回数は可変だが工夫する
  • ループ回数の条件を与える

ループ回数を固定する

以下のコードでは何らかの軽い処理 some_process をループ内で実行しています。 x[i] を読みこんで y[i] に処理結果を入れています。 ここではコンパイラはインライン関数に対応していると仮定しています。 some_process がループカウンタ i を変更することはなく, このループは入力を変えながら some_processn 回実行することがわかります。

static inline int some_process(int x);
extern int n;
extern int x[];
extern int y[];
int i;
for (i = 0; i < n, i++) {
  y[i] = some_process(x[i]);
}

問題の n は外部参照でありコンパイラが知らないどこか別の場所で変更されるようです。 n == 0 で一度も実行されないループかも知れないし, n はとんでもなく大きく,何度もループするかも知れません。 x, y もサイズが与えられていないのでどこまでアクセスされるのか不明です。

コンパイラはしかたなくループの度に条件判定をして, 次の処理を行うべきか確認します。

extern int n で可変の値をループ回数にするのではなく, マクロなどで定数 N を定義し,n の代わりにループ回数とした場合はどうでしょうか。 Nコンパイル時点で確定している定数なので, コンパイラはこのループが確実に N 回実行できると認識して最適化してくれるかもしれません。 ループ展開してもいいくらいの回数だったら勝手に展開してくれるかも知れないし, 展開するには回数が多すぎる場合も条件判定回数を減らしてくれるかもしれません。 実行する処理を確定できるのでより効果的なパイプライン処理を組んでくれるかもしれません。

問題はもともとは可変回数だったループをどうやって定数回数のループにするかです。 たとえば n は 0 から 64 までの範囲で変化し, n == 64 でも演算時間オーバーしてはいけない条件だったとします。 i 回目の処理では y[i] を求める処理をしているとします。 出力 y[i] は入力 x[i] にのみ依存し, x[i] がどんな値であってもとりあえず例外を発生せずに y[i] がえられるとします。 そして y[i] 自体は外部出力ではなく,メモリ上の変数で, i >= n である不使用の領域にゴミを書いても他の処理に影響を与えないとします。

こんな条件があるなら必要に応じて n を変えるよりも, とりあえず最大数の N 回処理して,あとから不要な y[i] は捨ててしまう (あとの処理で使わない) ようにできます。 n が小さいときは無駄な処理を行っていますが, nN に近い時はコンパイラの最適化が効いて速くなる可能性があります。

ループ回数は可変だが工夫する

そうはいってもすべてのループを固定回数にはできません。 内部処理であれば,処理内容を調整して不使用部分の処理を無駄にやっても, 他の処理に影響がでないようにできル可能性があります。 外部入出力の場合は,不使用範囲までアクセスすると, 応答が返ってこないとか,誤動作するとか不具合がでる可能性が高いです。

全体としてはループ回数を固定にできない場合も, なんとか一部だけでもループ回数を固定にできないか検討します。

例えば 0 から 64 までのループ回数の可能性がありますが, 実はほとんどの場合は 32 回以上実行するというのであれば, 32 回の固定回数ループと32回未満のループに分ける手があります。

i = 0;
while (i + 32 <= n) {
  int j;
  for (j = 0; j < 32; j++) {
    y[i+j] = some_process(x[i+j]);
  }
  i += 32;
}
while (i < n) {
  y[i] = some_process(x[i]);
  i++;
}

こうすると 32 回未満の場合は可変回数のループを回り, 32 回以上の場合は 32 回固定でやったあと,残りを可変回数のループで処理できます。 なるべく固定回数で最適化されたループを回る割合を増やします。

32回未満のループも 8 回とか 4 回とかの固定回数ループで回してから, 残りを可変回数ループで回す手があります。 (コンパイラによっては最適化がうまくかかる最小限の固定回数ループと可変回数ループに勝手にやってくれ, コード上なにもしなくても良いかもしれません。)

ループ回数の条件を与える

ループ回数は必ず 2 の倍数になるなどの条件を与えると, CPU やデータバスの構成を考慮してコンパイラが最適化してくれる場合があります。 CPU のマニュアルを読むとどんな条件で最適化が可能か書いてあったりします。

メモリアクセス削減

グローバル変数のアクセスを最小限にする

何度も同じグローバル変数を読みに行く記述はやめてローカル変数にコピーします。 そんなことをしなくても, 「関数処理中で書き換えていないなら,グローバル変数書き換わらないでしょ」 とコンパイラが最適化して一度だけレジスタにコピーしてくれていたりします。

最適化のためにコピーするというよりは, 人間が最適化がかかっているのを忘れて, 「毎回変数を読みに行っているはずだから, 外部入力の変更反映されるよね」 といった勘違いをしないために,グローバル変数のアクセスは最小限になる記述にしておきます。

1回のループでアクセスする変数を増やしすぎない

条件分岐判定を減らそうと,1回のループに処理をつめこんで, 多くの変数を使用すると,レジスタに乗り切らない場合があります。 ループの最初に読んだ変数がループの最後ではレジスタから消えていて, 次のループでもう一度読まないといけなくなります。 いくらメモリキャッシュがあって高速になっていたとしても, アクセス速度でレジスタには勝てません。

キャッシュミスを減らす

メモリにキャッシュがついている場合は, キャッシュミスを減らすと無駄な待ち時間が減ります。

キャッシュミスを減らす基本方針としては時間的に近くで読み書きする変数を, メモリ上も近くに配置します。 ただし,キャッシュの構成によって,より結果がよくなる配置が変わります。

多次元配列へのアクセスの場合もメモリ上で連続している方向にアクセスするように構成します。

static inline int some_process(int x);
extern int x[M][N];
extern int y[M][N];
int i;
for (i = 0; i < M; i++) {
  int j;
  for (j = 0; j < N; j++) {
    y[i][j] = some_process(x[i][j]);
  }
}

for 文の順序を入れ替えると,メモリ上を N*sizeof(int) byte ずつ飛びながらアクセスすることになり, キャッシュがうまく働かない場合があります。