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

[dominikh]

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.

[minux]

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]

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]

Taking long to compile is a bug.

[minux]

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]

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]

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]

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]

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.