Essenの開発メモ#0002
進捗: 2017.04.24
- さあ今日からEssenの開発を優先してがんばるぞー。
- 今日は高速なmalloc/freeを書いた。どちらもO(1)。昨日の自作OSもくもく会で教えてもらったTLFSとは違うアルゴリズム（というかそれよりも格段に劣るアルゴリズム）。
- なぜ高速なmalloc/freeが必要なのかといえばEssenはmallocもfreeも多用するから。ここが遅いと泣ける。
- 次に作るのは変数の値を管理する部分。肝心の言語処理系は多分最後に作る。まずは変数をどうやって記憶するかの部分をきちんと作りたい。それができたら、それを操作するための言語として言語処理部を書けばいい。
- 予定では、a="abcdefg...vwxyz"みたいな26文字の文字列があったとして、b=aを実行してもメモリ消費量は26バイト増えるわけではない、みたいなものを想定している。そりゃ多少は増えるけど、それはデータの長さとは直接は関係ない。ただし内容が異なる場合は、普通にバイト数に比例して増える。
- 要するにポインタなんだろ、って言われると、まあ半分は正しい。でも、単純なポインタではないので、aの文字列を一部書き換えてもそれはbには影響しない。アルゴリズム的にはCopyOnWriteをやる。
- これができると何がうれしいか。
- 変数の値をコピーするコストは非常に低いので、気軽にコピーできる。CopyOnWriteをサポートしない言語では、大きなオブジェクトのコピーはそれなりに重いので敬遠されて、ポインタでがんばることになる。そしてポインタは（特に初心者には）難しいので、バグの温床になる。
- サイズの大きいオブジェクトはその内容に応じてID化されるので、比較が速い。ハッシュ値の比較みたいなものだと思えばいいが、ハッシュ値との違いは、ハッシュ値の衝突が起きないことを保証しているところである。だから内部ID値が一致すれば、中身は完全に同一である。
- a="abcdefg"; b="abcdef"; b+="g"; みたいに演算結果として値が一致した場合でも、aとbの内容のIDは一致する。だからこのケースでも比較は高速化される。
- 内容が一致したら、それらを別々にメモリにおいておく必要はないので、メモリ内では1つにまとめられる。だからメモリも節約される。
進捗: 2017.04.28
- 高速に重複データを検出する仕組みはたぶんできた。まあ高速とはいってもO(log(N))オーダーではあるけど。ハッシュは特定の値の時にハッシュ値の衝突が起きるかもしれなくて、そうなったときに手におえないので、個人的に好きじゃない。
- ちなみに crit-bit tree を採用しています。
- どんな言語を作るにせよ、とにかく得意技が一つは必要だ！ さて、何を得意技にしようか・・・。
こめんと欄
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
