cmd/compile: fails to eliminate allocation of method values returned as `iter.Seq`

[guillaumebrunerie]

Go version

go1.25.12 darwin/arm64

Output of go env in your module/workspace:

AR='ar'
CC='cc'
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_ENABLED='1'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
CXX='c++'
GCCGO='gccgo'
GO111MODULE=''
GOARCH='arm64'
GOARM64='v8.0'
GOAUTH='netrc'
GOBIN=''
GOCACHE='/Users/guillaumeb/Library/Caches/go-build'
GOCACHEPROG=''
GODEBUG=''
GOENV='/Users/guillaumeb/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFIPS140='off'
GOFLAGS=''
GOGCCFLAGS='-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/dh/nrtxn8ld57s41r3s70jtz2rw0000gn/T/go-build1424532482=/tmp/go-build -gno-record-gcc-switches -fno-common'
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMOD='/Users/guillaumeb/iterator_slowdown/go.mod'
GOMODCACHE='/Users/guillaumeb/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='darwin'
GOPATH='/Users/guillaumeb/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/opt/homebrew/Cellar/go@1.25/1.25.12/libexec'
GOSUMDB='sum.golang.org'
GOTELEMETRY='local'
GOTELEMETRYDIR='/Users/guillaumeb/Library/Application Support/go/telemetry'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/opt/homebrew/Cellar/go@1.25/1.25.12/libexec/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.25.12'
GOWORK=''
PKG_CONFIG='pkg-config'

What did you do?

When compiling the following code, the compiler allocates memory in (Kind).Seq in order to return Kind(0).Iter, whereas the hand-written loop does not allocate memory and is therefore significantly faster.

package iterator_slowdown

import (
	"iter"
	"testing"
)

type Kind int

func (Kind) Iter(yield func(Kind) bool) {
	_ = yield(0) &&
		yield(1) &&
		yield(2) &&
		yield(3)
}

func (Kind) Seq() iter.Seq[Kind] {
	return Kind(0).Iter
}

func MethodSeq() {
	for range Kind(0).Seq() {
	}
}

func Manual() {
	for k := Kind(0); k < 4; k++ {
	}
}

func BenchmarkMethodSeq(b *testing.B) {
	b.ReportAllocs()

	for i := 0; i < b.N; i++ {
		MethodSeq()
	}
}

func BenchmarkManual(b *testing.B) {
	b.ReportAllocs()

	for i := 0; i < b.N; i++ {
		Manual()
	}
}

What did you see happen?

Benchmarks: the version with the iterator allocates memory (unlike the manual version) and is 10x slower.

> go test -bench=. -benchmem
goos: darwin
goarch: arm64
pkg: iterator_slowdown
cpu: Apple M2
BenchmarkMethodSeq-8    47928670                24.94 ns/op           24 B/op          2 allocs/op
BenchmarkManual-8       517899820                2.301 ns/op           0 B/op          0 allocs/op
PASS
ok      iterator_slowdown       3.659s

Build log, showing that Kind(0).Iter escapes to heap in Kind.Seq.

