Gradually, Go generics are being used more and more in Go’s standard library. Some standard library types such as container/heap, container/list, container/ring and math have the opportunity to support generics, but given Go’s backwards compatibility, these packages will probably not be modified directly, but will most likely be new concurrent packages, or placed in extension packages.
This article will cover a relatively complex example, a modification to sync.Map that allows it to support generics.
Find the variable and change it to a type parameter
sync.Map is a map, so it follows the K-V mapping relationship of a map. The key is a type that can be compared for equality checking, and the value is an arbitrary type. sync.Map has keys and values of type any, but the keys are actually of type comparable for this to work. The following code will compile, but will run with an error.
1
2
3
|
var m sync.Map
key := func() {}
m.Store(key, "value")
|
The type of the key and the type of the value are variables that can be changed to type parameters, so we start with these two variables and change them to type parameters.
The standard library mainly uses two map objects for storage in read and dirty data, so we create these two map objects using type parameters.
The entry is also changed to a generic support.
sync.Map in the standard library
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
type Map struct {
mu Mutex
read atomic.Pointer[readOnly]
dirty map[any]*entry
misses int
}
type readOnly struct {
m map[any]*entry
amended bool
}
var expunged = new(any)
type entry struct {
p atomic.Pointer[any]
}
|
sync.Map with generic support
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
type Map[K comparable, V any] struct { // Define K,V type parameters
mu sync.Mutex
read atomic.Pointer[readOnly[K, V]] //readonly also supports generics, as it also uses a map internally
dirty map[K]*entry[V] //map converted to generic
misses int
}
type readOnly[K comparable, V any] struct {
m map[K]*entry[V] // Change this to a generic
amended bool
}
var expunged = unsafe.Pointer(new(any)) // A special mark for the deleted value
type entry[V any] struct {
p atomic.Pointer[V] // Generic types, atomic.Pointer supports generic types
}
|
Basically we have changed the types associated with sync.Map to types that support generic types with a few modifications.
After the relevant type has been transformed to support generics, compilation will fail because the relevant method will also need to be modified.
Generic functions such as newEntry The exception message prompted by the compiler or editor says that entry is generic and we change it to generic based on this prompt.
1
2
3
4
5
|
func newEntry[V any](i V) *entry[V] {
e := &entry[V]{}
e.p.Store(&i)
return e
}
|
In the generic method we change the type of Receiver to Map[K, V], preferably replacing (m * Map) with all of them. The return value readonly is also changed to the definition of the generic type.
1
2
3
4
5
6
|
func (m *Map[K, V]) loadReadOnly() readOnly[K, V] {
if p := m.read.Load(); p != nil {
return *p
}
return readOnly[K, V]{}
}
|
The next step is to modify the Load method by changing the Key and Value types from any to K,V parameters.
A small problem here is that the source standard library may return a nil value, we need to change this to return a zero value of type V; there are three ways to create a zero value of type V, we use var zero V to create the zero value.
sync.Map in the standard library
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
func (m *Map) Load(key any) (value any, ok bool) {
read := m.loadReadOnly()
e, ok := read.m[key]
if !ok && read.amended {
m.mu.Lock()
// Avoid reporting a spurious miss if m.dirty got promoted while we were
// blocked on m.mu. (If further loads of the same key will not miss, it's
// not worth copying the dirty map for this key.)
read = m.loadReadOnly()
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key]
// Regardless of whether the entry was present, record a miss: this key
// will take the slow path until the dirty map is promoted to the read
// map.
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
return nil, false
}
return e.load()
}
|
sync.Map with generic support
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func (m *Map[K, V]) Load(key K) (value V, ok bool) {
read := m.loadReadOnly()
e, ok := read.m[key]
if !ok && read.amended {
m.mu.Lock()
read = m.loadReadOnly()
e, ok = read.m[key]
if !ok && read.amended {
e, ok = m.dirty[key]
// Regardless of whether the entry was present, record a miss: this key
// will take the slow path until the dirty map is promoted to the read
// map.
m.missLocked()
}
m.mu.Unlock()
}
if !ok {
var zero V
return zero, false
}
return e.load()
}
|
Next I present another tricky modification case.
The load method determines that p == expunged, expunged being a special value to mark as deleted that has not yet been cleaned up. But at this point p is of type *V, and p is of type unsafe.Pointer(new(interface{})), which is a different type and points to a different value.
How do I change it?
1
2
3
4
5
6
7
|
func (e *entry) load() (value any, ok bool) {
p := e.p.Load()
if p == nil || p == expunged {
return nil, false
}
return *p, true
}
|
We can use unsafe.Pointer(p) == expunged to convert to the same type, first of all the type is the same, plus we still use unsafe.Pointer(new(interface{})) to mark the deleted key.
1
2
3
4
5
6
7
8
|
func (e *entry[V]) load() (value V, ok bool) {
p := e.p.Load()
if p == nil || unsafe.Pointer(p) == expunged {
var zero V
return zero, false
}
return *p, true
}
|
In the unexpungeLocked method, we force expunged to *V, even though it points to an any, and the value of expunged is not modified anyway, so there is no risk in this forced conversion.
1
2
3
|
func (e *entry[V]) unexpungeLocked() (wasExpunged bool) {
return e.p.CompareAndSwap((*V)(expunged), nil)
}
|
The rest of the method is transformed in the same way, and can even be handled by batch replacement. Eventually we transformed the whole sync.Map to support generic types.
The full code can be found in the generic sync map.
The official test code was copied over and tested with no problems.
The final concern is whether this modification will lead to a performance improvement. The functional improvement is obvious, as our input and return values are of a specific type, and we don’t need to do type assert anymore.
Still adapting the official standard library’s bench code for sync.Map, we add a support for this generic type, and to be fair during the period we use the key and value as int types. The relevant code can be found in map_bench_test.go.
The test results are as follows, you can see that in most scenarios our generic Map is faster than the sync.Map in the standard library, only in the BenchmarkMapCompareAndSwapNoExistingKey and BenchmarkMapCompareAndSwapValueNotEqual scenarios is it slower than sync. In two scenarios it is slower than sync.Map, and much slower. I will find out why, and if I have any analysis results I will present them in another article.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
BenchmarkMapLoadMostlyHits/*syncx.SyncMap[int,int]-8 319121388 3.725 ns/op
BenchmarkMapLoadMostlyHits/*syncx.Map[int,int]-8 897178652 2.491 ns/op
BenchmarkMapLoadMostlyMisses/*syncx.SyncMap[int,int]-8 478179013 2.426 ns/op
BenchmarkMapLoadMostlyMisses/*syncx.Map[int,int]-8 866405142 2.315 ns/op
BenchmarkMapLoadOrStoreBalanced/*syncx.SyncMap[int,int]-8 5727007 223.4 ns/op
BenchmarkMapLoadOrStoreBalanced/*syncx.Map[int,int]-8 8712914 171.7 ns/op
BenchmarkMapLoadOrStoreUnique/*syncx.SyncMap[int,int]-8 2843049 405.7 ns/op
BenchmarkMapLoadOrStoreUnique/*syncx.Map[int,int]-8 4316347 321.8 ns/op
BenchmarkMapLoadOrStoreCollision/*syncx.SyncMap[int,int]-8 312317070 3.799 ns/op
BenchmarkMapLoadOrStoreCollision/*syncx.Map[int,int]-8 1000000000 1.800 ns/op
BenchmarkMapLoadAndDeleteBalanced/*syncx.SyncMap[int,int]-8 242927908 4.978 ns/op
BenchmarkMapLoadAndDeleteBalanced/*syncx.Map[int,int]-8 656539690 3.040 ns/op
BenchmarkMapLoadAndDeleteUnique/*syncx.SyncMap[int,int]-8 599912763 1.958 ns/op
BenchmarkMapLoadAndDeleteUnique/*syncx.Map[int,int]-8 1000000000 1.186 ns/op
BenchmarkMapLoadAndDeleteCollision/*syncx.SyncMap[int,int]-8 361118110 3.283 ns/op
BenchmarkMapLoadAndDeleteCollision/*syncx.Map[int,int]-8 669603936 2.184 ns/op
BenchmarkMapRange/*syncx.SyncMap[int,int]-8 744468 1594 ns/op
BenchmarkMapRange/*syncx.Map[int,int]-8 887029 1378 ns/op
BenchmarkMapAdversarialAlloc/*syncx.SyncMap[int,int]-8 8579004 139.1 ns/op
BenchmarkMapAdversarialAlloc/*syncx.Map[int,int]-8 10151095 117.4 ns/op
BenchmarkMapAdversarialDelete/*syncx.SyncMap[int,int]-8 28653038 42.42 ns/op
BenchmarkMapAdversarialDelete/*syncx.Map[int,int]-8 37976685 31.75 ns/op
BenchmarkMapDeleteCollision/*syncx.SyncMap[int,int]-8 688516219 1.797 ns/op
BenchmarkMapDeleteCollision/*syncx.Map[int,int]-8 1000000000 1.288 ns/op
BenchmarkMapSwapCollision/*syncx.SyncMap[int,int]-8 8715524 137.1 ns/op
BenchmarkMapSwapCollision/*syncx.Map[int,int]-8 10524654 114.5 ns/op
BenchmarkMapSwapMostlyHits/*syncx.SyncMap[int,int]-8 61979068 20.24 ns/op
BenchmarkMapSwapMostlyHits/*syncx.Map[int,int]-8 100000000 14.85 ns/op
BenchmarkMapSwapMostlyMisses/*syncx.SyncMap[int,int]-8 2543487 471.1 ns/op
BenchmarkMapSwapMostlyMisses/*syncx.Map[int,int]-8 3203072 374.4 ns/op
BenchmarkMapCompareAndSwapCollision/*syncx.SyncMap[int,int]-8 74106286 17.56 ns/op
BenchmarkMapCompareAndSwapCollision/*syncx.Map[int,int]-8 2704873 448.8 ns/op
BenchmarkMapCompareAndSwapNoExistingKey/*syncx.SyncMap[int,int]-8 560624862 2.116 ns/op
BenchmarkMapCompareAndSwapNoExistingKey/*syncx.Map[int,int]-8 1000000000 1.417 ns/op
BenchmarkMapCompareAndSwapValueNotEqual/*syncx.SyncMap[int,int]-8 264941869 4.297 ns/op
BenchmarkMapCompareAndSwapValueNotEqual/*syncx.Map[int,int]-8 5341881 225.9 ns/op
BenchmarkMapCompareAndSwapMostlyHits/*syncx.SyncMap[int,int]-8 74957446 15.56 ns/op
BenchmarkMapCompareAndSwapMostlyHits/*syncx.Map[int,int]-8 188375540 8.393 ns/op
BenchmarkMapCompareAndSwapMostlyMisses/*syncx.SyncMap[int,int]-8 215614034 5.475 ns/op
BenchmarkMapCompareAndSwapMostlyMisses/*syncx.Map[int,int]-8 514081917 2.111 ns/op
BenchmarkMapCompareAndDeleteCollision/*syncx.SyncMap[int,int]-8 100000000 11.49 ns/op
BenchmarkMapCompareAndDeleteCollision/*syncx.Map[int,int]-8 221624979 10.07 ns/op
BenchmarkMapCompareAndDeleteMostlyHits/*syncx.SyncMap[int,int]-8 55139349 21.67 ns/op
BenchmarkMapCompareAndDeleteMostlyHits/*syncx.Map[int,int]-8 129426009 12.53 ns/op
BenchmarkMapCompareAndDeleteMostlyMisses/*syncx.SyncMap[int,int]-8 500900576 2.476 ns/op
BenchmarkMapCompareAndDeleteMostlyMisses/*syncx.Map[int,int]-8 486840268 2.307 ns/op
|
Ref
https://colobu.com/2023/06/11/make-sync-Map-to-generic/