コンパイラ最適化の種類をいくつか知っておくと、冗長的なコードの記述を回避できたり、余計で無意味なパフォーマンスチューニングをしなくても済むようになります。これを機会にコンパイラ最適化のバリエーションを把握しておきましょう。
コンパイラ最適化への理解は、可読性の高いコードを重視する志向にも繋がります。コンパイラのためのコードではなく、プログラマのためのコードが書けるようになります。コンパイラ最適化はプログラマの教養と言うべきものです。
目次
- 定数畳み込み、定数伝播(定数式の事前計算)
- 冗長性の除去、共通部分式除去(計算結果の再利用)
- コードの置き換え(同等の処理に置き換える)
- ループ展開、ループ反転、ループ転置
- デッドコード削除(使われない処理を除去)
- インライン展開(関数内の処理を展開)
- インライン展開と更なる最適化
- 再帰呼び出し除去(再帰を繰り返し文に置き換える)
- goto文への置き換え
- 後置インクリメントの値更新タイミング
- 繰り返し文 条件式の最適化
プログラミング言語やコンパイラの種類、最適化レベル等によって最適化の結果は異なります。過信はしないようにしましょう。
定数畳み込み、定数伝播
定数値からなる式は事前に計算されます。(定数畳み込み)
// Before
int value = 1 + 1;
// After
int value = 2;
// Before
int SECONDS_PER_HOUR = 60 * 60;
int SECONDS_PER_DAY = 60 * 60 * 24;
// After
int SECONDS_PER_HOUR = 3600; // 1時間は3600秒
int SECONDS_PER_DAY = 86400;
既存の定数値も置き換えの対象になります。(定数伝播)
int SECONDS_PER_WEEK = SECONDS_PER_DAY * 7;
↓
int SECONDS_PER_WEEK = 60 * 60 * 24 * 7;
↓
int SECONDS_PER_WEEK = 3600 * 168;
↓
int SECONDS_PER_WEEK = 604800;
上記の例のように、定数畳み込みと定数伝播は同時に行われることがあります(この過程で更なる最適化が適用される場合もあります)。
質の良いコンパイラでは、関数の呼び出しの結果をコンパイル時計算してくれる場合もあります。
size_t length = strlen("abc");
↓
size_t length = 3;
ちなみに、C++言語にはこのコンパイル時計算を実現するための仕組みが言語機能として取り込まれています。
constexpr int sum(int a, int b) { return a + b; }
constexpr int c = sum(1, 2);
// const int c = 3; と同等
冗長性の除去、共通部分式除去
主に計算結果の再利用を目的としています。
冗長的なコードや副作用の無い単純な処理は、計算結果の再利用が行われる場合があります。(冗長性の除去)
// Before
int r = (i * 2) + (i * 2) + (i * 2);
// After
int V = (i * 2); // キャッシュ
int r = V + V + V; // 再利用
もっとも上記の例であれば、次のような最適化が行われる場合もあります。
int r = (i * 2) + (i * 2) + (i * 2);
↓
int r = (i * 2) * 3;
↓
int r = i * 6;
複数の箇所で共通の式が用いられている場合にも再利用が行われます。(共通部分式除去)
// Before
int x = a * b + c;
int y = a * b - c;
// After
int z = a * b;
int x = z + c;
int y = z - c;
コードの置き換え
非効率な処理は、より効率的な処理に置き換わる場合があります。
// Before
printf("\n");
printf("Shop %d\n", 99);
printf("%c", '9');
// After
puts("");
puts("Shop 99");
putchar('9');
処理の結果は変わりませんが、より低レベルで効率的な関数に置き換わっています。
ループ展開、ループ反転、ループ転置
ループの回数が明確かつ小さな繰り返し文は、インライン化される場合があります。(ループ展開)
for (int i = 0; i < 2; i++)
printf("%d", i);
以下のように、各ループ毎の処理が展開されます。
printf("%d", 0);
printf("%d", 1);
また上記のコードは、先程「# コードの置き換え」で紹介した最適化と組み合わさって、さらなる置き換えが行われます。
printf("%d", 0);
printf("%d", 1);
↓
printf("0");
printf("1");
↓
putchar('0');
putchar('1');
ループの回数が極端に多くなる場合は、実行ファイルサイズの肥大化を招くため、ループ展開は行われません。
なお、カウンタを参照しないループ文の場合であれば、以下のような最適化が働くケースもあります。(ループ反転)
for (int i = 0; i <= 99; i++) puts("hello");
↓
for (int i = 100; i != 0; --i) puts("hello");
これにより実行時のステップ数が軽減される場合があります。ただし、この辺の最適化は処理系によって程度や内容も異なるため過信はできません。
またwhile文相当の繰り返し処理がdo while文相当の繰り返し処理に置き換わることもあります。(ループ転置)
int i = 0;
while (i++ < 9) {
printf(".");
}
↓
int i = 0;
do {
printf(".");
} while (i++ < 8);
これによって初回のループで生じる条件判定のオーバーヘッドが回避されます。
副作用を伴う処理が記述された場合には、初回の条件判定が付加されるため複雑な処理になりますが、CPU側での高速化の恩恵が得られる場合があります。
int i = argc;
if (i < 9) {
do {
printf("%d", i);
} while (i++ < 8);
}
デッドコード削除
あからさまに実行されることが無いような処理は、実行ファイルに含まれること無く、消えてなくなります。(デッドコード削除)
到達不能コード/デッドコードの例
// 警告: Code will never be executed
if (false) puts("i was here"); // 消える
goto label;
if (false) label: puts("here i am"); // 普通は消えない
int v = 9;
if (v != 9) puts("私はここにいない"); // 普通に消える
int fn() {
do {
break;
puts("what you see"); // 消える
} while (false);
return 0;
return isdigit('9'); // 消える
}
/* */ int a = 1;
/* */ int b = 2;
volatile int c = 3; // volatileで最適化を抑制
while (a != 10) {
printf("%d", a);
a++; // 消えない
b++; // 消える
c++; // 消えない
}
struct { const char* s; int size; } str = {"ab", 2};
if (str.size != 2) puts("1"); // 大抵は消える
str.size = strlen(str.s);
if (str.size != 2) puts("2"); // 消えることがある
以下の最適化は関数のインライン展開と共に働く事があります。
inline void f(bool b) {
if (b) puts("a");
puts("b");
}
f(false); // `if (b)`の判定処理は省略される事が多い
関数のインライン展開については次項以降に紹介します。
中でも以下の最適化は意外と便利で気に入っています。リファクタリングも効くのでコメントやプリプロセッサよりもスマートに扱えます。このケースでは到達不能コードに対する警告はされません。
#ifdef DEBUG
bool isDebug = true;
#else
bool isDebug = false;
#endif
if (isDebug) {
// リリースビルド時に消えることが多い
puts("password"); // ただし、パスワードを扱っているため過信は禁物
}
同様に、以下のような記述についてもコンパイラ側の警告は発生しません。なかなか面白い気の利かせ方です。中の人御用達のテクニックだったりするのかもしれません。
return 0;
return isdigit('9'); // 消える
インライン展開
関数内部の処理が関数の呼び出し箇所に展開されます。(インライン展開)
// インライン関数
inline void print(int i) { printf("%d" i); }
// Before
int main() {
print(99);
}
// After
int main() {
printf("%d" 99); // print関数の処理が展開された
}
これによって関数呼び出しによるオーバロードが回避され、より高速な処理が実現されます。
関数定義時にinline
キーワードを指定することで、コンパイラ側にインライン展開を促す事ができます。ただしinlineを指定してもインライン化が行われない場合もあります。逆にinlineを指定していない関数であっても、インライン展開が行われる場合があります。
コンパイラによっては__attribute__((always_inline))
という属性機能を利用することで、関数のインライン化を強制することもできます。ただし、関数のインライン化によって逆に処理効率が悪くなるケースもあるため、インライン関数の強制は無闇に行うべきではありません。
インライン展開と更なる最適化
インライン展開後の処理に対しても「# デッドコード削除」が働くことがあります。
inline void f(bool b) {
if (b) puts("a"); else puts("b");
}
f(true);
↓
if (true) puts("a"); else puts("b");
↓
puts("a");
f(false);
↓
if (false) puts("a"); else puts("b");
↓
puts("b");
この組み合わせによる最適化は、冗長的なコードを回避する上で非常に重要な最適化となっています。
この最適化によって、例えば以下のようなコードが躊躇なく書けるようになります。
inline void c(bool flag) {
puts("begin");
if (flag) puts("a"); else puts("b");
puts("end");
}
void a() { c(true); }
void b() { c(false); }
コンパイラ最適化によってインライン展開が働くと、a
とb
の関数はそれぞれ以下のように展開されます。
void a() {
puts("begin");
puts("a");
puts("end");
}
void b() {
puts("begin");
puts("b");
puts("end");
}
オーバーヘッドの無い理想的なコードに変化しました。このような展開後のコードは、冗長的で保守性も悪くなるため、実際の人間が書くべきではありませんが、コンパイラによるインライン展開とデッドコード削除の最適化を活用すれば、このような「冗長的ではあるが効率的な処理」を自動的に生成することもできます。
この手のコード展開は、これまで関数形式のマクロを用いることで実現されていましたが、インライン関数を用いることでコンパイラの型チェックやエラーチェックの恩恵を強く受けることが可能になりました。
次のような、コードの可読性と汎用性を向上させるための機能を少ないオーバーヘッドで実現することも可能になります。
// func print(String s, bool might = true)
// { if (might) print(s) }
print('<input type="text" value="0"');
print(' disabled="disabled"', might: !this.enabled);
print(' />');
再帰呼び出し除去
void print_dot(int n) {
if (n) {
printf(".");
print_dot(n - 1);
}
}
再帰呼び出しが関数の末尾で行われている場合は、再帰呼び出しが除去され、ループ文に置き換わる場合があります。
void print_dot(int n) {
while (n--) {
printf(".");
}
}
再帰呼び出しは処理の最後に行う必要があり、逆にprint_dot呼び出し後にprintfを呼び出すような処理を書いてしまうと、最適化の対象にはならないため注意が必要です。
goto文への置き換え
非効率なコードがより効率的なジャンプ命令に置き換わる場合があります。
元コード
for (int i = 1; i <= 9; i++) {
bool escape = false;
for (int j = 1; j <= 9; j++) {
if (i * j == 10) {
escape = true; // 非効率
break;
}
printf("%d, ", i * j);
}
if (escape) break; // 非効率
printf("\n");
}
fflush(stdout);
最適化後の擬似コード
for (int i = 1; i <= 9; i++) {
// bool escape = false;
for (int j = 1; j <= 9; j++) {
if (i * j == 10) {
// escape = true; // 非効率
// break;
goto label; // 置き換わった
}
printf("%d, ", i * j);
}
// if (escape) break; // 非効率
printf("\n");
}
label: // ここにジャンプする
fflush(stdout);
後置インクリメントの値更新タイミング
このコードは、
if (c != *s++) return false;
このように最適化されることがあります。
if (c != *s) return false;
++s;
return false;
実行前の余計なインクリメント処理が回避されました。
繰り返し文 条件式の最適化
繰り返し文の条件式内の関数呼び出しの結果はキャッシュされる場合があります。
for (int i = 0; i < string.length(); i++);
上記のコードは、以下ように最適化される場合があります。
int c = string.length();
for (int i = 0; i < c; i++);
ただし、lengthメソッドが返す内部値は基本的にプリミティブ型の定数である必要があります。またメソッドに副作用があってはなりません。
stringクラスとlengthメソッドの定義例は以下の通りです。
const struct String {
const char* s;
const size_t n;
String(const char* s) : s(s), n(strlen(s)) {}
size_t length() const { return n; }
} string = "abc";
ミュータブルなオブジェクトに対しても同様の最適化が行われることがあります。
これらの最適化はlength関数の結果がプリミティブ型の定数の場合に限ります。パスカル文字列やポインタへの間接参照は最適化の対象にならない可能性があります。
ですから以下のようなケースでは、strlen
関数を使用しているため結果は純粋な定数とはみなされず、ループの度にlength
関数が呼ばれることになります。
const struct {
const char* s;
size_t length() const { return strlen(s); }
} string = {"abc"};
for (size_t i = 0; i < string.length(); i++);