Go 切片调整大小的不同表现

Question

我花了一些时间试验 Go 的内部结构，最后我使用切片编写了自己的 stack 实现。正如一位 reddit 用户在 this post and as outlined by another user in this SO answer 中正确指出的那样，Go 已经尝试优化切片调整大小。

不过，事实证明，我宁愿使用自己的切片增长实现来提高性能，也不愿坚持使用默认实现。

这是我用来保存堆栈的结构：

type Stack struct {
    slice []interface{}
    blockSize int
}

const s_DefaultAllocBlockSize = 20;

这是我自己 Push 方法

的实现

func (s *Stack) Push(elem interface{}) {
    if len(s.slice) + 1 == cap(s.slice) {
        slice := make([]interface{}, 0, len(s.slice) + s.blockSize)
        copy(slice, s.slice)
        s.slice = slice
    }

    s.slice = append(s.slice, elem)
}

这是一个简单的实现

func (s *Stack) Push(elem interface{}) {
    s.slice = append(s.slice, elem)
}

运行我使用 Go 的 testing 包实现的基准我自己的实现是这样执行的：

Benchmark_PushDefaultStack  20000000            87.7 ns/op        24 B/op          1 allocs/op

虽然依靠普通append结果如下

Benchmark_PushDefaultStack  10000000           209 ns/op          90 B/op          1 allocs/op

我运行测试的机器是 2011 年初 Mac Book Pro，2.3 GHz Intel Core i5，8GB RAM 1333MHz DDR3

编辑实际问题是：我的实现真的比默认的追加行为更快吗？还是我没有考虑到什么？

Answer 1

我相信你的例子更快，因为你有一个相当小的数据集并且分配的初始容量为 0。在你的 append 版本中，你通过更早地显着增加块大小来抢占大量分配（到 20) 绕过（在这种情况下）昂贵的 reallocs，这些 reallocs 会带你通过所有那些微不足道的小容量 0,1,2,4,8,16,32,64 ect

如果您的数据集大得多，这可能会因大副本的成本而被边缘化。我在 Go 中看到了很多对 slice 的误用。通过使您的切片具有合理的默认容量，可以获得明显的性能胜利。

Answer 2

阅读您的代码、测试、基准测试和结果，很容易看出它们存在缺陷。完整的代码审查超出了 Whosebug 的范围。

一个特定的错误。

// Push pushes a new element to the stack
func (s *Stack) Push(elem interface{}) {
    if len(s.slice)+1 == cap(s.slice) {
        slice := make([]interface{}, 0, len(s.slice)+s.blockSize)
        copy(slice, s.slice)
        s.slice = slice
    }

    s.slice = append(s.slice, elem)
}

应该是

// Push pushes a new element to the stack
func (s *Stack) Push(elem interface{}) {
    if len(s.slice)+1 == cap(s.slice) {
        slice := make([]interface{}, len(s.slice), len(s.slice)+s.blockSize)
        copy(slice, s.slice)
        s.slice = slice
    }

    s.slice = append(s.slice, elem)
}

copying slices

The function copy copies slice elements from a source src to a destination dst and returns the number of elements copied. The number of elements copied is the minimum of len(src) and len(dst).

你复制了0，你应该复制了len(s.slice)。

不出所料，您的 Push 算法非常慢：

append:

Benchmark_PushDefaultStack-4     2000000           941 ns/op          49 B/op          1 allocs/op

alediaferia:

Benchmark_PushDefaultStack-4      100000       1246315 ns/op       42355 B/op          1 allocs/op

append 的工作原理：append complexity。

还有其他地方不对。您的基准测试结果通常无效。

Go 切片调整大小的不同表现

Different performances in Go slices resize

go

stack

benchmarking

slice