list - slice 和容器/列表之间的区别

Question

我刚开始使用 Go，我有一种情况需要创建一组实体，其大小/长度仅在运行时已知。我最初认为使用列表会很合适，但很快意识到 slice 是 Go 中惯用的数据结构。 好奇，我写了以下基准

package main

import (
    "container/list"
    "testing"
)

var N = 10000000

func BenchmarkSlices(B *testing.B) {
    s := make([]int, 1)
    for i := 0; i < N; i += 1 {
        s = append(s, i)
    }
}

func BenchmarkLists(B *testing.B) {
    l := list.New()
    for i := 0; i < N; i += 1 {
        l.PushBack(i)
    }
}

给了我

BenchmarkSlices-4       2000000000               0.03 ns/op
BenchmarkLists-4               1        1665489308 ns/op

假设 append 会创建一个新数组，并在旧数组变满时将所有数据从旧数组复制到新数组，我希望列表的性能比示例中的 slice 更好以上。但是，我的期望显然是错误的，我正在努力理解原因。

我写了以下内容是为了更好地理解 append 如何在需要时创建新数组:

package main

import "fmt"

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

func main() {
    s := make([]int, 2)
    for i := 0; i < 15; i += 1 {
        fmt.Println(i)
        describe(s)
        s = append(s, i)
    }
}

给了我

0
len = 2, cap = 2
1
len = 3, cap = 4
2
len = 4, cap = 4
3
len = 5, cap = 8
4
len = 6, cap = 8
5
len = 7, cap = 8
6
len = 8, cap = 8
7
len = 9, cap = 16
8
len = 10, cap = 16
9
len = 11, cap = 16
10
len = 12, cap = 16
11
len = 13, cap = 16
12
len = 14, cap = 16
13
len = 15, cap = 16
14
len = 16, cap = 16

我目前唯一的猜测是，为什么 slice 比列表表现更好，因为每次插入时为一个大小为双倍的新数组分配内存并复制所有数据比为单个元素分配内存要快。 我的猜测正确吗？我错过了什么吗？

Answer 1

您运行的基准测试有误。您应该首先设置初始数据结构，然后按照 testing.B 实例指示的次数运行被基准测试的操作。

我将您的代码替换为:

var N = 1

func BenchmarkSlices(B *testing.B) {
    s := make([]int, 1)
    for n := 0; n < B.N; n++ {
        for i := 0; i < N; i++ {
            s = append(s, i)
        }
    }
}

func BenchmarkLists(B *testing.B) {
    l := list.New()
    for n := 0; n < B.N; n++ {
        for i := 0; i < N; i++ {
            l.PushBack(i)
        }
    }
}

得到这个结果:

BenchmarkSlices-4       100000000               14.3 ns/op
BenchmarkLists-4         5000000               275 ns/op

至少这次差异似乎是合理的，而不是一万亿倍。

请注意，我还将 N 的值替换为 1，这样 ns/op 实际上意味着 nanoseconds per operation 而不是 每 N 次操作的纳秒数。但是，这也可能会影响结果。

现在回答您的问题:与简单地将另一个 int 添加到预分配的 slice 相比，在 Go 中实现的链表会产生额外的成本:list 方法需要创建一个新的 Element。 ，将您的值包装在 interface{} 中并重新分配一些指针。

与此同时，追加到尚未达到最大容量的 slice 将导致仅在 CPU 级别执行几条指令:将 int 移动到内存位置，增加 slice 的长度，然后就完成了。

还有一个事实是，底层分配器可能会就地重新分配 slice ，从而完全避免复制现有底层数组元素的需要。