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

dsnet · 2022-07-14T19:18:07Z

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

The text was updated successfully, but these errors were encountered:

dsnet · 2022-07-14T19:20:05Z

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

\cc @ianlancetaylor

mknyszek · 2022-07-14T19:26:43Z

@dsnet Which versions of Go does this affect?

dsnet · 2022-07-14T19:27:48Z

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

dsnet · 2022-07-15T01:00:53Z

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 · 2022-07-15T01:03:27Z

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 · 2022-07-15T01:07:53Z

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

gopherbot · 2022-07-15T01:13:51Z

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

dsnet · 2022-07-18T17:54:04Z

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 · 2022-07-20T01:08:59Z

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

gopherbot · 2022-07-20T13:43:56Z

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

…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 · 2022-08-08T17:26:55Z

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

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 · 2022-08-08T20:04:09Z

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

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>

…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>

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>

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>

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>

Repeatedly calling Grow on a slice with sufficient capacity should effectively be a noop. However, this was not the case since it would zero out the elements between the length and capacity. Avoid that behavior to ensure Grow remains cheap in the common case. Also provide a workaround for golang/go#53888 to ensure that the number of allocations when growing is always 1. Fixes golang/go#53853 Change-Id: Id52c0d50ae9a97fe8af9acfeb666360859f336c0 Reviewed-on: https://go-review.googlesource.com/c/exp/+/417494 Reviewed-by: Daniel Martí <mvdan@mvdan.cc> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Eli Bendersky <eliben@google.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Run-TryBot: Joseph Tsai <joetsai@digital-static.net>

gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 14, 2022

dsnet added Performance and removed compiler/runtime Issues related to the Go compiler and/or runtime. labels Jul 14, 2022

mknyszek added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jul 14, 2022

mknyszek added this to the Backlog milestone Jul 14, 2022

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 closed this as completed in 2493072 Aug 8, 2022

dmitshur added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Aug 8, 2022

dmitshur modified the milestones: Backlog, Go1.20 Aug 8, 2022

golang locked and limited conversation to collaborators Aug 8, 2023

gopherbot added the FrozenDueToAge label Aug 8, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

dsnet commented Jul 14, 2022 •

edited

dsnet commented Jul 14, 2022

mknyszek commented Jul 14, 2022

dsnet commented Jul 14, 2022

dsnet commented Jul 15, 2022

dsnet commented Jul 15, 2022 •

edited

dsnet commented Jul 15, 2022

gopherbot commented Jul 15, 2022

dsnet commented Jul 18, 2022

gopherbot commented Jul 20, 2022

gopherbot commented Jul 20, 2022

gopherbot commented Aug 8, 2022

gopherbot commented Aug 8, 2022

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

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

Comments

dsnet commented Jul 14, 2022 • edited

dsnet commented Jul 14, 2022

mknyszek commented Jul 14, 2022

dsnet commented Jul 14, 2022

dsnet commented Jul 15, 2022

dsnet commented Jul 15, 2022 • edited

dsnet commented Jul 15, 2022

gopherbot commented Jul 15, 2022

dsnet commented Jul 18, 2022

gopherbot commented Jul 20, 2022

gopherbot commented Jul 20, 2022

gopherbot commented Aug 8, 2022

gopherbot commented Aug 8, 2022

dsnet commented Jul 14, 2022 •

edited

dsnet commented Jul 15, 2022 •

edited