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 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)

}

复制切片

该函数将copy切片元素从源复制src到目标，dst并返回复制的元素数。复制的元素的数目是最小len(src)和len(dst)。

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

正如预期的那样，您的推送算法非常慢：

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工作的：追加复杂性。

还有其他一些错误。您的基准测试结果通常无效。