Special features of Go map

Zero Value Characteristic

Some operations of uninitialized map s are legal:

    var testMap map[int]int
    size := len(testMap)     // size is 0
    _, present := testMap[0] // present is false
    non := testMap[123]      // non is 0, won't case panic
    testMap[1] = non         // panic: assignment to entry in nil map

Only write operations will produce panic.

Temporary iteration of obj's address problem.

When iterating over containers such as map and slice, you can't use the address of temporary variables!
Simply put, this obj uses the same address. If you save the address of this variable, it will be a disaster.

Code snippet:

var(gSlice []*obj)
func foosp(v *obj) {
    gSlice = append(gSlice, v)
for _, obj := range objSlice {

In the for loop, the caller is given the illusion that "every value in objSlice has been passed out", but in fact the external function receives only the same address. Each time foosp() starts executing, the value of *(& obj) is indeed the value of the current element in objSlice, but when the entire code is executed, the value of gSlice[-1] will be a pointer to the same address.

map lock

First, let's look at the basic features of go's map: hash implementation, key needs to be comparable, and will not be automatically initialized.

Maps are not safe for concurrent use: it's not defined what happens when you read and write to them simultaneously. If you need to read from and write to a map from concurrently executing goroutines, the accesses must be mediated by some kind of synchronization mechanism. One common way to protect maps is with sync.RWMutex.

Extracted from: go-maps-in-action

When concurrently reading and writing map s, we must lock them. We can use read and write locks. At present, concurrent reading seems to be no problem.

A big map, if you use a sync.RWMutex, and if there are many routine s in use, then performance is bound to suffer, so someone wrote a way to divide a lock into N locks with less force.

For example []( https://github.com/orcaman/co...
Earlier syncmap

Initially, syncmap was used in the project. But this library has a fatal flaw (as is the case in go-maps-in-action).

Consider a scenario like this:

graph LR
A(Routine A.1)-->A2("A.2 inspect map.Get(key)Does it exist?")
A2 --> A3("A.3 Write in map.Set(key, vA)")
B(Routine B.1)-->B2("B.2 inspect map.Get(key)Does it exist?")
B2 --> B3("B.3 Write in map.Set(key, vB)")

A.2 A.3 B.2 B.3 These four operations are indeed protected by locks, but what we want is actually to turn them into locks.
Two separate operations, A.2 & A.3 and B.2 & B.3, are protected.
If A.2 B.2 is implemented, A.3 and B.3 may cover each other.

We have this requirement in our project, so a colleague added an Update function to do this:

func (m *SyncMap) Update(key Key, f func(value interface{}) interface{}) {
    shard := m.locate(key)
    v := shard.items[key]
    r := f(v)
    if r != nil {
        shard.items[key] = r
    } else {
        delete(shard.items, key)

By passing in a function, shard.Lock protects what user hanshu f does with the code.
The new concurrent_map on the later github is implemented in the same way.


type UpsertCb func(exist bool, valueInMap interface{}, newValue interface{}) interface{}

// Insert or Update - updates existing element or inserts a new one using UpsertCb
func (m ConcurrentMap) Upsert(key string, value interface{}, cb UpsertCb) (res interface{}) {
    shard := m.GetShard(key)
    v, ok := shard.items[key]
    res = cb(ok, v, value)
    shard.items[key] = res
    return res

After Go 1.7, a language level (built-in library) sync.Map was provided to implement concurrent reading and writing of Maps.

There's a great Chinese blog about sync.Map.
Go 1.9 sync.Map Unveiling

Through blogs and reading code (as well as comments), we know how to implement it:

  • Most read operations are unlocked using a redundant map.
  • Using sync.Mute and atomic to achieve similar
  • Use miss counts to flip read and write map s to achieve better performance.

According to the description, the performance is excellent in scenarios where each key is written only once (because almost no Mutex is used).

The libexec/src/sync/map_bench_test.go of Go source code has their own performance tests. The results I tested on my own machine (Intel i7-4770HQ 16G DDR3) are as follows:

BenchmarkLoadMostlyHits/*sync_test.DeepCopyMap-8             100000000            19.7 ns/op
BenchmarkLoadMostlyHits/*sync_test.RWMutexMap-8              20000000            60.2 ns/op
BenchmarkLoadMostlyHits/*sync.Map-8                          100000000            18.0 ns/op

BenchmarkLoadMostlyMisses/*sync_test.DeepCopyMap-8           100000000            14.7 ns/op
BenchmarkLoadMostlyMisses/*sync_test.RWMutexMap-8            20000000            62.5 ns/op
BenchmarkLoadMostlyMisses/*sync.Map-8                        100000000            12.4 ns/op

BenchmarkLoadOrStoreBalanced/*sync_test.RWMutexMap-8          3000000           549 ns/op
BenchmarkLoadOrStoreBalanced/*sync.Map-8                      3000000           421 ns/op

BenchmarkLoadOrStoreUnique/*sync_test.RWMutexMap-8            2000000           896 ns/op
BenchmarkLoadOrStoreUnique/*sync.Map-8                        2000000           880 ns/op

BenchmarkLoadOrStoreCollision/*sync_test.DeepCopyMap-8       200000000             7.85 ns/op
BenchmarkLoadOrStoreCollision/*sync_test.RWMutexMap-8        10000000           181 ns/op
BenchmarkLoadOrStoreCollision/*sync.Map-8                    200000000             9.02 ns/op

BenchmarkRange/*sync_test.DeepCopyMap-8                        300000          4325 ns/op
BenchmarkRange/*sync_test.RWMutexMap-8                          30000         58693 ns/op
BenchmarkRange/*sync.Map-8                                     300000          4169 ns/op

Finally, there is the Adversarial Alloc / Delete for the implementation details of sync.Map, which I think is meaningless and neglected.

Three types of map with concurrent access are tested here:

  • The way of using read-write locks mentioned earlier.
  • sync.Map using composite implementation.
  • Use atomic copies every time you write to avoid using Mutex or WLock.

Among them, the third way of deep copy is actually not dare to use (COPY whole map operation is too terrible), here is just a comparison, the author may feel that in some cases with fewer key s, its performance will be more similar to native map?

Several scenarios where sync.Map is the best test result:

  • When concurrent read-write conflicts occur in large numbers (lock avoidance).
  • range time.

In fact, I don't think there will be any extreme conflict between reading and writing. If there are similar scenarios, the logic must be changed.
Normally, read-write is several times better than RWMutextMap, which avoids lock, but I doubt if it can be better than RWMutextMap with appropriate shard values.

So my conclusion at present is:

For map s with concurrent read and write requirements, RWLockMap optimized by shard is sufficient.

Keywords: Go github less

Added by IceDragon on Tue, 03 Sep 2019 12:13:27 +0300