1.循环

1. 经典循环

下面是一段经典的三段式循环的代码，我们将它编译成汇编指令：

package main

func main() {
	for i := 0; i < 10; i++ {
		println(i)
	}
}

"".main STEXT size=98 args=0x0 locals=0x18
	00000 (main.go:3)	TEXT	"".main(SB), $24-0
	...
	00029 (main.go:3)	XORL	AX, AX                   ;; i := 0
	00031 (main.go:4)	JMP	75                         
	00033 (main.go:4)	MOVQ	AX, "".i+8(SP)
	00038 (main.go:5)	CALL	runtime.printlock(SB)
	00043 (main.go:5)	MOVQ	"".i+8(SP), AX
	00048 (main.go:5)	MOVQ	AX, (SP)
	00052 (main.go:5)	CALL	runtime.printint(SB)
	00057 (main.go:5)	CALL	runtime.printnl(SB)
	00062 (main.go:5)	CALL	runtime.printunlock(SB)
	00067 (main.go:4)	MOVQ	"".i+8(SP), AX
	00072 (main.go:4)	INCQ	AX                       ;; i++
	00075 (main.go:4)	CMPQ	AX, $10                  ;; 比较变量 i 和 10
	00079 (main.go:4)	JLT	33                         ;; 最关键的一行：跳转到 33 行如果 i < 10
	...

  1. 0029 ~ 0031 行负责循环的初始化；

    1. 对寄存器 AX 中的变量 i 进行初始化并执行 JMP 75 指令跳转到 0075 行；

  2. 0075 ~ 0079 行负责检查循环的终止条件，将寄存器中存储的数据 i 与 10 比较；

    1. JLT 33 命令会在变量的值小于 10 时跳转到 0033 行执行循环主体；

    2. 大于 10 时跳出循环体执行下面的代码；

  3. 0033 ~ 0072 行是循环内部的语句；

    1. 通过多个汇编指令打印变量中的内容；

    2. INCQ AX 指令会将变量加一，然后再与 10 进行比较，回到第二步；

在汇编语言中，无论是经典的 for 循环还是 for-range 循环都会使用 JMP 等命令跳回循环体的开始位置复用代码。

for-range 这种写法经过编译器优化最终也会转换成普通的 for 循环。

Go 语言中的经典循环在编译器看来是一个 OFOR 类型的节点，这个节点由以下四个部分组成：

  1. 初始化循环的 Ninit；

  2. 循环的继续条件 Left；

  3. 循环体结束时执行的 Right；

  4. 循环体 NBody：

for Ninit; Left; Right {
    NBody
}

2. 范围循环

范围循环同时使用 for 和 range 两个关键字，编译器会在编译期间将所有 for-range 循环变成经典循环。从编译器的视角来看，就是将 ORANGE 类型的节点转换成 OFOR 节点。

节点类型的转换过程都发生在中间代码生成阶段，所有的 for-range 循环都会被 cmd/compile/internal/gc.walkrange 转换成不包含复杂结构、只包含基本表达式的语句。接下来，我们按照循环遍历的元素类型依次介绍遍历数组和切片、哈希表、字符串以及管道时的过程。

2.1 数组和切片

对于数组和切片来说，Go 语言有三种不同的遍历方式，这三种不同的遍历方式分别对应着代码中的不同条件，它们会在 cmd/compile/internal/gc.walkrange 函数中转换成不同的控制逻辑，我们会分成几种情况分析该函数的逻辑：

  1. 分析遍历数组和切片清空元素的情况；

  2. 分析使用 for range a {} 遍历数组和切片，不关心索引和数据的情况；

  3. 分析使用 for i := range a {} 遍历数组和切片，只关心索引的情况；

  4. 分析使用 for i, elem := range a {} 遍历数组和切片，关心索引和数据的情况；

2.1.1 切片清空元素

当我们想要在 Go 语言中清空一个切片或者哈希时，一般都会使用以下的方法将切片中的元素置零：

func main() {
	arr := []int{1, 2, 3}
	for i, _ := range arr {
		arr[i] = 0
	}
}

依次遍历切片和哈希看起来是非常耗费性能的，因为数组、切片和哈希占用的内存空间都是连续的，所以最快的方法是直接清空这片内存中的内容。Go 语言在遍历时会做如下优化：

