1+1を計算するために、関数型言語を作ってしまった
Needed 1+1, built a functional programming language
データ構造の課題で1+1+1を二分木で評価する必要があった。評価器を作り始めたら、変数、クロージャ、ハッシュテーブル、アリーナアロケータ、チャンクアロケータ、そしてガベージコレクタまでC言語で実装することに。fib(40)が12GB以上のメモリを消費してOOMでクラッシュしたため、不要ノードを回収するGCの構築に踏み切った。
fib(40)はOOMでクラッシュする前に、文字通り12ギガバイト以上を消費した。なぜか？ 約13億個のノードを生成するからだ。ノードあたり48バイトとして、約62.4GB分のノード割り当てに相当する。
HNでの議論
75- CodesInChaos
Greenspunのプログラミングに関する第10の法則：
> 十分に複雑なCまたはFortranのプログラムには、その場限りの、非公式に仕様が決められた、バグだらけの、遅いCommon Lispの半分の実装が含まれている。
- tromp
> 全体として、私はグラフ還元エンジンを構築した
私は純粋関数型プログラミング言語BLC/BLC2の高性能実装でも同じことをした。それは400行以上で、コンビネータ論理のためのグラフ還元エンジンを含み、ラムダ計算のプログラムはKiselyovのブラケット抽象化アルゴリズムによって変換される。
- heronbank
共感できる。年に2回しか実行されない、誰も読まないレポートのためのクエリを1週間かけて最適化した。この沼は本当に深い。
- gnarlouse
これは数十年前を思い出させる…待って、私は3年前までまだコードを書いていた。
- Joker_vD
> 問題は、このメモリブロック内で全てのノードが互いを指していることだ。サイズを増やしてreallocすると、新しいメモリアドレスに移動する可能性がある。すると全てのポインタが完全に壊れてセグフォールトが起きる！この問題にどう対処する？
アリーナ配列へのインデックスを保存すれば？4バイトのインデックスを使えばメモリ使用量を削減できるかも…
> Fib(40)は文字通り12ギガバイト以上を消費してOOMでクラッシュした。なぜか？約13億個のノードを生成するからだ。
わかった、なら8バイトのインデックスを保持すればいい。
> 我々がちょうど完成させたマークアンドスイープガベージコレクタはストップ・ザ・ワールド方式だ。そして実行しているアルゴリズムは本質的に指数関数的だ。
ならコピーイングコレクタはどう？再帰的フィボナッチは大量のゴミを生成するが、IIRCではどの時点でもライブセットは実際かなり小さい。もし関数が本当に巨大なライブセットを持つ場合のGCのベンチマークが必要なら、こんな感じで
def garbage(n):
if n == 0:
return None
return (garbage(n-1), garbage(n-1))
うまくいくはず。適切なデータ構造がなければクロージャでかなり簡単にシミュレートできる。
> そしてfib自体の評価方法についても何とかできる
つまり「再帰的にASTを辿るのをやめる」か「非指数関数的なフィボナッチを書く」ということ？