Find limit of recursion: Difference between revisions

Go features stacks that grow as needed making the effective recursion limits relatively large.

Pre-Go 1.2 this could be all of memory and the program would grow without bounds until the system swap space was exhausted and the program was killed (either by the a [http://golang.org/ref/spec#Run_time_panics run-time panic] after an allocation failure or by the operating system killing the process).

Go 1.2 set a limit to the maximum amount of memory that can be used by a ''single goroutine'' stack.

The initial setting is 1 GB on 64-bit systems, 250 MB on 32-bit systems.

The default can be changed by [https://golang.org/pkg/runtime/debug#SetMaxStack <code>SetMaxStack</code>] in the <code>runtime/debug</code> package. It is documented as "useful mainly for limiting the damage done by goroutines that enter an infinite recursion."

import (

"flag"

"fmt"

"runtime/debug"

)

stack := flag.Int("stack", 0, "maximum per goroutine stack size or 0 for the default")

flag.Parse()

if *stack > 0 {

debug.SetMaxStack(*stack)

}

r(1)

if l%1000 == 0 {

fmt.Println(l)

}

r(l + 1)

Run without arguments on a 64-bit system:

{{out}}

<pre>

[…]

4471000

4472000

4473000

runtime: goroutine stack exceeds 1000000000-byte limit

fatal error: stack overflow

runtime stack:

runtime.throw(0x5413ae)

/usr/local/go/src/pkg/runtime/panic.c:520 +0x69

runtime.newstack()

/usr/local/go/src/pkg/runtime/stack.c:770 +0x486

runtime.morestack()

/usr/local/go/src/pkg/runtime/asm_amd64.s:228 +0x61

goroutine 16 [stack growth]:

main.r(0x444442)

[…]/rosetta/stack_size/stack.go:9 fp=0xc2680380c8 sp=0xc2680380c0

main.r(0x444441)

[…]/rosetta/stack_size/stack.go:13 +0xc5 fp=0xc268038140 sp=0xc2680380c8

main.r(0x444440)

[…]

...additional frames elided...

created by _rt0_go

/usr/local/go/src/pkg/runtime/asm_amd64.s:97 +0x120

goroutine 19 [finalizer wait]:

runtime.park(0x412a20, 0x542ce8, 0x5420a9)

/usr/local/go/src/pkg/runtime/proc.c:1369 +0x89

runtime.parkunlock(0x542ce8, 0x5420a9)

/usr/local/go/src/pkg/runtime/proc.c:1385 +0x3b

runfinq()

/usr/local/go/src/pkg/runtime/mgc0.c:2644 +0xcf

runtime.goexit()

/usr/local/go/src/pkg/runtime/proc.c:1445

exit status 2

</pre>

Run with "-stack 262144000" (to simulate the documented 250 MB limit on a 32-bit system):

{{out}}

<pre>

[…]

1117000

1118000

runtime: goroutine stack exceeds 262144000-byte limit

fatal error: stack overflow

[…]

</pre>

On a 32-bit system an <code>int</code> is 32 bits so the maximum value to <code>debug.SetMaxStack</code> is 2147483647 (nearly 2 GB).

On a 64-bit system an <code>int</code> is usually 64 bits so the maximum value will much larger, more than the available memory. Thus setting the maximum value will either exhaust all the system memory and swap (as with pre-Go 1.2) or will result in a allocation failure and run-time panic (e.g. 32-bit systems often have more memory and swap in total than the memory accessible to a single user program due to the limits of a 32 bit address space shared with the kernel).

Note, unlike with some other systems, increasing or changing this value only changes the allocation ''limit''.

The stack still starts out very small and only grows as needed, there is no large stack pre-allocation even when using a very high limit.

Also note that this is ''per-goroutine'', each goroutine can recurse independently and approach the limit.

The above code built pre-Go 1.2 (without the then non-existent <code>debug.SetMaxStack</code> call) and

run on a 1 GB RAM machine with 2.5 GB swap filled available RAM quickly, at a recursion depth of about 10M.

It took a several minutes to exhaust swap before exiting with this trace: (as you see, at a depth of over 25M.)

[…]