GopherCon 2016: Inside the Map Implementation - Keith Randall

What people said

Recommends John Balvin Arias · 2018-06 · Stack Overflow · on “is the adress value return by map.LoadOrStore the same as the input in case of nested maps?”

are you sure? I thought with maps you couldn't do that [this video] minute 21:31 explains why, or sync.Map behave different?, that's why I didn't pass a pointer in first place

Recommends peterSO · 2019-08 · Stack Overflow · on “Why are map values not addressable?”

Being from a C++ background. Why are [Go] map values not addressable? If all other languages were like C++ there would be no point in having other languages. C++ is a complex, hard-to-read language. Remember the Vasa! - Bjarne Stroustrup [LINK] Go, by design, is a simple, readable language. dotGo 2015 - Rob Pike - Simplicity is Complicated [LINK] A Go map is a hash map. A deterministic hash function is applied to a map key. The hash value is used to determine the primary map bucket for the entry (key-value pair). A bucket stores one or more map entries. A primary bucket may overflow to secondary buckets. Buckets are implemented as an array. As the number of map entries increases by insertion

Recommends nipuna · 2021-08 · Stack Overflow · on “How does go implement Generic in built-in type like map and slice?”

Found related explanation in Gopher Academy youtube channel, Keith Randall explaining about maps and how it is implemented to have many types without generics. video link - Keith Randall - Inside the Map Implementation [this video] As it is described and you can see in src/runtime/type.go [LINK] Type informations are handled by this _type . type _type struct { size uintptr ptrdata uintptr // size of memory prefix holding all pointers hash uint32 tflag tflag align uint8 fieldAlign uint8 kind uint8 // function for comparing objects of this type // (ptr to object A, ptr to object B) -> ==? equal func(unsafe.Pointer, unsafe.Pointer) bool // gcdata stores the GC type data for the garbage collector. //

Cites peterSO · 2016-11 · Stack Overflow · on “Concurrent access to maps with 'range' in Go”

The unit of concurrent access for a for range loop over a map is the map. Go maps in action [LINK] . A map is a dynamic data structure that changes for inserts, updates and deletes. Inside the Map Implementation [this video] . For example, The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next. If map entries that have not yet been reached are removed during iteration, the corresponding iteration values will not be produced. If map entries are created during iteration, that entry may be produced during the iteration or may be skipped. The choice may vary for each entry created and from one iteration to the next. If the map is nil, the nu

Cites peterSO · 2017-03 · Stack Overflow · on “Why don't they use ints to define constants instead of using bit shift operators?”

const ( // Maximum number of key/value pairs a bucket can hold. bucketCntBits = 3 bucketCnt = 1 << bucketCntBits ) The number of key/value pairs a bucket can hold depends on the number of bits used ( bucketCntBits = 3 ). That translates to a bucket count ( bucketCnt ) of 1 << bucketCntBits or 8. If we change the number of bits to 4 ( bucketCntBits = 4 ) or 2 ( bucketCntBits = 2) then bucketCnt is still 1 << bucketCntBits or 16 or 4. // A map is just a hash table. The data is arranged // into an array of buckets. Each bucket contains up to // 8 key/value pairs. The low-order bits of the hash are // used to select a bucket. Each bucket contains a few // high-order bits of each hash to distingu

Cites user13097 · 2018-03 · Stack Overflow · on “Why does Go forbid taking the address of (&) map member, yet allows (&) slice element?”

A fundamental difference between map and slice is that a map is a dynamic data structure that moves the values that it contains as it grows. The specific implementation of Go map may even grow incrementally, a little bit during insert and delete operations until all values are moved to a bigger memory structure. So you may delete a value and suddenly another value may move. A slice on the other hand is just an interface/pointer to a subarray. A slice never grows. The append function may copy a slice into another slice with more capacity, but it leaves the old slice intact and is also a function instead of just an indexing operator. In the words of the map implementor himself: [this video] "It int

Cites peterSO · 2018-03 · Stack Overflow · on “Why doesn't Go allow taking the address of map value?”

Let's start with this misconception: I wanted to modify a map struct value in place. Numeric values in maps can be modified in place using operators like ++ or += func icandothis() { cmap := make(map[int]complex64) cmap[1] += complex(1, 0) fmt.Println(cmap[1]) } Let's expand the shorthand form: package main import ( "fmt" ) func icandothisShort() { cmap := make(map[int]complex64) cmap[1] += complex(1, 0) fmt.Println(cmap[1]) } func icandothisLong() { cmap := make(map[int]complex64) // An assignment operation x op= y where op is a binary arithmetic operator // is equivalent to x = x op (y) but evaluates x only once. // cmap[1] += complex(1, 0) v := cmap[1] // v = zero value = complex(0, 0) v

Cites peterSO · 2018-09 · Stack Overflow · on “How large is the struct underlying a map in golang?”

The zero value for a Go map variable is a nil pointer. var m map[string]int make intializes a map and sets the map variable to point to a package runtime hmap struct . m = make(map[string]int) In Go, all arguments are passed by value. In the case of a map value, a reference type, a map value is a pointer. Therefore, passing a map value as a function or method argument is fast, you are passing a pointer. The Go map runtime struct s are currently located in the src/runtime/map.go Go source file. Since you only see a hmap pointer, their size is unlikely to be relevant. See GopherCon 2016: Keith Randall - Inside the Map Implementation [this video] .

Cites peterSO · 2019-01 · Stack Overflow · on “A Go map thread safety problem while reading a cache DIY book”

You have a data race. Your results are undefined. Simplifying your code so that it compiles and runs, package main import ( "sync" "time" ) func main() { testMap := make(map[string]string) mutex := sync.RWMutex{} for i := 0; i < 64; i++ { mutex.Lock() now := time.Now().String() testMap[now] = now mutex.Unlock() } go func() { for { mutex.Lock() now := time.Now().String() testMap[now] = now time.Sleep(100 * time.Millisecond) mutex.Unlock() } }() for k, v := range testMap { mutex.RLock() _, _ = k, v mutex.RUnlock() time.Sleep(100 * time.Millisecond) } } Output: $ go run -race racer.go ================== WARNING: DATA RACE Read at 0x00c00008c060 by main goroutine: runtime.mapiternext() /home/pet

Cites zangw · 2022-03 · Stack Overflow · on “Golang map internal implementation - how does it search the map for a key?”

Overview Map [LINK] bucket details of map[string]string [LINK] Each bucket stores an array of hash codes The array of hash codes stores the hash code for each key in the bucket, this is used for faster comparison. a list of key-value pairs Each bucket can store a maximum of 8 such key-value pairs. an overflow pointer. The overflow pointer can point to a new bucket if a bucket receives more than 8 values. What happens when we insert a new value in the map Hash function is called and a hash code is generated for the given key, based on a part of the hash code a bucket is determined to store the key-value pair. Once the bucket is selected the entry needs to be held in that bucket. The complete