sync.Map の他にも concurrent な hash map の実装はあって少ししらべてみると

というのがあった。　lrita/cmap　はベンチ取ると遅いしふつうにmutex しているので特に参考にならない。 cornelk/hashmap　はけっこうコンセプトが似ていて興味深い。というかこれは俺と同じようにやっていたら Split-Ordered Lists: Lock-Free Extensible Hash Tables　と同じに行き着いたのか、すでに知っていたのか わからないけど基本的なアルゴリズムは同じだ

  • key/value item は全部 doubly linked list でつないで全部単一のdoubly linked list でいてkey のhash 値でsort されている
  • bucket から　item への参照は　dummy item をいれる

という形だ。でも100000レコードを先に入れておいて取得するベンチを取ってみると

Benchmark_Map/skiplistmap4_w/_0_bucket=_16-16         	35947046	        38.25 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap4_w/_0_bucket=_32-16         	36800390	        36.61 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/hashmap______w/_0_bucket=__0-16         	20071834	        63.11 ns/op	      31 B/op	       2 allocs/op

けっこう差がでる。あとベンチではまだみてないがkey の追加が非常に遅い。(ベンチ前の初期化時間が圧倒的に長いので) 純粋にdoubly linked list の性能差がでてるのじゃないかなぁとおもった。 ざっと違いは

  • linked-list で deleted field をもっている
  • list の最小単位が異なる
  • shard によるlocality がない
  • value は直接もたずに unsafe.Pointer にしてるかどうか

という感じだ

それで cornelk/hashmap のlinked list を見ると

type List struct {
	count uintptr
	head  *ListElement
}
type ListElement struct {
	keyHash         uintptr
	previousElement unsafe.Pointer // is nil for the first item in list
	nextElement     unsafe.Pointer // is nil for the last item in list
	key             interface{}
	value           unsafe.Pointer
	deleted         uintptr // marks the item as deleting or deleted
}

こうなってる。一方 skiplistmap のitem は

type SampleItem struct {
	K interface{}
	V interface{}
	MapHead
}

type mapState byte

type MapHead struct {
	state    mapState
	conflict uint64
	reverse  uint64
	elist_head.ListHead
}
// from elist_head
type ListHead struct {
	prev uintptr
	next uintptr
}

大差はないのだけどいくつか異なっていて hashmap は value をunsafe.Pointer でもっているのはたぶん別の場所でvalue はまとめている (これはskiplistmap も後で改造したほうがいいかも)

linked-list で deleted field をもっている

insert の処理は

  1. 追加するエレメントの接続先の prev/next
  2. 前と後ろのelement の next/prev をcas でつながるまで繰り返す

という作りで変えようがない。

delete が異なっていて

deleted というfield があるということだ。これは削除marking 用で 削除にはいったら

func (l *List) Delete(element *ListElement) {
	if !atomic.CompareAndSwapUintptr(&element.deleted, uintptr(0), uintptr(1)) {
		return // concurrent delete of the item in progress
	}

まぁ1を立てている。立てられない場合は削除失敗という感じ、調べてみないとわからないけど、これはもしかしたら削除と追加が同時に 走ると壊れそうだがこれは map 用のlinked list なのでたぶん同時にエントリ削除は前提にしてないのだろう

skiplistmap では　　left <-> fordeleted <-> right という前提だとすると

  1. foredelete.prev/.next に marking で　|1 で立てる。
  2. left/right のprev/next を互いにcas で向ける
  3. 同時に連続したitem が削除することを考えて自分に向くポインタがなくなるまで待つ

ということをしている。そのため、skiplistmap では deleted field はいらない。struct としては MapHead.state という bucket の item かどうかの情報をもってるstate があるのでstruct としてのサイズは代わりないが、traverse していくときに　ListElement　のstruct 全体を 見続ける必要があるのと、　MapHead　は　 reverse/elist_head.ListHead だけでいいのでその差がでているような気がする。

linked list のlock free な add/delete を考えると list は delete では自分をいれて3個、add では2個ないと head かtail か特殊な処理がはいってしまう。実際に　cornelk/hashmap　は以下のようになってる。

func (l *List) insertAt(element *ListElement, left *ListElement, right *ListElement) bool {
	if left == nil {
		//element->previous = head
		element.previousElement = unsafe.Pointer(l.head)



func (l *List) Delete(element *ListElement) {
	if !atomic.CompareAndSwapUintptr(&element.deleted, uintptr(0), uintptr(1)) {
		return // concurrent delete of the item in progress
	}

	for {
		left := element.Previous()
		right := element.Next()

		if left == nil { // element is first item in list?
			if !atomic.CompareAndSwapPointer(&l.head.nextElement, unsafe.Pointer(element), unsafe.Pointer(right)) {
				continue // now head item was inserted concurrently
			}

これはlist の初期状態が head とtail のみの2つのterminater だけで構成されるのとは違う。というか、最初はlista_encabezado もそうだったが 全部初期状態は2element のlist に変えた。insert/add するものは単位tで問題ないので

type List struct {
	count uintptr
	head  *ListElement
}

type initedListHead [2]ListHead

// NewEmptyList ... make Empty List . this has only head and tail terminater.
//   elist_head require head/tail terminater for list operation.
func NewEmptyList() initedListHead {

	list := initedListHead{}
	InitAsEmpty(&list[0], &list[1])
	return list
}

この2つも大きな差になっている。 cornelk/hashmap　をみたおかげで skiplistmap もまだ改良の余地があって

  • value は interface{}　より unsafe.Pointer とかにして別で管理したほうがいい。(interface{}からの取り出しコストもある)どうせread では最後にしか使わないしね
  • MapHead.state を delete marking と完全に融合することで state field をなくす

ということをしたらもう少しパフォーマンスはあがりそうだ。後者のほうはtraverse 時に演算がはいってしまうので、むしろ遅くなるかもしれないが やってみる価値はあるかも。

他の実装をみることでやはりいろいろな知見は手にはいる。