英文:
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 (
"fmt"
"reflect"
"unsafe"
)
func permute(nums []int) [][]int {
resLen := 1
for i := 1; i<= 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 < (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
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 < (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 "testing"
func Benchmark(b *testing.B){
for i:=0;i<b.N;i++{
permute([]int{1,2,3,4,5,6})
}
}
When i run go build -gcflags="-m"
, 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 < (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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论