- 追加された行はこの色です。
- 削除された行はこの色です。
* Essen Object Management Library #0002
-(by [[K]], 2017.02.20)
** レイヤ構造
-Essen:言語レイヤ
--EOMLの範囲外
-ObjSys(OS) : オブジェクトの管理をするレイヤ
--階層構造など
-ValSys(VS) : 値の管理をするレイヤ
--可変長なデータを扱いやすくする&メモリ管理&重複管理
** 基本型
-通常データ:
--intとかdoubleとか文字列型とか、まあなんでも。
--サイズが規定できればよい。型のタイプも記述する。
--可変長でもあってもいい。
-メタデータ:
--通常データと似た扱いを受けるが、多少の追加サポートがある。
--(dir) (memberTable) (namelessDir)
** ディレクトリ
-Essenにおけるディレクトリは、構造体と配列を融合したようなもの。
-たとえば以下のようなデータを考える。
(a:1 b:2)
-このデータをシステムは以下のように管理する。
p0: (dir)[p1 p2 p3] // p1がメンバ名情報, p2とp3は値.
p1: (memberTable)[2 p4 p5] // 2はメンバ総数, p4とp5は名前.
p2: (int)[1]
p3: (int)[2]
p4: (string)["a"]
p5: (string)["b"]
** ValSys
typedef struct Val_ {
unsigned int linkCount; // プライベートの時は常に1
unsigned int hash;
unsigned int flags;
unsigned int siz, siz1; // siz1まではとりあえずメモリを確保してある
unsigned int mini[4];
struct Val_ *typ;
struct Val_ *link[2]; // 内部管理用であって、ObjSysやEssenはこれを使えない
void *p;
} Val;
-このとき、さらに以下のような記述をしたとする。
(a:3 b:1)
-このデータは次のように管理される。
p6: (dir)[p1 p7 p2]
p7: (int)[3]
--つまり、データは共有される
---ただしデフォルトで自動共有されるためには条件がある
---しかし明示的に共有を指示すれば確実に共有部分は共有される
---自動共有がデフォルトではない最大の理由は、重複排除のための比較にそれなりにコストがかかるため。
---もちろんハッシュ値などを使って高速化するが、それでも何もしないよりはどうしたって遅い。
-flags:
--VS_F_PUB : パブリック
--VS_F_MAL : pはmallocで確保した領域を指している(=解放時にはfreeしてほしい)
--VS_F_VHS : hashの値はvalidである
--VS_F_EXT : pは外部のメモリ域を指している(ValSysは寿命を管理しない)
--VS_F_RDO : リードオンリー属性
-さらに以下のようなケースを考える。
(0:(a:1 b:2) 1:(a:3 b:1))
-このデータは次のように管理される。
p8: (dir)[p9 p0 p6]
p9: (memberTable)[2 p10 p2]
p10: (int)[0]
-ただし、メンバ名が(int)で0,1,2,...の場合に限って簡略表現を用意したい。そうすればメンバーテーブルの氾濫を緩和できる。
-データの状態にはpriとpubがある。プライベートとパブリック。
--プライベートの時は、データを共有しないので値を直接書き換えてよい。最初にアロケートした時はプライベートになる。
--パブリックの時は書き換えてはいけない。書き換えたければプライベートに戻してから書きかえる。書き換え後にパブリックに戻してよい。
--プライベートだったデータをパブリックに切り替えるとき、Valのアドレスが変化する可能性がある。またパブリックだったデータをプライベートに切り替えるときも、Valのアドレスが変化する可能性がある。しかしそれ以外の操作でアドレスが変化することはない。
-メンバ名を持たないディレクトリも作れる。
((a:1 b:2) (a:3 b:1)) → (namelessDir) [2 p0 p6]
--まあそれぞれの名前をnulにしても同じことはできる。しかし出現頻度を考えると、内部的に(namelessDir)があったほうが有利だと思う。
** ObjSys
typedef struct Obj_ {
Val *val;
Val *parent;
unsigned int flags;
unsigned int sign; // シグネチャ これがあるから消されて再利用されたときに気付くことができる 常に非零
unsigned int linkCount; // 自分の子がこのObjを指している回数(子以外でもここを参照しているものがあれば数える)
unsigend int psign; // parentのsign
} Obj;
-(註)初期のバージョンのEssenでは双方向リストを使ってこれらを管理していたが、今後のバージョンではこのように双方向リストを使わない実装をメインに据える。
-flags:
--OS_F_DTY : データは改変された(これは必要だろうか?)
** 配列
-メモリをより節約したいという観点では、ディレクトリのメンバの型がすべて同じときには、それらをまとめられる機能がほしくなる。
--でもそんなことをしても大して節約できないのかもしれない。
--ということでまずは検討してみる。効果が大したことなければ没にする。
-p8の内容を書きかえてみる。
p11: (array) [p9 p1 p2 p3 p7 p2]
--これでどれだけ節約されたのか?
--p0やp6の内容はいらなくなった。それでオブジェクト2つが節約できた。ポインタの数としては差し引き3個得した。
--微妙だなあ。役に立っていると言えばそうなんだけど、内部タイプを増やすだけの価値があるかというと悩ましい。
-よし、悩んだときは作らない!
-Valはプライべートにするかパブリックにするかでアドレスが変わるので、それを解消するために用意されるレイヤがObjSys。Objのアドレスはその変数をdelするまでずっと変わらずに存在する。
--変数名を変更しても、変数のパスを変更しても(変数を別のフォルダに移動させても)、Objのアドレスは一切変わらない。
-ルート以外のObjは一つの親を必ず持つ。
-リンクカウントが0になってもObjを消さないほうが高速だろうと思われる。
--Objのメモリを節約する観点では、こまめに消したほうがいいのだが、Objを消す最大の目的はパブリックにさせるためなので、Objのメモリを節約することは考えなくていいと思う。
** サイズの省略
-(memberTable)でサイズを明示する必要ってあるだろうか?データのサイズは取得できるのだから、そこから分かりそうなものだ。
-(namelessDir)にもサイズは不要だろう。
** dir
(dir) {
[p(Val:typ)]
[n]
[p(Obj), sign]
[p(Obj), sign]
[p(Obj), sign]
...
}
-それぞれのsignが0のときは、ObjではなくValへのポインタになる。
-nはsignが0ではない個数。
--nが0になったら、パブリックにできる
--パブリックにしたら、親に対して「signを0にできますよ」と伝える。
** 双方向リストのサポート
-Essenの式評価アルゴリズムを考えると、要素の挿入や削除がかなり頻繁に繰り返されるので、双方向リスト的なものはやはり必要である。だからそのサポートも必要だ。
-双方向リストのノードは、前後が誰であるかという情報を持っているので、そのポインタ情報があだとなって値が同じでも共有はまずできない(=他と同じ値になることはまずないだろう)。
-となれば、値だけを別のオブジェクトに追い出すことによって共有の可能性を高めるという方法は可能ではある。
(doublyLinkedList) [p0 p1 p2]
--p0がprev, p1はnext, p2がvalueへのポインタ
-フラグがtyp側にあるといいかもしれない。
--メンバ名ソート済みフラグ、メンバ名ソート推奨フラグ、メンバ名のユニークを強制するフラグ
** メモ
-[1] 高速にdirをコピーしたい
--dirのポインタをすべてVal化してコピーすればよさそう(再帰的に)
--プライベートが含まれている部分についてはObjのままにして頑張って比較する
-[2] できるだけ高速にdirを比較したい
--Val化しているものに関しては、それより下が完全に同じなので中まで比較する必要がない。