从源码学习 Go 的基础数据结构 —— Slice

博主： EwdAger
发布时间：2021 年 06 月 05 日
1459次浏览
1 条评论
3413字数
分类： Golang 学习笔记

# 0x01

本篇源码分析基于 **Go 1.14.12** 以及 **Python 3.7.4** 注意信息时效
</div>

Go 里面的 Slice 的实现并不是很难，跟 Python 中的 List 的实现非常相似，所以我们同时分析下这两种结构。

# Go 中 Slice 的实现

## Slice 的数据结构

```go
func main() {
    sli := make([]int, 3)
    fmt.Println(sli)
}
```

```bash
[root@8fd81d703265 src]# go tool compile -S test_slice.go | grep CALL
        0x003e 00062 (test_slice.go:6)  CALL    runtime.makeslice(SB)
        0x005e 00094 (test_slice.go:7)  CALL    runtime.convTslice(SB)
        0x00b4 00180 ($GOROOT/src/fmt/print.go:274)     CALL    fmt.Fprintln(SB)
        0x00c3 00195 (test_slice.go:5)  CALL    runtime.morestack_noctxt(SB)
```

请使用上面的示例代码方式创建 Slice 而不要使用 sli := []int{0, 0,0}，不然会是另一种创建方法，很难定位到具体位置
</div>

于是我们找到了创建 Slice 的的函数`makeslice()`

```go
func makeslice(et *_type, len, cap int) unsafe.Pointer {
	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
	if overflow || mem > maxAlloc || len < 0 || len > cap {
		// NOTE: Produce a 'len out of range' error instead of a
		// 'cap out of range' error when someone does make([]T, bignumber).
		// 'cap out of range' is true too, but since the cap is only being
		// supplied implicitly, saying len is clearer.
		// See golang.org/issue/4085.
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}

return mallocgc(mem, et, true)
}
```

看起来好像平平无奇，就是创建了一个类型 * 容量`cap`大小的内存空间。然后我们查阅 Go 的官方 Spec ，上面也提到了：

> A slice, once initialized, is always associated with an underlying array that holds its elements. A slice therefore shares storage with its array and with other slices of the same array; by contrast, distinct arrays always represent distinct storage.
>
> 切片一旦初始化便始终关联到存放其元素的底层数组。因此切片会与其数组和相同数组的其它切片共享存储区；相比之下，不同的数组总是代表不同的存储区域。

所以我们可以得出结论，切片底层就是由数组组成，甚至和底层数组共享内存区。

