cmd/compile: large return value can take very long time to compile #14032

dominikh · 2016-01-20T05:56:28Z

The following piece of code takes several minutes to compile (I gave up after a while):

package main

func fn() (arr [1e10]bool) {
    println(len(arr))
    return
}

func main() {
    fn()
}

Possibly but not necessarily related to #14028.

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

minux · 2016-01-20T06:22:29Z

Not only it takes time to compile, it probably won't run. Per the Go ABI, it will be returning 1e10 bytes on the stack. And that's almost 10GB. Not to mention that fn will have to clear it on entry. Given that even it compiles, it probably won't run, I don't think this issue matters.

dominikh · 2016-01-20T06:38:49Z

You can reduce it to 1e9 bytes, which will compile in ~30 seconds and run just fine. However, it only runs fine if using println(len(arr)) – Using fmt.Println(len(arr)) will fail with

runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

I agree that this issue doesn't matter by itself. Nobody will/should write code like that. But I do think it is uncovering real issues that may matter in other situations. Why does it take so long to compile (is that expected or not)? Should the println version even work? If everything is WAI, by all means, close the issue. I was hoping it could point at real bugs.

bradfitz · 2016-01-20T06:44:30Z

Taking long to compile is a bug.

minux · 2016-01-20T07:48:25Z

The compiler is stuck in a O(N) loop on array bounds to generate pointer bitmaps. See http://tip.golang.org/src/cmd/compile/internal/gc/plive.go#L945 we can optimize for this trivial case, but if I really don't think this matters. The real problem is that the stack pointer maps are not encoded, so it's O(N) bits for array [N]. Even if we fix the compiler to not looping over array bound (by replicating the pointer map for one array entry), the underlying problem is still there: GC still need to traverse the huge pointer map, and we still need to emit this huge pointer map to binary. Without fixing this problem, making compiler compile this edge case fast will just make it easier for Go to produce 1GB binaries which will then trigger other problems in the toolchain (we can't handle static data bigger than 2GB in the linker.)

ianlancetaylor · 2016-01-20T14:37:15Z

I suggest that we change the ABI so that objects above a certain size are returned by invisible reference. The function will allocate them on the heap and return a pointer. The caller will use the pointer instead of storing the value on the stack, as it already does for large local variables (see MaxStackVarSize in cmd/compile/internal/gc).

rsc · 2016-10-21T03:58:23Z

I'm going back and forth between milestone Go1.9 and milestone Unplanned. I feel like the compiler used to reject this kind of thing out of hand as the stack frame being too large. That seems fine to me. Not sure we should bother to make it "work".

dominikh · 2016-10-21T06:42:08Z

As a data point from my end: The code isn't from an actual use case, but rather came to exist while trying to reproduce the issue in the linked bug. I don't see a practical reason for going out of your way to make it work and failing cleanly seems fine. My only concern would be how it relates to the spec and whether it'd be a compiler limitation or not?

josharian · 2017-05-18T19:48:10Z

With tip (638ebb0), this now compiles and executes in a moderate amount of time:

$ time go run x.go
10000000000

real	0m3.598s
user	0m2.975s
sys	0m0.667s

Seems good enough to me; closing.

ianlancetaylor added this to the Go1.7 milestone Jan 20, 2016

rsc modified the milestones: Go1.8, Go1.7 May 17, 2016

quentinmit added the NeedsFix The path to resolution is known, but the work has not been done. label Oct 11, 2016

rsc modified the milestones: Go1.9, Go1.8 Oct 21, 2016

josharian closed this as completed May 18, 2017

josharian added the ToolSpeed label May 18, 2017

golang locked and limited conversation to collaborators May 18, 2018

gopherbot added the FrozenDueToAge label May 18, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: large return value can take very long time to compile #14032

cmd/compile: large return value can take very long time to compile #14032

dominikh commented Jan 20, 2016

minux commented Jan 20, 2016 via email

dominikh commented Jan 20, 2016

bradfitz commented Jan 20, 2016

minux commented Jan 20, 2016 via email

ianlancetaylor commented Jan 20, 2016

rsc commented Oct 21, 2016

dominikh commented Oct 21, 2016

josharian commented May 18, 2017

cmd/compile: large return value can take very long time to compile #14032

cmd/compile: large return value can take very long time to compile #14032

Comments

dominikh commented Jan 20, 2016

minux commented Jan 20, 2016 via email

dominikh commented Jan 20, 2016

bradfitz commented Jan 20, 2016

minux commented Jan 20, 2016 via email

ianlancetaylor commented Jan 20, 2016

rsc commented Oct 21, 2016

dominikh commented Oct 21, 2016

josharian commented May 18, 2017