ArrayList Add() 方法的选择

[linkai-pro]

感谢大明大佬 @flycash 的帮助，让我完成了本次测试

以下比较ArrayList Add方法的三种实现：

方法一：

func (a *ArrayList[T]) Add(index int, t T) error {
	if index < 0 || index > len(a.vals) {
		return newErrIndexOutOfRange(len(a.vals), index)
	}
	a.vals = append(a.vals[:index], append([]T{t}, a.vals[index:]...)...)
	return nil
}

方法二：

func (a *ArrayList[T]) Add2(index int, t T) error {
	if index < 0 || index > len(a.vals) {
		return newErrIndexOutOfRange(len(a.vals), index)
	}
	newVals := make([]T, 0, cap(a.vals)+1)
	newVals = append(newVals, a.vals[:index]...)
	newVals = append(newVals, t)
	newVals = append(newVals, a.vals[index:]...)
	a.vals = newVals
	return nil
}

方法三：

来自作者 786797661 的 pr https://github.com/gotomicro/ekit/pull/21/files

func (a *ArrayList[T]) Add3(index int, t T) error {
	if index < 0 || index > len(a.vals) {
		return newErrIndexOutOfRange(len(a.vals), index)
	}
	a.vals = append(a.vals, t)
	copy(a.vals[index+1:], a.vals[index:])
	a.vals[index] = t
	return nil
}

benchmark测试代码：

func BenchmarkArrayList_Add(b *testing.B) {
	list := &ArrayList[int]{
		vals: make([]int, 0),
	}

	b.Run("Add", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			list.Add(0, 1)
		}
	})

	b.Run("Add2", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			list.Add2(0, 1)
		}
	})
	b.Run("Add3", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			list.Add3(0, 1)
		}
	})
}

测试运行命令：

go test -bench=BenchmarkArrayList_Add -benchmem -benchtime=100000x

go版本：go version go1.18.2 darwin/amd64
mac版本：12.4 (21F79)

benchmark测试结果：

benchmark测试结果分析：

指标说明：

allocs/op 意味着有多少不同的内存分配发生在每个操作（单次迭代）。
B/op 是每个操作分配了多少个字节。
ns/op 代表每执行一次的时间为多少纳秒。

初步结论：

从结果可看出方法三在每次操作的内存分配远远小于其他两种方法，也就是内存占用会更低。不过方法一在每次操作的时间上会微弱的快于方法三。
主要原因我想可能是方法二进行了更多次的切片合并和临时变量的申请等原因。
而方法三只有一次单元素的切片合并和一次切片深拷贝，并且没有方法一和方法二都用到的切片解构。