func walkrange(n *Node) *Node {
	switch t.Etype {
	case TARRAY, TSLICE:
		if arrayClear(n, v1, v2, a) {
			return n
		}

在 arrayClear 函数中，Go 语言会直接使用 runtime.memclrNoHeapPointers 或者 runtime.memclrHasPointers 清除目标数组内存空间中的全部数据，并在执行完成后更新遍历数组的索引。

2.1.2 for range a

处理了上面的特殊情况之后，我们可以回到 ORANGE 节点的处理过程了。这里会设置 for 循环的 Left 和 Right 字段，也就是终止条件和循环体每次执行结束后运行的代码：

		ha := a

		hv1 := temp(types.Types[TINT])
		hn := temp(types.Types[TINT])

		init = append(init, nod(OAS, hv1, nil))
		init = append(init, nod(OAS, hn, nod(OLEN, ha, nil)))

		n.Left = nod(OLT, hv1, hn)
		n.Right = nod(OAS, hv1, nod(OADD, hv1, nodintconst(1)))

		if v1 == nil {
			break
		}

如果循环是 for range a {}，那么就满足了上述代码中的条件 v1 == nil，即循环不关心数组的索引和数据，这种循环会被编译器转换成如下形式：

ha := a
hv1 := 0
hn := len(ha)
v1 := hv1
for ; hv1 < hn; hv1++ {
    ...
}

这是 ORANGE 结构在编译期间被转换的最简单形式，由于原代码不需要获取数组的索引和元素，只需要使用数组或者切片的数量执行对应次数的循环，所以会生成一个最简单的 for 循环。

2.1.3 for i := range a

如果我们在遍历数组时需要使用索引 for i := range a {}，那么编译器会继续会执行下面的代码：

		if v2 == nil {
			body = []*Node{nod(OAS, v1, hv1)}
			break
		}

v2 == nil 意味着调用方不关心数组的元素，只关心遍历数组使用的索引。它会将 for i := range a {} 转换成下面的逻辑，与第一种循环相比，这种循环在循环体中添加了 v1 := hv1 语句，传递遍历数组时的索引：

ha := a
hv1 := 0
hn := len(ha)
v1 := hv1
for ; hv1 < hn; hv1++ {
    v1 = hv1 // 多了一步这个，v1 用于返回索引
    ...
}

2.1.4 for i, elem := range a

处理这种情况会使用下面这段的代码：

		tmp := nod(OINDEX, ha, hv1)
		tmp.SetBounded(true)
		a := nod(OAS2, nil, nil)
		a.List.Set2(v1, v2)
		a.Rlist.Set2(hv1, tmp)
		body = []*Node{a}
	}
	n.Ninit.Append(init...)
	n.Nbody.Prepend(body...)

	return n
}

这段代码处理的使用者同时关心索引和切片的情况。它不仅会在循环体中插入更新索引的语句，还会插入赋值操作让循环体内部的代码能够访问数组中的元素：

ha := a
hv1 := 0
hn := len(ha) // 这个遍历条件在遍历前就拷贝不变了
v1 := hv1     // 要返回的索引
v2 := nil     // 要返回的值
for ; hv1 < hn; hv1++ {
    tmp := ha[hv1]
    v1, v2 = hv1, tmp // 拷贝要返回的索引和值
    ...
}

因此可以解释以下现象：

  1. 循环期间向原切片追加元素，循环次数并不会变：因为要循环切片的长度一开始就拷贝走了，这个变量不会变

  2. 在循环中如果对变量进行取址，该地址也不会变：因为取的一直是同一个变量 v2 的地址，它的地址一直没变，只是在循环期间会修改值

2.2 哈希表

在遍历哈希表时，编译器会使用 runtime.mapiterinit 和 runtime.mapiternext 两个运行时函数重写原始的 for-range 循环：

// for key, val := range hash {} 这种写法的展开：
ha := a
hit := hiter(n.Type)
th := hit.Type
mapiterinit(typename(t), ha, &hit) // 遍历开始
for ; hit.key != nil; mapiternext(&hit) {
    key := *hit.key
    val := *hit.val
}

遍历前会通过 mapiterinit 函数初始化 runtime.hiter 结构体中的字段，并通过 runtime.fastrand 生成一个随机数帮助我们随机选择一个遍历桶的起始位置。Go 团队在设计哈希表的遍历时就不想让使用者依赖固定的遍历顺序，所以引入了随机数保证遍历的随机性。

