Go切片的长度和容量及growslice源码分析
<p>虽然说 Go 的语法在很大程度上和 PHP 很像，但 PHP 中却是没有“切片”这个概念的，在学习的过程中也遇到了一些困惑，遂做此笔记。<br><strong>困惑1</strong>：使用 append 函数为切片追加元素后，切片的容量时变时不变，其扩容机制是什么？<br>
<strong>困惑2</strong>：更改切片的元素会修改其底层数组中对应的元素。为什么有些情况下更改了切片元素，其底层数组元素没有更改？</p>
<h4 id="一切片的声明">一、切片的声明</h4>
<p>切片可以看成是数组的引用。在 Go 中，每个数组的大小是固定的，不能随意改变大小，切片可以为数组提供动态增长和缩小的需求，但其本身并不存储任何数据。</p>
<pre><code class="language-go">/*
* 这是一个数组的声明
*/
var a int //只指定长度，元素初始化为默认值0
var a int{1,2,3,4,5}
/*
* 这是一个切片的声明：即声明一个没有长度的数组
*/
// 数组未创建
// 方法1：直接初始化
var s []int //声明一个长度和容量为 0 的 nil 切片
var s []int{1,2,3,4,5} // 同时创建一个长度为5的数组
// 方法2：用make()函数来创建切片：var 变量名 = make([]变量类型,长度,容量)
var s = make([]int, 0, 5)
// 数组已创建
// 切分数组：var 变量名 []变量类型 = arr，low和high为数组的索引。
var arr = int{1,2,3,4,5}
var slice []int = arr //
</code></pre>
<h4 id="二切片的长度和容量">二、切片的长度和容量</h4>
<p>切片的长度是它所包含的元素个数。<br>
切片的容量是从它的第一个元素到其底层数组元素末尾的个数。<br>
切片 s 的长度和容量可通过表达式 <code>len(s)</code> 和 <code>cap(s)</code> 来获取。</p>
<pre><code class="language-go">s := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} // len=10,cap=10
s1 := s // len=5,cap=10
s2 := s // len=5,cap=5
</code></pre>
<h4 id="三切片追加元素后长度和容量的变化">三、切片追加元素后长度和容量的变化</h4>
<h5 id="1append-函数">1.append 函数</h5>
<p>Go 提供了内建的 append 函数，为切片追加新的元素。</p>
<blockquote>
<pre><code>func append(s []T, vs ...T) []T
</code></pre>
<p>append 的结果是一个包含原切片所有元素加上新添加元素的切片。</p>
</blockquote>
<p>下面分两种情况描述了向切片追加新元素后切片长度和容量的变化。<br>
Example 1:</p>
<pre><code class="language-go">package main
import "fmt"
func main() {
arr := int{1,2,3,4,5} //
fmt.Println(arr)
s1 := arr //
printSlice(s1)
s1 = append(s1, 6)
printSlice(s1)
fmt.Println(arr)
}
func printSlice(s []int) {
fmt.Printf("len=%d cap=%d %p %v\n", len(s), cap(s), s, s)
}
</code></pre>
<p>执行结果如下：</p>
<pre><code>
len=3 cap=5 0xc000082030
len=4 cap=5 0xc000082030
</code></pre>
<p>可以看到切片在追加元素后，其容量和指针地址没有变化，但底层数组发生了变化，下标 3 对应的 4 变成了 6。</p>
<p>Example 2:</p>
<pre><code class="language-go">package main
import "fmt"
func main() {
arr := int{1,2,3,4} //
fmt.Println(arr)
s2 := arr //
printSlice(s2)
s2 = append(s2, 5)
printSlice(s2)
fmt.Println(arr)
}
func printSlice(s []int) {
fmt.Printf("len=%d cap=%d %p %v\n", len(s), cap(s), s, s)
}
</code></pre>
<p>执行结果如下：</p>
<pre><code>
len=3 cap=3 0xc00001c130
len=4 cap=6 0xc00001c180
</code></pre>
<p>而这个切片在追加元素后，其容量和指针地址发生了变化，但底层数组未变。</p>
<p>Example 3:</p>
<pre><code class="language-go">package main
import "fmt"
func main() {
s3 := []int{1,2} //
printSlice(s3)
s3 = append(s3, 3,4,5)
printSlice(s3)
}
func printSlice(s []int) {
fmt.Printf("len=%d cap=%d %p %v\n", len(s), cap(s), s, s)
}
</code></pre>
<p>执行结果如下：</p>
<pre><code>len=2 cap=2 0xc42006a190
len=5 cap=6 0xc42006e090
</code></pre>
<p>这个切片在追加元素后，其容量和指针地址发生了变化。前面两个 case，容量都是翻了两倍，但在这个 case 中，容量翻了三倍。</p>
<h4 id="四切片的源代码学习">四、切片的源代码学习</h4>
<p>Go 中切片的数据结构可以在源码下的 <code>src/runtime/slice.go</code> 查看。以下源代码基于 go1.17.5 版本，有删减。</p>
<h5 id="41-slice-的结构体">4.1 slice 的结构体</h5>
<p>切片作为数组的引用，有三个属性字段：指向数组的指针、长度和容量。</p>
<pre><code class="language-go">type slice struct {
// 指向底层数组的指针
array unsafe.Pointer
// slice 当前元素个数，即 len() 时返回的数
len int
// slice 的容量，即 cap() 时返回的数
cap int
}
</code></pre>
<h5 id="42-slice-的追加和扩容">4.2 slice 的追加和扩容</h5>
<p><code>slice</code> 通过调用 <code>append</code> 函数来针对slice进行尾部追加元素，如果此时 <code>slice</code> 的 <code>cap</code> 值小于当前 <code>len</code> 加上 <code>append</code> 中传入值的数量，就会调用 <code>runtime.growslice</code> 函数，进行扩容。</p>
<p><code>growslice</code>代码可以分成三部分：</p>
<ul>
<li>基本扩容规则</li>
</ul>
<pre><code class="language-go">func growslice(et *_type, old slice, cap int) slice {
// 新容量默认为原有容量
newcap := old.cap
doublecap := newcap + newcap
// 如果新容量大于旧容量的两倍，则直接按照新容量大小申请
if cap > doublecap {
newcap = cap
} else {
// 如果原有长度小于1024，则新容量是旧容量的2倍
if old.len < 1024 {
newcap = doublecap
} else {
// 按照原有容量的 1/4 增加，直到满足新容量的需要
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// 检查容量是否溢出。
if newcap <= 0 {
newcap = cap
}
}
}
}
</code></pre>
<p><code>et</code> 代表 <code>slice</code> 中的元素类型，<br>
<code>old</code> 是扩容前的切片，<br>
<code>cap</code> 是期望容量，也就是扩容后至少需要的最小容量，即 <code>old.cap</code> + 本次新增的元素数量。</p>
<p><code>newcap</code> 的增长规则如下：<br>
期望容量大于当前容量的 2 倍，新容量为期望容量；<br>
旧切片长度小于 1024 ，新容量为旧容量的 2 倍；<br>
旧容量以 0.25 的速率进行扩容，直到大于等于期望容量。</p>
<ul>
<li>内存字节对齐<br>
容量翻倍或者是增加 25% 后，还会进行接下来的计算：</li>
</ul>
<pre><code class="language-go">func growslice(et *_type, old slice, cap int) slice {
var overflow bool
var lenmem, newlenmem, capmem uintptr
// 对于不同的slice元素大小，选择不同的计算方法，获取需要申请的内存大小。
switch {
case et.size == 1:
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
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)
case isPowerOfTwo(et.size):
var shift uintptr
if sys.PtrSize == 8 {
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)
}
}
</code></pre>
<p><code>sys.PtrSize</code> 是一个指针的大小，在 64 位中为 8。</p>
<pre><code>const PtrSize = 4 << (^uintptr(0) >> 63)
</code></pre>
<p>这里根据 <code>et.size</code> 的大小使用 <code>roundupsize</code> 函数调整 <code>newcap</code> 的大小。</p>
<ul>
<li>数据拷贝</li>
</ul>
<pre><code class="language-go">func growslice(et *_type, old slice, cap int) slice {
memmove(p, old.array, lenmem)
}
</code></pre>
<p>最后返回一个新的切片：</p>
<pre><code class="language-go">func growslice(et *_type, old slice, cap int) slice {
return slice{p, old.len, newcap}
}
</code></pre>
<p>上面的 Example1 和 Example2，都走到了扩容的 <code>else</code> 里，切片的容量均小于 1024 个元素，所以扩容的时候，每增加一个元素，其容量翻番。</p>
<p>Example2 中，因为切片的底层数组没有足够的可用容量，append() 函数会创建一个新的底层数组，将被引用的现有的值复制到新数组里，再追加新的值，所以原数组没有变化，不是我想象中的，</p>
<p>Example3 中，切片原来只有 2 个元素，追加 3 个元素，走到了扩容的 <code>if</code> 里，所以 <code>newcap</code> 变成了 5。接着调用了 <code>roundupsize</code> 函数，得到 48，最终，新的 slice 的容量为 6。</p>
<h5 id="43-切片扩容的内部实现">4.3 切片扩容的内部实现</h5>
<p>扩容1：切片扩容后其容量不变</p>
<pre><code class="language-go">slice := []int{1,2,3,4,5}
// 创建新的切片，其长度为 2 个元素，容量为 4 个元素
mySlice := slice
// 使用原有的容量来分配一个新元素，将新元素赋值为 40
mySlice = append(mySlice, 40)
</code></pre>
<p>执行上面代码后的底层数据结构如下图所示：<br>
<img src="https://img2018.cnblogs.com/blog/953680/202001/953680-20200131011736120-1875404111.png" alt="" loading="lazy"></p>
<p>扩容2：切片扩容后其容量变化</p>
<pre><code class="language-go">// 创建一个长度和容量都为 5 的切片
mySlice := []int{1,2,3,4,5}
// 向切片追加一个新元素，将新元素赋值为 6
mySlice = append(mySlice, 6)
</code></pre>
<p>执行上面代码后的底层数据结构如下图所示：<br>
<img src="https://img2018.cnblogs.com/blog/953680/202001/953680-20200131011753142-1890662245.png" alt="" loading="lazy"></p>
<h4 id="五小结">五、小结</h4>
<ol>
<li>切片是一个结构体，保存着切片的容量，长度以及指向数组的指针（数组的地址）。</li>
<li>尽量对切片设置初始容量值，以避免 append 调用 growslice，因为新的切片容量比旧的大，会开辟新的地址，拷贝数据，降低性能。</li>
</ol>
<hr>
<h4 id="changelog202213更新源码学习笔记">ChangeLog：2022.1.3更新源码学习笔记</h4><br><br>
来源：https://www.cnblogs.com/sunshineliulu/p/12244532.html
頁:
[1]