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

Jump to bottom

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

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

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

DhiaTN opened this issue Mar 9, 2020 · 1 comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone
Backlog

Comments

@DhiaTN
Copy link

DhiaTN commented Mar 9, 2020 •
edited

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

I believe the allocations are coming from here:

go/src/runtime/map.go

Line 821 in b559a17

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 the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Mar 9, 2020
@toothrot toothrot added this to the Backlog milestone Mar 9, 2020
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 7, 2022
@fredbi fredbi mentioned this issue Feb 1, 2023
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
Go Compiler / Runtime
Status: Triage Backlog
Milestone
Backlog
Development

No branches or pull requests
4 participants
@toothrot @DhiaTN @randall77 @gopherbot