cmd/compile: avoid slices.Clone for non-mutating slices

[dsnet]

Go version

go1.25

Output of go env in your module/workspace:

n/a

What did you do?

I have code like:

func Benchmark(b *testing.B) {
	b.ReportAllocs()
	for b.Loop() {
		Select([]reflect.SelectCase{
			{},
			{},
			{},
		}...)
	}
}

func Select(cases ...reflect.SelectCase) int {
	return selectImmutableCases(slices.Clone(cases)...)
}

//go:noinline
func selectImmutableCases(cases ...reflect.SelectCase) int {
	// Pretend this is the rest of the implementation of reflect.Select,
	// which does not copy, escape, or mutate cases.
	return 0
}

What did you see happen?

It allocates the []reflect.SelectCase.

What did you expect to see?

It doesn't allocate at all.

This is a hypothetical idea for how to optimize reflect.Select, which always allocates when there are enough cases. This is unfortunate as many calls to reflect.Select are given a slice literal with a statically known number of cases.

The purpose of slices.Clone in Select is to ensure that Select can operate on the slice with the assurance that the caller isn't messing with the slice while blocked. In a vast majority of cases, I suspect Select is called with a slice literal where it is never mutated, so this is an unnecessary amount of defensive copying.

Ideally, we can make slices.Clone a noop (i.e., return the input verbatim) if the following conditions are true:

1. The input slice is provably never mutated
2. The output slice is provably never mutated
3. The capacity of the slice is never observable (and by implication the elements between len and cap are never observed).
4. The address of individual element are never observed.

By making Select inlineable with just the slices.Clone, it allows the compiler to better analyze the calling context and see that the input slice is never mutated.

This would be a useful optimization technique as there are many patterns (not just in reflect.Select) that does defensive copying of a slice, when it otherwise was already safe to use verbatim.

Note that I'm just using slices.Clone as a signal to trigger this optimization, the same could be said about:

func Select(cases ...reflect.SelectCase) int {
	return selectImmutableCases(append([]reflect.SelectCases(nil), cases...)...)
}

but the compiler analysis would further need to prove that nil-ness of the output slice never mattered.

\cc @bradfitz

[mateusz834]

We already stack allocate:

func foo(a int) {
    make([]byte, a)
}
foo(123)

In case the function inlines, i think we can do that also here, and then the alloc can be outlined.

I will give this a look and see if i can do it.

[mateusz834]

Yup, it possible to do:

goos: linux
goarch: amd64
pkg: reflect
cpu: 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz
                                │ /tmp/before  │             /tmp/after              │
                                │    sec/op    │   sec/op     vs base                │
SelectStaticLit/[4]SelectCase-8   217.2n ±  5%   159.7n ± 4%  -26.46% (p=0.000 n=10)
SelectStaticLit/[8]SelectCase-8   472.1n ± 11%   344.6n ± 2%  -27.01% (p=0.000 n=10)
geomean                           320.2n         234.6n       -26.73%

                                │ /tmp/before │             /tmp/after             │
                                │    B/op     │    B/op     vs base                │
SelectStaticLit/[4]SelectCase-8   224.00 ± 0%   96.00 ± 0%  -57.14% (p=0.000 n=10)
SelectStaticLit/[8]SelectCase-8    512.0 ± 0%   256.0 ± 0%  -50.00% (p=0.000 n=10)
geomean                            338.7        156.8       -53.71%

                                │ /tmp/before │             /tmp/after             │
                                │  allocs/op  │ allocs/op   vs base                │
SelectStaticLit/[4]SelectCase-8    6.000 ± 0%   5.000 ± 0%  -16.67% (p=0.000 n=10)
SelectStaticLit/[8]SelectCase-8    11.00 ± 0%   10.00 ± 0%   -9.09% (p=0.000 n=10)
geomean                            8.124        7.071       -12.96%

for such code:

_, _, _ = Select([]SelectCase{sc, sc, sc, sc})

[gopherbot]

Change https://go.dev/cl/707255 mentions this issue: cmd/compile: propagate len([]T{}) to make builtin to allow stack allocation

[gopherbot]

Change https://go.dev/cl/707275 mentions this issue: reflect: outlilne []runtimeSelect allocation in Select

[mateusz834]

CC @randall77

[dsnet]

@mateusz834, your suggestion is an improvement over before, but IIRC, it's still going to make a stack copy in Select. IIUC, this still needs to make a local copy on the stack. It would be even better if we can avoid copies entirely for provably immutable slices.

[mateusz834]

but IIRC, it's still going to make a stack copy in Select

But it would always have to to since these are two different types. []SelectCase and []runtimeSelect and both are used in the loop.

[dsnet]

Ah yes, you're correct in the particular case of reflect.Slice. I've still wanted this behavior for other patterns where I still defensively copy a slice.

[thepudds]

It would be even better if we can avoid copies entirely

This might not be too bad to avoid the copy more generally via escape analysis for more the general case of slices.Clone and the pattern that slices.Clone represents (along with maybe some minor variations of that pattern).

I'm taking a look now, and seems plausible so far (but I reserve the right to reevaluate that opinion 😅).

@dsnet, do you have maybe ~2 roughly trivial examples that you are hoping would avoid a copy, and then maybe ~1-2 non-trivial examples (maybe from a real code base, or just slightly more complicated versions of your trivial examples, or something like that).

That might help make it more concrete, and would help me make sure I'm starting with examples that are useful to you.

(Separately, the change that @mateusz834 already sent seems to separately be a useful change to help with the stack allocation).