性能とプロファイル
訳注:本章は編集の都合と読みやすさの観点から、原文の中身を一部別パートに分割しています。
罪な引用...
「よい言語を採用するにあたって一つ深刻な障害がある。 速度のためにはなにもかも犠牲にするという考え方だ。 実生活と同じくコンピュータ言語でもスピードは人殺しだ。」 — Mike Vanier
(訳注:全文はおそらくこちら)
速度
OCamlはなぜ速いのか? まぁ、もう一歩引いて聞こうか。OCaml は速いのか?
どうしたらプログラムを高速化できるのか? この章では、OCaml
プログラムがコンパイルされて機械語に落ちる際、
実際に何が起こっているのかを見ていこうと思う。 ここから、OCaml
が単に素晴らしいプログラミング言語というだけでなく、
実に高速な言語であることもわかることと思う。
さらに、コンパイラによりよい機械語を吐かせられるようになるだろう。
また、ocamlopt と打ってから実行バイナリを得るまでに行っていることの
考え方を知っておくのもプログラマにとっていいことだ(とわたしは信じてる)。
ただし、このセクションを最大限に活用するためには、 アセンブラを知っておく必要がある。恐がることはない! アセンブリ言語をCライクな擬似コードに翻訳してわかりやすくするつもりだ。 (だって、Cは可搬性のあるアセンブリ言語だろう?)
アセンブリ言語の基礎
この章で示す例は全て x86-Linux マシンでのコンパイル結果である。 もちろん x86(IA-32) は 32bit マシンなので x86 の「ワード(語)」は 4byte(=32bit)長だ。 機械語レベルにおいては、OCaml は大抵ワードサイズのオブジェクトを扱うので、 バイト単位のサイズが必要な時には4倍することを忘れないように。
さて頭を切り替えて。 汎用レジスタはそれぞれ1ワード分を記憶できるのだが、
x86 には汎用レジスタが少ない。 Linux のアセンブラ(GNU as)
はレジスタ名の前に % を付ける。 つまりレジスタは %eax, %ebx,
%ecx, %edx, %esi, %edi,
%ebp(スタックフレーム用レジスタ),セクションで用いる。
%esp(スタックポインタ) だ。
Linux のアセンブラではレジスタやメモリの転送の元/先は以下のように書く (他の Unix のアセンブラも同じだが、MS系アセンブラは逆)。
movl from, to(訳注: この点について、実際にはMS系というわけではなく Intel
のアセンブラ表記 そのものが Linux を含む Unix
系アセンブラ表記(これらはAT&T表記と呼ぶ)と逆。 Microsoft は
Intel表記に忠実に従っているだけなので念のため。
Intel表記だと以下の通りで、MASM
等ではサイズ表記のサフィックス(l)を省略できて
movl to, fromとなる。他にも MASM と GAS(GNU as) でのアセンブラディレクティブの違い (コードセグメントとテキストセクションというように呼びかたが違うなど) があったりするので、Windows/MS-DOS 系の知識がある人は適宜推測して 読みかえてほしい。)
つまり、movl %ebx, %eax (Intel表記なら mov eax,ebx) というのは、
「レジスタ ebx の中身をレジスタ eax にコピーする」
という意味だ(逆じゃないよ)。
アセンブリ言語は movl のような機械語命令だけでなく、
アセンブラディレクティブというものからも構成されていること
を見ておく必要がある。 これらのディレクティブは(訳注:AT&T系の場合) .
(ピリオド) で始まり、 文字どおり直接アセンブラに対して指示する。
ここで Linux アセンブラの主要なディレクティブを紹介する:
.text
text というのは「プログラムコード」の Unix 流の呼びかただ。
テキストセグメント(テキスト領域)
というのは単にプログラムコードが置かれている実行可能領域のことだ。
.text ディレクティブによってアセンブラはセグメントを切り替え、
ここからテキストセグメントが始まる。 (訳注:ただし、アセンブリ言語で
.text の部分はテキストセクションと呼ぶ。
テキストセクションにあるものが割り付けられる先のメモリ領域
をテキストセグメントと呼ぶのが一般的か。以下の訳はこれをベースに使い分けてみた)
.data
同様に、.data ディレクティブによって
実行可能なデータセグメント(領域)が始まるように切り替えられる。
.globl とラベル
.globl foo
foo:これは foo という大域シンボルを宣言している。 宣言の次に foo
という名前で登場するやつのアドレスを意味する。 .globl
ディレクティブを伴わず単に foo: と書いた場合は、
局所シンボルの宣言(そのファイルに閉じた宣言)となる。
定数指示など
.long 12345
.byte 9
.ascii "hello"
.space 4.long はそこにワード(4バイト)を書く。 .byte は1バイトを書く。
.ascii はバイト列(nul文字による終端はない)を書く。 .space
はゼロで指定バイト数を埋める。 普通、これらはデータセクションで用いる。
"hello, world" プログラム
もうアセンブラについては十分だろう。 以下のプログラムを smallest.ml
というファイルに書こう。
print_string "hello, world\n"で、以下のようにネイティブコードにコンパイルする:
ocamlopt -S smallest.ml -o smallest-S (大文字のS) でコンパイラにアセンブリ言語ファイル (smallest.s -
こっちは小文字) を消さずに残すよう指示している。
smallest.s ファイルにコメントを付け加えたり強調したりして手を加えた
のがここにある。まずはデータセクションだ:
.data
.long 4348 ; 文字列ヘッダ
.globl Smallest__1
lest__1:
.ascii "hello, world\12" ; 文字列
.space 2 ; 文字列の後ろ
.byte 2 ; のパディング次はテキストセクション(プログラムコード):
.text
.globl Smallest__entry ; プログラムの入口
lest__entry:
; 以下は擬似Cコードの以下と同じ
; Pervasives.output_string (stdout, &Smallest__1)
movl $Smallest__1, %ebx
movl Pervasives + 92, %eax ; Pervasives + 92 == stdout
call Pervasives__output_string_212
; return 1
movl $1, %eax
retC では全てが関数の中にないといけない。 C では単に
printf ("hello, world\n"); とは書けず、 main() { ... }
の中に書かないといけないことを思い起こそう。 OCaml
では関数の中じゃなくトップレベルに命令を書くことができる。
しかし、これをアセンブリ言語に翻訳するとき、
これらの命令はどこに置けばいいのだろう?
外部からこれらの命令を呼び出すなんらかの方法が必要だ。
だからまず何らかのラベルをつける。 上のコード片を見るとわかるだろうが、
OCaml ではファイル名(smallest.ml)の 先頭を大文字にして __entry
を付け加えたシンボル、 つまり Smallest__entry というシンボルで
ファイル中のトップレベルコマンドを参照できるようにしている。
次は OCaml が生成したコードを見てみよう。 元のコードは
print_string "hello, world\n" だったが、OCaml はそれと等価な
Pervasives.output_string stdout "hello, world\n" でコンパイルした。
なーんでだ? pervasives.ml を調べるとその理由がわかる。
let print_string s = output_string stdout sOCaml はこの関数をインライン展開した。 インライン化 (関数定義を展開して突っ込む) は 余計な関数呼び出しのオーバーヘッドを避けて オプティマイザにやれることを増やす方向に働くので、 性能上有利なことがある。 逆にインライン展開が良くないこともある。 コードが脹れあがる方向に働くので、 その結果 CPUキャッシュ 上で順調に動いていたものが 溢れてメタメタに遅くなってしまう (そのうえ、関数呼び出しは今時の CPU では全然高コストじゃない)。 OCaml はこれみたいな単純な呼び出しの場合は、 本質的に危険性がないのでインライン化する。 ほとんどの場合、ちょっとだけ性能向上するだろう。
これについて他に気づいたことは?
呼び出し規約は、どうやら最初のふたつの引数を %eax と %ebx
レジスタそれぞれに 渡しているように見える。
他に引数があればスタック渡しされるのだろうが、
それについては後で見ていこう。
Cプログラムには ASCIIZ
として知られる文字列を格納する単純な規約がある。 これは単に文字列を
ASCII 列で格納して末尾に NUL文字(\0) を付けるというものだ。 OCaml
では文字列はこれとは違った方法で格納しており、それは
上のデータセクションを見ればわかると思う。
文字列はこのように格納されている:
4バイトのヘッダ: 4348
文字列本体: h e l l o、SP w o r l d\n
パディング: \0 \0 \002この形式は普通じゃない。 これについては OCaml メーリングリストに投稿されたもの に書かれている。
一つめには、パディングは文字列のワード長(例では4ワード、16バイト)に ぴったりになるようにしている。 このパディングは良く考えて設計されており、 その文字列に割り当てられているワード数を知っていれば その実際のバイト数での長さがわかるようになっている。 これを求めるコードは自明だ(自分で証明できるはずだ)。
この長さが自明な文字列には、 C ではくっつけるのが煩わしかった ASCII
NUL(\0)文字もその文字列表現にくっついている、 という特長がある。
だが反対に、OCaml 文字列を Cネイティブコードに渡すときに
意識する必要がある: ASCII NUL を含んでいると C の str*
関数で失敗することだ。
(訳注:本当? NUL があるから C でのハンドリングは楽なはずで、 C から OCaml に持ち帰るときに気にする必要があるだけでは?)
ふたつめは、ヘッダ部分があることだ。 OCaml では全ての boxed (アロケートされた) オブジェクトには ヘッダがあり、 ガベージコレクタ(GC)に、 オブジェクトがワード換算でどれくらいの大きさがあるのか、 オブジェクトに含まれるものはなんなのか、等を伝える役目がある。 ヘッダに数値4348 (=0x10fc) が書かれているというのは:
ワード換算のオブジェクト長: 0000 0000 0000 0000 0001 00 (4ワード)
カラー(GCが使う): 00
タグ: 1111 1100 (String_tag)OCaml
におけるヒープに割り当てられたオブジェクトの形式についての詳しい情報は
/usr/include/caml/mlvalues.h あたりを見よ。
一つ変わっているのは、コードは Pervasives.output_string に
文字列の開始位置(つまりヘッダの直後のワード)のポインタを渡していることだ。
つまり、output_string はポインタから4を引かないことには、
ヘッダを得て文字列長を判別できないということだ。
この簡単な例で何か忘れてることはないですかね?
うーん、上のテキストセクションでは全部ではないな。 OCaml が単純な hello
world プログラムを上のたった5行のアセンブリに
翻訳したのなら本当にいいことだが、 実際のプログラムで Smallest__entry
を呼び出してるのは何かが疑問だ。 この点について、 OCaml では
ガベージコレクタやメモリの初期化とアロケート、ライブラリの初期化呼び出し
などを行うブートストラップコード全部を含んでいる。 OCaml
は最終実行ファイルにこれらコードを静的にリンクしており、
このプログラムが結局 95,442
バイトもの大きさ(Linuxの場合)にもなる理由です。 にもかかわらず、Java
のまともなプログラムの起動時間は数秒、 Perl
スクリプトで約1秒などに比べると、
まだまだこのプログラムの起動時間は測定不能な程度に小さい(ミリ秒以下)。
末尾再帰
第6章(訳注:7章(If文、ループと再帰)では?)で、 OCaml は末尾再帰関数を単純ループに変換できると述べた。 これは本当に正しいのだろうか? 単純な末尾再帰のコンパイル結果を見てみよう。
let rec loop () =
print_string "I go on forever ...";
loop ()
let () = loop ()これのファイル名を tail.ml とすると、 関数名は OCaml
の標準的な手続きに則って付けられて、 この関数は Tail__loop_nnn となる
(nnn は他の名前つき関数と区別するために OCaml が付け足す
ユニークな数値)
これが上で定義した loop 関数のアセンブリだ。
.text
.globl Tail__loop_56
Tail__loop_56:
.L100:
; 文字列の表示
movl $Tail__2, %ebx
movl Pervasives + 92, %eax
call Pervasives__output_string_212
.L101:
; この movl は実際には使われない
movl $1, %eax
; 上のラベル .L100 に戻る (i.e. 永久ループ)
jmp .L100たしかにそうなっている。 Tail__loop_56
を呼び出すとまず文字列を表示して、 そのあと先頭に戻る。
そして文字列を表示して戻り、それが永遠に続く。
これは単純ループであって再帰的な関数呼び出しになっていないから、
スタック領域を全く消費しない。
脱線:型はいずこに?
ことあるごとに言ってきた通り、OCaml は静的型だ。
だから、コンパイル時には OCaml は loop の型が unit -> unit
であることを知っている。 "hello, world\n" が string
型であることも知っている。 この事実を何ら output_string
関数に伝えようとしていない。 output_string は channel と string を
引数にとることが期待値であり、実際にそれが引き渡されている。 例えば
string のかわりに int を渡してしまったら 何が起こるのだろう?
これは本質的には不可能な状況だ。 OCaml
はコンパイル時に型を知っているので、
実行時に型の対処や型チェックをする必要がない。
コンパイラを騙してPervasives.output_string stdout 1という
呼び出しを生成される方法は、純粋な OCaml には存在しない。
コンパイル時に型推論によってエラーが通知されるから
決してコンパイルできないだろう。
その結果、OCaml コードがコンパイルされてアセンブラに渡るときにはもう、 型情報がほとんどの場合不要ということだ。 確かに上で見たケースではコンパイル時に型が全部わかっており、 多相型がない。
コンパイル時に型を全部知っているということは、
実行時の動的型チェックを完全回避できるから性能で勝る主要因だ。 Java
のメソッド実行、たとえば obj.method() と比べてみよ。 インスタンス
obj の具体的なクラスを知る必要があって、
そこからメソッドを探さないといけないのだから、 これは高価な操作だ。
そしておそらくいつ、どんなメソッドであってもこうしなければならない。
オブジェクトのキャストもまたJava
では実行時にかなりの仕事をする必要がある ケースだ。OCaml
は静的型だからこれは許されていない。
多相型
上の議論から推測しているかもしれないが、 多相型(コンパイラがコンパイル時には関数の型が完全にはわからない) は性能に影響があるかもしれない。 ふたつの整数の最大値を返す関数が欲しいとしよう。 最初の例はこれだ:
# let max a b =
if a > b then a else b;;
val max : 'a -> 'a -> 'a = <fun>
とても単純だ、だがしかし、> (より大きい) 演算子は OCaml
では多相型であることを思いだそう。 つまりこの型は 'a -> 'a -> bool
で、 ここで定義した関数 max は多相型になっているということだ。
# let max a b =
if a > b then a else b;;
val max : 'a -> 'a -> 'a = <fun>
実際OCamlがこの関数から生成したコードに反映されているが、 かなり複雑だ。
.text
.globl Max__max_56
Max__max_56:
; スタック領域を2ワード予約
subl $8, %esp
; ふたつの引数(aとb)をスタックに保存
movl %eax, 4(%esp)
movl %ebx, 0(%esp)
; C の greaterthan 関数(OCamlライブラリにある)を呼ぶ
pushl %ebx
pushl %eax
movl $greaterthan, %eax
call caml_c_call
.L102:
addl $8, %esp
; greaterthan が1を返したら .L100 に分岐
cmpl $1, %eax
je .L100
; 返値が0なら、スタックに保存しておいた引数 a を取得し
; 戻る
movl 4(%esp), %eax
addl $8, %esp
ret
; 返値が1なら、スタックに保存しておいた引数 a を取得し
; 戻る
.L100:
movl 0(%esp), %eax
addl $8, %esp
ret基本的に > 演算は OCaml ライブラリから C 関数を呼び出すことで処理される。 これは > の動作をする高速なインラインのアセンブリ言語を生成する類の 効果的なものには見えず、あまり効果的ではなさそうだ。
このことは、どうやっても損になるというわけじゃない。 やるべきことは
OCaml コンパイラに、
引数が実際には整数であるというヒントをあたえることだ。 次に引数が int
の時のみ動作するよう特化したバージョンの max を作ってみる。
# let max (a : int) (b : int) =
if a > b then a else b;;
val max : int -> int -> int = <fun>
この関数から生成されたアセンブリコードがこれ:
.text
.globl Max_int__max_56
Max_int__max_56:
; > 演算子の動作は cmpl 命令1個になった
cmpl %ebx, %eax
; %ebx > %eax なら .L100 に分岐
jle .L100
; 単に a を返す
ret
; b を返す
.L100:
movl %ebx, %eax
retたった5行のアセンブリになった。 これは大体思った通りの単純さだろう。
こんなコードはどうだろうか:
# let max a b =
if a > b then a else b
let () = print_int (max 2 3);;
3val max : 'a -> 'a -> 'a = <fun>
OCaml は賢く max 関数をインライン化して整数に特化するだろうか。
残念ながら答えはノーだ。 OCaml は外部に Max.max
シンボルを生成する必要がある
(これはモジュールだからモジュールの外からこの関数が呼ばれるかもしれない)。
別のパターンはどうか:
# let max a b =
if a > b then a else b in
print_int (max 2 3);;
3- : unit = ()
残念ながら、 このコードの max はローカル定義
(モジュール外から呼び出せない)にもかかわらず、 まだ OCaml
はこの関数を特化してくれない。
教訓: 意図しないところで多相型になっている関数があったら、 引数の型を特定してあげるとコンパイラが助かる。
整数の内部表現、タグビット、ヒープに割り当てられた値
OCaml の整数にはいっぱい変わったところがある。 一つは、整数の実体が 32ビットではなく 31ビットというところだ。 この"失われた"ビットで何が起きているのだろう?
int.ml にこう書こう:
# print_int 3;;
3- : unit = ()
で、ocamlopt -S int.ml -o int とコンパイルして int.s
にアセンブリ言語ファイルをつくる。 上の論議を思い出すと、OCamlは
print_int 関数を output_string (string_of_int 3)
とインライン展開することが期待されるから、 OCaml
が本当にそうしたかどうかをアセンブリ言語出力で 検証しよう。
.text
.globl Int__entry
Int__entry:
; Call Pervasives.string_of_int (3)
movl $7, %eax <----重要!!
call Pervasives__string_of_int_152
; Call Pervasives.output_string (stdout, result_of_previous)
movl %eax, %ebx
movl Pervasives + 92, %eax
call Pervasives__output_string_212重要なコードを赤で示した(訳注:されてないので別途示した)。
ここについて2点指摘する: 一つは整数が unbox
である(ヒープに割り当てられていない) かわりに、この関数内で直接レジスタ
%eax に渡されている。 これは高速だ。
だが、2点め、ここで渡されている数値は3じゃなく7だということがわかる。
OCaml における整数表現の結果こうなっている。 整数の最下位ビットはタグ(これがなんなのかは次で述べる) として使われており、上位31ビットが実際の整数だ。 7は2進表現で111だから最下位ビットが1で上位31ビットが二進数の11 つまり3だ。 OCaml表現から整数を得るには2で割って切り捨てれば良い。
何故タグビットがあるのか?
このビットは、整数とヒープ上の構造体へのポインタとを
区別するために使っており、
多相関数を呼び出すときのみこの区別が必要になる。 上のケースでは、
string_of_int を呼ぶところは、タグビットは調べられていないが
引数は常に int でなければならないわけだ。
整数が二つの内部表現をもたないようにするために、 OCaml
では整数は全てタグビットを持ち回っている。
何故タグビットが本当に必要で、何故そこにあるのかを理解するために、 ポインタに関するちょっとした背景が必要だろう。 SPARC, MIPS, Alpha のような RISC チップの世界では、 ポインタはワード境界に揃えないといけない。 だから例えば昔の 32bit SPARC では、 4(バイト)の倍数境界に揃っていない ポインタは作ることも使うこともできない。 もし使おうとすれば、CPU は例外を発生して プログラムは基本的にはセグメント例外 (訳注:実際にはバスエラーになるはずだ)になる。 こうしている理由は、メモりアクセスを単純にするためだ。 ワード境界に揃ったアクセスだけ気にすればいいのであれば CPU のメモリサブシステムの設計はずいぶんと簡単になる。
歴史的な理由(x86は8ビットチップに由来する)から x86 は境界に揃っていないメモリアクセスをサポートしているが、 4の倍数にメモリアクセスを揃えておけばより高速に動く
OCaml では全てのポインタはアラインされている、 つまり32bit CPU なら4の倍数、64bit CPU なら8の倍数になっている。 OCaml のポイントはどれも最下位ビットが常に0 ということだ。
ゆえにレジスタの最下位ビットを見れば、即、 そこにポインタが格納されている(タグビットが0)か 整数が格納されている(タグビットが1)かがわかる。
前のセクションで、多相の > 関数が
いろいろ面倒だったことを覚えているだろうか。 アセンブル結果を見たら
OCaml は多相の > をいつでも C 関数の greaterthan
呼び出しにしていることがわかったはずだ。 この関数 greaterthan
は二つの引数を レジスタ %eax, %ebx にとるが、
整数、浮動小数、文字列、よくわからないオブジェクトでも呼び出せる。
どうやって %eax と %ebx が指している ものが何なのかを知るのだろう?
以下の判断ツリーをたどる:
- タグビットが 1 : 二つの整数を比較して戻る。
- タグビットが 0 :
%eaxと%ebxは2つのヒープから割り当てられたメモリブロックを指すポインタだ。そのメモリブロックのヘッダから、そのブロックの中身を示すタグであるヘッダワードの下位8ビットを見る。- String_tag : 二つの文字列を比較する
- Double_tag : 二つの浮動小数点数を比較する。
- その他
> が 'a -> 'a -> bool という型であり、
引数が両方とも同じ型でないといけないことに注意。
コンパイラはコンパイル時にこれを強制するが、 たぶん greaterthan
には実行時にも正常かどうかチェックするコードがあると思う。
浮動小数点数
浮動小数点数はデフォルトでは boxed (ヒープに割り当てられる)だ。 以下を
float.ml でセーブして ocamlopt -S float.ml -o float
とコンパイルしよう:
# print_float 3.0;;
3.- : unit = ()
数値は、前述整数型のように直接 %eax レジスタにセットされて
string_of_float に渡されることはない。
かわりにデータセクションに静的に生成される。
.data
.long 2301
.globl Float__1
Float__1:
.double 3.0そしてこの浮動小数点数へのポインタが %eax 経由で渡される。
movl $Float__1, %eax
call Pervasives__string_of_float_157浮動小数点数の構造に注意: ヘッダ(2301=0x8fd)があって、 その後ろに8バイト(2ワード)の数値自身がある。 ヘッダは二進数で書き下すと解読できる:
オブジェクトのワード単位の長さ: 0000 0000 0000 0000 0000 10 (8 バイト)
カラー: 00
タグ: 1111 1101 (Double_tag)string_of_float は多相型ではないが、 多相型の引数を一つとる多相関数
foo : 'a -> unit があると仮定しよう。 %eax に 7 を代入して foo
を呼び出すことは foo 3 と同じなのに対し、 %eax に上記 Float__1
へのポインタを代入して fooを呼び出すのが foo 3.0
と同じということだ。
配列
以前、OCaml の目標の一つに数値計算があると述べた。
数値計算ではベクトルや配列 (本質的には浮動小数点数の配列)
の計算を大量に行う。 これをより高速に行うための特別なハックとして、OCaml
では 「unboxed な浮動小数点数の配列」を実装している。 これは
float array 型(浮動小数点数の配列)
のオブジェクトが特殊ケースであることを意味し、
ヒープ上に10個の浮動小数点数を別々にアロケートして
そこへのポインタの配列を持つのではなく、 OCaml でも以下の C
コードと同じように格納している。
double array[10];実際にこれを見てみよう:
let a = Array.create 10 0.0;;
for i = 0 to 9 do
a.(i) <- float_of_int i
doneこのコードを範囲チェックを外す -unsafe オプションを積んで
コンパイルする(説明のためにコードを簡単にするためだ)。
最初の行で配列を作っているがコンパイル結果は単純な C
関数コールになっている:
pushl $Arrayfloats__1 ; Boxed の浮動小数点数 0.0
pushl $21 ; 整数の 10
movl $make_vect, %eax ; C の関数呼び出しのアドレス
call caml_c_call
; ...
movl %eax, Arrayfloats ; この結果の配列へのポインタを
; ヒープに格納ループはコンパイルされて比較的単純なアセンブリ言語になっている:
movl $1, %eax ; %eax に 0を代入。以降 %eax に i が入る
cmpl $19, %eax ; %eax > 9 ならループを抜ける
jg .L100 ; (最後のラベル .L100 に行く)
.L101: ; ここからループ本体の開始
movl Arrayfloats, %ecx ; 配列のアドレスを %ecx へ
movl %eax, %ebx ; i を %ebx にコピー
sarl $1, %ebx ; ebx からタグビットを削除
; (右1ビットシフト)
; これで整数 i そのものになった
pushl %ebx ; %ebx を浮動小数点に変換
fildl (%esp)
addl $4, %esp
fstpl -4(%ecx, %eax, 4) ; 配列の i 番目に浮動小数点を格納
addl $2, %eax ; i に 1 を足す
cmpl $19, %eax ; i <= 9 ならまたループ
jle .L101
.L100:浮動小数点数を配列に格納している文が重要だ:
fstpl-4(%ecx、%eax、4)アセンブリ構文はかなり複雑だが、 括弧で括られた式 -4(%ecx, %eax, 4)
は「%ecx + 4*%eax - 4 のアドレス」という意味だ。 %eax は i の
OCaml 表現だったから、 タグビットつきの完全な状態だ。 なので中身は
i*2+1 に等しい。 代入して掛けてみよう:
%ecx + 4*%eax - 4
= %ecx + 4*(i*2+1) - 4
= %ecx + 4*i*2 + 4 - 4
= %ecx + 8*i(配列の各浮動小数点数は8バイト長だ)
ゆえに期待どおり浮動小数点数の配列は unboxed だ。
部分適用された関数とクロージャ
OCamlはどうやって部分適用されただけの関数をコンパイルするのだろうか? このコードをコンパイルしよう:
Array.map ((+) 2) [| 1; 2; 3; 4; 5 |]文法を思い出してみると、[| ... |]
で配列(ここではint arrayだ)を宣言していて、 ((+) 2)
が「2と何かを足す関数」というクロージャだ。
このコードをコンパイルすると面白い新機構が姿をあらわす。 最初に配列をアロケートするコード:
movl $24, %eax ; 5*4+4 = 24バイトのメモリをアロケート
call caml_alloc
leal 4(%eax), %eax ; %eax は確保したメモリの
; 4バイト先を指すポインタになるヒープからの割り付けは全部同じ形式だ:4バイトのヘッダ+データ。 この場合データは5つの整数だから、ヘッダの4バイトとデータの 5*4 バイト を足したぶんだけ確保する。 ポインタは最初のデータワード(i.e. 確保されたメモリブロックの4バイト先) を指すように更新される。
次に OCaml は配列の初期化コードを生成している:
movl $5120, -4(%eax)
movl $3, (%eax)
movl $5, 4(%eax)
movl $7, 8(%eax)
movl $9, 12(%eax)
movl $11, 16(%eax)ヘッダワードは5120(=0x1400)で、これは二進数で書くと 5ワードあってタグが0であるこことがわかる。 0のタグというのは配列など「構造化したブロック」を意味する。 また 1,2,3,4,5の数を配列の適切な場所にコピーしている。 ここで OCaml の整数表現が使われていることに注意。 構造化されたブロックなので ガベージコレクタ(GC)はブロック内の各ワードをスキャンするのだが、 GC は整数か他のヒープ上のブロックへのポインタなのかを 区別できる必要があるのだ (GC には配列から型情報をアクセスする手段がない)。
次にクロージャ ((+) 2) が作られる。
このクロージャはデータセクション上に割り当てられたブロックにある。
.data
.long 3319
.globl Closure__1
Closure__1:
.long caml_curry2
.long 5
.long Closure__fun_58ヘッダは3319(=0xcf7)で、3ワード長の Closure_tag
であることを示している。 ブロック内の3ワードは caml_curry2
のアドレス、整数値2、 この関数自身のアドレスとなっている。
.text
.globl Closure__fun_58
Closure__fun_58:
; この関数は二つの引数 %eax、%ebx をとる。
; この行では %eax + %ebx - 1 を返している。
lea -1(%eax, %ebx), %eax
retこの関数は何をしているのだろうか。
表面上は二つの引数を足して1を引いている。だが、 %eax と %ebx は
OCaml の整数表現であることを思いだそう。 こういうことだ:
%eax = 2 * a + 1%ebx = 2 * b + 1
ここでいう a と b は実際の整数引数だ。 だからこの関数の返値は
%eax + %ebx - 1
= 2 * a + 1 + 2 * b + 1 - 1
= 2 * a + 2 * b + 1
= 2 * (a + b) + 1言い替えると、この関数は OCaml の整数表現での和 a+b を返している。
この関数は (+) だ!
(実際にはこう言うにはちょっと微妙だ。 計算を高速に実行するために OCaml は x86設計者が意図してないだろう方法、 x86のアドレッシングハードを用いている)
(訳注: ここは一見わかりやすい add 命令(普通の整数演算)でなく lea
命令(メモリ操作のためのアドレス計算を転用して演算する)
使っていることを指している。が、 もっと古い CISC マシンである
メインフレームでも lea 相当の命令(LA)で 加算をするのは普通なので、
x86 設計チームもこういう使いかたは知っているだろう。 実際に add も
lea も Pentium 以降は1サイクルで動作する最速動作の命令であり、
一命令で加算と定数減算をやっている lea 命令を使わない場合、 add
した後に別途1を引かないといけない (sub命令も必要)分遅くなるのだ)
それでクロージャに戻ると、 caml_curry2 の詳細には立ち入らないが、
このクロージャは関数(+)に引数2を適用したもので
二つ目の引数待ちであるといっている。予想ではあるが。
Array.map 関数の実際の呼び出しを理解するのはかなり困難だが、 上の
OCaml のテストコードから、コードの要点は:
Array.mapはクロージャを明示して呼び出す。- 関数呼び出しをインラインに展開したりループに変換したりしない。
この通り、確かに Array.map
の呼び出しは手で配列のループ処理を書くよりも遅い。 主なオーバーヘッドは
配列の要素ごとにクロージャを評価しているところであり、
クロージャーを関数のようにインライン展開するほど速くない
(この最適化が可能だったとして)。 だが、
((+) 2)より大きいクロージャならこのオーバーヘッドは小さくなるだろう。
関数型プログラミング版はまた、
命令型のループを書くより、高価なプログラマの時間を節約できる。
プロファイルの採取
OCaml プログラムに対して2種類のプロファイルのとりかたがある:
- バイトコードの場合、実行回数を取得する
- ネイティブコードの場合、本物のプロファイルを取得する
バイトコードの場合
ocamlcp と ocamlprof でバイトコードのプロファイルを計測する。
例を示す:
(* $ ocamlcp -p a graphics.cma graphtest.ml -o graphtest
$ ./graphtest
$ ocamlprof graphtest.ml *)
let () =
Random.self_init ();
Graphics.open_graph " 640x480"
let rec iterate r x_init i =
(* 12820000 *) if i == 1 then (* 25640 *) x_init
else
(* 12794360 *) let x = iterate r x_init (i-1) in
r *. x *. (1.0 -. x);;
let () =
for x = 0 to 640 do
(* 641 *) let r = 4.0 *. (float_of_int x) /. 640.0 in
for i = 0 to 39 do
(* 25640 *) let x_init = Random.float 1.0 in
let x_final = iterate r x_init 500 in
let y = int_of_float (x_final *. 480.) in
Graphics.plot x y
done
done(* nnn *) というコメントが ocamlprof が付け加えたもので、
そのコード部分が何回呼ばれたかを示している。
ネイティブコードの場合
ネイティブコードのプロファイルについては、 使っている OS
のプロファイラにネイティブ対応している。 Linux の場合 gprof を使う。
ネイティブコードのプロファイルの実例を示すにあたり、 エラトステネスの篩(元コード) で最初の3000個の素数を求める。 このプログラムはチュートリアルの範囲外のテクニックである stream と camlp4 を使っている。
let rec filter p = parser
[< 'n; s >] -> if p n then [< 'n; filter p s >] else [< filter p s >]
let naturals =
let rec gen n = [< 'n; gen (succ n) >] in gen 2
let primes =
let rec sieve = parser
[< 'n; s >] -> [< 'n; sieve (filter (fun m -> m mod n <> 0) s) >] in
sieve naturals
let () =
for i = 1 to 3000 do
ignore (Stream.next primes)
doneコンパイラに対して gprof のプロファイル情報を含めるよう、
コンパイル時に ocamlopt に -p オプションを積む。
ocamlopt -p -pp "camlp4o pa_extend.cmo" -I +camlp4 sieve.ml -o sieve普通にプログラムを走らせると、 プロファイル情報が gmon.out という
gprof 用のファイルに出力される。
$ gprof ./sieve
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
10.86 0.57 0.57 2109 0.00 0.00 sweep_slice
9.71 1.08 0.51 1113 0.00 0.00 mark_slice
7.24 1.46 0.38 4569034 0.00 0.00 Sieve__code_begin
6.86 1.82 0.36 9171515 0.00 0.00 Stream__set_data_140
6.57 2.17 0.34 12741964 0.00 0.00 fl_merge_block
6.29 2.50 0.33 4575034 0.00 0.00 Stream__peek_154
5.81 2.80 0.30 12561656 0.00 0.00 alloc_shr
5.71 3.10 0.30 3222 0.00 0.00 oldify_mopup
4.57 3.34 0.24 12561656 0.00 0.00 allocate_block
4.57 3.58 0.24 9171515 0.00 0.00 modify
4.38 3.81 0.23 8387342 0.00 0.00 oldify_one
3.81 4.01 0.20 12561658 0.00 0.00 fl_allocate
3.81 4.21 0.20 4569034 0.00 0.00 Sieve__filter_56
3.62 4.40 0.19 6444 0.00 0.00 empty_minor_heap
3.24 4.57 0.17 3222 0.00 0.00 oldify_local_roots
2.29 4.69 0.12 4599482 0.00 0.00 Stream__slazy_221
2.10 4.80 0.11 4597215 0.00 0.00 darken
1.90 4.90 0.10 4596481 0.00 0.00 Stream__fun_345
1.52 4.98 0.08 4575034 0.00 0.00 Stream__icons_207
1.52 5.06 0.08 4575034 0.00 0.00 Stream__junk_165
1.14 5.12 0.06 1112 0.00 0.00 do_local_roots
[ etc. ]このプログラムではガベージコレクタが時間を多く消費していることがわかる。 (驚くなかれ、このプログラムはエレガントだが最適化はしていない。 配列やループを使った方がはるかに速く動作するだろう)
まとめ
あなたの書くプログラムから最高の性能を引き出すための秘訣をここでまとめる。
- できるだけ単純にプログラムを書く。実行時間が長すぎる場合はプロファイルを取って時間のかかっているところを見つけ、その部分の最適化に注力すること。
- 意図していない多相型がないかチェックして、コンパイラに型情報のヒントをあたえる。
- クロージャは単純な関数呼び出しよりも遅いが、メンテナンス性と可読性は上がる。
- 最後の手段としてプログラムのホットスポットを C で書き直す(ただし、まず OCaml コンパイラが吐いたアセンブリ言語をチェックして、これ以上よくならないかどうか見直すこと)
- 性能は外的要因に依存しているかもしれない(データベースのクエリやネットワークの速度だったりしないか?)。もしそうならどんな最適化を施しても無駄だ。
もっと読む
OCaml の内部表現の違いについては マニュアルの18章(「Objective Caml と C
言語のインタフェース」
(OCaml.JPにある日本語訳))や
ヘッダファイル mlvalues.h を見るとわかるだろう。