β

对Go的Slice进行Append的一个“坑”

ShareCore 516 阅读

今天我们说说Go为数不多的一个“坑”。这个“坑”的代码是这样的:

func main() {
  arr1 := [5]int{1, 2, 3, 4, 5}
  slice1 := arr1[1:2]
  slice1 = append(slice1, 6, 7, 8)
  fmt.Println("slice1:", slice1)
  fmt.Println("arr1:", arr1)

  arr2 := [5]int{1, 2, 3, 4, 5}
  slice2 := arr2[1:3]
  slice2 = append(slice2, 6, 7, 8)
  fmt.Println("slice2:", slice2)
  fmt.Println("arr2:", arr2)
}

上面代码输出结果是:

$ go run sliceTrap.go
slice1: [2 6 7 8]
arr1: [1 2 6 7 8] //神奇地,原数组被改变了
slice2: [2 3 6 7 8]
arr2: [1 2 3 4 5] //一切正常

从上结果发现,原来的arr1的值被“莫名”改变了,但arr2的值并没有改变,这貌似并不符合我们的预期。当然,这是Go代码的一个“坑”,我们写代码时需要特别注意避免。接下来,探讨一下这个“坑”的背后原因。

首先,我们需要了解一个slice有三个基本组成元素:一个指向首元素的指针,一个长度值和一个容量值。我们可以下面这样的结构来表示slice。(go的内部类似实现可以在/src/pkg/runtime/runtime.h下查看)

type slice struct{
 Ptr *int //指向分配的数组的指针
 Len int  // 长度
 Cap int  // 容量
}

可以调用make方法来创建一个slice

func make([]T, len, [cap]) []T

通过make方式的参数,可以看到,一个slice接收一个指定类型,一个指定长度和一个可选的容量参数。make方法调用后,它背后其实一样分配了一个指定类型的数组,并返回一个slice引用指向该数组。如:

slice:= make([]int, 5, 5)
//注意:Go的默认零值
// slice == []int{0, 0, 0, 0, 0}

调用make时,当cap参数未指定,那它的值与len相同。如:

slice:=make([]int,5)
//len(slice)==5
//cap(slice)==5

除了以上两种方式创建slice,我们也可以采用对原slice或数组进行切片的方式来创建,如:

arr := [5]int{1, 2, 3, 4, 5}
s1 := arr[1:4]//对数组进行切片
//len(s1)== 3 //len为切片开始位置到结束位置的个数
//cap(s1)=4 //容量为原数组总长度减开始位置

s2:=s1[2:] //对slice进行切片
//len(s2)==1 //len为切片开始位置到结束位置的个数
//cap(s2)==2 //容量为原slice总容量减开始位置

这里有一点需要特别了解,对slice进行切片操作,并不会新创建一个对象(分配内存),而只是在原来slice的基础上移动指针位置。了解对一点,对我们结合下文,理解本文开头提到的“坑”有帮助。我们用下面的图来说明这一点,更好理解。

slice := []int{1, 2, 3, 4, 5}
newslice:=slice[2:4]

slicing

slice的容量值,限定了slice可容纳元素的最多个数,当我们往slice里添加新元素,导致元素个数超过容量时(len>cap),则需要对slice进行扩容(Growing slices)。append方法的调用就是典型的扩容示例。我们来来模拟一下append方法的基本实现:

func AppendInt(slice []int, data ...int) []int {
    m := len(slice)
    n := m + len(data)
    if n > cap(slice) {//判断是否需要扩容
      //创建新的slice,其实也就是开辟了一个新的内存空间,
      //并返回了指向新地址的指针(一般会是增加为总需要长度的两倍,加1是为了防止n=0的情况)
        newSlice := make([]int, (n+1)*2)

        //将旧的slice的元素值,copy到新创建的slice
        copy(newSlice, slice)

       //关键的一步,slice重新指向新分配的slice,这也就是本文开头的例子里arr2的值没有变化的原因
        slice = newSlice
    }
    slice = slice[0:n]
   //由于本步的copy操作,直接改变了原slice(如果没有重分配的话)里元素的值,
   //所以导致了本文开头的例子里arr2的值的变化
    copy(slice[m:n], data)
    return slice
}

上面的代码,基本模拟了buitIn方法append的实现,具体的内部实现可以从Go的代码/src/pkg/runtime/slice.c里看到,也可以在文章最后附加内容里查看。

通过上面的模拟append函数的代码可以看出,当append进来的元素个数会导致超出原slice的容量限制时会执行下面步骤:

  1. 创建一个容量更大的slice(扩容)。与对slice进行切片操作不同,这个slice是全新的,它的数组也是全新的,指针也是指向新数组的首位置。

  2. 新slice创建好后,会将原来被append的slice的元素内容进行值复制到新的slice。

  3. 将要被append元素,追加到新slice的末尾。

从以上几步可以看出,对slice进行扩容后追加元素,原slice的状态不会发生任何改变。这也就解释了本文开头的代码里,arr2的值,为什么没有发生变化。

但与slice需要扩容不同的是,当原slice容量足够,不需要进行扩容时,那对slice元素的追加,都是发生在原slice里的(数组里),所以,原数组被“悄悄”改变了。这也解释了,为什么arr1的状态被改变了的原因。

附:/src/pkg/runtime/slice.c runtime·appendslice函数代码

void runtime·appendslice(SliceType *t, Slice x, Slice y, Slice ret)
{
  intgo m;
  uintptr w;
  void *pc;
  uint8 *p, *q;

  m = x.len+y.len;
  w = t->elem->size;

  if(m < x.len)
      runtime·throw("append: slice overflow");

  if(m > x.cap)
      growslice1(t, x, m, &ret);
  else
      ret = x;

  if(raceenabled) {
      // Don't mark read/writes on the newly allocated slice.
      pc = runtime·getcallerpc(&t);
      // read x[:len]
      if(m > x.cap)
          runtime·racereadrangepc(x.array, x.len*w, w, pc, runtime·appendslice);
      // read y
      runtime·racereadrangepc(y.array, y.len*w, w, pc, runtime·appendslice);
      // write x[len(x):len(x)+len(y)]
      if(m <= x.cap)
          runtime·racewriterangepc(ret.array+ret.len*w, y.len*w, w, pc, runtime·appendslice);
  }

  // A very common case is appending bytes. Small appends can avoid the overhead of memmove.
  // We can generalize a bit here, and just pick small-sized appends.
  p = ret.array+ret.len*w;
  q = y.array;
  w *= y.len;
  if(w <= appendCrossover) {
      if(p <= q || w <= p-q) // No overlap.
          while(w-- > 0)
              *p++ = *q++;
      else {
          p += w;
          q += w;
          while(w-- > 0)
              *--p = *--q;
      }
  } else {
      runtime·memmove(p, q, w);
  }
  ret.len += y.len;
  FLUSH(&ret);
}

static void growslice1(SliceType *t, Slice x, intgo newcap, Slice *ret)
{
  intgo m;

  m = x.cap;
  
  // Using newcap directly for m+m < newcap handles
  // both the case where m == 0 and also the case where
  // m+m/4 wraps around, in which case the loop
  // below might never terminate.
  if(m+m < newcap)
      m = newcap;
  else {
      do {
          if(x.len < 1024)
              m += m;
          else
              m += m/4;
      } while(m < newcap);
  }
  makeslice1(t, x.len, m, ret);
  runtime·memmove(ret->array, x.array, ret->len * t->elem->size);
}
Included file ‘post/copyright.html’ not found in _includes directory
作者:ShareCore
ShareCore
原文地址:对Go的Slice进行Append的一个“坑”, 感谢原作者分享。

发表评论