slice的扩容

Go1.18之前切片的扩容是以容量1024为临界点，当旧容量 < 1024个元素,扩容变成2倍；当旧容量 > 1024个元素，那么会进入一个循环，每次增加25%直到大于期望容量。
然而这个扩容机制已经被Go 1.18弃用了，官方说新的扩容机制能更平滑地过渡

1.18版本之前（包括1.18）

在1.18版本之前，通过1024作为区分点，公式如下，较为简单不做具体描述，其中cap为预期容量，也就是说添加了数据之后需要的容量

注意，在1.18之前，会进行内存对齐，Go 1.17切片扩容时会进行内存对齐，这个和内存分配策略相关。进行内存对齐之后，新 slice 的容量是要 大于等于老 slice 容量的 2倍或者1.25倍。

1.18之后

1.18之后，Go1.18不再以1024为临界点，而是设定了一个值为256的threshold，以256为临界点；超过256，不再是每次扩容1/4，而是每次增加（旧容量+3*256）/4；其中cap为预期容量，也就是说添加了数据之后需要的容量

当新切片需要的容量cap大于两倍扩容的容量，则直接按照新切片需要的容量扩容；
当原 slice 容量 < threshold 的时候，新 slice 容量变成原来的 2 倍；
当原 slice 容量 > threshold，进入一个循环，每次容量增加（旧容量+3*threshold）/4。

有什么好处呢，首先是双倍容量扩容的最大阈值从1024降为了256，只要超过了256，就开始进行缓慢的增长。其次是增长比例的调整，之前超过了阈值之后，基本为恒定的1.25倍增长，而现在超过了阈值之后，增长比例是会动态调整的，随着切片容量的变大，增长比例逐渐向着1.25进行靠拢

内存对齐

以上提到的只是第一步，大致估算容量，在进行了验证之后，我发现实际容量并不是严格按照上面方法算的，也就是说还有 其他步骤，此时来到了第二步，内存对齐（页对齐）。
源码如下（以下代码在src/runtime/slice中查看）：

switch {
      // 当数组元素的类型大小为1时，不需要乘除计算就能够得到所需要的值  
      case et.size == 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        //前面两个语句只是对老长度和预期cap的类型转换，关键是下一个语句决定了newcap的长度
        // 内存对齐
        capmem = roundupsize(uintptr(newcap))
        // 判断是否溢出
        overflow = uintptr(newcap) > maxAlloc
        newcap = int(capmem)
      // 当类型大小是8个字节时  
      case et.size == sys.PtrSize:
        lenmem = uintptr(old.len) * sys.PtrSize
        newlenmem = uintptr(cap) * sys.PtrSize
        capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
        overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
        newcap = int(capmem / sys.PtrSize)
      // 当类型大小是2的幂次方时  
      case isPowerOfTwo(et.size):
        var shift uintptr
        if sys.PtrSize == 8 {
            // Mask shift for better code generation.
            shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
        } else {
            shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
        }
        lenmem = uintptr(old.len) << shift
        newlenmem = uintptr(cap) << shift
        capmem = roundupsize(uintptr(newcap) << shift)
        overflow = uintptr(newcap) > (maxAlloc >> shift)
        newcap = int(capmem >> shift)
      // 当大小不是上面任何一种时  
      default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }

对于字节为八字节的数据如int数组capmem = roundupsize(uintptr(newcap) * sys.PtrSize)则通过这个计算其具体容量（传入的参数是这个数组的总字节数）
其中roundupsize向上取整对齐的步骤如下

func roundupsize(size uintptr) uintptr {
    // 如果size < 32768(2的15次方，32KB)
    if size < _MaxSmallSize {
        // 如果size < 1024 - 8(2的10次方 - 8)
        if size <= smallSizeMax-8 {
        //sizetoclass看是那个类别的，classtosize找到对应类别的跨度，其中divRoundUp(size, smallSizeDiv)找到它是smallsizediv（8）的几倍之内，然后找到对应类别的class号和size号）
            return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
        } else {
            return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
        }
    }
    if size+_PageSize < size {//溢出
        return size
    }
    return alignUp(size, _PageSize)//把size对齐到pagesize的倍数从而实现内存对齐
}

对以上参数的解释如下

