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