Hello, I’m fried fish.

Recently, some students asked me this nikkei topic, want to turn his article, the results found that my public number unexpectedly did not send, so today I nagging two, good let everyone avoid this “pit”.

Some people do not pay attention to the Go Map output and traversal order, thinking that it is stable and orderly, and will directly rely on this result set order in business programs, resulting in a big stumble, eating online bugs.

Some partners know it is disordered, but they don’t know why, and some understand it wrong?

In this article, we will take a look at the “mystery” of the output of the for Range map and see what the internal implementation looks like and what the order is.

Start sucking the fish way.

preface

Examples are as follows:

func main(a) {
	m := make(map[int32]string)
	m[0] = "EDDYCJY1"
	m[1] = "EDDYCJY2"
	m[2] = "EDDYCJY3"
	m[3] = "EDDYCJY4"
	m[4] = "EDDYCJY5"

	for k, v := range m {
		log.Printf("k: %v, v: %v", k, v)
	}
}
Copy the code

Suppose I ran this code, what would the output look like? Is it ordered or is it unordered?

k: 3, v: EDDYCJY4
k: 4, v: EDDYCJY5
k: 0, v: EDDYCJY1
k: 1, v: EDDYCJY2
k: 2, v: EDDYCJY3
Copy the code

In terms of the output, the output is not fixed order, that is, different every time. But why?

First of all, I suggest you think about why. Secondly, I’ve heard some stories in interviews. Some people say that because it’s hashed it’s unordered and so on. I was a little…

This is also the reason for this article, I hope we can discuss together, clear up this problem 🙂

Look at the assembly

. 0x009b 00155 (main.go:11) LEAQ type.map[int32]string(SB), AX 0x00a2 00162 (main.go:11) PCDATA $2, $0 0x00a2 00162 (main.go:11) MOVQ AX, (SP) 0x00a6 00166 (main.go:11) PCDATA $2, $2 0x00a6 00166 (main.go:11) LEAQ "".. autotmp_3+24(SP), AX 0x00ab 00171 (main.go:11) PCDATA $2, $0 0x00ab 00171 (main.go:11) MOVQ AX, 8(SP) 0x00b0 00176 (main.go:11) PCDATA $2, $2 0x00b0 00176 (main.go:11) LEAQ "".. autotmp_2+72(SP), AX 0x00b5 00181 (main.go:11) PCDATA $2, $0 0x00b5 00181 (main.go:11) MOVQ AX, 16(SP) 0x00ba 00186 (main.go:11) CALL runtime.mapiterinit(SB) 0x00bf 00191 (main.go:11) JMP 207 0x00c1 00193 (main.go:11) PCDATA $2, $2 0x00c1 00193 (main.go:11) LEAQ "".. autotmp_2+72(SP), AX 0x00c6 00198 (main.go:11) PCDATA $2, $0 0x00c6 00198 (main.go:11) MOVQ AX, (SP) 0x00ca 00202 (main.go:11) CALL runtime.mapiternext(SB) 0x00cf 00207 (main.go:11) CMPQ "".. autotmp_2+72(SP), $0 0x00d5 00213 (main.go:11) JNE 193 ...Copy the code

To take a look at the overall process, we focus on two Runtime methods that handle the Go Map loop iteration as follows:

  • runtime.mapiterinit
  • runtime.mapiternext

But you might be wondering, why are these two functions there when I’m iterating over for range? What’s going on?

Let’s look at the transformation

var hiter map_iteration_struct
for mapiterinit(type.range, &hiter); hiter.key ! =nil; mapiternext(&hiter) {
    index_temp = *hiter.key
    value_temp = *hiter.val
    index = index_temp
    value = value_temp
    original body
}
Copy the code

The compiler actually implements the loop iteration of slice and map differently, not just by throwing it away, but by doing additional actions. The code above is a pseudo-implementation of the for Range map expanded by the compiler

Take a look at the source code

runtime.mapiterinit

func mapiterinit(t *maptype, h *hmap, it *hiter){... it.t = t it.h = h it.B = h.B it.buckets = h.bucketsift.bucket.kind&kindNoPointers ! =0 {
		h.createOverflow()
		it.overflow = h.extra.overflow
		it.oldoverflow = h.extra.oldoverflow
	}

	r := uintptr(fastrand())
	if h.B > 31-bucketCntBits {
		r += uintptr(fastrand()) << 31
	}
	it.startBucket = r & bucketMask(h.B)
	it.offset = uint8(r >> h.B & (bucketCnt - 1))
	it.bucket = it.startBucket
    ...

	mapiternext(it)
}
Copy the code

Reading the mapIterInit method, you can see that its main purpose is to initialize the map while iterating through it. There are three parameters that read the type information of the current hash table, the storage information of the current hash table, and the data of the current iterated iteration

why

Let’s look at the fastrand part of the source code, the method name, is not familiar. That’s right, it’s a way to generate random numbers. Look again at the context:

.// decide where to start
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
	r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))

// iterator state
it.bucket = it.startBucket
Copy the code

In this code, it generates random numbers. Used to determine where to start the loop iteration. To be more specific, select a bucket location as the starting point for traversal iteration based on random number

So every time you re-create the for range map, you see a different result. That’s because its starting position is not fixed at all!

runtime.mapiternext

func mapiternext(it *hiter){...for ; i < bucketCnt; i++ {
		...
		k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
		v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize))
		...
		if(b.tophash[offi] ! = evacuatedX && b.tophash[offi] ! = evacuatedY) || ! (t.reflexivekey || alg.equal(k, k)) { ... it.key = k it.value = v }else {
			rk, rv := mapaccessK(t, h, k)
			if rk == nil {
				continue // key has been deleted
			}
			it.key = rk
			it.value = rv
		}
		it.bucket = bucket
		ifit.bptr ! = b { it.bptr = b } it.i = i +1
		it.checkBucket = checkBucket
		return
	}
	b = b.overflow(t)
	i = 0
	goto next
}
Copy the code

In the previous section, we selected the location of the starting bucket. The next step is to iterate through the action using MapiterNext. The method mainly involves the following:

  • Iterate from the selected bucket looking for the next element in the bucket to process
  • If the bucket has been traversed, overflow the bucketoverflow bucketsPerform traversal processing

By reading this method, you can know the traversal rules for buckets and the processing of capacity expansion (which is not the focus of this article). So there is no specific expansion)

conclusion

At the beginning of this article, let’s start with the core discussion point: “Why is the Go Map traversal output not in fixed order?” .

After all this analysis, the reason is simple. The for range map does random seeding when it starts processing loop logic…

Why, you ask?

Of course, this is intentional, because in the early days of Go (1.0), although it was iterated steadily, there was no guarantee that the iteration rules would be the same for each version of Go. This leads to portability issues.

So, change it. And please don’t rely on…

If you have any questions, welcome feedback and communication in the comments section. The best relationship is mutual achievement. Your praise is the biggest motivation for the creation of fried fish, thank you for your support.

This article is constantly updated, you can search for “brain into fried fish” on wechat to read, reply [000] there are questions and materials I prepared for the interview algorithm of frontline big factory.

In this paper, making github.com/eddycjy/blo… Star has been included, welcome to urge more.

reference

  • Go maps in action