bytes ではなかった

解凍器は、コンパイルが通ると正しいバイトを印字した —— そして一つの誤った数を。1 メガバイトの ファイルの展開に 484 メガバイトのメモリを使った。bytes アーク全体がある設計の問いへ積み上がって いた: 言語に本物の bytes 型は要るか、バイナリデータを 1 格納バイトにつき 8 バイトの int vector で 表現していたのだから。484 はその答えが請求書として届いたように見えた。違った。この話は、数を もっともらしい原因でなく実際の原因まで追い、もっともらしい方が完全に無罪だと分かる話だ。

3 つの測定

効いた規律は、容疑者を確認する前に直すのを拒んだことだ。測定 1: 100 万個の整数を vector に push するだけのループ、他は何もなし —— 17 メガバイト。これが 8 バイト/int の表現に倍々バッファの 残りを足したもので、このスケールでの byte 表現の全コストだ。484 メガバイトを食っていたのが何で あれ、int の vector ではなかった。測定 2: 解凍器のホットパスの形をした最小プログラム —— 4 引数 カリー化 inner 再帰関数を 100 万回呼ぶ —— 769 メガバイト。そこにあった。測定 3、確認: 同一の 計算を、inner 関数が 4 つのカリー化引数でなく単一 tuple 引数を取る形にする —— 1.4 メガバイト。 500 倍の差、そして唯一の変数はカリー化だった。bytes は無罪、犯人は関数の形だった。

言語の半分にしか届いていなかった uncurrying

機構は、名前がつけば明快だった。カリー化関数 fn a -> fn b -> fn c -> fn d -> ... を 4 引数 全部に適用するのは、下では 4 つの適用だ: 各々が 1 引数を供給し、それを閉じ込めた新しい関数を 返す。top-level 関数についてはコンパイラが、以前の話以来、uncurried な双子 —— 全引数を一度に 取る単一関数、呼び出し地点が全部一度に供給するときに使い中間 closure を飛ばす —— を emit して きた。inner（ネスト）関数はその扱いを一度も受けていなかった。だから解凍器の Huffman デコーダ、 シンボル毎に一度呼ばれ各呼び出し内で数回再帰する 4 引数 inner 再帰関数は、部分適用ごと・再帰 ステップごとに region から新しい closure 環境を alloc し —— そして region は、bump アロケータで、 決して解放しない。1 メガバイトの出力は数百万シンボル。closure が数百メガバイトに積み上がった。

修正は uncurrying を inner 関数に拡張する: 具体的な引数型を持つカリー化 inner 関数はいまや同じ direct 双子を得て、飽和呼び出し —— 決定的に、関数自身の body 内の再帰自己呼び出しを含めて —— がそれを使い、closure alloc なし。単一引数の closure 形は稀な部分適用のために残るので、変更は additive だ。測定: 100 万反復の microbench は 769 メガバイトから 1.46 へ —— tuple 書き換えの数を、 何も書き換えずに達成 —— そして解凍器は 484 メガバイトから 34 へ、チェックサム検証つきで byte 単位に同一の出力を出したまま。bytes 型を秤にかけに出たアークは、メモリが bytes と何の関係も 無かったと分かって閉じた。それが本当に訊いていた設計の問いは、2 つ前の機能で、top-level 関数に だけ、既に答えられていた。dogfood の貢献は、言語のもう半分が同じ答えを要すると示したことだ。 次の Part が何を測るかは、いつものように未定 —— 本物のプログラムが指し示す。