というわけで、リハビリがてらなんか書こう。関数型言語がC言語よりも高速だという話。
http://d.hatena.ne.jp/w_o/20050924#p2
ここらへんの話の関連。C言語では、操作が、「メモリを変更する」という具体的なものになってしまうので、最適化が難しいという話。
次のコードを考えよう。
struct stack {
char *buf;
int pos;
};
void push( struct stack *stk, char v )
{
stk->buf[stk->pos] = v;
++stk->pos;
}
void pop( struct stack *stk )
{
--stk->pos;
};
void nop( struct stack *stk )
{
push( stk, '\0' );
pop( stk );
}さて、ここで、nop はどんなコードになるでしょうか。
こういう場合、nop はその名のとおり、何もしないコードになってほしいところだけど、大抵のコンパイラでは、そういうコードにはならない。
手元の環境(GCC-4.1.1)では、↓こうなった。
.globl nop .type nop, @function nop: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax ; 8(%ebp) が q : eax = q movl (%eax), %edx ; edx = (%eax) = (*q) = q->buf movl 4(%eax), %eax ; eax = 4(%eax) = q->pos movb $0, (%edx,%eax) ; q->buf[q->pos] = 0 popl %ebp ret
さて何故、コンパイラは、これを何もしないコードに書きかえてくれないのでしょうか？最適化機能がヘボいから？
まあ、色々あるんだけど、とりあえず、上のが最適化されない理由として、q->buf[q->pos] を書きかえてしまっているから、というのがある。
もし、ここで、{ push(stk,n); pop(stk); } がなにもしないコードに最適化されてしまったとしたら、
char op( )
{
struct stack stk;
char c;
stk.buf = &c;
stk.pos = 0;
nop( &stk );
return c;
}こういうプログラムがあったときに、最適化された場合とされなかった場合で、結果が変わってしまうよね。（最適化した場合:未定義、最適化しなかった場合:'\0'）
そうならないように、コンパイラは、無駄のように見えるコードでも、最適化を我慢しないといけない、というわけ。（エイリアスの問題）
有名…かどうかは知らないけど、コンパイラというのは、一応、このへんをなんとかするために、ポインタアクセス一個ごとに、「このポインタ書き換えは消してしまっても大丈夫…だよね…」というのをチェックする「エイリアス解析」というのを行ってはいる。
のだけど、それでも、分割コンパイルした瞬間に、全てが闇の中へ消えてしまって、まあ、そこらへんは、リンカに最適化機能とかが無いと無理なんだけど。
（iccのipoとか、そういう話だと思うんだけど…使ったことないのでわからない。）
で、さて、関数型言語の話。関数型言語では、C言語と違って、そういうような心配は一切無く。
type stack = char list ;; let push s n = n::s;; let pop (t::s) = s;; let top (t::s) = t;; let nop s = pop( push s 0xffff);;
こういうコードを考えよう（OCamlね）。
こういうように副作用が無い場合は、エイリアス解析などそもそも必要無く、単純に簡約していくだけで、nopがほんとうになにもしないコードになる↓
nop s = pop ( push s 0xffff ) = pop ( (0xffff::s) ) = s nop s = s
ほあー。Cコンパイラは、変数が生きてるとか死んでるとか、合流とか、そういうのを考慮して、エイリアス解析しても、まだ、最適化できないような部分なのだが、しかし、副作用の無い言語では、そんな複雑なことを一切無しに、単純に置換していくだけで、最適なコードが生成されるのである！もうC言語なんて要らないね！
このことは、色々関連する話があって、FORTRANは何故C言語より速いか、とか、そういう話なんだけど、例えば、Javaって、C言語の配列と違って、配列の途中を配列にできないよね。
// C言語 char a[20]; char *b = &a[10]; // 配列の途中
// Java char a[] = new char [20]; char ……？
こういうの。これのせいで、JavaはCよりも無駄があるよなー、と思ってしまいがちなんだけど、Javaの場合、このルールによって、「配列はいくら書きかえてもその配列オブジェクト以外のオブジェクトは変更されない」という前提が生まれるので、もっと強力な最適化が可能なんである。
というわけで、関数型言語は、C言語よりも最適化できるという話。
例えば、上のOCamlのコードをコンパイルすると、↓
camlStack__nop_67: .L114: movl %eax, %ebx .L115: movl caml_young_ptr, %eax subl $12, %eax movl %eax, caml_young_ptr cmpl caml_young_limit, %eax jb .L116 leal 4(%eax), %eax movl $2048, -4(%eax) movl $131071, (%eax) movl %ebx, 4(%eax) jmp camlStack__pop_61
こんな…
えー。駄目じゃん（読めないけど…）！アロケートとかしてるし！！
やっぱりメモリ管理も自分の制御化に置いておけるC/C++言語が一番だね！
まあ、そういう話。本来、関数型言語とか、そういう高級言語は、C言語よりも最適化できるはずなんだけど、まあ、なかなかそういうわけにはいかず、C/C++は人口が多いので、マンパワーで勝ってしまうというそういう話でした。
あと、CPUベンダがCコンパイラ出すからね！最近のCPUは魑魅魍魎で、もうICCとか絶対ぐちょぐちょと泥臭い最適化とかしてたりするんだぜきっと見たことないから知らんけど！
一度でよいから、
http://download.intel.com/jp/developer/jpdoc/IA32_Final_i.pdf
を読んでみよう！商用のコンパイラ屋ってほんと大変なんだろうなー。君はinc命令がadd命令よりも遅い理由を知っているか！
まとめ:
C言語と関数型言語では、関数型言語のほうが最適化できるけど、理論的に可能であるというのは、実際に可能かどうかとは話が別。
