GO Range内幕

GO 刘宇帅 5年前 阅读量: 4076

原文地址:Go Range Loop Internals

Go range是非常方便的,但是我总感觉它非常的神秘。不只是我这样认为:

#golang pop quiz: does this program terminate?

func main() {
v := []int{1, 2, 3}
for i := range v {
v = append(v, i)
}
}

— Dαve Cheney (@davecheney) January 13, 2017 Today's #golang gotcha: the two-value range over an array does a copy. Avoid by ranging over the pointer instead.https://t.co/SbK667osvA — Damian Gryski (@dgryski) January 3, 2017

我可以把这些死记下来,但是如果我不了解真正的原理的话,我很容易就会把这些给忘掉。所以下面就详细分析下原理。

第一步:读官方文档

第一步就是去读range的官方文档。range的官方文档在for语句模块这里。这里就不去复制文档内容了,下面做一些总结。
首先让我们记住下面的代码:

for i := range a {
    fmt.Println(i)
}

range变量

你们大多数都知道在range语句中可以这样赋值循环变量:

  • 赋值(=)
  • 短变量声明(:=) 你也可以什么都不放,忽略循环变量。
    如果你使用短变量声明的方式赋值,那么在range循环中这个变量会被复用。

    range表达式

    在range语句中处于range右侧的子句,我们称为range表达式。在range表达式中可以放在右侧别遍历的数据类型包括如下几种:

  • array
  • array指针
  • slice
  • string
  • map
  • 允许接收数据的channel range表达式在循环开始之前被'evaluated '一次。例外说明:如果你是对一个数组或一个数组的指针做迭代并且只需要索引值,那么只‘ evaluated ’len(a)。也就是说可能会在编译的时候'evaluated 'len(a),并用一个常量去代替表达式。len函数的文档定义如下:

    如果s的数据类型是数组或则是数组的指针,并且s不包含channel接收数据和函数调用,那么len(s)就是一个常量。在这种情况下s是不会被求值的。否者lencap函数就不是常数,s也会被求值。

那么上面说的evaluated是什么意思呢?很不幸,我在官方文档里并没有找到说明。当然我可以猜测它的意思是执行这个表达值知道它可以被迭代。无论如何这个求值一定是在循环开始之前执行一次,你如何只执行一个表达式一次呢?只能把它赋值给一个变量!这就是这里发生的事吗?
有趣得是官方文档提到一些关于map增加删除的特殊(slice没有提到):

If map entries that have not yet been reached are removed during iteration, the corresponding iteration values will not be produced. If map entries are created during iteration, that entry may be produced during the iteration or may be skipped.

稍后再来说map

第二步:range支持的数据类型

如果我们假设range表达式在循环开始前被赋值给一个变量,这意味着什么?这依赖于具体的数据类型,所以让我们详细看下range支持的数据类型。
开始之前,我必须要知道:在Go里只要是赋值就都是值的拷贝。如果你给指针赋值那么你就复制指针,如果你给结构体赋值你就复制结构体。函数调用的时候也是一样的。

类型 具体的数据结构
array array
string 一个包含长度和数组的结构体
slice 一个包含长度,容量和数组的结构体
map 结构体的指针
channel 结构体的指针

想要了解这些数据类型的底层的数据结构可以看下面的参考文献。
那么这意味着什么呢?下面的例子展示具体的不同:

// 复制整个数组
var a [10]int
acopy := a

// 复制slice的struct结构体,并不复制底层的数组
s := make([]int, 10)
scopy := s

// 复制map变量的指针,不复制底层数据结构
m := make(map[string]int)
mcopy := m

第三步:Go编译源码

我比较懒惰,在google上找的Go的编译源码。我找的第一件事就是编译器的GCC的版本。有趣的是,在statements.cc里有和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:
//   len_temp := len(range)
//   range_temp := range
//   for index_temp = 0; index_temp < len_temp; index_temp++ {
//           value_temp = range_temp[index_temp]
//           index = index_temp
//           value = value_temp
//           original body
//   }

slices:

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

两个对比有两个共同点:

- 所有类型的循环都是C语言风格的循环封装
- 你想要遍历的所有变量都会被赋值给一个临时变量

这就是在GCC前端里的实现。我知道大多数人都是使用go编译器,go编译器其实也是做了同样的事

总结

  1. 循环变量会被重复利用,每次循环的时候都会被赋值
  2. range表达式(要被遍历的对象)在循环开始之前会被赋值给一个变量
  3. 在循环构成中,你可以给map添加或的删除成员,添加的成员可能会也可能不会被循环到。 在我们了解了这之后,我们回头再看看文章开头的例子。

    Dave's tweet

    golang pop quiz: does this program terminate?

    func main() { v := []int{1, 2, 3} for i := range v { v = append(v, i) } } — Dαve Cheney (@davecheney) January 13, 2017

程序会终止的,因为上面的代码翻译层底层代码如下:

for_temp := v
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
        v = append(v, index)
}

我们知道slices是语法糖,它其实是一个结构体的指针,结构体属性包含一个数组的指针。上面的循环是在原始变量的副本for_temp上进行的,任何在v上的修改都不会影响for_temp。但是他们的数组属性还在共享一个数组的指针,所以如果执行v[i]=1则会影响for_temp

Damian's tweet

Today's #golang gotcha: the two-value range over an array does a copy. Avoid by ranging over the pointer instead.https://t.co/SbK667osvA — Damian Gryski (@dgryski) January 3, 2017

和上面的例子一样,数组在遍历开始之前被赋值给一个新的变量,也就是说是对真个数组的复制。但是如果如果是数组指针那么复制就是指针的值,并不是真个数组。

maps

在Go语言规范里我们知道:

  • 在range循环中添加和删除元素是安全的
  • 如果你在循环中添加一个新元素,那么在真个循环结束时可能看不到新加的值。 这是为什么呢?举个例子:我们知道map是一个struct的指针,在循环开始之前这个指针会被复制,循环的时候并不是原来的数据结构,所以可以在循环的时候添加或者删除元素。
    但是为什么你添加的元素未必能在后续的循环中看到呢?map的底层是hash表,如果你知道hash表的具体实现那么你就知道hash里元素的顺序并不是特定顺序的。你添加的元素可能会被放在第一个索引的位置。所以如果你给map添加元素,那么它可能会被放在任意的位置,你无法预测的。

    参考文献

    1. The Go Programming Language Specification
    2. Go slices: usage and internals
    3. Go Data Structures
    4. Inside the map implementation: slides | video
    5. Understanding nil: slides | video
    6. string source code
    7. slice source code
    8. map source code
    9. channel source code

提示

功能待开通!