Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

runtime: Benchmarking reports unexpected memory allocation when using range with map structure #37757

Open
DhiaTN opened this issue Mar 9, 2020 · 1 comment
Milestone

Comments

@DhiaTN
Copy link

@DhiaTN DhiaTN commented Mar 9, 2020

What version of Go are you using (go version)?

$ go version go1.14 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GOHOSTARCH="amd64"
GOHOSTOS="darwin"

What did you do?

In order to solve a given problem I wrote 2 variant of the same code (slightly different), one is trying to find the max value from a map structure as I'm filling it, and the second one is building the map structure first then loop over it with range to find the max:

// Given a list of fractions find the fraction with the most occurrence 
// and return the number of occurrences

func gcd(a, b int) int {
    for b != 0 {
	t := b
	b = a % b
	a = t
    }
    return a
}

// Solution1 ...
func Solution1(X []int, Y []int) int{
    maxOccurrence := 1
    fractionMap := make(map[[2]int]int)
	
    for i:=0 ; i < len(X); i++ {
	g := gcd(X[i], Y[i])
	fractionMap[[2]int{X[i]/g, Y[i]/g}]++
    }
	
    for i, v := range fractionMap {
        if v > maxOccurrence {
            maxOccurrence = fractionMap[i]
        }
    }
    return maxOccurrence
}

// Solution2 ...
func Solution2(X []int, Y []int) int{
    maxOccurrence := 1
    fractionMap := make(map[[2]int]int)
	
    for i:=0 ; i < len(X); i++ {
	g := gcd(X[i], Y[i])
	key := [2]int{X[i]/g, Y[i]/g}
	fractionMap[key]++
	if fractionMap[key] > maxOccurrence {
	    maxOccurrence = fractionMap[key]
	}
    }
    return maxOccurrence
}

What did you expect to see?

As both implementations are using value semantics for the data going in and out, It was expected to see a benchmarking report of 0 allocations for both.

func BenchmarkSolution1(b *testing.B) {
	b.ReportAllocs()
	X := []int{1, 2, 3, 4, 0, 1, 6, 1, 9}
	Y := []int{2, 3, 6, 8, 4, 1, 6, 1, 9}
	for i := 0; i < b.N; i++ {
		Solution1(X, Y)
	}
}

func BenchmarkSolution2(b *testing.B) {
	b.ReportAllocs()
	X := []int{1, 2, 3, 4, 0, 1, 6, 1, 9}
	Y := []int{2, 3, 6, 8, 4, 1, 6, 1, 9}
	for i := 0; i < b.N; i++ {
		Solution2(X, Y)
	}
}

What did you see instead?

  1. The benchmarking reported 2 allocations for Solution 1
  2. The allocations are not being reported in the escape analysis
➜  go test -bench . -gcflags -m=2 -memprofile p.out
# coding [coding.test]
./solution.go:4:6: cannot inline gcd: unhandled op FOR
./solution.go:14:6: cannot inline Solution1: unhandled op FOR
./solution.go:32:6: cannot inline Solution2: unhandled op FOR
./solution_test.go:5:6: cannot inline BenchmarkSolution1: unhandled op FOR
./solution_test.go:6:16: inlining call to testing.(*B).ReportAllocs method(*testing.B) func() { testing.b.showAllocResult = bool(true) }
./solution_test.go:14:6: cannot inline BenchmarkSolution2: unhandled op FOR
./solution_test.go:15:16: inlining call to testing.(*B).ReportAllocs method(*testing.B) func() { testing.b.showAllocResult = bool(true) }
./solution.go:14:16: X does not escape
./solution.go:14:25: Y does not escape
./solution.go:16:21: make(map[[2]int]int) does not escape
./solution.go:32:16: X does not escape
./solution.go:32:25: Y does not escape
./solution.go:34:21: make(map[[2]int]int) does not escape
./solution_test.go:5:25: b does not escape
./solution_test.go:7:12: []int literal does not escape
./solution_test.go:8:12: []int literal does not escape
./solution_test.go:14:25: b does not escape
./solution_test.go:16:12: []int literal does not escape
./solution_test.go:17:12: []int literal does not escape
# coding.test
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:36:6: can inline init.0 as: func() { testdeps.ImportPath = "coding" }
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:42:6: cannot inline main: function too complex: cost 200 exceeds budget 80
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24: inlining call to testing.MainStart func(testing.testDeps, []testing.InternalTest, []testing.InternalBenchmark, []testing.InternalExample) *testing.M { testing.Init(); return &testing.M literal }
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24: &testing.M literal escapes to heap:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24:   flow: ~R0 = &{storage for &testing.M literal}:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24:     from &testing.M literal (spill) at $WORK/b001/_testmain.go:44:24
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24:     from ~R0 = <N> (assign-pair) at $WORK/b001/_testmain.go:44:24
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24:   flow: m = ~R0:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24:     from m := (*testing.M)(~R0) (assign) at $WORK/b001/_testmain.go:44:4
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24:   flow: {heap} = m:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24:     from m.Run() (call parameter) at $WORK/b001/_testmain.go:46:15
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:42: testdeps.TestDeps literal escapes to heap:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:42:   flow: testing.deps = &{storage for testdeps.TestDeps literal}:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:42:     from testdeps.TestDeps literal (spill) at $WORK/b001/_testmain.go:44:42
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:42:     from testing.deps, testing.tests, testing.benchmarks, testing.examples = <N> (assign-pair) at $WORK/b001/_testmain.go:44:24
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:42:   flow: {storage for &testing.M literal} = testing.deps:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:42:     from testing.M literal (struct literal element) at $WORK/b001/_testmain.go:44:24
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:42: testdeps.TestDeps literal escapes to heap
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build569785797/b001/_testmain.go:44:24: &testing.M literal escapes to heap
goos: darwin
goarch: amd64
pkg: coding
BenchmarkSolution1-8     1572651       744 ns/op         64 B/op      2 allocs/op
BenchmarkSolution2-8     1558770       746 ns/op         0 B/op       0 allocs/op
PASS
ok      coding  3.907s
  • Now running the following tests shows that the issue does not occur with a slice but does occur with map if it's initialized within the test but not when it's passed down the stack:
