関数型言語はC言語よりも高速

というわけで、リハビリがてらなんか書こう。関数型言語が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言語と関数型言語では、関数型言語のほうが最適化できるけど、理論的に可能であるというのは、実際に可能かどうかとは話が別。

attribute malloc

関連する話として、アロケータに、__attribute__((malloc))を付けましょうという話。


まず、

extern void * alloc_buffer( );
extern void free_buffer( int * );

int 
nanika( int *a )
{
	int x;
	int ret;
	int * buf = alloc_buffer( );

	x = a[0];

	buf[0] = 0;

	ret = x - a[0];

	free_buffer( buf );

	return ret;
}

こういうコードを考える。さて、このコードの戻り値は？
0 … のように見える（x = a[0]; ret = x-a[0]; return 0;）けど、ひょっとすると、0ではないかもしれない。
なぜか？alloc_bufferの返してくる値が、int *aが指しているバッファと重なってるかもしれないから（何を言ってるかわからない人は、もう一度上の話を読み直そう。それでもわからない場合は、抗議のメールを出そう！そんなことされたら困る）。

上のをコンパイルすると、

nanika:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%esi
	pushl	%ebx
	movl	8(%ebp), %ebx
	call	alloc_buffer
	movl	(%ebx), %esi
	subl	$12, %esp
	movl	$0, (%eax)
	subl	(%ebx), %esi  ; 減算
	pushl	%eax
	call	free_buffer
	leal	-8(%ebp), %esp
	popl	%ebx
	movl	%esi, %eax
	popl	%esi
	leave
	ret

減算してるのがわかると思う。最適化してくれない。


ところが…！このコードを、

int 
nanika2( int *a )
{
	int x;
	int ret;
	int * buf = malloc( 10 );

	x = a[0];
	buf[0] = 0;
	ret = x - a[0];

	free( buf );

	return ret;
}

こんなふうに、malloc、freeを使うように修正すると、

nanika2:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$20, %esp
	pushl	$10
	call	malloc
	movl	$0, (%eax)
	movl	%eax, (%esp)
	call	free
	xorl	%eax, %eax
	leave
	ret

アラ不思議！減算処理が消えてしまいました！xorl eax, eax！（GCC4.1だとうまくいかない？GCC3.2だとうまくいった。）


実は、GCC拡張のattributeに、'malloc'というのがあって、

GCC info より
`malloc'
The `malloc' attribute is used to tell the compiler that a function
may be treated as if any non-`NULL' pointer it returns cannot
alias any other pointer valid when the function returns. This
will often improve optimization. Standard functions with this
property include `malloc' and `calloc'. `realloc'-like functions
have this property as long as the old pointer is never referred to
(including comparing it to the new pointer) after the function
returns a non-`NULL' value.


適当訳: `malloc' attribute は 関数が返すNULL以外の戻りポインタが他の有効なポインタとエイリアスしないものと示すのに使います。
これは、たまに最適化を良くします。
（以下略）

まあ、なんかそんな。戻したポインタがエイリアスしませんよ。と。そういう話。

extern void * alloc_buffer( ) __attribute__((malloc));
extern void free_buffer( int * );

int 
nanika( int *a )
{
	int x;
	int ret;
	int * buf = alloc_buffer( );

	x = a[0];
	buf[0] = 0;
	ret = x - a[0];
	free_buffer( buf );

	return ret;
}

こうすると、ほら不思議。


というわけで、自分でアロケータ書いた場合は、__attribute__((malloc))を付けましょう