Go for-range VS for

Go 语言中，for-range 可以用来遍历string、数组(array)、切片(slice)、map和channel，实际使用过程踩了一些坑，所以，还是总结记录下for-range的原理。

首先，go是值传递语言。变量是指针类型，复制指针传递，变量是结构体类型，复制结构体传递，变量作为函数入参也是如此。再看下string、array、slice、map和channel的底层数据结构：

数据类型	底层结构
string	结构体：一个变量 len 、一个指针指向存储数据的字符数组
array(数组)	数组：底层分配的连续内存
slice(切片)	结构体：一个变量 len、一个变量 cap 、一个指针指向存储数据的数组。也称为动态数组
map	指向一个结构体的指针
channel	指向一个结构体的指针

一、for-range编译器源码

源码来自于 go GCC 版本的编译器的 statements.cc/For_range_statement::do_lowe：https://github.com/golang/gofrontend/blob/master/go/statements.cc，

编译器对 for range 表达式的解析注释如下：

// Arrange to do a loop appropriate for the type.  We will produce
//   for INIT ; COND ; POST {
//           ITER_INIT
//           INDEX = INDEX_TEMP
//           VALUE = VALUE_TEMP // If there is a value
//           original statements
//   }

可见range实际上是一个C风格的循环结构。每种类型的实现如下。

array

// The loop we generate:
//   for_temp := range
//   len_temp := len(for_temp)
//   for index_temp = 0; index_temp < len_temp; index_temp++ {
//           value_temp = for_temp[index_temp]
//           index = index_temp
//           value = value_temp
//           original body
//   }

slice

//   for_temp := range
//   len_temp := len(for_temp)
//   for index_temp = 0; index_temp < len_temp; index_temp++ {
//           value_temp = for_temp[index_temp]
//           index = index_temp
//           value = value_temp
//           original body
//   }

数组与数组指针的遍历过程与slice基本一致。

遍历slice前会先获得slice的长度len_temp作为循环次数，循环体中，每次循环会先获取元素值，如果for-range中接收index和value的话，则会对index和value进行一次赋值。循环开始前循环次数就已经确定了，所以循环过程中新添加的元素是没办法遍历到的。

map

// Lower a for range over a map.
// The loop we generate:
//   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
//   }

遍历map时没有指定循环次数，循环体与遍历slice类似。由于map底层实现与slice不同，map底层使用hash表实现，插入数据位置是随机的，所以遍历过程中新插入的数据不能保证遍历到。

channel

// Lower a for range over a channel.
// The loop we generate:
//   for {
//           index_temp, ok_temp = <-range
//           if !ok_temp {
//                   break
//           }
//           index = index_temp
//           original body
//   }

一直循环读数据，如果有数据则取出，如果没有则阻塞，如果channel被关闭则退出循环

string

// Lower a for range over a string.
// The loop we generate:
//   len_temp := len(range)
//   var next_index_temp int
//   for index_temp = 0; index_temp < len_temp; index_temp = next_index_temp {
//           value_temp = rune(range[index_temp])
//           if value_temp < utf8.RuneSelf {
//                   next_index_temp = index_temp + 1
//           } else {
//                   value_temp, next_index_temp = decoderune(range, index_temp)
//           }
//           index = index_temp
//           value = value_temp
//           
// original body
//   }

for-range迭代的共同点

1. 所有类型的 range 本质上都是 C 风格的for循环。

2. 遍历到的值会被赋值给一个临时变量。(赋值给临时变量的操作理论上是会产生一次数据copy)

二、for-range常见问题/坑

1. 迭代时取元素地址

	strings := []string{"a", "b", "c"}
	
	// bad
	for index, str := range strings {
		fmt.Println(index, " ", str, " ", &str)
	}

	// good
	for index, str := range strings {
		fmt.Println(index, " ", str, " ", &strings[index])
	}

原因：for-range迭代集合时，声明了一个临时变量，每次将集合的元素赋值给临时变量，&元素取的一直都是临时变量的地址，并不是实际集合元素的地址。

2. 数组迭代

	strings := [3]string{"a", "b", "c"}

	// bad
	for index, str := range strings {
		fmt.Println(index, " ", str)
	}
	// bad
	for index := range strings {
		fmt.Println(index, " ", strings[index])
	}

	// good
	for i := 0; i < len(strings); i++ {
		fmt.Println(i, " ", strings[i])
	}

原因：for-range迭代数组，底层copy了一个新数组，for-range是对copy的新数组进行循环处理。2.1 for-range迭代数组时，若原数组发生数据更新不会影响到for-range的数据。

	strings := [5]string{"a", "b", "c"}
	for index, str := range strings {
		strings[0], strings[1], strings[2], strings[3] = "aa", "bb", "cc", "dd"
		fmt.Println(index, " ", str)
	}
	fmt.Println(strings)

