Why is traversal of Go map unordered?

  Back end, golang, php

image

Some small partners did not pay attention to the output sequence of Go map and thought it was stable and orderly. Some small partners know that there is disorder, but they don’t know why. Some of them understand wrong? Today we will unveil through this articlefor range mapThe “mysterious” veil of the, see what is its internal implementation, output order is what?

Original address:Why is traversal of Go map unordered?

Preface

func main() {
    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)
    }
}

Assuming this code is run, are the output results in sequence? Or disorderly output?

2019/04/03 23:27:29 k: 3, v: EDDYCJY4
2019/04/03 23:27:29 k: 4, v: EDDYCJY5
2019/04/03 23:27:29 k: 0, v: EDDYCJY1
2019/04/03 23:27:29 k: 1, v: EDDYCJY2
2019/04/03 23:27:29 k: 2, v: EDDYCJY3

Judging from the output results, it is output in non-fixed order, that is, it is different every time (the title is also mentioned). But why?

First of allI suggest you think about the reason first.. Secondly, I heard some statements during the interview. Some people say that there is no (random) order because it is hashed. At that time, I was a little bit? ? ?

This is also the reason why this article appears. I hope everyone can discuss it together and sort out 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
    ...

Let’s take a look at the overall process, focusing on the two runtime methods that deal with Go map loop iteration, as follows:

  • runtime.mapiterinit
  • runtime.mapiternext

But you might think, obviously, it isfor rangeHow did these two functions come into being and how did they happen?

Look at the conversion

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
}

In fact, the compiler has different implementations for loop iteration of slice and map, notforAs soon as it was thrown, it was finished and some additional actions were taken to deal with it. And the above code isfor range mapPseudo-implementation after Compiler Deployment

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.buckets
    if t.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)
}

By rightmapiterinitAfter reading the method, we can know that its main purpose is when map is iteratedPerform initialization action. There are three parameters for reading the type information of the current hash table, the storage information of the current hash table and the data of the current traversal iteration

Why?

We pay attention to the source codefastrandPart of, this method name, is fan familiar. Yes, it is a method of generating random numbers. Look at the context again:

...
// 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

In this code, it generates random numbers. Used to decide where to start the loop iteration. More specifically, according to the random number, a bucket position is selected as a starting point for traversal iteration

So every time I try againfor range mapThe results you see are different. 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
        if it.bptr != b { 
            it.bptr = b
        }
        it.i = i + 1
        it.checkBucket = checkBucket
        return
    }
    b = b.overflow(t)
    i = 0
    goto next
}

In the previous section, we have already chosen the position of the starting barrel. The next step is to passmapiternextcarry throughSpecific loop traversal actions. The method mainly involves the following steps:

  • Traversal is started from the selected bucket to find the next element in the bucket for processing.
  • If the bucket has been traversed, the overflow bucketoverflow bucketsCarry out traversal processing

Through reading this method, we can know its effect on bucketsTraversal ruleAs well as some treatment for expansion (this is not the focus of this article. Therefore, it is not specifically expanded)

Summary

At the beginning of this article, let’s first put forward the core discussion point: “why is the output of Go map traversal not in a fixed order?” . And through this analysis, the reason is very simple and clear. exactlyfor range mapAt the beginning of processing the cyclic logic, random seeding was done. …

Why do you want to ask? Of course, it was intentionally done by the government, because although Go iterated steadily in the early period (1.0), in terms of results, it is actually impossible to guarantee that every iteration traversal rule of Go version is the same. This will lead to portability problems. Therefore, change it. Also please don’t rely on it …

References