Golang – 切片性能:append 比赋值操作具有更好的性能。

huangapple go评论78阅读模式
英文:

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 &lt; m {
        value1 := nums1[index1]
        for index2 &lt; n {
            value2 := nums2[index2]
            if value1 &lt;= value2 {
                break
            } else {
                tmpSlice[tmpIndex] = value2    \\ &lt;-- Assign
                index2++
                tmpIndex++          
            }
        }
        tmpSlice[tmpIndex] = value1    \\ &lt;-- 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 &lt; m {
        value1 := nums1[index1]
        for index2 &lt; n {
            value2 := nums2[index2]
            if value1 &lt;= value2 {
                break
            } else {
                tmpSlice = append(tmpSlice, value2)    \\ &lt;-- Append
                index2++
                tmpIndex++          
            }
        }
        tmpSlice = append (tmpSlice, value1)    \\ &lt;-- 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语言编写的。基准测试的目的是比较两个函数的性能。BenchmarkMerge1BenchmarkMerge2函数分别对应两个函数merge1merge2。基准测试的结果显示,两个函数的性能几乎相同。

这是可以预料的,因为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 &quot;testing&quot;

func BenchmarkMerge1(b *testing.B) {
	for i := 0; i &lt; 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 &lt; m {
		value1 := nums1[index1]
		for index2 &lt; n {
			value2 := nums2[index2]
			if value1 &lt;= value2 {
				break
			} else {
				tmpSlice[tmpIndex] = value2 // &lt;-- Assign
				index2++
				tmpIndex++
			}
		}
		tmpSlice[tmpIndex] = value1 // &lt;-- Assign
		index1++
		tmpIndex++
	}

	copy(nums1, tmpSlice[:tmpIndex])
	copy(nums1[tmpIndex:], nums2[index2:])
}

func BenchmarkMerge2(b *testing.B) {
	for i := 0; i &lt; 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 &lt; m {
		value1 := nums1[index1]
		for index2 &lt; n {
			value2 := nums2[index2]
			if value1 &lt;= value2 {
				break
			} else {
				tmpSlice = append(tmpSlice, value2) // &lt;-- Append
				index2++
				tmpIndex++
			}
		}
		tmpSlice = append(tmpSlice, value1) // &lt;-- 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

huangapple
  • 本文由 发表于 2022年1月8日 21:29:37
  • 转载请务必保留本文链接:https://go.coder-hub.com/70632776.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定