2.2 for-range迭代数组，数组越大，效率越低，性能越差。

func BenchmarkArrayFor(b *testing.B) {
	for i := 0; i < b.N; i++ {
		strings := [1024]string{"a", "b", "c"}
		// good
		for i := 0; i < len(strings); i++ {
			_ = i
			_ = strings[i]
		}
	}
}
func BenchmarkArrayRange(b *testing.B) {
	for i := 0; i < b.N; i++ {
		strings := [1024]string{"a", "b", "c"}
		// bad
		for index, str := range strings {
			_ = index
			_ = str
		}
	}
}
func BenchmarkArrayRange2(b *testing.B) {
	for i := 0; i < b.N; i++ {
		strings := [1024]string{"a", "b", "c"}
		// bad
		for index := range strings {
			_ = index
			_ = strings[index]
		}
	}
}

benchmark结果：

go test -bench=. -benchmem

BenchmarkArrayFor-12             4597723               257.8 ns/op             0 B/op          0 allocs/op
BenchmarkArrayRange-12           2538220               486.1 ns/op             0 B/op          0 allocs/op
BenchmarkArrayRange2-12          2261341               546.4 ns/op             0 B/op          0 allocs/op

3. slice迭代、map迭代

声明一个User

type User struct {
	ID        int64
	Name      string
	Desc      string
	Brother   *User
	ByteSlice []byte
	ByteArray [4096]byte
}

var userSlice = make([]User, 10240)
var userSlicePointer = make([]*User, 10240)
var userMap = make(map[int64]User, 10240)

	// bad
	for i := 0; i < len(userSlice); i++ {
		_ = userSlice[i]
	}

	// good
	for _, user := range userSlice {
		_ = user
	}

原因：for-range迭代简单清晰，for-range迭代slice、map不会copy底层存储数据的数组，虽然编译器初始有一次赋值操作的数据copy，但由于编译器后续的优化(一般是SSA静态单一赋值)，实际for-range迭代slice、map比for可能还要更快。

3.1 for-range迭代slice时，若原slice发生数据更新会影响到for-range的数据。

	strings := []string{"a", "b", "c"}
	for index, str := range strings {
		strings[0], strings[1], strings[2] = "aa", "bb", "cc"
		fmt.Println(index, " ", str)
	}
	fmt.Println(strings)

3.2 for-range迭代slice、map比for要快

数据初始化，运行时在变量小于32B时，可能直接在栈分配空间，尽量避免这种情况：

func initUser() {
	for i := 0; i < 10240; i++ {
		userSlice[i] = User{
			ID: int64(i),
			Name: "测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，" +
				"测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，" +
				"测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，" +
				"测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，" +
				"测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，" +
				"测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，yzh" + strconv.Itoa(i),
			Desc: "测试描述哈哈哈哈 hello world",
			Brother: &User{
				ID: int64(i + 1),
				Name: "测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，" +
					"测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，" +
					"测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，" +
					"测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，测试名称，yzh" + strconv.Itoa(i),
				Desc: "测试描述哈哈哈哈 hello world Brother",
			},
			ByteSlice: initByte(),
		}
	}

	for i := 0; i < 10240; i++ {
		userSlicePointer[i] = &User{
			ID:   int64(i),
			Name: "yzh" + strconv.Itoa(i),
			Desc: "测试描述哈哈哈哈 hello world",
		}
	}

	for i := 0; i < 10240; i++ {
		userMap[int64(i)] = User{
			ID:   int64(i),
			Name: "yzh" + strconv.Itoa(i),
			Desc: "测试描述哈哈哈哈 hello world",
		}
	}
}

func initByte() []byte {
	buf := make([]byte, 0, 4096)
	for i := 0; i < 4096; i++ {
		buf = append(buf, 'a')
	}
	return buf
}

benchmark代码：

func BenchmarkForSlice(b *testing.B) {
	initUser()
	for i := 0; i < b.N; i++ {
		var a int64
		var b1 string
		var c string
		var d *User
		var e []byte
		for k := 0; k < len(userSlice); k++ {
			a = userSlice[k].ID
			b1 = userSlice[k].Name
			c = userSlice[k].Desc
			d = userSlice[k].Brother
			e = userSlice[k].ByteSlice
		}
		_ = a
		_ = b1
		_ = c
		_ = d
		_ = e
	}
}

