skiplistmap の最適化その1でsyn.Map にほぼread でおいついたけど、まだもう少し ということで次は bucket の構造をすこしいじって最適化をさらにすすめてみた
bucketBuffer というのを作成してlinked list でレベルごとに管理してたのだけど level 1 -> level2
type bucketBuffer struct {
start *list_head.ListHead
last *list_head.ListHead
buf []bucket
max int
list_head.ListHead
}
考えなしで設計したからか、レベルが深ければ bucketBuffer.buf のサイズがでかくなる ( 16 -> 256 -> 4096 -> 65536) level4 ではもうメモリを食いすぎるので パフォーマンス的には 3 ぐらいにしないと出ない状態だった
単一のバッファにしたりいろいろ考えたけど slice のappend があると当然realloc があるからアドレスが変わるので bucket のlinked list がつながらなくなる。
もっと単純にbucketBuffer を廃止して、bucket 自体を拡張することにした
len int64
start *list_head.ListHead // to MapEntry
- downLevel *list_head.ListHead // to bucket.Levelhead
+ downLevels []bucket
LevelHead list_head.ListHead // to same level bucket
list_head.ListHead
下位バケットは常に 上限が16個だし必要なものしかはえない。 不要なときはからっぽにして必要になったら len が1 でcapacity 16 で作成して
if cap(b.downLevels) == 0 {
b.downLevels = make([]bucket, 1, 16)
bucket が不要になったら bucket.downLevels のbucket のlinked list をはずしてprev/next を全部自己参照にして b.downLevels[0] 以外が自己参照になったら消すみたいな作りにした。こすると 0x321 というkey で検索したい場合は
map.buckets[1].downlevels[2].downlevels[3]
みたいな感じでbucket 検索はできる。
多次元slice をつかって一撃で
map.buckets[1][2][3]
とかでもいいんだろうが具体的にはみてないけど多次元slice の場合はかならず、要素がSliceHeader
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
になってしまうので具合がよくなさそう。 もっとbit 演算でばしっとなりそうだが、それは更に先でやればいいかなと。
だいぶ linked-list なのか?感はあるけどなんだかん削除追加の利便性としてはslice とlinked-list の いいところどりはしたい concurrent に使うにも ということで更にベンチを取りました。
Benchmark_Map/mapWithMutex__________________w/_0_bucket=__0-16 17055374 69.39 ns/op 15 B/op 1 allocs/op
Benchmark_Map/sync.Map______________________w/_0_bucket=__0-16 25268019 42.00 ns/op 63 B/op 2 allocs/op
Benchmark_Map/skiplistmap___________________w/_0_bucket=_32-16 26189863 47.96 ns/op 15 B/op 1 allocs/op
Benchmark_Map/skiplistmap___________________w/_0_bucket=_16-16 32570624 44.40 ns/op 15 B/op 1 allocs/op
Benchmark_Map/skiplistmap3__________________w/_0_bucket=_16-16 36449119 40.41 ns/op 15 B/op 1 allocs/op
Benchmark_Map/RMap__________________________w/_0_bucket=__0-16 34806978 33.39 ns/op 31 B/op 2 allocs/op
Benchmark_Map/mapWithMutex__________________w/50_bucket=__0-16 3314656 364.6 ns/op 16 B/op 1 allocs/op
Benchmark_Map/sync.Map______________________w/50_bucket=__0-16 14289441 70.34 ns/op 134 B/op 4 allocs/op
Benchmark_Map/skiplistmap___________________w/50_bucket=_32-16 21370478 64.18 ns/op 27 B/op 2 allocs/op
Benchmark_Map/skiplistmap___________________w/50_bucket=_16-16 21110790 65.22 ns/op 27 B/op 2 allocs/op
Benchmark_Map/RMap__________________________w/50_bucket=__0-16 21455697 53.36 ns/op 72 B/op 4 allocs/op
!
!!!
!!!!!
Benchmark_Map/sync.Map______________________w/_0_bucket=__0-16 42.00 ns/op
Benchmark_Map/skiplistmap3__________________w/_0_bucket=_16-16 40.41 ns/op
read でsync.Map を越えました!
うぉおおおおおおおおおおおおおおおおおおおおおお!!!!!!!!
いまま iMac Pro で実装作業しててそこでみてたのですが。
ついでに新たに購入したAMD Ryzen 7 5700G な ubutun 環境だと
Benchmark_Map/mapWithMutex__________________w/_0_bucket=__0-16 41431610 28.34 ns/op 15 B/op 1 allocs/op
Benchmark_Map/sync.Map______________________w/_0_bucket=__0-16 50776604 23.00 ns/op 63 B/op 2 allocs/op
Benchmark_Map/skiplistmap___________________w/_0_bucket=_16-16 36047734 29.84 ns/op 15 B/op 1 allocs/op
Benchmark_Map/skiplistmap3__________________w/_0_bucket=_16-16 50611837 25.67 ns/op 15 B/op 1 allocs/op
Benchmark_Map/skiplistmap3__________________w/_0_bucket=_32-16 48226480 25.57 ns/op 15 B/op 1 allocs/op
Benchmark_Map/RMap__________________________w/_0_bucket=__0-16 55773645 20.60 ns/op 31 B/op 2 allocs/op
Benchmark_Map/mapWithMutex__________________w/50_bucket=__0-16 5165390 469.4 ns/op 16 B/op 2 allocs/op
Benchmark_Map/sync.Map______________________w/50_bucket=__0-16 29077965 40.88 ns/op 136 B/op 4 allocs/op
Benchmark_Map/skiplistmap___________________w/50_bucket=_16-16 27622237 43.30 ns/op 29 B/op 2 allocs/op
Benchmark_Map/skiplistmap3__________________w/50_bucket=_16-16 35663386 37.63 ns/op 27 B/op 2 allocs/op
Benchmark_Map/skiplistmap3__________________w/50_bucket=_32-16 31481182 37.29 ns/op 27 B/op 2 allocs/op
Benchmark_Map/RMap__________________________w/50_bucket=__0-16 37502930 31.29 ns/op 70 B/op 4 allocs/op
めっちゃはええな全然ちがうな! っていうのは置いておいて
Benchmark_Map/sync.Map______________________w/_0_bucket=__0-16 50776604 23.00 ns/op
Benchmark_Map/skiplistmap3__________________w/_0_bucket=_32-16 48226480 25.57 ns/op
あぁ… まだ負けとるやん….
ぐぐぐこの環境だとまだ負けてるんじゃが…
malloc の特性の違いとかかかな…
くやしいのでまだ続く
手がつきてきたので
- unsafe.Pointer 祭り
- item (key/value) の hash値の局所性を高めたallocation とかかなぁ(具体的にはbucket に持たせるとか?)具体的にtraverse するときはアドレス的に近いところを見に行くようにする。再配置とかもいりそう
というめんどくせえなぁ。たいへんだなぁ
みたいなのしか残ってない…