func mapiterinit(t *maptype, h *hmap, it *hiter) {
	it.t = t
	it.h = h
	it.B = h.B
	it.buckets = h.buckets

	r := uintptr(fastrand())             // 随机数
	it.startBucket = r & bucketMask(h.B) // 随机数 % 2^B 作为起点桶下标
	it.offset = uint8(r >> h.B & (bucketCnt - 1))
	it.bucket = it.startBucket
	mapiternext(it) // 遍历
}

遍历哈希会使用 runtime.mapiternext 方法，该方法主要做两件事：桶的选择，以及桶内元素的遍历。

2.2.1 桶的选择

这步主要做两件事：

  1. 在待遍历的桶为空时，定位到下一个要遍历的桶；

  2. 遍历一轮，回到起始位置后，中止遍历

func mapiternext(it *hiter) {
	h := it.h
	t := it.t
	bucket := it.bucket
	b := it.bptr
	i := it.i
	alg := t.key.alg

next:
	if b == nil {
		if bucket == it.startBucket && it.wrapped { // 遍历一轮，回到起始位置后，中止遍历
			it.key = nil
			it.value = nil
			return
		}
		b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) // 下一个要遍历的桶地址
		bucket++                                                   // 下一个要遍历的桶下标
		if bucket == bucketShift(it.B) {                           // 下标到边界时，重置为0，从头开始遍历
			bucket = 0
			it.wrapped = true
		}
		i = 0
	}

2.2.2 桶内元素遍历

这个主要是遍历桶内的8个kv，以及溢出桶。如果哈希表处于扩容期间就会调用 runtime.mapaccessK 获取键值对。

	for ; i < bucketCnt; i++ {                   // bucketCnt=8
		offi := (i + it.offset) & (bucketCnt - 1)
		k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) // 遍历8个kv
		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 { // 如果处于扩容期间，调用 mapaccessK 遍历旧桶
			rk, rv := mapaccessK(t, h, k)
			it.key = rk
			it.value = rv
		}
		it.bucket = bucket
		it.i = i + 1
		return
	}
	b = b.overflow(t) // 遍历溢出桶
	i = 0
	goto next
}

2.3 字符串

遍历字符串的过程与数组、切片和哈希表非常相似，只是在遍历时会获取字符串中索引对应的字节并将字节转换成 rune。我们在遍历字符串时拿到的值都是 rune 类型的变量，for i, r := range s {} 的结构都会被转换成如下所示的形式：

ha := s
for hv1 := 0; hv1 < len(ha); {
    hv1t := hv1
    hv2 := rune(ha[hv1])
    if hv2 < utf8.RuneSelf { // ASCII 编码，只占用一个字节长，直接+1 即可
        hv1++
    } else {
        hv2, hv1 = decoderune(ha, hv1) // 占用多个字节，需要解码，索引也不是只+1了
    }
    v1, v2 = hv1t, hv2
}

字符串是一个只读的字节数组切片，所以范围循环在编译期间生成的框架与切片非常类似，只是细节有一些不同。

使用下标访问字符串中的元素时得到的就是字节，但是这段代码会将当前的字节转换成 rune 类型。如果当前的 rune 是 ASCII 的，那么只会占用一个字节长度，每次循环体运行之后只需要将索引加一，但是如果当前 rune 占用了多个字节就会使用 runtime.decoderune 函数解码

2.4 通道

使用 range 遍历 Channel 也是比较常见的做法，一个形如 for v := range ch {} 的语句最终会被转换成如下的格式：

ha := a
hv1, hb := <-ha
for ; hb != false; hv1, hb = <-ha {
    v1 := hv1
    hv1 = nil
    ...
}

循环会使用 <-ch 从管道中取出等待处理的值，这个操作会调用 runtime.chanrecv2 并阻塞当前的协程，当 runtime.chanrecv2 返回时会根据布尔值 hb 判断当前的值是否存在：

  • 如果不存在当前值，意味着当前的管道已经被关闭；

  • 如果存在当前值，会为 v1 赋值并清除 hv1 变量中的数据，然后重新陷入阻塞等待新数据

原文链接

https://draveness.me/golang/docs/part2-foundation/ch05-keyword/golang-for-range

Previous4.常用关键字Next2.defer

Last updated