![图来源：Go 语言圣经](https://gvoidy.cn/usr/uploads/2021/06/210834612.png)

而这也解释了 Slice 的特性，**修改 Slice 中的元素，原始数组也会被修改**，即

```go
package main

import "fmt"

func main() {

arr := [...]int{1, 2, 3}
    // 输出 [1 2 3]
    fmt.Println(arr)

sli := arr[1:2]
    sli[0] = 4
    // 输出 [1 4 3]
    fmt.Println(arr)

}
```

## Slice 的扩容

通过上边我们知道了 Slice 底层实现就是数组，同时我们又知道 Slice 和数组的最大的区别就是，Slice 可以使用 `append` 进行扩容，而数组不行。那么接下来我们来看看 `append`的实现。

```go
package main

import "fmt"

func main() {

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

}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/4036582116.png)

由于 `append()` 涉及到了很多编译器优化的方法，这里也就仿照 **Go 语言圣经** 来分析 Go 早期的 `appendInt()` 方法，大致分析下扩容是怎么回事
</div>

```go
func appendInt(x []int, y int) []int {
    var z []int
    zlen := len(x) + 1
    if zlen <= cap(x) {
        // There is room to grow.  Extend the slice.
        z = x[:zlen]
    } else {
        // There is insufficient space.  Allocate a new array.
        // Grow by doubling, for amortized linear complexity.
        zcap := zlen
        if zcap < 2*len(x) {
            zcap = 2 * len(x)
        }
        z = make([]int, zlen, zcap)
        copy(z, x) // a built-in function; see text
    }
    z[len(x)] = y
    return z
}
```

可以看出逻辑非常简单，先判断 Slice 添加一个元素后容量`cap`有没有到达上限，没有达到上限就直接在`len(x)`位置添加`y`

![image.png](https://gvoidy.cn/usr/uploads/2021/06/4010434619.png)

如果超过了容量`cap`，就把新建一个 2 倍容量`cap`的切片`z`，再将老的切片`x`复制进去，最后在`len(x)`位置添加`y`

![image.png](https://gvoidy.cn/usr/uploads/2021/06/4200291156.png)

最后，我们测试一下`append()`的时间复杂度：

```go
// main.go
package main

var size = 1 << 20

func Append() {
    var s []int
    for i := 0; i < size; i++ {
        s = append(s, i)
    }
    _ = s
}
func Make() {
    s := make([]int, size)
    for i := 0; i < size; i++ {
        s[i] = i
    }
    _ = s
}

```

```go
// main_test.go

package main

import "testing"

func BenchmarkAppend(b *testing.B) {
    for n := 0; n < b.N; n++ {
        Append()
    }
}
func BenchmarkMake(b *testing.B) {
    for n := 0; n < b.N; n++ {
        Make()
    }
}

```

```bash
D:\code\go_project\helloworld\src>go test -bench=.
goos: windows
goarch: amd64
pkg: project/src
BenchmarkAppend-12           200           5978824 ns/op
BenchmarkMake-12             771           1562907 ns/op
PASS
ok      project/src     3.338s

```

从结果可以看出，如果扩容比不扩容的`append()`要将近多吃 75% 的 CPU。所以我们又可以得到以下结论：

- `append()`尽管理论上时间复杂度为 O(1)，但是如果发生扩容，那么操作也是比较昂贵的
- 发生扩容的情况，最耗时的就是将老 Slice 的数据 Copy 到新 Slice，其时间复杂度为 O(n)
- 如果我们使用 Slice 时大致知道`cap`为多少，最好在 make 的时候就定义好，避免 Slice 经常发生扩容

## Slice 的缩容

目前版本的 Slice 是没有办法自动缩容的! 缩容需要用户自己判断/处理
</div>

```go
func main() {
    sli := []int{10, 10}
    for i := 0; i < 1000; i++ {
        sli = append(sli, i)
    }
    println(cap(sli))

if cap(sli) > 1000{
        sli = []int{10, 10}
    }
    println(cap(sli))

}
```

# Python 中的 List

经过上面对 Go 中 Slice 的分析，我们明显的可以感觉到他和 Python 中的 List 非常的相似。那么我们顺手看看 Python 中 List 的实现。

## List 的数据结构

我们都知道 Python 是 C 实现的，其底层数据结构基本都是写在 C 文件里的，并没有 Go 那么好分析。经过查阅得知，Python 中 List 的实现在头文件`Include/listobject.h`中:

```c
typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

/* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/265881535.png)

## List 的扩容

跟 Go 中一样，Python 的 List 也有 `append()`方法，根据上面我们查到的 List 底层数据结构，可以轻易得出 List 进行 `append()` 在容量`allocate` 不够的情况下也会发生扩容。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/1215079072.png)

## List 的缩容

Python 中的 List 支持自动缩容

```python
lst = []

for i in range(10000):
    lst.append(i)

# 10000 10945
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)

for i in range(10000):
    lst.pop()

# 0, 0
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)
```

# Slice 和 List 的异同

Go 中的 Slice 和 Python 中的 List，大体上实现非常类似。但是 Go 的 Slice 底层是 Go 中的数组结构，而 Python 的底层是 C 的数组结构。从用户的角度，Go 用户能很轻易的改变 Slice 底层的数组，而 Python 用户几乎无法修改底层的 C 数组。所以可以总结出以下结论：

- Go 初始化 Slice 时可以定义 `len` 和 `cap` 并且最好自行确定 `cap`大小；而 Python 中无法指定 `len` 和 `cap` ，其扩容均为 Python 帮我们自动控制
- Go Slice 无法自动缩容，当 `cap` 到一定量级时，需要用户自行处理缩容操作；而 Python 中的 List 可以自动处理缩容
- Go 由于修改 Slice 会将底层数组一起改变，所以在操作从程序上文数组创建的 Slice 时需要格外小心；而 Python 底层的数组用户无法维护，所以基本不用考虑这种问题

最后不得不感叹一下 Python 真是太智能了，基本上啥东西都帮用户考虑好了，但也因此 Python 总被别人吐槽慢，处于鄙视链最底层。（画外音：觉得慢有本事你们都去用汇编写程序啊！）

# Reference

[Go Slices: usage and internals](https://blog.golang.org/slices-intro)

[Go 语言圣经 4.2. Slice](https://book.itsfun.top/gopl-zh/ch4/ch4-02.html)

[Python 源码深度剖析/11 list 对象，容量自适应的数组式容器](https://www.imooc.com/read/76/article/1907)

[Go语言copy()：切片复制（切片拷贝）](http://c.biancheng.net/view/29.html)

最后修改：2021 年 07 月 09 日 01 : 21 PM

如果觉得我的文章对你有用，请随意赞赏

1 条评论

Armeal
June 5th, 2021 at 04:19 pm

行云流水，颇有魏晋之风。

回复

发表评论取消回复

评论 *

名称 *

🎲

邮箱

地址

从源码学习 Go 的基础数据结构 —— Slice

EwdAger • 2021 年 06 月 05 日

# 0x01

本篇源码分析基于 **Go 1.14.12** 以及 **Python 3.7.4** 注意信息时效
</div>

Go 里面的 Slice 的实现并不是很难，跟 Python 中的 List 的实现非常相似，所以我们同时分析下这两种结构。

# Go 中 Slice 的实现

## Slice 的数据结构

```go
func main() {
    sli := make([]int, 3)
    fmt.Println(sli)
}
```

请使用上面的示例代码方式创建 Slice 而不要使用 sli := []int{0, 0,0}，不然会是另一种创建方法，很难定位到具体位置
</div>

于是我们找到了创建 Slice 的的函数`makeslice()`

return mallocgc(mem, et, true)
}
```

看起来好像平平无奇，就是创建了一个类型 * 容量`cap`大小的内存空间。然后我们查阅 Go 的官方 Spec ，上面也提到了：

所以我们可以得出结论，切片底层就是由数组组成，甚至和底层数组共享内存区。

![图来源：Go 语言圣经](https://gvoidy.cn/usr/uploads/2021/06/210834612.png)

而这也解释了 Slice 的特性，**修改 Slice 中的元素，原始数组也会被修改**，即

```go
package main

import "fmt"

func main() {

arr := [...]int{1, 2, 3}
    // 输出 [1 2 3]
    fmt.Println(arr)

sli := arr[1:2]
    sli[0] = 4
    // 输出 [1 4 3]
    fmt.Println(arr)

}
```

## Slice 的扩容

```go
package main

import "fmt"

func main() {

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

}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/4036582116.png)

由于 `append()` 涉及到了很多编译器优化的方法，这里也就仿照 **Go 语言圣经** 来分析 Go 早期的 `appendInt()` 方法，大致分析下扩容是怎么回事
</div>

可以看出逻辑非常简单，先判断 Slice 添加一个元素后容量`cap`有没有到达上限，没有达到上限就直接在`len(x)`位置添加`y`

![image.png](https://gvoidy.cn/usr/uploads/2021/06/4010434619.png)

如果超过了容量`cap`，就把新建一个 2 倍容量`cap`的切片`z`，再将老的切片`x`复制进去，最后在`len(x)`位置添加`y`

![image.png](https://gvoidy.cn/usr/uploads/2021/06/4200291156.png)

最后，我们测试一下`append()`的时间复杂度：

```go
// main.go
package main

var size = 1 << 20

```

```go
// main_test.go

package main

import "testing"

func BenchmarkAppend(b *testing.B) {
    for n := 0; n < b.N; n++ {
        Append()
    }
}
func BenchmarkMake(b *testing.B) {
    for n := 0; n < b.N; n++ {
        Make()
    }
}

```

从结果可以看出，如果扩容比不扩容的`append()`要将近多吃 75% 的 CPU。所以我们又可以得到以下结论：

## Slice 的缩容

目前版本的 Slice 是没有办法自动缩容的! 缩容需要用户自己判断/处理
</div>

```go
func main() {
    sli := []int{10, 10}
    for i := 0; i < 1000; i++ {
        sli = append(sli, i)
    }
    println(cap(sli))

if cap(sli) > 1000{
        sli = []int{10, 10}
    }
    println(cap(sli))

}
```

# Python 中的 List

经过上面对 Go 中 Slice 的分析，我们明显的可以感觉到他和 Python 中的 List 非常的相似。那么我们顺手看看 Python 中 List 的实现。

## List 的数据结构

```c
typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

![image.png](https://gvoidy.cn/usr/uploads/2021/06/265881535.png)

## List 的扩容

![image.png](https://gvoidy.cn/usr/uploads/2021/06/1215079072.png)

## List 的缩容

Python 中的 List 支持自动缩容

```python
lst = []

for i in range(10000):
    lst.append(i)

# 10000 10945
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)

for i in range(10000):
    lst.pop()

# 0, 0
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)
```

# Slice 和 List 的异同

# Reference

[Go Slices: usage and internals](https://blog.golang.org/slices-intro)

[Go 语言圣经 4.2. Slice](https://book.itsfun.top/gopl-zh/ch4/ch4-02.html)

[Python 源码深度剖析/11 list 对象，容量自适应的数组式容器](https://www.imooc.com/read/76/article/1907)

[Go语言copy()：切片复制（切片拷贝）](http://c.biancheng.net/view/29.html)

1 条评论

发表评论 取消回复

从源码学习 Go 的基础数据结构 —— Slice

发表评论取消回复