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

cmd/compile: runtime.growslice optimization does not work with named slice types #53888

Closed
dsnet opened this issue Jul 14, 2022 · 12 comments
Closed
Labels
NeedsFix Performance
Milestone

Comments

@dsnet
Copy link
Member

dsnet commented Jul 14, 2022

Using 558785a

Consider the following benchmark:

var s []byte
var n = 100

func BenchmarkConcrete(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		s = nil
		bytesExtend(s, n)
	}
}
func bytesExtend(s []byte, n int) []byte {
	return append(s[:cap(s)], make([]byte, n)...)[:len(s)]
}

func BenchmarkGeneric(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		s = nil
		genericExtend(s, n)
	}
}
func genericExtend[S ~[]E, E any](s S, n int) S {
	return append(s[:cap(s)], make(S, n)...)[:len(s)]
}

Running these produces:

BenchmarkConcrete-24    	35770728	        33.78 ns/op	     112 B/op	       1 allocs/op
BenchmarkGeneric-24     	18596673	        63.85 ns/op	     224 B/op	       2 allocs/op

There's an additional allocation in BenchmarkGeneric over BenchmarkConcrete,
even though the benchmarks are semantically equivalent where bytesExtend is identical to genericExtend[[]byte].
The compiled logic for genericExtend[[]byte] contains a call to runtime.makeslice that does not exist in bytesExtend.

\cc @randall77

@gopherbot gopherbot added the compiler/runtime label Jul 14, 2022
@dsnet dsnet added Performance and removed compiler/runtime labels Jul 14, 2022
@dsnet
Copy link
Member Author

dsnet commented Jul 14, 2022

This bug affects slices.Grow such that growing always allocates twice.

\cc @ianlancetaylor

@mknyszek mknyszek added the NeedsInvestigation label Jul 14, 2022
@mknyszek mknyszek added this to the Backlog milestone Jul 14, 2022
@mknyszek
Copy link
Contributor

mknyszek commented Jul 14, 2022

@dsnet Which versions of Go does this affect?

@dsnet
Copy link
Member Author

dsnet commented Jul 14, 2022

Go1.18.4 up to and including HEAD (go1.19-558785a0a9)

@dsnet
Copy link
Member Author

dsnet commented Jul 15, 2022

Interesting. This benchmark only allocates once as expected:

func BenchmarkGeneric2(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		s = nil
		genericExtend2(s, n)
	}
}
func genericExtend2[T any](s []T, n int) []T {
	return append(s[:cap(s)], make([]T, n)...)[:len(s)]
}
BenchmarkGeneric2-24    	35662242	        37.90 ns/op	     112 B/op	       1 allocs/op

It seems that somehow [S ~[]E, E any](s S) instead of [E any](s []E) as the signature makes the difference.

@dsnet
Copy link
Member Author

dsnet commented Jul 15, 2022

Okay, the following fixes the optimization:

func genericExtend[S ~[]E, E any](s S, n int) S {
	return S(append([]E(s)[:cap(s)], make([]E, n)...)[:len(s)])
}

where we directly cast S to []E.

@dsnet
Copy link
Member Author

dsnet commented Jul 15, 2022

More details: It seems that this is unrelated to generics, but rather that the growslice optimization simple does not work with named slices. This benchmark also allocates twice and does not use generics:

func BenchmarkConcrete2(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		s = nil
		bytesExtend2(s, n)
	}
}

type S []byte
func bytesExtend2(s S, n int) S {
	return append(s[:cap(s)], make(S, n)...)[:len(s)]
}
BenchmarkConcrete2-24    	18076892	        68.63 ns/op	     224 B/op	       2 allocs/op

@dsnet dsnet changed the title cmd/compile: runtime.growslice optimization does not work correctly with generic functions cmd/compile: runtime.growslice optimization does not work with named slice types Jul 15, 2022
@gopherbot
Copy link

gopherbot commented Jul 15, 2022

Change https://go.dev/cl/417494 mentions this issue: slices: avoid mutating elements between length and capacity in Grow

@dsnet
Copy link
Member Author

dsnet commented Jul 18, 2022

I looked briefly into what was going with the compiler. It seems that this is a bug in the type-checker. If the expression is make([]E, n), the ir.Node.Op is correctly identified as ir.OMAKESLICE. However, when the expression is make(S, n), it strangely becomes ir.OCONVNOP, which breaks the optimization.

