go のmap と戦ってみたの後、やはり linked listで作成した dirty の探査が遅い という問題がある。
まぁhash table を自分で実は実装したことがないので、やってみようということでやってみた。
まずは Hash関数だけどこれはgo のruntime を呼び出してやるよくやるやり口だ
//go:noescape
//go:linkname memhash runtime.memhash
func memhash(p unsafe.Pointer, h, s uintptr) uintptr
func MemHash(data []byte) uint64 {
ss := (*stringStruct)(unsafe.Pointer(&data))
return uint64(memhash(ss.str, 0, uintptr(ss.len)))
}
func MemHashString(str string) uint64 {
ss := (*stringStruct)(unsafe.Pointer(&str))
return uint64(memhash(ss.str, 0, uintptr(ss.len)))
}
func KeyToHash(key interface{}) (uint64, uint64) {
if key == nil {
return 0, 0
}
switch k := key.(type) {
case uint64:
return k, 0
case string:
return MemHashString(k), xxhash.Sum64String(k)
case []byte:
return MemHash(k), xxhash.Sum64(k)
case byte:
return uint64(k), 0
case int:
return uint64(k), 0
case int32:
return uint64(k), 0
case uint32:
return uint64(k), 0
case int64:
return uint64(k), 0
default:
panic("Key type not supported")
}
}
hash 値から実際のアイテムを参照するような作りでやるとして
ふつうにやる感じだと
こういう感じで bucket(table) ごとにlinked list をもってやる。 bucket 自体もlinked list にしてしまえば bucket もlock free(concurrent) にできるし しかし実装するのにbucket ごとにlinked list というのもめんどくさい
なので item は単一のlinked list にしてbucket からの参照用のdummy のitem を追加すれば linked list 自体は 2本ですむ。
でもこれでも結局 bucket 自体は線形探索だし、たとえば 下位1バイトでbucket を作るにしても 数が多くなるとbucket にぶら下がってる部分は線形探索だ
それならbucket を16とかじゃなくてもっと増やせばいいわけだけどそうするとまた単純にそれだとbucket の探査がつらいなので下位から何byte 目までをみてるかでそれをlevel にして 検索するようにしてみた
type Map struct {
buckets bucket
lastBucket *list_head.ListHead // bucket の最後
len int64
maxPerBucket int
start *list_head.ListHead //key/value item の最初
last *list_head.ListHead // key/value item の最後
modeForBucket SearchMode
mu sync.Mutex
levelCache [16]atomic.Value // buckets level のcache uint64 なので1バイトごとで16段階
ItemFn func() MapItem
}
type bucket struct {
level int
reverse uint64
len int64
start *list_head.ListHead // bucket のdummy/empty item へ
LevelHead list_head.ListHead // 同レベルの bucket へ接続
list_head.ListHead // 次のbucket
}
hash 関数によってhash 値は平坦化されるし、実質平衡skip list みたいになった おれすげえ天才じゃねぇか とおもったらこんな俺のような浅はかな思いつきは世の中に存在するらしく Split-Ordered Lists: Lock-Free Extensible Hash Tables まぁ、ふつうに思いつくよなと思いながら、論文ですでにあるというのはそれなりに妥当な手法を 選んだわけでということにしておく。
ついでに実装物は skiplistmap においておいた。
補足
level bucket のあたりで疲れはじめて、そこはけっこう適当でずるしてる。 bucket は直接下位への直接参照をしてないので たどっていくのだけど、そこをちょっと速くしようとして
Map に map.levelCache をもっている。これは全level のbucket のいちを記録してるのだけど 探索時には
func (h *Map) searchKey(k uint64, ignoreBucketEnry bool) HMapEntry {
// ... 略
levels := [16]*bucket{}
実は
levels := make([]*bucket, 0, 16 )
とか
levels := make([]*bucket, 16)
とかしても heap をつかってしまうので結局slice 使わないで固定長のarray になってたりする。 もうちょっと調査してなんとかしたい。もっと byte 単位じゃない粒度の細かい level にもしたいしね