結局自分で concurrent なmap を実装した

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 にもしたいしね