> go build -gcflags='-m=2' -a
# iterator_slowdown
./iter_xxx.go:10:6: cannot inline Kind.Iter: function too complex: cost 85 exceeds budget 80
./iter_xxx.go:17:6: can inline Kind.Seq with cost 4 as: method(Kind) func() iter.Seq[iterator_slowdown.Kind] { return Kind(0).Iter }
./iter_xxx.go:21:6: cannot inline MethodSeq: function too complex: cost 105 exceeds budget 80
./iter_xxx.go:22:2: can inline MethodSeq-range1 with cost 20 as: func(Kind) bool { #tmpState := #state1; #state1 = 2; if #tmpState != 1 { runtime.panicrangestate(#tmpState) }; #state1 = 1; return true }
./iter_xxx.go:26:6: can inline Manual with cost 12 as: func() { for loop }
./iter_xxx.go:31:6: can inline BenchmarkMethodSeq with cost 78 as: func(*testing.B) { (*testing.B).ReportAllocs(b); for loop }
./iter_xxx.go:39:6: can inline BenchmarkManual with cost 33 as: func(*testing.B) { (*testing.B).ReportAllocs(b); for loop }
./iter_xxx.go:22:23: inlining call to Kind.Seq
./iter_xxx.go:32:16: inlining call to testing.(*B).ReportAllocs
./iter_xxx.go:40:16: inlining call to testing.(*B).ReportAllocs
./iter_xxx.go:43:9: inlining call to Manual
<autogenerated>:1: inlining call to Kind.Seq
./iter_xxx.go:10:18: yield does not escape
./iter_xxx.go:18:16: Kind(0).Iter escapes to heap in Kind.Seq:
./iter_xxx.go:18:16:   flow: ~r0 ← &{storage for Kind(0).Iter}:
./iter_xxx.go:18:16:     from Kind(0).Iter (spill) at ./iter_xxx.go:18:16
./iter_xxx.go:18:16:     from return Kind(0).Iter (return) at ./iter_xxx.go:18:2
./iter_xxx.go:18:16: Kind(0).Iter escapes to heap
./iter_xxx.go:22:2: MethodSeq capturing by ref: #state1 (addr=false assign=true width=8)
./iter_xxx.go:22:2: func literal escapes to heap in MethodSeq:
./iter_xxx.go:22:2:   flow: #yield1 ← &{storage for func literal}:
./iter_xxx.go:22:2:     from func literal (spill) at ./iter_xxx.go:22:2
./iter_xxx.go:22:2:     from #yield1 := func literal (assign) at ./iter_xxx.go:22:2
./iter_xxx.go:22:2:   flow: {heap} ← #yield1:
./iter_xxx.go:22:2:     from .autotmp_2(#yield1) (call parameter) at ./iter_xxx.go:22:2
./iter_xxx.go:22:2: #state1 escapes to heap in MethodSeq:
./iter_xxx.go:22:2:   flow: {storage for func literal} ← &#state1:
./iter_xxx.go:22:2:     from #state1 (captured by a closure) at <unknown line number>
./iter_xxx.go:22:2:     from #state1 (reference) at <unknown line number>
./iter_xxx.go:22:2: moved to heap: #state1
./iter_xxx.go:22:2: func literal escapes to heap
./iter_xxx.go:22:23: Kind(0).Iter does not escape
./iter_xxx.go:31:25: b does not escape
./iter_xxx.go:39:22: b does not escape
<autogenerated>:1: Kind(0).Iter escapes to heap in (*Kind).Seq:
<autogenerated>:1:   flow: ~r0 ← &{storage for Kind(0).Iter}:
<autogenerated>:1:     from Kind(0).Iter (spill) at <autogenerated>:1
<autogenerated>:1:     from ~r0 = Kind(0).Iter (assign-pair) at <autogenerated>:1
<autogenerated>:1:   flow: ~r0 ← ~r0:
<autogenerated>:1:     from return ~r0 (return) at <autogenerated>:1
<autogenerated>:1: Kind(0).Iter escapes to heap

What did you expect to see?

Using (Kind).Seq should not allocate memory and should not be significantly slower than the manual loop.

Rewriting (Kind).Seq as follows also removes the allocation and is five times faster:

func (Kind) Seq() iter.Seq[Kind] {
	return func(yield func(Kind) bool) {
		Kind(0).Iter(yield)
	}
}

[gabyhelp]

Related Issues

• cmd/compile: idiomatic (returned) iterators are slower than unidiomatic, direct iterators #69411 (closed)
• cmd/compile: iterators cannot be composed without incurring extra heap allocations (val + func literals) #69539 (closed)
• cmd/compile: poor escape analysis of `strings.SplitSeq` #73524
• cmd/compile: optimisation opportunity with nested iterators #66469 (closed)
• cmd/compile: iter implementations significantly slower than equivalent for loops #69015
• iter: `iter.Seq` returns incorrect values for subsequent next calls #64646 (closed)
• cmd/compile: inlining of range funcs should be more aggressive #69885 (closed)
• reflect: Value.Seq2 on a map value allocates more than Value.MapRange #77576
• cmd/compile: unexpected escape when ranging over an anonymous struct containing functions #21709 (closed)
• iter: range over seq (variable of type iter.Seq[T]) must have one iteration variable #64645 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[mrkfrmn]

cc @dr2chase who might have some ideas.