Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #108777

Re: setrecursionlimit

Show key headers only | View raw

On Wed, May 18, 2016 at 9:19 AM, Ned Batchelder <ned@nedbatchelder.com>
wrote:

> I believe the issue here is that Python recursion results in the C stack
> growing.  Each Python function call creates a number of C function calls,
> which grows the C stack.  The crash you see is the C stack overflowing.
>
> Is there a way to know how large the C stack can grow, and how much it
> will grow for each Python function call? That sounds complicated to get
> right.
>

I'm fairly sure that it is, in fact, basically impossible to get right.

Some Python calls will use more memory on the C stack than others. They may
call more C functions internally, or C functions that require more stack
space. In the most extreme example, you could have a single Python call
crash (for example, having a super deeply recursive call as a single Python
call), or you could theoretically have extremely deep Python recursion
without a problem (presuming optimizations that do not exist in CPython for
a number of, generally good, reasons).

Even in more typical cases, I believe a Python call with keyword arguments
requires more stack than one with only positional arguments, which may
require more than one with no arguments (depending on which CPython APIs
were used). Additionally, even within the standard library, some of the
native calls will require more stack (think OS calls) than most of the
basic math functions and simple operators (like int add).

The root of the issue is that, much of the time, C function arguments are
allocated on the stack, if they exceed certain limits based on the calling
convention used. 32-bit Windows only allocates the "this" pointer as a
register, all other arguments are stack [1]. 64-bit Windows allocates up-to
4 word arguments as registers, and the rest on the stack [2]. I do not know
what the Linux conventions are. Naturally, these rules may vary based on
the compiler, for any functions the compiler knows is being compiled by the
compiler - the rules listed for the OS are only required for OS calls,
however most compilers will follow them for ease. Additionally, any local
variables that do not fit in registers will be offloaded to the stack, and
sometimes they will be offloaded even if they do fit, at the compiler's
decision, especially if function calls are made.

All of this means that, as Ned mentioned, it is very complicated to figure
out a *recursion* depth that will cause a stack overflow. Generally, there
will be an OS method to determine the stack size in *bytes*, however (and
often, the application can control this when creating threads and in
executable meta data for the main thread). There is basically no way to
convert that bytes to a recursion level, however - the best you can do is
as Rob said, see that a depth is obviously higher than valid, as it is a
reasonable (but not guaranteed) guess that each recusion will use some
number of bytes of stack.

[1] https://msdn.microsoft.com/en-us/library/984x0h58.aspx
[2] https://msdn.microsoft.com/en-us/library/zthk2dkh.aspx

Chris

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

setrecursionlimit Steven D'Aprano <steve@pearwood.info> - 2016-05-19 02:11 +1000
  Re: setrecursionlimit Ned Batchelder <ned@nedbatchelder.com> - 2016-05-18 09:19 -0700
    Re: setrecursionlimit Rob Gaddi <rgaddi@highlandtechnology.invalid> - 2016-05-18 16:29 +0000
      Re: setrecursionlimit Steven D'Aprano <steve@pearwood.info> - 2016-05-19 03:15 +1000
        Re: setrecursionlimit Ian Kelly <ian.g.kelly@gmail.com> - 2016-05-18 11:38 -0600
        Re: setrecursionlimit Chris Kaynor <ckaynor@zindagigames.com> - 2016-05-18 10:47 -0700
          Re: setrecursionlimit breamoreboy@gmail.com - 2016-05-18 14:43 -0700
            Re: setrecursionlimit Rustom Mody <rustompmody@gmail.com> - 2016-05-18 20:19 -0700
              Re: setrecursionlimit Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2016-05-19 21:04 +1200
        Re: setrecursionlimit Christian Gollwitzer <auriocus@gmx.de> - 2016-05-18 20:11 +0200
        Re: setrecursionlimit Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2016-05-19 21:00 +1200
    Re: setrecursionlimit Chris Kaynor <ckaynor@zindagigames.com> - 2016-05-18 09:56 -0700
    Re: setrecursionlimit Nobody <nobody@nowhere.invalid> - 2016-05-19 11:28 +0100
  Re: setrecursionlimit Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2016-05-19 10:27 +0100

csiph-web