なるほど、アロケータをSkipListの構築時に指定させて、削除はアロケータの削除時にまとめて消させるつもりなのね。これは賢い。後は一貫性を壊さないコンパクションがあれば最高に使いやすそう。
2011-05-17 16:27:4016M要素を入れるぐらいまでがちょうどよくなるようにハードコーディングされてる。パラメータ化しようと思えば簡単にできただろうにあえてそれをやらないのね。目的を絞ってるわけだ。>skiplist
2011-05-17 16:43:19そういえばLevelDBとTokyoCabinetは全然違うっぽいので,なんでTCが候補に挙がったのかが気になる.パフォーマンス以前の問題な気がするんだけどどど…
2011-05-17 17:57:02LevelDBのSkipListはレベル数の違いごとにノード単位で利用メモリを切り詰めてて好感持てる。placement newとか使ってるけどw
2011-05-17 18:02:01圧縮周りは未実装らしく、圧縮成功したかどうかをboolで返すところでとりあえずfalseを返してる。圧縮したい相手によって適切な圧縮アルゴリズムは変わりそうだ。
2011-05-17 18:04:00@kumagi_bot 圧縮はport_chroniumでは実装されてるので、GoogleとしてはChromiumで動けば十分ということでは。
2011-05-17 18:08:48何度読み返してもallocatorもskip listもlock-freeはおろかマルチスレッドreadyにも見えない。何故二分木やB木ではなくSkipListにする必要があったのかが今のところの謎。
2011-05-17 18:07:11@kumagi_bot あれ,"Only a single process (possibly multi-threaded) "ってあるけどマルチスレッドreadyじゃないの?
2011-05-17 18:09:31@repeatedly here since Insert() is externally synchronized. とか書いてあるように、levelDB側で外から排他してるのでskip listはlock-freeではない。という感じです。
2011-05-17 18:12:14search処理も何のことはなく典型的なシングルスレッドなSkipListっぽい。引数2つ取るのにコンストラクタにexplicitって書いてあるんだけどgoogleコード規約にそんなのあったっけな。でも全体的に読みやすそうなコード。
2011-05-17 18:19:40template<key,comperator>なくせに、コンストラクタ内部でNewNode(0/* anykey will do */,kMaxHeight)とか書いて初期化してる。0から最小キーへと暗黙変換できるkeyじゃないとダメっぽい。
2011-05-17 18:24:38んー。シングルスレッドのくせに何でlevelの保持にatomicな変数を利用しているのがわからん。同時アクセスしたらそもそも壊れるんじゃないかこのskip list
2011-05-17 18:46:46最大レベルの存在意義は検索の為か。検索処理はconstメソッドだからinsertと同時に走れる。マルチライターな状態にさえならなければ読み出しと書き込みは並列できる、と。これが二分木ではなくskiplistを利用した理由かな。断じてlock-freeではない。
2011-05-17 18:57:56arenaアロケータも素晴らしい。AllocateとAllocateAlignedとMemoryUsageしかない。free不可。消すときゃ全部消せという男らしい実装。
2011-05-17 19:56:57