源码分析--Go append

func append (s [] T, vs …T) [] T 的增长原理

在学 Go 语言的过程中，了解到切片，同时学到了切片增长函数 append，在使用的过程中发现一些问题，所以研究源码记录一下。

Why

在官方的 A tour of Go 中，有这样一段代码

package main

import "fmt"

func main () {
 var s [] int
 printSlice (s)

 //append works on nil slices.
 s = append (s, 0)
 printSlice (s)

 // The slice grows as needed.
 s = append (s, 1)
 printSlice (s)

 // We can add more than one element at a time.
 s = append (s, 2, 3, 4)
 printSlice (s)
}

func printSlice (s [] int) {
 fmt.Printf ("len=%d cap=%d %v\n", len (s), cap (s), s)
}

//result:
//len=0 cap=0 []
//len=1 cap=1 [0]
//len=2 cap=2 [0 1]
//len=5 cap=6 [0 1 2 3 4]GO

我发现一个规律：

len=5 cap=6
len=7 cap=8
len=9 cap=10
len=11 cap=12

在 0-5 容量内，len 和 cap 保持一致，在 len>5 对其进行扩容时，Go 似乎总是把 cap+2，然后我写了一段测试代码

package main

import "fmt"

func main () {
 var nums [] int
 fmt.Printf ("初始状态:\n %v, len=%d, cap=%d\n", nums, len (nums), cap (nums))
 fmt.Println ("------------------------")

 for i := 1; i <= 1000; i++ {
  toAdd := make ([] int, 1)

  nums = append (nums, toAdd...)
  fmt.Printf ("追加 %d 个元素 %v 后:\n", i, toAdd)
  fmt.Printf ("len=%d, cap=%d\n", len (nums), cap (nums))
  fmt.Println ("------------------------")
 }
}

//result:
// 初始状态:
//  [], len=0, cap=0
//------------------------
// 追加 1 个元素 [0] 后:
//len=1, cap=1
//------------------------
// 追加 2 个元素 [0] 后:
//len=2, cap=2
//------------------------
// 追加 3 个元素 [0] 后:
//len=3, cap=4
//------------------------
//...
// 追加 5 个元素 [0] 后:
//len=5, cap=8
//------------------------
//...
// 追加 9 个元素 [0] 后:
//len=9, cap=16
//------------------------
//...
// 追加 17 个元素 [0] 后:
//len=17, cap=32
//......
//......
// ------------------------
// 追加512个元素[0]后:
// len=512, cap=512
// ------------------------
// 追加513个元素[0]后:
// len=513, cap=848GO

发现 512 cap 以内是按照 2 的指数来增长的，和上面代码的区别在于，这里是循环调用 append 增加 1 个元素，所以我非常好奇 append 的底层原理是怎么实现的？

append

官方文档解释很简洁，当切片 cap 不够时，分配一个新数组存储，然后返回

当我点击进去时只能看到 append 的函数声明

文件位于 go/src/builtin/builtin.go，这个文件只包含声明（declarations），不包含实现（implementations）。它的主要目的是：

为IDE提供类型信息
为开发者提供文档
为编译器提供类型检查信息

寻找源码的过程被迫中断了，去哪找呢？

我尝试问 AI 发现，类似 make, new, append… 这些函数属于 Go 的 builtin 函数，他们不需要导包就能使用，也没有具体的函数体实现，而是由编译器直接处理。

又回到了找源码的问题，编译过程怎么查看？

可以通过指定编译参数来查看编译步骤，比如指定 GOSSAFUNC=main 查看 main 函数。

接下来我对一段简单的 append 代码生成编译阶段：

package main

func main() {
 var s []int
 s = append(s, 0)
}GO

通过上面步骤会在当前目录生成一个 ssa.html 文件。使用浏览器打开内容如下：

v13 (5) = StaticLECall <[]int,mem> {AuxCall{runtime.growslice}} [64] v5 v9 v7 v8 v11 v12TEXT

重点看这行代码，append 实际上对应到了 runtime.growslice。

growslice & nextslicecap

接下来到官方源码目录下找到 runtime.growslice，位于 src/runtime/slice.go 文件中，函数体如下：

// growslice allocates new backing store for a slice.
//
// arguments:
//
// oldPtr = pointer to the slice's backing array
// newLen = new length (= oldLen + num)
// oldCap = original slice's capacity.
//    num = number of elements being added
//     et = element type
//
// return values:
//
// newPtr = pointer to the new backing store
// newLen = same value as the argument
// newCap = capacity of the new backing store
//
// ......
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type)GO

growslice 前面是一堆检查，后面是针对内存的优化处理，暂且略过，主要针对 nextslicecap 的代码进行研究

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type)
 ... // 检查
 newcap := nextslicecap(newLen, oldCap)
 ... // 分配内存

