map - Go :: 为霜的博客

1. Basic concepts#

A map value is a pointer to a runtime.hmap structure, when you write the statement:

m := make(map[int]int)

The compiler replaces it with a call to runtime.makemap, which has the signature

// makemap implements a Go map creation make(map[k]v, hint)
// If the compiler has determined that the map or the first bucket
// can be created on the stack, h and/or bucket may be non-nil.
// If h != nil, the map can be created directly in h.
// If bucket != nil, bucket can be used as the first bucket.
func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap

func main() {
	var m map[int]int
	var p uintptr
	fmt.Println(unsafe.Sizeof(m), unsafe.Sizeof(p)) // 8 8 (linux/amd64)
}

⚠️ Map value just a pointer, therefore, we don’t need to pass a pointer to a map for better performance. This is similar to slices, slice just a struct that has a pointer element which pointer to an underlaying array, so we don’t need to set a pointer of slice as a paramter. This also applys function’s return type.

Maps, like channels, but unlike slices, are just pointers to runtime types. As you saw above, a map is just a pointer to a runtime.hmap structure.

Learn more: maps | Dave Cheney

2. `var` vs `make()`#

In previous post we know that you can append a nil slice directly, but this is not the case in a map:

var cats map[string]int
// panic: assignment to entry in nil map
cats["Coco"] = 3

Therefore, for map you should use make or map literal

// They are equivlent
cats := map[string]int{}
dogs := make(map[string]int)

3. Commone usage of map#

3.1. Use map as a counter#

// as a counter
counts := make(map[string]int)
for name := range users {
	counts[name]++
}
// check if exist, O(1)
ele, ok := m["key"]
if !ok {...}

3.2. Copy map#

Find a blog talks copy map, share it here:

Like slices, maps hold references to an underlying data structure. So by assigning its value to another variable, only the reference will be passed. To copy the map, it is necessary to create another map and copy each value:

// Create the original map
originalMap := make(map[string]int)
originalMap["one"] = 1
originalMap["two"] = 2

// Create the target map
targetMap := make(map[string]int)

// Copy from the original map to the target map
for key, value := range originalMap {
  targetMap[key] = value
}

Deep copy a map or slice: encoding/gob & encoding/json in golang - David’s Blog

4. Map in concurrent programming#

First version:

func (s *memoryStore) monitorExpiredSessions() {
	for {
    	// detect every seconds
		time.Sleep(time.Second)
		memoryMutex.Lock()
		if len(s.sessions) == 0 {
			memoryMutex.Unlock()
			continue
		}
		for k, info := range s.sessions {
			if info.expiresTimestamp <= time.Now().Unix() {
				delete(s.sessions, k)
			}
		}
		memoryMutex.Unlock()
	}
}

// in other place will call this method
go s.monitorExpiredSessions()

This is not good, as the size of s.sessions grows, the time to iterate through s.sessions will increase, leading to longer lock holding times. We can optimize lock usage, possibly by using more granular locks or lock-free structures.

Second version:

func (s *memoryStore) monitorExpiredSessions() {
    ticker := time.NewTicker(time.Second)
    defer ticker.Stop()
	for range ticker.C {
		if s.isEmpty() {
			continue
		}
		for k, info := range s.sessions {
			if info.expiresTimestamp <= time.Now().Unix() {
				s.delete(k)
			}
		}
	}
}

func (s *memoryStore) delete(k string) {
	memoryMutex.Lock()
	defer memoryMutex.Unlock()
	delete(s.sessions, k)
}

func (s *memoryStore) isEmpty() bool {
	memoryMutex.RLock()
	defer memoryMutex.RUnlock()
	return len(s.sessions) == 0
}

Some problems:

There is no lock when ranging map s.sessions
You cannot require a RLock or Lock before range, if you do that, the memoryMutex.Lock() residing in s.delete() will block forever. Because you have hold a lock before the loop, which havn’t been released yet, and you cannot acquire another lock in the loop.

Third version:

I find fiber memory storage on github which suits my condition provided by a gopher.

I’ll share the code here:

// Adopted from: https://github.com/gofiber/storage/blob/main/memory/memory.go
func (s *cookieStore) gc() {
	ticker := time.NewTicker(s.gcInterval)
	defer ticker.Stop()
	var expired []string
	for range ticker.C {
		if s.isEmpty() {
			continue
		}
		mutex.RLock()
		for k, session := range s.sessions {
			if session.expiry <= time.Now().Unix() {
				expired = append(expired, k)
			}
		}
		mutex.RUnlock()
		mutex.Lock()
		// Double-checked locking.
		// User might have reset the max age of the session in the meantime.
		for i := range expired {
			v := s.sessions[expired[i]]
			if v.expiry <= time.Now().Unix() {
				delete(s.sessions, expired[i])
			}
		}
		mutex.Unlock()
	}
}

func (s *cookieStore) isEmpty() bool {
	mutex.RLock()
	defer mutex.RUnlock()
	return len(s.sessions) == 0
}

When I test this, the codes get panic sometimes:

At v.expiry <= time.Now().Unix() :

v := s.sessions[expired[i]]
if v.expiry <= time.Now().Unix() {
  ...
}

panic: runtime error: invalid memory address or nil pointer dereference

This means we get a nil session from s.sessions[expired[i]], so there is a problem with slice expired, I was thinking if its length is 0, the range still iterate it. Turns out the range won’t iterate an empty slice, just do nothing.

Then I realize that I did’t update the slice, woops, we need drop the useless element in last round:

...
for range ticker.C {
  // drop the useless elements.
  expired = expired[:0]
  .....
}

map - Go