結局自分で concurrent なmap を実装した で実装したskiplistmap だけどだいたい機能はそろった。
最適化の時間です!.
とりあえずベンチとると
read only でsync.Map の100倍ぐらい遅い。 (map[uint64]atomic.Value に比べて)
linked-list の traverse が遅い
最近は vscode からもかんたんにpprof とか呼べて素晴らしい。まず list_head.LinkedList.Next() が 糞重いのが判明
理由としては traverse mode が以下のようになってたけど
- DirectMode head.next をいきなりたどる
- WaitNoMark delete marking 用に busy loop
- SkipMark marking されたやつの外したと過程して、先にすすむ主にmarking 後の後処理用
func (head *ListHead) Next(opts ...TravOpt) (nextElement *ListHead) {
mode := ModeTraverse{t: TravDirect}
for _, opt := range opts {
opt(&mode)
}
err := retry(100, func(retry int) (exit bool, err error) {
nextElement = head.DirectNext()
var DefaultModeTraverse *ModeTraverse = &ModeTraverse{t: TravDirect}
func (head *ListHead) Next(opts ...TravOpt) (nextElement *ListHead) {
mode := DefaultModeTraverse
//return head.next
defer mode.Error()
for _, opt := range opts {
//opt(&mode)
opt(mode)
}
if !head.Empty() && mode.Mu != nil {
mode.Mu(head).RLock()
defer mode.Mu(head).RUnlock()
}
こういう感じあと後ろについてるretry もこれのおかげでinlie にらなないので
func (head *ListHead) Next(opts ...TravOpt) *ListHead {
//return ListPrev(head, opts...)
return ListNext(head, opts...)
}
func ListNext(head *ListHead, opts ...TravOpt) *ListHead {
if len(opts) > 0 {
DefaultModeTraverse.Option(opts...)
//defer DefaultModeTraverse.Option(prevs...)
}
switch DefaultModeTraverse.t {
case TravDirect:
return nextDirect(head)
case TravWaitNoMark:
return nextWaitNoMark(head)
case TravSkipMark:
return nextSkipMark(head)
}
return nextDefault(head)
}
こうしてモードごとに別の関数にした まぁretry をはずしたおかげもあり、 まずinline 化されて functional option のlambdaを毎回呼ぶのも抑制した。
functional option でやっているが毎回指定するとやはり遅い
func (head *ListHead) DirectNext() *ListHead {
return head.next
}
これの 1.5倍程度までには落ち着いた。 まぁ俺が適当すぎるよ!ってことですね
bucket を16個固定なので item(key/value) の数が多いと線形探索が多い
とりあえず key のhash の下位1バイトで 16個のbucket を固定長にして
type Map struct {
buckets [16]bucket
}
とかにしてたがやはり数が多いと線形探索になってそこが遅い
bucket を可変長にして linked list をbinary search
type bucket struct {
level int
list_head.ListHead
}
でlinked list にして可変長にしてみたがはやりbucket 間のitem を探すのは面倒 sort されてるとはいえ やはり linked list で単純にbinary search は無理がある。かといって 単純にskip list element にするのはつらい。binary search にすることで3割ぐらいは向上
bucket をlevel制に
- level=1 0x0 … 0xf
- level=2 0x01 … 0xff
- level=3 0x001 … 0xfff
みたいなlevel bucket にしてみた
type LevelHead list_head.ListHead
type bucket struct {
level int
down *LevelHead
LevelHead
list_head.ListHead
}
こうやって 同一レベルのbucket は LevelHead で すべてのbucket の linked list は bucket.ListHead でみていくという作りにした で下位レベルへのポインタ
down を追加
LevelHead は
0x1 <-> 0x2 <-> 0x3
みたいにつないで down で
0x1 -> 0x11
とかでつないだ
traverse を試行錯誤
すこしでもbucket の探索をはやくしようと 進んだりもどったりで最適化 この時点でどうにか sync.Map の2倍ぐらいの処理時間になる
bucket buffer を導入
やはり bucket を全部 linked list でつないでたどっていうのはそれなりにつらい ということでそもそも bucket は上位レベルであればあったままでも構わないので
type bucketBuffer struct {
bufs []bucket
list_head.ListHaad
}
でつくって とりあえず 1level ごとに ひとつで3つつくって (buffer は 16, 256, 65536) level3 を使うとかなりでかいがそのときははっきりいってすでに 65536個以上のelement があるので 問題ない
ついでに bufs[] は全部 添字アクセスできるので level=3 だとしたら buf[0xf13] とか bucket のlevel3 の探索コストがかなり下がる
てことでここまできて
こういう結果になりました w というのは処理のwrite の割合
- mapWithMutex map で read 時は RWMutex.RLock 書き込み時は Lock()
- sync.Map
- RMap sync.Map のdirty だけ skiplistmap にしたのもの bcuket=16 とかは最下位bucket ごとにぶら下がってる element の数,線形探索数の限界
Benchmark_Map/mapWithMutex__________________w/_0_bucket=__0-16 17338737 73.84 ns/op 15 B/op 1 allocs/op
Benchmark_Map/sync.Map______________________w/_0_bucket=__0-16 24670666 45.57 ns/op 63 B/op 2 allocs/op
Benchmark_Map/skiplistmap___________________w/_0_bucket=_32-16 25320975 45.63 ns/op 15 B/op 1 allocs/op
Benchmark_Map/skiplistmap___________________w/_0_bucket=_16-16 32241116 47.67 ns/op 15 B/op 1 allocs/op
Benchmark_Map/RMap__________________________w/_0_bucket=__0-16 37374686 33.79 ns/op 31 B/op 2 allocs/op
Benchmark_Map/mapWithMutex__________________w/50_bucket=__0-16 3231487 364.0 ns/op 16 B/op 1 allocs/op
Benchmark_Map/sync.Map______________________w/50_bucket=__0-16 15917422 71.63 ns/op 133 B/op 4 allocs/op
Benchmark_Map/skiplistmap___________________w/50_bucket=_32-16 21050286 64.47 ns/op 26 B/op 2 allocs/op
Benchmark_Map/skiplistmap___________________w/50_bucket=_16-16 22411369 58.43 ns/op 26 B/op 2 allocs/op
Benchmark_Map/RMap__________________________w/50_bucket=__0-16 21543603 59.90 ns/op 71 B/op 4 allocs/op
read はほぼ sync.Map(の map[uint64]atomic.Value) にならんだ、write はついに最速です。