func nextslicecap(newLen, oldCap int) int {
 newcap := oldCap
 doublecap := newcap + newcap
 if newLen > doublecap {
  return newLen
 }

 const threshold = 256
 if oldCap < threshold {
  return doublecap
 }
 for {
  // Transition from growing 2x for small slices
  // to growing 1.25x for large slices. This formula
  // gives a smooth-ish transition between the two.
  newcap += (newcap + 3*threshold) >> 2

  // We need to check `newcap >= newLen` and whether `newcap` overflowed.
  // newLen is guaranteed to be larger than zero, hence
  // when newcap overflows then `uint(newcap) > uint(newLen)`.
  // This allows to check for both with the same comparison.
  if uint(newcap) >= uint(newLen) {
   break
  }
 }

 // Set newcap to the requested cap when
 // the newcap calculation overflowed.
 if newcap <= 0 {
  return newLen
 }
 return newcap
}GO

解释：

当 newLen(oldCap+num) > doublecap，直接返回 newLen
否则，当 oldCap < 256 时，返回 doublecap，也就是两倍的 oldCap
当 oldCap 超过 256 时，增长倍数从 2x -> 1.25x
最后是做溢出检查

参考上面的代码，每次扩容的数量应该是：

一次性添加多个：1 2 3 4 5 6 7 8 9 10…
循环添加一个：1 2 4 8 16 32 64 128 256 512 832…

但是实际上却是：

一次性添加多个：1 2 3 4 6 8 10…
循环添加一个：1 2 4 8 16 32 64 128 256 512 848…

why？

roundupsize

从 nextslicecap 接着往下走，发现一个函数 roundupsize，如下所示

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
 ...
 case et.Size_ == goarch.PtrSize:
  lenmem = uintptr(oldLen) * goarch.PtrSize
  newlenmem = uintptr(newLen) * goarch.PtrSize
  capmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)
  overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
  newcap = int(capmem / goarch.PtrSize)
 case isPowerOfTwo(et.Size_):
  var shift uintptr
  if goarch.PtrSize == 8 {
   // Mask shift for better code generation.
   shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
  } else {
   shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
  }
  lenmem = uintptr(oldLen) << shift
  newlenmem = uintptr(newLen) << shift
  capmem = roundupsize(uintptr(newcap)<<shift, noscan)
  overflow = uintptr(newcap) > (maxAlloc >> shift)
  newcap = int(capmem >> shift)
  capmem = uintptr(newcap) << shift
 ...
}

func roundupsize(size uintptr, noscan bool) (reqSize uintptr) {
 reqSize = size
 if reqSize <= maxSmallSize-mallocHeaderSize {
  // Small object.
  if !noscan && reqSize > minSizeForMallocHeader { // !noscan && !heapBitsInSpan(reqSize)
   reqSize += mallocHeaderSize
  }
  // (reqSize - size) is either mallocHeaderSize or 0. We need to subtract mallocHeaderSize
  // from the result if we have one, since mallocgc will add it back in.
  if reqSize <= smallSizeMax-8 {
   return uintptr(class_to_size[size_to_class8[divRoundUp(reqSize, smallSizeDiv)]]) - (reqSize - size)
  }
  return uintptr(class_to_size[size_to_class128[divRoundUp(reqSize-smallSizeMax, largeSizeDiv)]]) - (reqSize - size)
 }
 // Large object. Align reqSize up to the next page. Check for overflow.
 reqSize += pageSize - 1
 if reqSize < size {
  return size
 }
 return reqSize &^ (pageSize - 1)
}GO

growslice 里面通过 roundupsize 重新优化算出 newcap 所占字节数，再重新将字节数转成 newcap 的大小
重点就是下面这串代码，能够把 5->6 832->848，为什么这么做呢？

class_to_size[size_to_class8[divRoundUp(reqSize, smallSizeDiv)]]GO

这样做的原因主要有下面几点：

a) 内存规整：

// 不规整的分配
make([]byte, 5)  -> 5字节
make([]byte, 7)  -> 7字节
// 会导致大量不同大小的内存块，难以复用

// 规整后的分配
make([]byte, 5)  -> 8字节
make([]byte, 7)  -> 8字节
// 相同大小便于复用GO

b) 内存复用：

// 示例场景
s1 := make([]byte, 5)  // 分配8字节
s2 := make([]byte, 7)  // 分配8字节
// s1 释放后的内存可直接给 s2 使用GO

c) 缓存友好：

// 固定大小的内存块有利于内存缓存
// 例如：所有8字节的块可以放在一起管理
span1 := []*8bytes    // 8字节的块池
span2 := []*16bytes   // 16字节的块池GO

小结

本次折腾结束，Go 对内存做了很多处理，能够让我们不手动管理内存也能得到极高的效率，这点确实要比 C 好很多。

疑问：
goarch.PtrSize 代表什么意思？

Tech

#Go #源码分析

源码分析--Go append

https://artibix.github.io/go-append/

作者

Artibix

发布于

2024年11月8日

许可协议

Linux 权限控制系统上一篇

编程随想--代码整洁之道下一篇