Ribbon: C++をSchemeにする(準備)
okuokuとりあえず、Schemeで書いたVMでSchemeのプログラムが実行できるところまでは来た。というわけで適当にVMを移植してみて単体動作するようにしたい。
まぁC++かな。。
C++はほぼScheme(迫真)
C++にはSchemeを作るのに必要なものがだいたい揃っている。
- GC -- スマートポインタがある(スマートポインタはGCと呼ばないことが多いが)
- 動的型 -- RTTIとDynamic cast
- UTF-8文字列
ただ、単純なスマートポインタは循環参照によってメモリリークさせられるため、 アロケーションした全てのGCオブジェクトをリンクリストで繋ぎ たまに全オブジェクトを巡回して循環参照が無いか検出する必要がある。この方式はPythonやPHPが採用している。
(現在のPythonはGC中は双方向リンクリストの prev 側を潰してGC用のrefcountとして再利用することで、リンクリストによるオーバヘッドを2 wordに抑えている)
- http://www.narihiro.info/translate/garbage_collection_for_python_jp.html -- 3ワード時代の解説(2000年、Python 2.0でここで説明されているgcが入った)
GCアルゴリズム
↑ の3ワード時代のアルゴリズムを実装する。これは4パスのアルゴリズムで、以下のようになる:
| 変数 | 内容 |
|---|---|
prev |
前のオブジェクト |
next |
次のオブジェクト |
gc_ref |
GCのrefcnt |
ref |
スマートポインタのrefcnt |
- 全てのオブジェクトの
gc_refをrefに初期化する - 全てのオブジェクトをスキャンし、
gc_refを参照のぶんだけ減算する -
gc_refがゼロになっていないオブジェクトと、そのオブジェクトから指されているオブジェクトをリンクリストから外す - リンクリストに残ったオブジェクトはどこからも参照されていないので削除する
この "全てのオブジェクト" が本当に全てのオブジェクトでなければならないということはない。実際、Pythonは一度GCから生き残ったオブジェクトは別のリストに繋いでgenerational GC(世代別GC)としている。
このアルゴリズムの対象になるのは、いわゆるコンテナオブジェクト(他のオブジェクトを指す可能性があるオブジェクト)だけで良い。例えば、文字列やbytevector(JSで言うところのBuffer)は他のオブジェクトを指すことが無いので、単純な参照カウントだけでリークを防ぐことができる。
okuoku型/クラスの設計
- 数値型(64bits)
- 0: singletonなオブジェクト(true / false / eof-object / nil)
- 1: 整数(常に符号付)
- 2: 浮動小数点数(double)
- 3: 文字
- オブジェクト(参照カウントされる)
- 5: 非コンテナオブジェクト
- String
- Bytevector
- 6: コンテナオブジェクト(GCされる)
- HashTable
- Rib
- Vector
- 5: 非コンテナオブジェクト
更に Value 型を用意し、スタック上にこれらの値または参照を保持できるようにする。浮動小数点数で64bitフルに必要になってしまうので、 Value 型は64bit値とその値の解釈を示すIDの両方を保持する必要がある。 ... って事はRTTI要らないじゃん。。あるいは Value の派生クラスを作ってそれで型を表現するか。。
... 実際に派生クラスで型を表現しようとすると、デストラクタを virtual に置くことになるので確実にvtblができてスタックを余計に消費することになる。まぁ後で真剣な実装を作るときの楽しみが減るから、今回は派生クラス -- いわゆる動的ポリモーフィズムで実装してみようかな。。
okuokuそもそもGCライブラリを評価しないのか
うーん。。BoehmGCとかOlipanのような有名どころは見た方が良いのか。。？
まぁパフォーマンスを気にしなければ(大問題)GCなんて一日で書けるので一旦は完全自作をコンセプトに作ってから考えても良いかもしれない。 ...であれば一旦はCで書くべきか。。
GitHubを適当に検索するだけでも色々ある。
MMTkはRustに転向したようなのでRust版を作るときに検討することにしよう。。この中だとuGCが面白そうかな。