Go 切片中的不同性能调整大小

Question

我花了一些时间来试验 Go 的内部结构，最后我使用切片编写了自己的堆栈实现。正如 reddit 用户在这篇文章中正确指出的那样，正如另一个用户在这个 SO 答案中所概述的那样，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 的测试包实现的基准测试，我自己的实现是这样执行的：

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 岁）增加块大小来抢占大量分配，从而绕过（在这种情况下）昂贵的重新分配，带您完成所有那些微不足道的小容量 0,1,2,4,8,16,32,64 等如果您的数据集大得多，这可能会因大副本的成本而被边缘化。我在 Go 中看到了很多对切片的误用。通过使您的切片具有合理的默认容量，可以获得明显的性能优势。

Answer 2

阅读您的代码、测试、基准和结果，很容易看出它们是有缺陷的。完整的代码审查超出了 StackOverflow 的范围。一个特定的错误。// Push pushes a new element to the stackfunc (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 stackfunc (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)}复制切片该函数将copy切片元素从源复制src到目标，dst并返回复制的元素数。复制的元素的数目是最小len(src)和len(dst)。你复制了0，你应该复制len(s.slice)。正如预期的那样，您的推送算法非常慢：append:Benchmark_PushDefaultStack-4     2000000           941 ns/op          49 B/op          1 allocs/opalediaferia:Benchmark_PushDefaultStack-4      100000       1246315 ns/op       42355 B/op          1 allocs/op这是如何append工作的：追加复杂性。还有其他一些错误。您的基准测试结果通常无效。