func BenchmarkRangeSlice(b *testing.B) {
	initUser()
	for i := 0; i < b.N; i++ {
		var a int64
		var b1 string
		var c string
		var d *User
		var e []byte
		for _, user := range userSlice {
			a = user.ID
			b1 = user.Name
			c = user.Desc
			d = user.Brother
			e = user.ByteSlice
		}
		_ = a
		_ = b1
		_ = c
		_ = d
		_ = e
	}
}

func BenchmarkForSliceUseArray(b *testing.B) {
	initUser()
	for i := 0; i < b.N; i++ {
		initUser()
		for i := 0; i < b.N; i++ {
			var a int64
			var b1 string
			var c string
			var d *User
			var e []byte
			var f [4096]byte
			for k := 0; k < len(userSlice); k++ {
				a = userSlice[k].ID
				b1 = userSlice[k].Name
				c = userSlice[k].Desc
				d = userSlice[k].Brother
				e = userSlice[k].ByteSlice
				f = userSlice[k].ByteArray
			}
			_ = a
			_ = b1
			_ = c
			_ = d
			_ = e
			_ = f
		}
	}
}

func BenchmarkRangeSliceUseArray(b *testing.B) {
	initUser()
	for i := 0; i < b.N; i++ {
		var a int64
		var b1 string
		var c string
		var d *User
		var e []byte
		var f [4096]byte
		for _, user := range userSlice {
			a = user.ID
			b1 = user.Name
			c = user.Desc
			d = user.Brother
			e = user.ByteSlice
			f = user.ByteArray
		}
		_ = a
		_ = b1
		_ = c
		_ = d
		_ = e
		_ = f
	}
}

func BenchmarkForSlicePoint(b *testing.B) {
	initUser()
	for i := 0; i < b.N; i++ {
		var tmp string
		for k := 0; k < len(userSlicePointer); k++ {
			tmp = userSlicePointer[k].Name
		}
		_ = tmp
	}
}

func BenchmarkRangeSlicePoint(b *testing.B) {
	initUser()
	for i := 0; i < b.N; i++ {
		var tmp string
		for _, user := range userSlicePointer {
			tmp = user.Name
		}
		_ = tmp
	}
}

func BenchmarkForMap(b *testing.B) {
	initUser()
	for i := 0; i < b.N; i++ {
		var tmp string
		for k := 0; k < len(userMap); k++ {
			tmp = userMap[int64(k)].Name
		}
		_ = tmp
	}
}

func BenchmarkRangeMap(b *testing.B) {
	initUser()
	for i := 0; i < b.N; i++ {
		var tmp string
		for _, user := range userMap {
			tmp = user.Name
		}
		_ = tmp
	}
}

benchmark结果：

go test -bench=. -benchmem

BenchmarkForSlice-12                      291997              4126 ns/op             546 B/op          0 allocs/op
BenchmarkRangeSlice-12                    435122              2620 ns/op             366 B/op          0 allocs/op
BenchmarkForSliceUseArray-12                 594           2411410 ns/op          268768 B/op        188 allocs/op
BenchmarkRangeSliceUseArray-12               398           2942304 ns/op          401127 B/op        282 allocs/op
BenchmarkForSlicePoint-12                  22102             50078 ns/op            7223 B/op          5 allocs/op
BenchmarkRangeSlicePoint-12                20089             50378 ns/op            7947 B/op          5 allocs/op
BenchmarkForMap-12                          4804            242261 ns/op           33232 B/op         23 allocs/op
BenchmarkRangeMap-12                        6156            192102 ns/op           25933 B/op         18 allocs/op

1、for-range迭代slice、map反而比for更快。编译器层面优化。

2、slice中存储原生类型比指针类型迭代更快。指针类型有额外性能消耗。so，指针类型不要滥用！

3、slice中含有数组元素，未使用到数组元素时，不管是for还是for-range，都不会产生数组复制。

4、slice中含有数组元素，使用到数组元素时，for更快。for-range会复制数组。

关闭编译器优化的benchmark：

go test -c -gcflags '-N -l' .

./slice.test -test.bench .

BenchmarkForSlice-12                        6429            162407 ns/op
BenchmarkRangeSlice-12                       346           3267555 ns/op
BenchmarkForSliceUseArray-12                  27          84980399 ns/op
BenchmarkRangeSliceUseArray-12               259           4216479 ns/op
BenchmarkForSlicePoint-12                   8480            118691 ns/op
BenchmarkRangeSlicePoint-12                11155            104476 ns/op
BenchmarkForMap-12                          2485            494308 ns/op
BenchmarkRangeMap-12                         330           4379847 ns/op

