Do Go implementations store the length of a map?

Question

Does a map have its length stored somewhere or is it calculated each time we call len(my_map)?

The language spec shows this for maps, which doesn't really help:

The number of map elements is called its length. For a map m, it can be discovered using the built-in function len and may change during execution. Elements may be added during execution using assignments and retrieved with index expressions; they may be removed with the delete built-in function.

Under the "Length and capacity" section we see this:

The expression len(s) is constant if s is a string constant. The expressions len(s) and cap(s) are constants if the type of s is an array or pointer to an array and the expression s does not contain channel receives or (non-constant) function calls; in this case s is not evaluated. Otherwise, invocations of len and cap are not constant and s is evaluated.

So it tells us that s isn't constant and is evaluated but it doesn't state if it's looked up as a stored value like they do with the slice type.

Answer 1

I haven't checked the sources, but I wrote a quick benchmark.

It tests 4 maps, 2 where keys are int, 2 where keys are string.

var m1 = make(map[int]int)    // key is of type int, len(m1) = 10
var m2 = make(map[int]int)    // key is of type int, len(m2) = 1000000
var s1 = make(map[string]int) // key is of type string, len(s1) = 10
var s2 = make(map[string]int) // key is of type string, len(s2) = 1000000

"Small" maps have 10 elements, "large" maps have a million elements. Maps are populated like this:

func init() {
    for i := 0; i < 10; i++ {
        m1[i] = i
        s1[strconv.Itoa(i)] = i
    }
    for i := 0; i < 1000000; i++ {
        m2[i] = i
        s2[strconv.Itoa(i)] = i
    }
}

A benchmark function looks like this:

func BenchmarkSmallIntMap(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for j := 0; j < 1000; j++ {
            _ = len(m1) + len(m1) + len(m1) + len(m1) + len(m1) + len(m1)
        }
    }
}

All the others are similar, but using m2, s1 and s2 obviously. Here are the results:

BenchmarkSmallIntMap     1000000              2085 ns/op
BenchmarkLargeIntMap     1000000              2087 ns/op
BenchmarkSmallStringMap  1000000              2087 ns/op
BenchmarkLargeStringMap  1000000              2086 ns/op

All are the same which pretty much tells that execution time of len(m) does not depend on the map size (number of key-value pairs), which suggests that map length is stored and not "counted" when called.

If interested, here is the complete test source: Go Playground.

And twotwotwo checked the sources, the length is stored.