Go source version 1.13.8

preface

Yes, I am a PHPer, too, and I must have a problem with our PHPer to Gopher 😁 : Go does not traverse the Map output elements in the same order each time, but it is stable in PHP. Today we’re going to look at why. This article is mainly developed from the following nodes:

Result of Go Map traversal is “out of order”
- The starting point of an index traversing a Map is random
Go’s Map is essentially “unordered”
- Out-of-order write
  - Normal writes (non-hashing writes)
  - Hash conflict writes
- capacity
  - Multiplication forces elements to change order
  - The same capacity

Result of Go Map traversal is “out of order”

What to see: Go does not iterate over Map output elements in the same order, but it is stable in PHP.

I won’t go into more details about this phenomenon, and I’m sure you’ve all searched online For articles about it, most of which explain why: Range … The index that traverses the Map starts at a random point, which, yes, is the following code.

/ / versions / 1.13.8 / SRC/CMD/compile/internal/gc/range. Go
func walkrange(n *Node) *Node {
	
    / / a little...

    // When traversing the Map
	case TMAP:
		
        / / a little...

        // Call mapiterinit as shown below
		fn := syslook("mapiterinit")

		/ / a little...

		fn = syslook("mapiternext")
		
        / / a little...
}

/ / versions / 1.13.8 / SRC/runtime/map. Go
func mapiterinit(t *maptype, h *hmap, it *hiter) {

    / / a little...

    // Yes, that's it
    // A random index value is used as the starting point for traversal
	// decide where to start
	r := uintptr(fastrand())
	if h.B > 31-bucketCntBits {
		r += uintptr(fastrand()) << 31
	}
	
    / / a little...

	mapiternext(it)
}
Copy the code

But have you ever speculated on the real reasons behind the Go writers? I think it’s because:

Go’s Map is essentially “unordered”

Go’s Map is essentially “unordered”. Why?

“Disorderly” write

1. Write (non-hash conflict write) : Writes are hash to a bucket instead of buckets.

Buckets are contiguous memory, but new keys may be written to this bucket:

You might also write about this bucket:

2. Hash conflict write: If hash conflict exists, write to the same bucket.

It may be written to this position:

In the limiting case, you might write it like this:

More likely to write into the overflow bucket:

Therefore, when writing data, there is no separate order of key-value pairs maintained. The PHP(Version 5) language maintains the order of elements in a Map through a global linked list.

capacity

Go Map expansion can be performed in two ways:

Multiple expansion
The same capacity

1. Multiplication forces elements to change order

To simplify our understanding of “multiply”, we assume the following conditions:

Has the followingmap
And themapThere are currently 2bucket(That’s 2Bmap structure)
The process of key hash is simply used here to take modulus (easy to understand)

// Take map as an example
map[int]int{
    1:  1.2:  2.3:  3.4:  4.5:  5.6:  6.7:  7.8:  8.9:  9.10: 10.11: 11.12: 12.13: 13,}Copy the code

Meanwhile, according to the above assumptions, we get the structure diagram corresponding to this map as follows:

When do you trigger multiple expansion?

Map write operation
(Number of elements/number of buckets) > 6.5

The following code analysis shows that:

/ / versions / 1.13.8 / SRC/runtime/map. Go
Map write operation
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	
    / / a little...

    // Whether capacity expansion verification is triggered
	if! h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        / / capacity
		hashGrow(t, h)
		goto again
	}

    / / a little...

}

/ / the load factor of the expansion and trigger threshold = loadFactorNum/loadFactDen = 13/2 = 6.5
loadFactorNum = 13
loadFactorDen = 2

