スタック消費量の測定
6-3. 継続渡し方式 に
インタープリタのスタック消費量を調べる課題があります。
ここでは簡易な方法として ocamlrun を用いた方法を紹介します。
以下の OCaml プログラムは、1 から n の整数の和を計算する関数 triangular と、
それを継続渡し方式で書いた triangular_cps を定義しています。
(* normal.ml *)
let rec triangular n =
if n = 0 then 0
else n + triangular (n - 1)
let () =
print_int (triangular (read_int ()));
print_newline ()
(* cps.ml *)
let rec triangular_cps n k =
if n = 0 then k 0
else triangular_cps (n - 1) (fun a -> k (n + a))
let () =
triangular_cps (read_int ()) print_int;
print_newline ()
ocamlc でこれらをバイトコードへコンパイルします。
$ ocamlc normal.ml -o normal
$ ocamlc cps.ml -o cps
ocamlrun を -v オプション付きで実行すると、ランタイムが管理するメモリに関する情報を
出力しながらバイトコードを実行することができます。
$ ocamlrun -v normal <<< 100000
Initial minor heap size: 256k words
Initial major heap size: 992k bytes
Initial space overhead: 120%
Initial max overhead: 500%
Initial heap increment: 15%
Initial allocation policy: 2
Initial smoothing window: 1
Initial stack limit: 8192k bytes
Growing stack to 64k bytes
Growing stack to 128k bytes
Growing stack to 256k bytes
Growing stack to 512k bytes
Growing stack to 1024k bytes
Growing stack to 2048k bytes
Growing stack to 4096k bytes
5000050000
$ ocamlrun -v cps <<< 100000
Initial minor heap size: 256k words
Initial major heap size: 992k bytes
Initial space overhead: 120%
Initial max overhead: 500%
Initial heap increment: 15%
Initial allocation policy: 2
Initial smoothing window: 1
Initial stack limit: 8192k bytes
Growing heap to 1472k bytes
Growing heap to 1952k bytes
Growing heap to 2432k bytes
Growing page table to 2048 entries
Starting new major GC cycle
5000050000
normal の実行では Growing stack to ... というメッセージが出力されており、
スタック領域が不足するたびにリサイズされる様子が観測できます。
cps の実行では Growing stack to ... は表示されておらず、
スタック領域のリサイズが起こっていないことが分かります。
これによって cps は normal と比較してスタック消費量が小さいことが確認できます。
注意
上記の方法は、coins の計算機にインストールされているバージョン 4.13.1 で動作確認をしています。 OCaml 5 ではうまくいかないようです。