英文:
Golang - Slice Performance append has better performance than assign
问题
我正在尝试理解Golang中切片追加(append)和赋值的性能问题。一般来说,我本以为赋值会更好,但在这段代码中,追加(append)似乎更好。我正在努力弄清楚原因,但遇到了困难。
下面是Leetcode中的合并排序数组问题,版本1的运行时间为3毫秒:
func merge(nums1 []int, m int, nums2 []int, n int) {
tmpSlice := make([]int, m+n)
tmpIndex := 0
index1 := 0
index2 := 0
for index1 < m {
value1 := nums1[index1]
for index2 < n {
value2 := nums2[index2]
if value1 <= value2 {
break
} else {
tmpSlice[tmpIndex] = value2 // <-- 赋值
index2++
tmpIndex++
}
}
tmpSlice[tmpIndex] = value1 // <-- 赋值
index1++
tmpIndex++
}
copy(nums1, tmpSlice[:tmpIndex])
copy(nums1[tmpIndex:], nums2[index2:])
}
版本2的运行时间为0毫秒:
func merge(nums1 []int, m int, nums2 []int, n int) {
tmpSlice := make([]int, 0, m+n)
tmpIndex := 0
index1 := 0
index2 := 0
for index1 < m {
value1 := nums1[index1]
for index2 < n {
value2 := nums2[index2]
if value1 <= value2 {
break
} else {
tmpSlice = append(tmpSlice, value2) // <-- 追加
index2++
tmpIndex++
}
}
tmpSlice = append(tmpSlice, value1) // <-- 追加
index1++
tmpIndex++
}
copy(nums1, tmpSlice[:tmpIndex])
copy(nums1[tmpIndex:], nums2[index2:])
}
这两个版本唯一的区别就是追加(append)和赋值的使用,而追加(append)更快。追加(append)会检查内存分配,然后进行赋值,对吗?追加(append)不应该更慢吗?
英文:
I am trying to understand performance of slice appends vs assigns in Golang, and I would have thought generally an assign would be better, but in this bit of code, it looks like append is better. I am trying to figure out why - but am struggling with it.
This is a Merge Sorted Array in Leetcode and version 1 below gives me Runtime of 3 ms
func merge(nums1 []int, m int, nums2 []int, n int) {
tmpSlice := make([]int, m+n)
tmpIndex := 0
index1 := 0
index2 := 0
for index1 < m {
value1 := nums1[index1]
for index2 < n {
value2 := nums2[index2]
if value1 <= value2 {
break
} else {
tmpSlice[tmpIndex] = value2 \\ <-- Assign
index2++
tmpIndex++
}
}
tmpSlice[tmpIndex] = value1 \\ <-- Assign
index1++
tmpIndex++
}
copy(nums1, tmpSlice[:tmpIndex])
copy(nums1[tmpIndex:], nums2[index2:])
}
Version 2 below gives me a Runtime of 0 ms
func merge(nums1 []int, m int, nums2 []int, n int) {
tmpSlice := make([]int, 0, m+n)
tmpIndex := 0
index1 := 0
index2 := 0
for index1 < m {
value1 := nums1[index1]
for index2 < n {
value2 := nums2[index2]
if value1 <= value2 {
break
} else {
tmpSlice = append(tmpSlice, value2) \\ <-- Append
index2++
tmpIndex++
}
}
tmpSlice = append (tmpSlice, value1) \\ <-- Append
index1++
tmpIndex++
}
copy(nums1, tmpSlice[:tmpIndex])
copy(nums1[tmpIndex:], nums2[index2:])
}
The only difference in the two versions is the append vs assign, and the append is faster. Append is checking for memory allocation and then doing an assign, right? Shouldn't Append be slower?
答案1
得分: 3
我将两个函数放在基准测试中,两者的性能几乎相等,append
函数稍慢一些,但差距几乎可以忽略不计。
这段代码是用Go语言编写的。基准测试的目的是比较两个函数的性能。BenchmarkMerge1
和BenchmarkMerge2
函数分别对应两个函数merge1
和merge2
。基准测试的结果显示,两个函数的性能几乎相同。
这是可以预料的,因为append
函数在切片有容量的情况下,实际上只是进行了赋值操作。append
函数还会增加切片头部的len
字段(感谢@rustyx的提示),这解释了两者之间的差异。
当切片没有设置初始容量并使用append
函数时,你会看到更大的差异,因为它会“增长”底层数组,这需要时间。
如果我们将tmpSlice := make([]int, 0, m+n)
改为tmpSlice := make([]int, 0)
,则会得到以下结果:
TL;DR,只要切片有容量,append
函数比赋值操作稍慢(因为切片的len
字段会增加),差距几乎可以忽略不计。
英文:
I put both in a benchmarks, performance between the two is almost equal, append
is slower, but by an almost negligible amount.
package main_test
import "testing"
func BenchmarkMerge1(b *testing.B) {
for i := 0; i < b.N; i++ {
num1 := []int{1, 2, 3}
num2 := []int{4, 5, 6}
merge1(num1, len(num1), num2, len(num2))
}
}
func merge1(nums1 []int, m int, nums2 []int, n int) {
tmpSlice := make([]int, m+n)
tmpIndex := 0
index1 := 0
index2 := 0
for index1 < m {
value1 := nums1[index1]
for index2 < n {
value2 := nums2[index2]
if value1 <= value2 {
break
} else {
tmpSlice[tmpIndex] = value2 // <-- Assign
index2++
tmpIndex++
}
}
tmpSlice[tmpIndex] = value1 // <-- Assign
index1++
tmpIndex++
}
copy(nums1, tmpSlice[:tmpIndex])
copy(nums1[tmpIndex:], nums2[index2:])
}
func BenchmarkMerge2(b *testing.B) {
for i := 0; i < b.N; i++ {
num1 := []int{1, 2, 3}
num2 := []int{4, 5, 6}
merge2(num1, len(num1), num2, len(num2))
}
}
func merge2(nums1 []int, m int, nums2 []int, n int) {
tmpSlice := make([]int, 0, m+n)
tmpIndex := 0
index1 := 0
index2 := 0
for index1 < m {
value1 := nums1[index1]
for index2 < n {
value2 := nums2[index2]
if value1 <= value2 {
break
} else {
tmpSlice = append(tmpSlice, value2) // <-- Append
index2++
tmpIndex++
}
}
tmpSlice = append(tmpSlice, value1) // <-- Append
index1++
tmpIndex++
}
copy(nums1, tmpSlice[:tmpIndex])
copy(nums1[tmpIndex:], nums2[index2:])
}
Running tool: /usr/local/go/bin/go test -benchmem -run=^$ -bench ^(BenchmarkMerge1|BenchmarkMerge2)$ example.com/m
goos: linux
goarch: amd64
pkg: example.com/m
cpu: Intel(R) Core(TM) i7-10870H CPU @ 2.20GHz
BenchmarkMerge1-16 34586568 36.40 ns/op 48 B/op 1 allocs/op
BenchmarkMerge2-16 32561293 36.77 ns/op 48 B/op 1 allocs/op
PASS
ok example.com/m 2.533s
This is to be expected since append basically does an assignment as long as the slice has capacity. append
also increment the len
field in the slice header(thx @rustyx for that hint), which explains the difference.
You will see a larger difference when not setting an initial capacity on the slice and using append since it will "grow" the underlying array which takes time.
If we change tmpSlice := make([]int, 0, m+n)
to tmpSlice := make([]int, 0)
in merge2
we get this result:
Running tool: /usr/local/go/bin/go test -benchmem -run=^$ -bench ^(BenchmarkMerge1|BenchmarkMerge2)$ example.com/m
goos: linux
goarch: amd64
pkg: example.com/m
cpu: Intel(R) Core(TM) i7-10870H CPU @ 2.20GHz
BenchmarkMerge1-16 37319397 32.34 ns/op 48 B/op 1 allocs/op
BenchmarkMerge2-16 14543529 87.75 ns/op 56 B/op 3 allocs/op
PASS
ok example.com/m 2.604s
TL;DR, append
is slower than assigning(since the len
field in the slice is incremented), by an almost negligible amount, as long as the slice has capacity
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论