組み込みにおけるCプログラムの速度最適化

最近は組み込み用CPUにも色々と高度な機能が付くようになったおかげで、
よほどそのCPUに熟知している人を除けば、自分でアセンブラを書くより
コンパイラに最適化を任せた方が早くなる事が増えてきたと思います。

と言う事で、僕が知っている組み込みソフトウェアの
最適化の定石やノウハウをまとめていきたいと思います。

wikipediaの最適化の項目が結構充実しているので、
こちらから目を通すと良いかも知れません。
https://ja.wikipedia.org/wiki/最適化_(情報工学)

## 前置き

ここでは速度の最適化のみを取り扱います。
サイズの最適化についてはスコープ外なので悪しからず。

基本的にARM向けの記述が多いです。
ARMについては以下を見ると良さそうです。
[[アセンブラ] ARMの仕様を見てみる](http://qiita.com/edo_m18/items/a7c747c5bed600dca977) 

アセンブラの出力例は以下のコンパイラがデフォルト設定で出力したものを使っています。
arm-none-eabi-gcc.exe (GNU Tools for ARM Embedded Processors) 5.4.1 20160919 (release) [ARM/embedded-5-branch revision 240496]

# 最適化の定石

一般的に言って、こんなところではないでしょうか。

## 1.性能を測定できる所まで保守性重視で実装する

この段階では保守性を最優先で進めた方が良いです。
高凝集・低結合で変化に強いコードを書きましょう。

https://ja.wikipedia.org/wiki/結合度
https://ja.wikipedia.org/wiki/凝集度

## 2.性能を測定してボトルネックを探し出す

まずはボトルネックがどこにあるのかを探します。
これをしないと、性能に全く影響しない所を延々と最適化してしまったりします。

なお、CPUによっては性能測定のための機能があったりします。
ARMだとパフォーマンスモニタが便利です。
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0363fj/Bgbfdfgh.html
あとはETMなんてのもあります。

## 3.大域最適化を行う

ボトルネックの修正のためには大きな設計変更が必要かも知れません。
この時に保守性の低いコードを書いていたりすると悲惨な目に遭います。

## 4.局所最適化を行う

関数単位の局所的な最適化を行います。
ここで得られる効果は微々たるものという事が多いのではないでしょうか。

# 最適化テクニック

## 関数をinline化する

常套手段ですね。
良く言われるのが関数の呼び出しコストです。

そのほかにもコンパイラによる最適化の自由度が上がるため、
処理の順番を変えてパイプラインハザードを解消してくれる時もあります。
https://ja.wikipedia.org/wiki/パイプライン処理

なお、「処理速度のため」と非常に長い関数を書く人も居ますが、
inline化で代替できるケースは多いです。

## constを付けられる変数にはconstを付けてみる

(追記)
.rodataのデフォルト配置先が低速なメモリになっている場合、
単純にconstを付けると逆に遅くなる可能性もあります。
@st1011 さんご指摘ありがとうございました。

constもコンパイラへの最適化のヒントとなりパイプラインハザードが無くなる場合があります。
有識者にとっては意外でもなかったりするのかもしれません。

## 空間的局所性の高いアクセスには構造体を使う

(追記)
最近のコンパイラは頭が良いので、構造体を使わずとも
オフセット付きロード/ストアにしてくれるようです。
@fujitanozomu さん検証して頂きありがとうございました。

構造体を使えば、オフセット付きロード/ストア命令によって高速化できる可能性があります。
0x40001000とその隣0x40001004を4Byteずつ取ってくる処理を考えます。

```c
#include <stdint.h>

uint32_t get_temperature(void){
    uint32_t *alpha = (uint32_t *)0x40001000;
    uint32_t *bravo = (uint32_t *)0x40001004;
    return *alpha + *bravo;
}
```

これのコンパイル結果はこのようになるはずです(レジスタ名はARMのものを使用)。
1. r2に0x40001000をセット
2. r2のアドレスの値をr0にロード
3. r2の値を+4
4. r2のアドレスの値をr1にロード
5. r0にr0とr1の和を入れる

構造体を使う場合、コードはこうなると思います。

```c
#include <stdint.h>

struct temperature{
    uint32_t alpha;
    uint32_t bravo;
};

uint32_t get_temperature(void){
    struct temperature *temperature = (struct temperature *)0x40001000;
    return temperature->alpha + temperature->bravo;
}
```
これのコンパイル結果は以下の様になります。
1. r2に0x40001000をセット
2. r2のアドレスの値をr0にロード
3. r2+4のアドレスの値をr1にロード
4. r0にr0とr1の和を入れる

Bravoにオフセット付きロードが使える分、1命令減ります。

## constなローカルの配列変数をスタックにコピーしたくない場合、宣言にstaticを付ける

~~この現象は原因が良く分からないのですが、以下のような配列変数がある場合~~

以下の様に関数内にconstなローカル配列変数があった場合、

```c
#include <stdint.h>
uint32_t read_const_table(uint32_t select)
{
    const uint32_t someTable[] = {0,1,2,3};
    return someTable[select];
}
```

以下の様に、配列の中身を初期化用のrodata領域から一度全て
スタックにコピーした後、そこから値を取りだすコードが出力されます。
(コメントでの指摘どおり、これは自体は言語規格通りの動作でした)。

```
mov	ip, r0
str	lr, [sp, #-4]!
ldr	r3, .L3
sub	sp, sp, #20
ldmia	r3, {r0, r1, r2, r3}
add	lr, sp, #16
stmdb	lr, {r0, r1, r2, r3}
add	ip, lr, ip, lsl #2
ldr	r0, [ip, #-16]
add	sp, sp, #20
ldr	lr, [sp], #4
bx	lr
```

この例ではコンパイラの最適化によって、スタックを介さずに初期化用のrodata領域から
直接r0に格納できそうな気もしますが、どうやらやってくれない様です（？）。

対策としては配列変数をcostからstatic constにします。

```c
#include <stdint.h>
uint32_t read_const_table(uint32_t select)
{
    static const uint32_t someTable[] = {0,1,2,3};
    return someTable[select];
}
```

こうすれば、スタックへのコピーを介さず直に読みだしてくれます。

```
ldr    r3, .L2
ldr    r0, [r3, r0, asl #2]
bx     lr
```

## コンパイラ付属のライブラリを使う

ガリガリに最適化されたライブラリが入っていることが多いので
車輪の再発明をせず素直につかってしまいましょう。

ただし、変なsection指定attributeが付いている事があるので要注意です。
僕は昔これで痛い目にあいました。
Linkerの出力から見かけないオブジェクトが変な所に配置されてないか確認しましょう。

## 既に確立されたアルゴリズムを使う

「実はこれってただのソートじゃないか」などと気づく事はありませんか。
高速に処理できるアルゴリズムが既にあるなら、それを採用しましょう。

## コンパイラの最適化オプションを変える

僕は割と最近までは知らなかったのですが、コンパイラの-O2と言ったものは
個別の最適化オプションの組み合わせでできています。

参照：
https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Options

これを変えるとぐっと高速になるかもしれません。
ただし、今まで最適化がかかって無かったために隠れていた
バグが表面化する事もあります。

## CPUの仕様書をじっくり読み込む

色々書きましたが、結局はこれが一番重要です。

パイプラインの段数によってパイプラインハザードをどの程度恐れる必要があるか変わりますし、
フォワーディング機能があればデータハザードは気にしなくて良いでしょう。

むしろ、早いコードの書き方がそのものズバリで書いてあったりします。

# アンチパターン

## 8bit,16bitのローカル変数を使ってしまう

32bit CPUを使う前提で書きます。

基本的に32bit CPUは32bit演算しかできません。
(64bit演算もできるものはあったりしますが)

では8bit,16bit変数の演算はどうなるかと言うと、
32bitで演算した結果に対して0xFF (8bit) / 0xFFFF (16bit)の
ビットマスクを掛けるので、その分遅くなります。

スタックの消費量の観点でも、スタックエントリはCPUの
レジスタサイズと同じというケースが多く、この場合8bit,16bit変数も
32bitでスタックに積まれます。

## register指定子を使ってしまう

これはコンパイラによる最適化の自由度を下げるので避けた方が良いです。
僕の経験からすると、むしろ遅くなる場合が多いです。

## 最初の実装で最適化してしまう

一般的に、プログラムの実行時間の80%は20%のコードが占有すると言われています。
僕が昔携わった製品では5%のコードが95%の実行時間を使っていました。

そのため、せっかく手間暇かけて最適化しても、プロダクトの性能に影響しなかったりします。
また、この段階で行える最適化となると局所最適化ですが、これによって保守性を下げてしまうと
大域最適化の障壁になり、目標性能を達成できなかったという事になりかねません。

## 命令数が減ったから早くなったと判断してしまう

逆アセンブラにかければ、その関数の命令数が分かります。
https://ja.wikipedia.org/wiki/逆アセンブラ

確かに命令数が減ったならその分早くなるケースは多いです。
しかし、パイプラインハザードを考えると、必ずしもそうとは言えません。
実行サイクル数を図ってみると逆に増えているケースもあります。

# まとめ

長々と最適化のテクニックについて書いていきましたが、
結局、保守性や可読性の高い素直で普通なコードを書いていれば、
大した話ではありません。

何か分かりづらい事や、あるいは間違っている点があれば気軽にコメントしてください。