skiplistmap の最適化その3 の続きだ。

たぶんアルゴリズム的にできることはたぶんこれでほぼやりきった感じだ

skiplistmap の最適化その3 で hash値が近い値を Pool で格納することで局所性をあげた

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

そもそもだったらこいつを bucket にぶら下げてしまえばいいのでは? といことだ。

  • bucket に samepleItemPool をぶら下げる
  • samepleItemPool.items を hash 値順にいれる

その結果

  • 同一bucket を探索するやつはその中のitem のみをみるので 局所性がある
  • bucket 内の探索がslice になるので slice の検索になる。ふつうにbinary search できる

という効用がある。とくに後者はいままでliked list を順番に探索していたので、bucket にぶら下げるアイテムの 数が 32 ぐらいが一番よかったがもうすこし大きくできる。

単純にやってしまうと当然 samepleItemPool.items への追加がconcurrent にならない

一番の問題はappend だ。けどsamepleItemPool は lock free な linked list なので 差し替えてしまえばいい。(linked list 的にいえばふつうのinsert だ) capacity が限界になるまでは そのまま追加していって、しまえばいい、items 内の削除は基本的には free list にうつしてしまって 本当に削除したいときは reflect.Swapper で cap のうしろにもっていしまえばいい。ふつうは同一のbucket に 追加というのはあまりないので、write 時だけ samepleItemPool をlock してしまうという手もある

ということで前回までのチューニングと比較すると

goos: darwin
goarch: amd64
pkg: github.com/kazu/skiplistmap
cpu: Intel(R) Xeon(R) W-2140B CPU @ 3.20GHz
Benchmark_Map/mapWithMutex_w/_0_bucket=__0-16         	16501183	        74.58 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/sync.Map_____w/_0_bucket=__0-16         	22049899	        50.48 ns/op	      63 B/op	       2 allocs/op
Benchmark_Map/skiplistmap4_w/_0_bucket=_16-16         	34046280	        48.22 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap4_w/_0_bucket=_32-16         	33678469	        44.03 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap5_w/_0_bucket=_16-16         	38717077	        32.81 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap5_w/_0_bucket=_32-16         	49338645	        30.14 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap5_w/_0_bucket=_64-16         	39260758	        31.41 ns/op	      15 B/op	       1 allocs/op

macos だと3割もはやくなった!

linux/ryzen マシンでも

goos: linux
goarch: amd64
pkg: github.com/kazu/skiplistmap
cpu: AMD Ryzen 7 5700G with Radeon Graphics         
Benchmark_Map/mapWithMutex_w/_0_bucket=__0-16         	42378322	        28.41 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/sync.Map_____w/_0_bucket=__0-16         	50100085	        22.68 ns/op	      63 B/op	       2 allocs/op
Benchmark_Map/skiplistmap4_w/_0_bucket=_16-16         	49729155	        23.54 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap4_w/_0_bucket=_32-16         	46195608	        22.92 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap5_w/_0_bucket=_16-16         	70823242	        17.09 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap5_w/_0_bucket=_32-16         	70995069	        16.16 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap5_w/_0_bucket=_64-16         	66454374	        16.46 ns/op	      15 B/op	       1 allocs/op

そんくらいはやくなった。

上でやった slice を linked list でつなげるのはいろいろ有用そうなのであとで公開します。