@gopherbot
Copy link

gopherbot commented Jul 20, 2022

Change https://go.dev/cl/418475 mentions this issue: cmd/compile: avoid assignment conversion in append(a, b...)

@gopherbot
Copy link

gopherbot commented Jul 20, 2022

Change https://go.dev/cl/418514 mentions this issue: [dev.unified] cmd/compile: make Unified IR always writes concrete type for expressions

gopherbot pushed a commit that referenced this issue Jul 22, 2022
…e for const exprs

So we don't have to depend on typecheck pass to fixup the concrete
type for some constant expressions. Previously, the problem won't show up,
until CL 418475 sent, which removes an un-necessary type conversion in
"append(a, b...) to help the optimization kicks in.

For #53888

Change-Id: Idaecd38b7abbaa3ad5b00ff3b1fb0fd8bbeb6726
Reviewed-on: https://go-review.googlesource.com/c/go/+/418514
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
@gopherbot
Copy link

gopherbot commented Aug 8, 2022

Change https://go.dev/cl/422037 mentions this issue: cmd/compile: disable append of make test on noopt builder

@dmitshur dmitshur added NeedsFix and removed NeedsInvestigation labels Aug 8, 2022
@dmitshur dmitshur modified the milestones: Backlog, Go1.20 Aug 8, 2022
gopherbot pushed a commit that referenced this issue Aug 8, 2022
Updates #53888

Change-Id: I34ef2c5bd23816e1991cfec2bef4cae72676b523
Reviewed-on: https://go-review.googlesource.com/c/go/+/422037
Reviewed-by: Than McIntosh <thanm@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com>
@gopherbot
Copy link

gopherbot commented Aug 8, 2022

Change https://go.dev/cl/422040 mentions this issue: cmd/compile: do not write implicit conversion for append in Unified IR

gopherbot pushed a commit that referenced this issue Aug 9, 2022
Same as CL 418475, but for Unified IR.

Updates #53888
Fixes #54337

Change-Id: I31d5a7af04d8e3902ed25db85009d46ea4c38dbe
Reviewed-on: https://go-review.googlesource.com/c/go/+/422040
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Than McIntosh <thanm@google.com>
jproberts pushed a commit to jproberts/go that referenced this issue Aug 10, 2022
…e for const exprs

So we don't have to depend on typecheck pass to fixup the concrete
type for some constant expressions. Previously, the problem won't show up,
until CL 418475 sent, which removes an un-necessary type conversion in
"append(a, b...) to help the optimization kicks in.

For golang#53888

Change-Id: Idaecd38b7abbaa3ad5b00ff3b1fb0fd8bbeb6726
Reviewed-on: https://go-review.googlesource.com/c/go/+/418514
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
jproberts pushed a commit to jproberts/go that referenced this issue Aug 10, 2022
There's no need for a and b to match types. The typechecker already
ensured that a and b are both slices with the same base type, or
a and b are (possibly named) []byte and string.

The optimization to treat append(b, make([], ...)) as a zeroing
slice extension doesn't fire when there's a OCONVNOP wrapping the make.
Fixes golang#53888

Change-Id: Ied871ed0bbb8e4a4b35d280c71acbab8103691bc
Reviewed-on: https://go-review.googlesource.com/c/go/+/418475
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Keith Randall <khr@google.com>
Run-TryBot: Keith Randall <khr@golang.org>
jproberts pushed a commit to jproberts/go that referenced this issue Aug 10, 2022
Updates golang#53888

Change-Id: I34ef2c5bd23816e1991cfec2bef4cae72676b523
Reviewed-on: https://go-review.googlesource.com/c/go/+/422037
Reviewed-by: Than McIntosh <thanm@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Auto-Submit: Cuong Manh Le <cuong.manhle.vn@gmail.com>
jproberts pushed a commit to jproberts/go that referenced this issue Aug 10, 2022
Same as CL 418475, but for Unified IR.

Updates golang#53888
Fixes golang#54337

Change-Id: I31d5a7af04d8e3902ed25db85009d46ea4c38dbe
Reviewed-on: https://go-review.googlesource.com/c/go/+/422040
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Reviewed-by: Than McIntosh <thanm@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsFix Performance
Projects
None yet
Development

No branches or pull requests

4 participants