go - Go slice 调整大小的不同表现

Question

我花了一些时间试验 Go 的内部结构，最后我编写了自己的 stack 实现。使用 slice 。 正如 reddit 用户在 this 中正确指出的那样发布并由另一位用户在 this SO answer 中概述Go 已经尝试优化 slice 调整大小。

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

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

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

阅读您的代码、测试、基准测试和结果，很容易看出它们存在缺陷。完整的代码审查超出了 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)
}

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 .

还有其他问题。您的基准测试结果通常无效。