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

runtime: unnecessary heap allocations when `range`ing over an empty array #39668

Open
kallsyms opened this issue Jun 17, 2020 · 1 comment
Open

runtime: unnecessary heap allocations when `range`ing over an empty array #39668

kallsyms opened this issue Jun 17, 2020 · 1 comment

Comments

@kallsyms
Copy link

@kallsyms kallsyms commented Jun 17, 2020

What version of Go are you using (go version)?

$ go version
go version go1.14.2 linux/amd64

Does this issue reproduce with the latest release?

Yes (1.15beta1)

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/nickgregory/.cache/go-build"
GOENV="/home/nickgregory/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/nickgregory/dev/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/lib/go-1.14"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/go-1.14/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build389543628=/tmp/go-build -gno-record-gcc-switches"

What did you do?

In an example like the following, thing is created on the heap even if the passed arr has length 0 and the loop body is never run:

package main

type foo struct {
	a uint64
	b uint64
}

var glob *foo

//go:noinline
func f(arr []foo) {
	for _, thing := range arr {
		glob = &thing
	}
}

func main() {
	f([]foo{})
}

This is contrived/minimalistic example (inlining is just to make the asm easier to read), but shows the point. This originally came up in a case where arr was generated in an event processing critical path, and this iteration over a (usually empty array) was creating millions of objects that escaped to heap (due to storage in another object, not assignment to a global), eating ~10% of run time.

What did you expect to see?

I would expect that the runtime.newobject call would only happen after the array is checked for length > 0.

What did you see instead?

...
  45d528:	e8 d3 e1 fa ff       	call   40b700 <runtime.newobject>
  45d52d:	48 8b 44 24 08       	mov    rax,QWORD PTR [rsp+0x8]
  45d532:	48 8b 4c 24 28       	mov    rcx,QWORD PTR [rsp+0x28]
  45d537:	48 85 c9             	test   rcx,rcx
  45d53a:	7e 35                	jle    45d571 <main.f+0x71>
  45d53c:	48 8b 54 24 20       	mov    rdx,QWORD PTR [rsp+0x20]
  45d541:	31 db                	xor    ebx,ebx
  45d543:	eb 04                	jmp    45d549 <main.f+0x49>
  45d545:	48 83 c2 10          	add    rdx,0x10
...
{loop body}
...
  45d569:	48 ff c3             	inc    rbx
  45d56c:	48 39 d9             	cmp    rcx,rbx
  45d56f:	7f d4                	jg     45d545 <main.f+0x45>
  45d571:	48 8b 6c 24 10       	mov    rbp,QWORD PTR [rsp+0x10]
  45d576:	48 83 c4 18          	add    rsp,0x18
  45d57a:	c3                   	ret    
...
@randall77
Copy link
Contributor

@randall77 randall77 commented Jun 17, 2020

This is more or less intentional. We want that allocation to happen outside the loop, so it only happens once even if the loop has many iterations. Of course, that's pessimistic if the loop has 0 iterations.

We could condition the allocation by checking the number if iterations first. Offhand I suspect this would be fairly hard to do, just because it requires some form of loop peeling. But it would be nice to handle this case.

@randall77 randall77 added this to the Unplanned milestone Jun 17, 2020
@andybons andybons changed the title unnecessary heap allocations when `range`ing over an empty array runtime: unnecessary heap allocations when `range`ing over an empty array Jun 18, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants
You can’t perform that action at this time.