为什么切片一直从堆栈中逃逸?

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

Why slice kept escaping from stack?

问题

我正在尝试解决LeetCode问题permutations。但是当我使用-benchmem进行测试时,我发现它分配了太多的内存,当permute([]int{1,2,3,4,5,6})时,每次操作分配了1957个内存。

我发现在生成子数字目标时,它逃逸到了堆上。即使我尝试分配[6]int,并使用unsafe包构建切片,它仍然会被移动到堆上。

我的问题是,为什么切片逃逸到堆上,我如何在栈上分配切片?

这是我的代码:

package main

import (
	"fmt"
	"reflect"
	"unsafe"
)


func permute(nums []int) [][]int {
	resLen := 1
	for i := 1; i<= len(nums);i ++{
		resLen *= i
	}
	// 预分配
	res := make([][]int, resLen)
	for i := range res{
		res[i] = make([]int, 0, len(nums))
	}

	build(res, nums)

	return res
}

func build(res [][]int,targets []int){
	step := len(res) / len(targets)
	for i := range targets{
		for j := i*step; j < (i+1) * step; j ++{
			res[j] = append(res[j], targets[i])
		}
		if len(targets) != 1{
			var ab = [6]int{}
			var buff []int
			var bp  *reflect.SliceHeader
			bp = (*reflect.SliceHeader)(unsafe.Pointer(&buff))
			bp.Data = uintptr(unsafe.Pointer(&ab))
			bp.Cap = 6
			buff = append(buff, targets[:i]...)
			buff = append(buff, targets[i+1:]...)
			build(res[i*step:(i+1)*step], buff)
		}
	}
	return
}

func main() {
	nums := []int{1,2,3}
	res := permute(nums)
	fmt.Println(res)
}

build函数没有使用unsafe,但是逃逸到了堆上:

func build(res [][]int, targets []int) {
	step := len(res) / len(targets)
	for i := range targets {
		for j := i * step; j < (i+1)*step; j++ {
			res[j] = append(res[j], targets[i])
		}
		if len(targets) != 1 {
			buff := make([]int, 0, 6) //  make([]int, 0, 6) 逃逸到了堆上
			buff = append(buff, targets[:i]...)
			buff = append(buff, targets[i+1:]...)
			build(res[i*step:(i+1)*step], buff)
		}
	}
	return
}

我的测试用例:

package main

import "testing"

func Benchmark(b *testing.B){
	for i:=0;i<b.N;i++{
		permute([]int{1,2,3,4,5,6})
	}
}

当我运行go build -gcflags="-m"时,它报告了./main.go:32:8: moved to heap: ab

英文:

I am trying to solve leetcode problem permutations.
But when i test with -benchmem, i found it allocs too much which reach 1957 allocs/op when permute([]int{1,2,3,4,5,6})

I found it escape to heap when generating sub-nums target. Even i try to allocate [6]int, and use unsafe package to build the slice, it still moved to heap.

My question is, why the slice escape to heap, and how could i allocate the slice on stack?

Here's my code:

package main
import (
&quot;fmt&quot;
&quot;reflect&quot;
&quot;unsafe&quot;
)
func permute(nums []int) [][]int {
resLen := 1
for i := 1; i&lt;= len(nums);i ++{
resLen *= i
}
// pre allocate
res := make([][]int, resLen)
for i := range res{
res[i] = make([]int, 0, len(nums))
}
build(res, nums)
return res
}
func build(res [][]int,targets []int){
step := len(res) / len(targets)
for i := range targets{
for j := i*step; j &lt; (i+1) * step; j ++{
res[j] = append(res[j], targets[i])
}
if len(targets) != 1{
var ab = [6]int{}
var buff []int
var bp  *reflect.SliceHeader
bp = (*reflect.SliceHeader)(unsafe.Pointer(&amp;buff))
bp.Data = uintptr(unsafe.Pointer(&amp;ab))
bp.Cap = 6
buff = append(buff, targets[:i]...)
buff = append(buff, targets[i+1:]...)
build(res[i*step:(i+1)*step], buff)
}
}
return
}
func main() {
nums := []int{1,2,3}
res := permute(nums)
fmt.Println(res)
}

build function without unsafe but escapes to heap:

func build(res [][]int, targets []int) {
step := len(res) / len(targets)
for i := range targets {
for j := i * step; j &lt; (i+1)*step; j++ {
res[j] = append(res[j], targets[i])
}
if len(targets) != 1 {
buff := make([]int, 0, 6) //  make([]int, 0, 6) escapes to heap
buff = append(buff, targets[:i]...)
buff = append(buff, targets[i+1:]...)
build(res[i*step:(i+1)*step], buff)
}
}
return
}

And my test case:

package main
import &quot;testing&quot;
func Benchmark(b *testing.B){
for i:=0;i&lt;b.N;i++{
permute([]int{1,2,3,4,5,6})
}
}

When i run go build -gcflags=&quot;-m&quot;, it reports ./main.go:32:8: moved to heap: ab

答案1

得分: 5

尝试使用unsafe.Pointer来破坏编译器只会让逃逸分析更加困难,从而阻止切片被分配到栈上。只需分配一个单独的切片,并在每次循环迭代中重用它:

func build(res [][]int, targets []int) {
    buff := make([]int, 0, 6)
    step := len(res) / len(targets)
    for i := range targets {
        buff = buff[:0]
        for j := i * step; j < (i+1)*step; j++ {
            res[j] = append(res[j], targets[i])
        }
        if len(targets) != 1 {
            buff = append(buff, targets[:i]...)
            buff = append(buff, targets[i+1:]...)
            build(res[i*step:(i+1)*step], buff)
        }
    }
    return
}

编译器可以正确优化这段代码:

./main.go:26:17: make([]int, 0, 6) does not escape

并且只会产生所需的分配:

Benchmark-8  44607  26838 ns/op  52992 B/op  721 allocs/op
英文:

Trying to subvert the compiler using unsafe.Pointer is only making it harder for the escape analysis to do its job, preventing the slice from being stack allocated. Simply allocate a single slice and reuse it for each loop iteration:

func build(res [][]int, targets []int) {
buff := make([]int, 0, 6)
step := len(res) / len(targets)
for i := range targets {
buff = buff[:0]
for j := i * step; j &lt; (i+1)*step; j++ {
res[j] = append(res[j], targets[i])
}
if len(targets) != 1 {
buff = append(buff, targets[:i]...)
buff = append(buff, targets[i+1:]...)
build(res[i*step:(i+1)*step], buff)
}
}
return
}

This can be correctly optimized by the compiler

./main.go:26:17: make([]int, 0, 6) does not escape

And will result in only the desired allocations:

Benchmark-8  44607	26838 ns/op	 52992 B/op	 721 allocs/op

huangapple
  • 本文由 发表于 2021年7月13日 01:43:22
  • 转载请务必保留本文链接:https://go.coder-hub.com/68351808.html
匿名

发表评论

匿名网友

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

确定