func BenchmarkSolution3(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		M := map[int]int{1: 2, 3: 4, 0: 1}
		for k, v := range M {
			M[k] = v + 1
		}
	}
}

func BenchmarkSolution4(b *testing.B) {
	b.ReportAllocs()
	M := map[int]int{1: 2, 3: 4, 0: 1}
	for i := 0; i < b.N; i++ {
		for k, v := range M {
			M[k] =  v + 1
		}
	}
}

func BenchmarkSolution5(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		A := []int{1, 2, 3, 4, 0, 1}
		for i, v := range A {
			A[i] = v + 1
		}
	}
}
go test -bench . -gcflags -m=2 -memprofile p.out Output

./solution.go:4:6: cannot inline gcd: unhandled op FOR
./solution.go:14:6: cannot inline Solution1: unhandled op FOR
./solution.go:32:6: cannot inline Solution2: unhandled op FOR
./solution_test.go:23:6: cannot inline BenchmarkSolution3: unhandled op FOR
./solution_test.go:24:16: inlining call to testing.(*B).ReportAllocs method(*testing.B) func() { testing.b.showAllocResult = bool(true) }
./solution_test.go:33:6: cannot inline BenchmarkSolution4: unhandled op FOR
./solution_test.go:34:16: inlining call to testing.(*B).ReportAllocs method(*testing.B) func() { testing.b.showAllocResult = bool(true) }
./solution_test.go:43:6: cannot inline BenchmarkSolution5: unhandled op FOR
./solution_test.go:44:16: inlining call to testing.(*B).ReportAllocs method(*testing.B) func() { testing.b.showAllocResult = bool(true) }
./solution.go:14:16: X does not escape
./solution.go:14:25: Y does not escape
./solution.go:16:21: make(map[[2]int]int) does not escape
./solution.go:32:16: X does not escape
./solution.go:32:25: Y does not escape
./solution.go:34:21: make(map[[2]int]int) does not escape
./solution_test.go:23:25: b does not escape
./solution_test.go:26:19: map[int]int literal does not escape
./solution_test.go:33:25: b does not escape
./solution_test.go:35:18: map[int]int literal does not escape
./solution_test.go:43:25: b does not escape
./solution_test.go:47:13: []int literal does not escape
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:38:6: can inline init.0 as: func() { testdeps.ImportPath = "coding" }
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:44:6: cannot inline main: function too complex: cost 200 exceeds budget 80
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: inlining call to testing.MainStart func(testing.testDeps, []testing.InternalTest, []testing.InternalBenchmark, []testing.InternalExample) *testing.M { testing.Init(); return &testing.M literal }
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: &testing.M literal escapes to heap:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: flow: ~R0 = &{storage for &testing.M literal}:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: from &testing.M literal (spill) at $WORK/b001/_testmain.go:46:24
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: from ~R0 = (assign-pair) at $WORK/b001/_testmain.go:46:24
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: flow: m = ~R0:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: from m := (*testing.M)(~R0) (assign) at $WORK/b001/_testmain.go:46:4
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: flow: {heap} = m:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: from m.Run() (call parameter) at $WORK/b001/_testmain.go:48:15
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:42: testdeps.TestDeps literal escapes to heap:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:42: flow: testing.deps = &{storage for testdeps.TestDeps literal}:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:42: from testdeps.TestDeps literal (spill) at $WORK/b001/_testmain.go:46:42
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:42: from testing.deps, testing.tests, testing.benchmarks, testing.examples = (assign-pair) at $WORK/b001/_testmain.go:46:24
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:42: flow: {storage for &testing.M literal} = testing.deps:
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:42: from testing.M literal (struct literal element) at $WORK/b001/_testmain.go:46:24
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:42: testdeps.TestDeps literal escapes to heap
/var/folders/h3/zg3k3y8d2nl70b_jwy9_wbmm0000gn/T/go-build114476779/b001/_testmain.go:46:24: &testing.M literal escapes to heap
goos: darwin
goarch: amd64
pkg: coding
BenchmarkSolution3-8 5297444 235 ns/op 64 B/op 2 allocs/op
BenchmarkSolution4-8 12254929 98.8 ns/op 0 B/op 0 allocs/op
BenchmarkSolution5-8 220697650 5.67 ns/op 0 B/op 0 allocs/op
PASS
ok coding 4.608s

@randall77
Copy link
Contributor

@randall77 randall77 commented Mar 9, 2020

I believe the allocations are coming from here:

h.createOverflow()

mapiterinit needs to allocate some overflow buckets. I'm not entirely sure what is going on here. I suspect this could be optimized.

@dvyukov @josharian @martisch

@toothrot toothrot changed the title Benchmarking reports unexpected memory allocation when using range with map structure runtime: Benchmarking reports unexpected memory allocation when using range with map structure Mar 9, 2020
@toothrot toothrot added this to the Backlog milestone Mar 9, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants
You can’t perform that action at this time.