• _MaxSmallSize: 其值为32768，即32kb大小。在Go中，当对象大小超过32kb时，内存分配策略和小于等于32kB时是有区别的。（对于内存大于32KB的称为大对象，会单独处理，对于内存小于等于32KB的对象，会在跨度类数组中找到合适的数组大小，其实这一步也就进行了内存对齐操作，找到了最小的对齐内存，所以往往newcap大小会比之前的稍有不同，一般都是向上取了一些值）
• smallSizeMax: 其值为1024字节。
• smallSizeDiv: 其值为8字节。
• largeSizeDiv: 其值为128字节。
• _PageSize: 8192字节，即8kb大小。Go按页来管理内存，而每一页的大小就为8kb。
• class_to_size:Go中的内存分配会按照不同跨度（也可理解为内存大小，有点类似于段），其中跨度是指，go每一页的大小是8kb，对datablock划分成不同大小的内存块，
  除了最小的8b，其余的大小都是8*2n,即8,16,32，48，…32768，具体规则间隔为8,16,32,64,128…，对应class_to_size的数组（1.18之后好像多了一个24元素）
  将内存分割成不同内存块链表。当需要分配内存时，按照对象大小去匹配最合适的跨度找到空闲的内存块儿。Go中总共分为67个跨度，class_to_size是一个长度为68的数组，分别记录0和这67个跨度的值。
• size_to_class8: 这是一个长度为129的数组，代表的内存大小区间为0~1024字节。以索引i为例，此位置的对象大小m为i
• smallSizeDiv，size_to_class8[i]的值为class_to_size数组中跨度最接近m的下标。
• size_to_class128：这是一个长度为249的数组，代表的内存大小区间为1024~32768字节。以索引i为例，此位置的对象大小m为smallSizeMax

• i*largeSizeDiv, size_to_class128[i]的值为class_to_size数组中跨度最接近m的下标。
• divRoundUp: 此函数返回a/b向上舍入最接近的整数。
• alignUp: alignUp(size, _PageSize) = _PageSize * divRoundUp(size,
  _PageSize)。
  

比如如下例子：

s3 := []int{1, 2}
s3 = append(s3, 3, 4, 5)
fmt.Println(cap(s3))

根据前文知，所需容量为5，又因所需容量大于2倍当前容量，故新容量也为5。

又因为int类型大小为8（等于64位平台上的指针大小），所以实际需要的内存大小为5 * 8 = 40字节。而67个跨度中最接近40字节的跨度为48字节，所以实际分配的内存容量为48字节。

最终计算真实的容量为48 / 8 = 6，和实际运行输出一致。

优化对比

package main

import (
    "fmt"
)

func main() {
    for i := 0; i < 2000; i += 100 {
        fmt.Println(i, cap(append(make([]bool, i), true)))
    }
}

在1.18版本前

在1.18版本后

很明显的看出，在新版本之后，slice扩容整体的增长曲线变得更加平滑
总的来说，Go的设计者不断优化切片扩容的机制，其目的只有一个：就是控制让小的切片容量增长速度快一点，减少内存分配次数，而让大切片容量增长率小一点，更好地节省内存。

如果只选择翻倍的扩容策略，那么对于较大的切片来说，现有的方法可以更好的节省内存。如果只选择每次系数为1.25的扩容策略，那么对于较小的切片来说扩容会很低效。之所以选择一个小于2的系数，在扩容时被释放的内存块会在下一次扩容时更容易被重新利用

补充

补充一下向上取整找合适的对齐页数的方法：

• &^运算，与非运算，它是位清除操作符，也称为位清除（bit clear）或位清零（bit clear to zero）操作符。它用于将某个值的指定位清零。具体来说， 表示对 a 进行位清除操作，其中 b 的每个位被设置为 0 时，a 对应位置上的位保持不变，而 b 的每个位被设置为 1 时，a 对应位置上的位将被清零。例如，假设 a 是二进制数 101010，b 是二进制数 011001，那么 的结果将是 100000。因为对应位上，当 b 的位是 0 时，a 的位保持不变，而当 b 的位是 1 时，a 的位被清零。
  假设原大小位55KB,页大小为8KB，要找到向上取整的页数，可以通过(55+8-1)&^(8-1)其中8-1我们可以理解为0111，对0111取反就是1000，再与63取与，就可以去掉后三位，得到结果7*8=56.
• 第二个方法直接(55+8-1)/(8-1)*(8-1)得到结果，或者是(55+8-1)>>>3<<<3右移三位再左移三位清空后三位数，找到8的倍数，文中divRoundUp(size, smallSizeDiv)其实就是(55+8-1)/(8-1)这一步，然后再根据索引找到对应的特制编号大小