skiplistmap の最適化その2 で最後にでてきてしまった linux/ryzen な環境だと まだ負けているということなので更にかけようとしたら、あまり手を掛けないのは難しい

トップバケットごとの item pool

バケットは hash 値の下位1バイトで現状振り分けてあるわけだが、 実質アイテムを探索するにはその範囲でしか探索しない。

ということで　heap にあるのはしょうがないとしてそこでのアドレスを近くする+トップバケットごとに goroutine で実質別thread に近いかたちでその中でallocation することで 局所性をあげてCPU のキャッシュにやさしくならないかなぁと考えた

goroutine とのやり取りがでてくるとchan を経由するので lock free ではないよねというのはありつつ とりあえずどんな感じか様子をみるために chan でやりとりする前提で実装してみた

type Pool struct {
    ...
	itemPool [cntOfPoolMgr]samepleItemPool
	mgrCh    [cntOfPoolMgr]chan poolReq
}

type poolReq struct {
	cmd       poolCmd
	item      MapItem
	onSuccess successFn
}

type samepleItemPool struct {
	freeHead elist_head.ListHead
	freeTail elist_head.ListHead
	items    []SampleItem
	list_head.ListHead
}

相対アドレスな linked list

結局実際のアロケーションが追加するたびにふえていくと そのときにアロケーションしたものは 以前とアドレスが遠くなる.

そのため samepleItemPool.items でslice で確保してそれを増やしていくという形にした でもslice は当然append は concurrent じゃないので工夫がいる

けどslice を増やしたら items のアドレスも変わるので 参照先を全部治す ということになる。それはさすがコストが高すぎるということで

lock free linked list の slice に埋め込んで使う用に next/prev を相対アドレスをいれるタイプの

elist_head というのを用意した、しかし当然相対アドレスだとGCが捕まえられないので本体はslice とかに いれるということでしか使えない。

こうすることでほとんどのものは　samepleItemPool.items 内で相互に参照するので ほとんどのものは書き換えはいらないですむようになる

samepleItemPool.items の拡張を conccurent に

samepleItemPool 自体もlinked list なので　増えていったらsamepleItemPoolを追加してlinked list としてつなげていく というアプローチもある。 しかし、それだと同一のsampleItempool にいるやつだと局所性は確保できるがことなるsampleItemPool 同士だと allocation したタイミングによる。実質Set したのが近いタイミングのものだけ局所性が確保される。 そして、それだと探査の歳にhash key をひっくり返した値を順序にたどっていくと 異なるsampleItempool 間を行き来することになる。

ということで sampleItemPool.items をappend で拡張していくのだが 単純に拡張したら当然 concurrent にならない

拡張時に　samepleItemPoolのcopy をつくってそこに追加していくという振る舞いにした

1. まず古いやつをdelete marking
2. copy をつくて prev/next を向ける
3. cas で　つなぎ直す

linked list のinsert/delete なのでふつうにlock free で動作する。 現状は一つのtop bucket は一つのgouroutine からしか操作もない。 多重に操作ができた場合に当然　同一のcopy したpool ができるわけだが どちらかが必ず後になるので、今回は何もしてないが先に追加したほうを削除すればいい

ということで linux/ryzen マシンでもベンチを取る

いったんread だけ

Benchmark_Map/mapWithMutex__________________w/_0_bucket=__0-32         	41051881	        29.09 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/sync.Map______________________w/_0_bucket=__0-32         	42438818	        24.15 ns/op	      63 B/op	       2 allocs/op
Benchmark_Map/skiplistmap4__________________w/_0_bucket=_16-32         	48874389	        24.69 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap4__________________w/_0_bucket=_32-32         	49224477	        23.23 ns/op	      15 B/op	       1 allocs/op
PASS
ok  	github.com/kazu/skiplistmap	7.348s

とりあえずsync.Map を無事上回りました。実は bucket のdummy node がbucket 側にあってその参照がけっこうアドレスジャンプしてlocality はアレな可能性はある そのため、bucket のmax が32 のほうが結果がいいのはそのあたりかもしれない。(linked list 自体もelist_head のほうがtraverse は性能がいい)

linux だとlock が軽い

imac pro/Xeon な環境だとlock のありなしで1.8倍ぐらい違うのだが、linux/ryzen のマシンだと実は大した差ではない。別にmutex 使えばよくね みたいな気分にはなって本末転倒ではある。

それだけ linux のfutex が優秀なのかな