可以看到：在没有优化的情况下，两种loop的性能都大幅下降，并且for range下降更多，性能显著不如普通for。可以对比一下函数在正常优化(go tool compile -S xxx.go)以及关闭优化时(go tool compile -S -N -l)的汇编代码片段，会发现关闭优化后，汇编代码使用了很多中间变量存储中间结果，而优化后的代码则消除了这些中间状态。

三、for-range原理总结

1. for-range 本质上是 C 风格的for循环。

2. for-range迭代时，声明了一个临时变量，每次将迭代的元素赋值给临时变量。编译器编译阶段。

3. 理论上赋值给临时变量的操作是会产生一次数据copy，但由于编译器的优化，可能会消除实际的copy。the compiler can eliminate the actual copy if it doesn't make any difference

4. for-range概念上都是copy，不管是数组、slice、map，迭代的都是值拷贝对象。数组是copy一份新数组，slice、map是copy一份新slice、map，但不会copy底层存储数据的结构。

四、for-range vs for最佳实践

1. for-range迭代集合时取元素地址使用 &集合[index]，而不是 &元素。

2. 数组迭代推荐使用for，避免使用for-range迭代数组，特别是大数组。

3. slice、map等引用类型推荐使用for-range迭代。

4. slice、map中含有数组元素，数组元素较大时，推荐使用for迭代。

Go编译代码

编译阶段

在将给定源语言的一个程序翻译成特定的目标机器代码的过程中，一个编译器可能构造出一系列中间表示(IR)，如下图：

高层中间表示更接近于源语言，而低层的中间表示则更接近于目标机器。在Go编译过程中，如果说内联优化使用的IR是高层中间表示，那么低层中间表示非支持静态单赋值(SSA)的中间代码形式莫属。

编译优化

go编译器的优化主要分为内联优化和静态单一赋值。

静态单一赋值(SSA)

静态单一赋值(Static Single Assignment，SSA)，是一种中间代码的表示形式(IR)，或者说是某种中间代码所具备的属性。具有SSA属性的IR都具有这样的特征：

1. 每个变量在使用前都需要被定义
2. 每个变量被精确地赋值一次(使得一个变量的值与它在程序中的位置无关)

下面是一个简单的例子(伪代码)：

y = 1
y = 2
x = y

转换为SSA形式为：

y1 = 1
y2 = 2
x1 = y2

由于SSA要求每个变量只能赋值一次，因此在转换为SSA后，变量y用y1和y2来表示，后面的序号越大，表明y的版本越新。从这一段三行的代码我们也可以看到，在SSA层面，y1 = 1这行代码就是一行死代码(dead code)，即对结果不会产生影响的代码，可以在中间代码优化时被移除掉。

SSA优化在编译过程中所处的位置：

通过使用SSA而启用或增强的编译器优化算法包括:

常量传播a=3*4+5;——将计算从运行时转换为编译时，例如，将指令视为a=17;
值范围传播 – 预先计算可能的计算范围，允许提前创建分支预测
稀疏条件常量传播——范围检查一些值，允许测试预测最可能的分支
死代码消除——删除对结果没有影响的代码
全局值编号——替换产生相同结果的重复计算
部分冗余消除——删除以前在程序的某些分支中执行的重复计算
强度降低——用更便宜但等效的操作替换昂贵的操作，例如用可能更便宜的左移（乘法）或右移（除法）替换整数乘法或除以 2 的幂。
寄存器分配——优化有限数量的机器寄存器如何用于计算

普通for循环

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

初始化循环的 Ninit；
循环的继续条件 Left；
循环体结束时执行的 Right；
循环体 NBody：

for Ninit; Left; Right {
    NBody
}

在生成 SSA 中间代码的阶段，cmd/compile/internal/gc.state.stmt 方法在发现传入的节点类型是 OFOR 时会执行以下的代码块，这段代码会将循环中的代码分成不同的块：

func (s *state) stmt(n *Node) {
	switch n.Op {
	case OFOR, OFORUNTIL:
		bCond, bBody, bIncr, bEnd := ...

		b := s.endBlock()
		b.AddEdgeTo(bCond)
		s.startBlock(bCond)
		s.condBranch(n.Left, bBody, bEnd, 1)

		s.startBlock(bBody)
		s.stmtList(n.Nbody)

		b.AddEdgeTo(bIncr)
		s.startBlock(bIncr)
		s.stmt(n.Right)
		b.AddEdgeTo(bCond)
		s.startBlock(bEnd)
	}
}

一个常见的 for 循环代码会被 cmd/compile/internal/gc.state.stmt 转换成下面的控制结构，该结构中包含了 4 个不同的块，这些代码块之间的连接表示汇编语言中的跳转关系，与我们理解的 for 循环控制结构没有太多的差别。