// The load factor is exceeded
func overLoadFactor(count int, B uint8) bool {
    Uintptr (count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
    / / get uintptr (count)/bucketShift (B) > loadFactorNum/loadFactorDen
    / / loadFactorNum/loadFactDen = 13/2 = 6.5
    // Uintptr (count)/bucketShift(B) > 6.5
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
Copy the code

In the above Map, when the key value 14:14 is written, we analyze whether multiple expansion will be triggered:

BucketShift (B) : 2 (13+1)/2 = 7 > 6.5 The current number of elements count: 13 bucketShift(B) : 2 (13+1)/2 = 7 > 6.5Copy the code

The process of doubling and expanding is as follows:

The originalbucketsBy pointing tooldbuckets
Multiply the new from initializationbucketsPoint to thebuckets
Write operations trigger capacity expansion
Only the corresponding key of the current key is expanded each timebucket(bmap)
The originalbucket(bmap) is split into two new onesbucket(bmap)

The process is shown in the figure below (the parts marked in red are the buckets for capacity expansion) :

After that, key 15:15 is written to complete the expansion process. The figure after expansion is as follows:

At the same time, through the above analysis, we can get the following conclusion: exponential expansion forces element order to change.

2. Equal capacity expansion

When is equal capacity expansion triggered?

The answer is shown in the following code:

// Determine equal capacity expansion
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	Count (buckets) = 2^B
	if B > 15 {
		B = 15
	}
	
    // Equal capacity expansion is triggered when the number of overflow buckets is greater than or equal to 2 x B
	return noverflow >= uint16(1)<<(B&15)}Copy the code

What is the purpose of equal expansion?

A: Organize overflow buckets and recycle redundant overflow buckets.Copy the code

Similarly, to simplify our understanding of “equal capacity expansion”, we assume the following conditions:

Has the followingmap
And themapThere are currently 2bucket(That’s 2Bmap structure)
The process of key hash is simply used here to take modulus (easy to understand)
Ignore index 1bucket(i.e.bucketsThe secondbmap)
With index 0bucket(i.e.bucketsThe firstbmap), for example
Suppose the first onebmapIs already written full (caused by a hash conflict) and is associated with the overflow bucketbmapIs also written full, and with this overflow bucketbmapAssociated with another overflow bucketbmapA key value is written

// Take map as an example
map[int]int{
    1:  1.2:  2.3:  3.4:  4.5:  5.6:  6./ /... Just a continuous value
    34: 34,}Copy the code

Meanwhile, according to the above assumptions, we get the structure diagram corresponding to this map as follows:

To illustrate the effect of “equal capacity expansion”, we continue to assume:

Delete the key valueHand,
Delete the key valueWhen he
Delete the key valueWhen it

At this point, the corresponding structure of the map is shown as follows:

Based on the assumptions above, will “equal expansion” be triggered when we write the key 36:36?

Noverflow >= Uint16 (1)<<(b&15) We have already assumed that buckets with index 1 should be ignored and buckets with index 0 should be used as buckets' first Bmap Noverflow = 2 B = 1 noverflow = 2 B = 1 noverflow = 2 B = 1 noverflow = 2 B = 1Copy the code

Conclusion: “Equal capacity expansion” is triggered when key 36:36 is written. The result of equal capacity expansion is as follows:

As can be seen from the above picture:

Tidy up the normal bucketbmapThe memory of
Tidy up the normal bucketbmapCorrespond to all overflowing bucketsbmapThe memory of
After the above defragmenting process, the green overflowing bucket shown above is collected by the GC garbage

Meanwhile, through the above analysis, it can be concluded that equal expansion does not change the order of elements.

conclusion

Through the above analysis, we can know the characteristics of Go Map:

Out-of-order write
Multiplication forces elements to change order

So you can say “Go’s Map is unordered”.

Secondly, through this paper, we:

The reason why the Map traversal result of Go is “disorderly” is reviewed again
You learned about the Map writing process
You have learned about the design and purpose of Double capacity expansion and equal capacity expansion of Map

Check out the Go Easy series for more

Link tigerb. Cn/go / # / kernal…

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Why is the Map of Go unordered?

preface

Result of Go Map traversal is “out of order”

Go’s Map is essentially “unordered”

“Disorderly” write

1. Write (non-hash conflict write) : Writes are hash to a bucket instead of buckets.

2. Hash conflict write: If hash conflict exists, write to the same bucket.

capacity

1. Multiplication forces elements to change order

2. Equal capacity expansion

conclusion

Check out the Go Easy series for more

Why is the Map of Go unordered?

preface

Result of Go Map traversal is “out of order”

Go’s Map is essentially “unordered”

“Disorderly” write

1. Write (non-hash conflict write) : Writes are hash to a bucket instead of buckets.

2. Hash conflict write: If hash conflict exists, write to the same bucket.

capacity

1. Multiplication forces elements to change order

2. Equal capacity expansion

conclusion

Check out the Go Easy series for more

Related Posts

Elasticsearch data synchronization practice based on MySQL Binlog

Prepare for the Java Interview: Thread pools in detail

Desktop system integration WEB authentication system solution