EssenMemo0002 のバックアップ(No.15)

Essenの開発メモ#0002

(by K, 2017.04.24)

↑

進捗: 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値の衝突が起きないことを保証しているところである。だから内部ID値が一致すれば、中身は完全に同一である。
- a="abcdefg"; b="abcdef"; b+="g"; みたいに演算結果として値が一致した場合でも、aとbの内容のIDは一致する。だからこのケースでも比較は高速化される。
- 内容が一致したら、それらを別々にメモリにおいておく必要はないので、メモリ内では1つにまとめられる。だからメモリも節約される。

↑

進捗: 2017.04.28

高速に重複データを検出する仕組みはたぶんできた。まあ高速とはいってもO(log(N))オーダーではあるけど。ハッシュは特定の値の時にハッシュ値の衝突が起きるかもしれなくて、そうなったときに手におえないので、個人的に好きじゃない。
- ちなみに crit-bit tree を採用しています。

どんな言語を作るにせよ、とにかく得意技が一つは必要だ！さて、何を得意技にしようか・・・。

↑

進捗: 2017.05.08

crit-bit treeはとても良いデータ構造だと思うけど、やっぱりこれだけで全てをまかなおうとすると無理がある気がしてきた。
やはりskip-listを入れるしかないか・・・。

どんな二分木でも多分木でも、結局リスト構造には勝てない要素が一つだけあって、それは「キーのない順序付け」に対応できないということ。その順番を再現できるような適当なダミーのキーを作ることもできなくはないけど、すごく不自然になりやすい。

たとえばプログラムの要素はリストで表現される：

a = 1 + b   c = 3

element[0] = 'a'
element[1] = '='
element[2] = '1'
element[3] = '+'
element[4] = 'b'
element[5] = 'c'
element[6] = '='
element[7] = '3'

ここで1+bを演算して25だという値になったら、element[2～4]を削除して、代わりに'25'を入れてやらなければいけない。
この例の場合は要素が減るのであまり問題はないけど、もし要素が増える場合はどうか？要素が挿入できる回数に上限ができてしまったりはしないか。

で、じゃあskip-listなら問題なくできるのかというと、問題なくできる。
ちなみにskip-listならキーがあればキーの順番に並べることも可能なので、そういう意味では最強ではある。
でもなあ、乱数がうまくいかない場合は性能があまりよくない。つまり性能が悪くなる可能性はある。
その後、スキップリスト万歳な状況へ： EssenMemo0004

↑

進捗: 2017.05.12

まだコツコツとスキップリストを作っています。このスキップリストは、たぶんかなり優秀になるので、いろんなところで汎用的に使えそうです。

↑

進捗: 2017.05.17

スキップリストは多分できあがったと思います。簡単なテストもある程度やりました。今はNが小さいときに単純なポインタの配列で代用するようにしてさらに高速化する部分を実装中です。
[Q]そんな下位の部分ばかり作ってどうするの？肝心の言語部分を先に作ればいいのに。
[A]それは一理あるのですが、しかし高速な下位を先に作れば、上位を作るときは動作が速くてデバッグがはかどるわけですし、下位もたくさんテストされることになるのでより信頼性が増すのではないかと思うのです。

↑

進捗: 2017.05.20

スキップリストのバグが見つかって、一時はデバッグの先が見えなかったけど、デバッグ支援用の機能をいくつかつけて、既知のバグが全部とれましたー。
よしよし。

↑

進捗: 2017.05.23

任意のオブジェクトの完全ハッシュを求められるようになりました。まあ完全ハッシュと言っても何かすごい数式があるわけではなくて、メモリ上にオブジェクトのコピーを置いて、そのポインタを返しているだけです。ハッシュなので同じ値に対しては同じハッシュ値を必ず返します。
これで値は4バイトで保持できるようになったので、ここから変数管理システムを構築することになります。

↑

進捗: 2017.05.24

当初は、演算子を自由に作れるとか、構文を自由に作れることを中心に考えていたけれど、FastIndexができたらそっちも気になって、アルゴリズムとかデータ構造とか難しいことを考えなくてもそこそこ速い言語としてやっていけるかもしれないと思い始めました。
こういうことがあるから、下位から作るのはいいなーと思いました。

専用か汎用か
私は汎用を目指すと失敗するという考えを持っているものの、FastIndexはもしかしたら既存のデータ構造のいくつかを過去のものにできるかもしれないと思い始めています。つまりかなり汎用のデータ構造といえるのではないか、と。もしそうなら、どこまでできてどこが限界なのか、行けるところまで行ってみたいなと思いました。

↑

進捗: 2017.05.26

今、64bit対応をどうするかで悩んでいます。

まず、Essenが64bit対応すると、永続変数をたくさんメモリ上に置けるので、非常によくなります。
しかし一方で、64bit版は32bit環境しかない人は動かせないので、残念になります。逆に32bit版なら64bit環境でも動かせる・・・んじゃないかと思っています。少なくともWindowsではそうなのですが、きっとLinuxやMacOSでも同じですよね？？
まあ両方作ればいいじゃんと言われるとその通りなのですが・・・。
一方で、インラインC言語とかを考えると、64bit対応するのは結構しんどいです。32bitと64bitではオブジェクトファイルのフォーマットが違うので、それぞれ別々に開発しなければいけない・・・。
うーん、できることならひとまず32bitだけで進めてしまいたいけれど、それでみんな許してくれるかなあ。

↑

こめんと欄

コメント	お名前	NameLink