プログラミング言語の最適化のしやすさについて

プログラミング言語の高級化はえてしてプログラムを複雑化し最適化を阻害してしまいます。
rowlの開発ではこのトレードオフについて神経質になろうと思っています。

最適化の基本

最適化には命令数削減・並列化・パイプライン最適化・レジスタ割り当て・スケジューリング・キャッシュ最適化・・・とさまざまな対象・手法が存在しますが、いずれにも共通する事は

元のプログラムをより良いものに変形する

という事で、その際に重要なのは

プログラムの意味を変えてはならない

という最適化の基本原則です。プログラムの意味を変えない為にはプログラムの解析が必要で、その為の手法は大きく分けると

1. フロー解析
2. 型解析

です。最適化がしやすい言語とはこれらを精度よく行う事が出来る言語と言う事ができます。
また、Haskellの様な参照透過性が完璧に保たれている言語ではこれらの解析をすることなくプログラムの変形が可能です。
型解析は数学理論としては古いですが、現実のコンパイラで最適化の為に使用されている例は少ないです。また型解析でフロー解析の仕事をカバーすることは今のところできません。そこでフロー解析に基づく最適化に注目します。

フロー解析

フロー解析は

1. 制御フロー解析
2. データフロー解析

の二つに分けられて、データフロー解析から派生してエイリアス解析などがあります。

制御フロー解析

制御フロー解析ではプログラムの入り口から出口までどのような経路で処理が進んでいくかを解析します。
制御フローには

基本ブロック内フロー

途中に分岐がない一直線のフロー

ブロック間フロー

if文やwhile文などでのジャンプによるフロー

関数間フロー

関数呼び出しによるフロー

の３つがあり、一般に後者を扱おうとする程解析が難しくなります。

データフロー解析

基本的にどこで定義された変数がどこで使用されるか、書き換えられるかという解析です。
制御フロー解析の結果に基づいてデータフロー方程式というものを立ててそれを解くことにより行います。
ポインタが存在する言語ではエイリアス解析も必要になりますが、エイリアス解析は一般に計算量が高く難しいです。

最適化手法の多くがデータフロー解析の結果を利用します。定数畳み込み・共通部分式除去・部分冗長性除去・ループ変換・・・・・。

最適化の阻害要因

動的関数呼び出し

実行時までどこにジャンプするかわからないので、フロー解析は不可能です。従って動的関数コールを跨いだ最適化はほぼ不可能です。
動的言語は基本的に全ての関数が動的束縛なのでフロー解析はまず不可能で、多くの最適化が実装できません。
関数型言語の高階関数・継続・クロージャ、オブジェクト指向言語の仮想関数も動的ですが、静的束縛の関数もありますので最適化のしやすさは静的と動的の割合に依ります。
動的束縛の問題は実行時最適化(いわゆるJIT)により解決できる可能性があります。しかし、実行時には変数名・関数名や制御構造に関する情報が失われている、最適化には時間がかかるという壁もあるので、どうしても最適化の効果は下がってしまいます。

例外機構

例外発生とはつまりジャンプですので、例外が発生する可能性のある全ての式で基本ブロックが分断されます。さらに例外発生箇所からどこに飛ぶのか分からない場合がほとんどです。高級な言語では配列の範囲チェック・nullチェック・型チェックなどそこらじゅうで例外を送出しますので、最適化が大きく阻害されます。
しかし、例外は

• 関数コールと違って戻ってこない
• めったに例外は発生しない

という特徴があるので、例外依存解析や脱最適化などを利用した最適化が可能です。

ポインタ演算

ほぼC/C++言語特有の問題です。メモリは一次元ですのでポインタを介して、メモリ空間全体にアクセスする事ができます。
つまり、ポインタ変数は原理的にヒープ上のデータだけでなくスタック上のデータについてもありとあらゆるデータとエイリアスします。
また、ポインタはオブジェクト(特に配列)の途中を指す事ができます。さて、C/C++言語では関数引数に配列を渡すとそれはポインタとして扱われます。そうすると

void f(double a[], double b[]) {
    ....
}

といった関数で実はa,bのメモリ領域が重複している可能性があり、しかもそれを検査する事ができません(もし配列の途中をポインタが指せないならば、a == bかどうかを実行時にチェックすることが可能)。
この為にC/C++にはrestrict指示子があります。また、これはCよりFortranの方が最適化が効きやすいと言われる理由の一つです。

ボックス化

整数・浮動小数点数・配列などのデータをヒープ上に置く事です。ボックス化型データを取り扱う為にはポインタ・参照型の変数が必要になりますが、そうするとエイリアシングが発生します。
高級言語の多くはデフォルトでボックス化されたデータを扱います。すると、エイリアス解析が必要になり最適化性能が下がります。
ただしエイリアス解析は型情報を利用して精度向上させる事ができますので、静的型付け言語が有利です。

FFI

外部関数コールの事で、例えば拡張ライブラリの実現などに使用されます。
他の言語で書かれた拡張ライブラリは処理系にとってブラックボックスです。そこで何が行われるか分からないので、外部関数コールを跨いだ最適化ができなくなります。
ユーザが自由に拡張ライブラリを書けるような言語では、将来の最適化を阻害しないように拡張ライブラリ設計に注意しなければなりません。

再帰関数

プログラムの実行時間の8割は一部のループの実行時間であるとよく言われます。従って、ループの最適化は重要です。
ループ最適化の基本対象はdo-all型ループです。

for (i = 0; i < n; i++) {
    ....
}

do-all型ループは変数iを含む式に対してシンボリックな解析が可能です。それによりアクセスパターンを解析してキャッシュ最適化、ループ依存検査をして並列化などの高度な最適化が可能になります。

しかし、関数型言語ではループを再帰関数で書く事を推奨する文化があります。再帰関数はdo-all型ループよりも表現能力が豊かである代わりに、上の様なシンボリックな解析は困難です。再帰関数のループ構造を解析して最適化する手法で大きく成功している手法はありません。
再帰関数の最適化では末尾再帰最適化が有名ですが、これは再帰呼び出しをwhileループにするだけであり、do-allループにする物ではありません。従って、それ以上の最適化はやはり難しいです。

最適化に有利な言語特徴

逆を考えます。

静的型付け

プログラムについて多くの事が型から分かりますから、動的型付けに比べ最適化しやすいです。データフロー解析の精度向上・非ボックス化・動的束縛の除去・・・など。
動的型付けの言語でも型情報のアノテーション(LISPやPythonなどでサポート)により高速化することが可能です。

参照透過性

完全に参照透過性な言語ではフロー解析の必要性がなくなります。ただし、Haskellを見ればわかるように完全な参照透過性の獲得の為の仕組みはオーバヘッドが大きい事も考慮する必要があると思います。
完全な参照透過性がなくても、十分最適化の役に立ちます。C/C++のconstなどの指示子も同様です。

ところで、参照透過性があると自動メモ化という最適化が出来たりしますが、実験的な実装はあるものの完全に自動化することは難しいです。例えば良くGHCは自動メモ化やってるんじゃないかという議論を見かけますがやってません。Haskellでは共通部分式の除去が外から見るとメモ化に見える事があります。

取り合えずここまで。後で追記するかもしれません。