Stack overflow with large program

[wheerd]

BPO	31113
Nosy	@brettcannon, @terryjreedy, @pfmoore, @ncoghlan, @pitrou, @scoder, @tjguk, @benjaminp, @jkloth, @ned-deily, @zware, @serhiy-storchaka, @eryksun, @zooba, @wheerd, @snordhausen
PRs	bpo-31113: Get rid of recursion in the compiler for normal control flow. #3015
Dependencies	bpo-24340: co_stacksize estimate can be highly off
Files	generated.zip

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2018-01-11.19:34:59.882>
created_at = <Date 2017-08-03.08:10:51.638>
labels = ['interpreter-core', '3.7', 'OS-windows', 'type-crash']
title = 'Stack overflow with large program'
updated_at = <Date 2018-01-11.19:34:59.880>
user = 'https://github.com/wheerd'

bugs.python.org fields:

activity = <Date 2018-01-11.19:34:59.880>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2018-01-11.19:34:59.882>
closer = 'serhiy.storchaka'
components = ['Interpreter Core', 'Windows']
creation = <Date 2017-08-03.08:10:51.638>
creator = 'Wheerd'
dependencies = ['24340']
files = ['47058']
hgrepos = []
issue_num = 31113
keywords = []
message_count = 23.0
messages = ['299689', '299695', '299696', '299732', '299749', '299750', '299752', '299772', '299775', '299776', '299804', '299805', '299808', '299849', '299850', '299870', '299876', '299896', '299937', '301023', '301025', '309818', '309825']
nosy_count = 16.0
nosy_names = ['brett.cannon', 'terry.reedy', 'paul.moore', 'ncoghlan', 'pitrou', 'scoder', 'tim.golden', 'benjamin.peterson', 'jkloth', 'ned.deily', 'zach.ware', 'serhiy.storchaka', 'eryksun', 'steve.dower', 'Wheerd', 'snordhausen']
pr_nums = ['3015']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue31113'
versions = ['Python 3.7']

[wheerd]

With a pattern matching library I am generating some Python code that matches patterns. For a very big pattern set I generate a Python file which is about 20MB and has ~300K LOC. When I try to execute the file with Python 3.6.2 on Windows 10 (64bit), the interpreter crashes. I do not have the Python source locally, but I could get it if necessary. The crash is because of a stack overflow when calling dfs() in compile.c. I can attach you the program, but it needs some dependencies which currently are only availiable via some Github repos.

I will try to split the ig file into multiple smaller ones, but I thought you might want to know about an interpreter crash.

[scoder]

1. Is this reproducible?

2. Getting a crash in compile.c indicates that this is happening at parse/compile time and not when your Python code is executing. Can you confirm that? Does it generate a .pyc file on import that would indicate a successful byte code compilation? If it's a compiler issue, then the dependencies won't actually matter.

3. Is the code position where the crash happens (in dfs()) predictable, or does it vary across multiple runs?

4. Does this appear to be specific to Windows, or can you reproduce it on other platforms, too?

And yes, seeing the file would be helpful. Could you at least compress it and make it available on the web somewhere for now?

[wheerd]

1. Yes.
2. A .pyc file was not generated.
3. It is always the same location where the error occurs.
4. It did not crash on the linux machine that I tested it on.

I have tried to split the code up into multiple files, but it still crashes. I have uploaded the file to http://wheerd.de/generated.zip
If you want I can also provide the code with multiple files.

[scoder]

I've looked at the file and it contains a huge amount of deeply nested if-statements. Given that parsers and compilers are typically recursive, I can well imagine that this is a problem, and my guess is that it's most likely just the different C level stack sizes, stack configurations and C compiler dependent stack allocation per function call that makes a difference for the platforms you tested. It would probably also crash on Linux, just for an even larger program.

I'm actually not in the position to decide if something should be done about this, so I'm asking in Antoine for a comment.

[scoder]

Regarding the user side of the problem, you might(!) be able to work around the crash by merging nested if-conditions into and-expressions if they have no elif/else. That's also why the split into multiple files doesn't help, it's the depth of the nesting and the overall code complexity that strike here, not the total length of the program.

Side note: just for fun, I compiled your file with Cython. It took a few minutes and then generated a 1.1 GB C file :D - hadn't seen it do that before. That's 31MB xz compressed. I was sure it would crash my C compiler if I tried to compile that, but since processing time and renewable energy are cheap these days, I gave it a try. Now "gcc -O3" is still working on it after 7 hours, currently using some 8.5 GB of RAM. It's probably worth first recompiling gcc itself with proper C compiler flags next time...

[wheerd]

I have already tried to reduce the nesting, but it still crashes. I have to admit that ~20 levels of nesting are still quite a lot. But I am surprised that so few levels of nesting already are a problem for the parser... I have attached the generated code with reduced nesting.

[pitrou]

I'm not an expert in the compiler myself.

[terryjreedy]

We know that compile has undocumented size limits of various sorts that are usually more than sufficient for normal human written code but which can be overwhelmed by machine-generated code. We do not regard this as a bug. However, 20 levels of if-nesting should not be a problem unless, say, you are recursively calling such a function.

How are you running python, on what machine? What do you mean by 'crash'? Are you running python from a console/terminal, so that there is someplace for tracebacks and exceptions to be displayed? What does 'It did not crash' mean, versus the 'crash' label above?

Have you tried increasing the recursion limit with sys.setrecursionlimit. The default for me is 1000. I have used 10000. On multi-gigabyte machines, 100000 might even work.

Instead of directly running your code, have you tried a driver program that reads your code (one file at a time) into a string and then compiles it with compile()? You might somehow get a better error message, or in any case, find out which of the separate files fail.

[serhiy-storchaka]

I concur with Stefan. Some parts of the compiler are recursive. The crash is expected for enough complex programs, and the size of C stack is platform depended. There are few hard-coded limits (MAXINDENT, CO_MAXBLOCKS) that may prevent the crash by converting it to exception, but they don't take role in this case (MAXINDENT is too large (100), and CO_MAXBLOCKS limits only the level of nested "for" and "try" blocks).

sys.setrecursionlimit doesn't have relation to C stack.

Increasing the size of C stack on Windows can solve this issue for this particular case.

[pitrou]

By the way, since you're using Python 3, you can probably workaround this issue by delegating some of the work to helper functions using yield from.

[wheerd]

@serhiy That would require me to compile Python myself though, right? Is there a reason why the limit is only for try/for and not for if?

@antoine Well, the goal is to be able to generate Python 2 compatible code . I will try to split the code into more functions and see if that helps...

[jkloth]

Using master to debug, the (first) offending part of the generated file is the get_match_iter() function. The problem is not that there is too much nesting, rather it is simply the fact of too many if's period.

Simple testing at the command prompt (using master debug build) reveals the limit for just ifs is around 25000 (on Windows x64). The actual limit is going to depend on the stack usage (debug/release/version of the C runtime).

To verify:

  exec('if a: b = 1\n' * 25150)

causes exceptions on my box. The precise limit will vary somewhat.

[pitrou]

exec('if a: b = 1\n' * 25150)

I need to increase it to 200000 and it fails with a stack overflow in dfs() here (git master on Ubuntu 16.04 in pydebug mode).

[serhiy-storchaka]

PR 3015 gets rid of recursion for normal control flow in the compiler. This fixes a stack overflow for this case.

[jkloth]

The PR resolved the stack overflow in dfs(), however it now fails in the stackdepth() routine (technically, the stackdepth_walk() helper).

[brettcannon]

One fix at a time. 😉

On Mon, Aug 7, 2017, 07:52 Jeremy Kloth, <report@bugs.python.org> wrote:

Jeremy Kloth added the comment:

The PR resolved the stack overflow in dfs(), however it now fails in the
stackdepth() routine (technically, the stackdepth_walk() helper).

----------

---

Python tracker <report@bugs.python.org>
<http://bugs.python.org/issue31113\>

---

[eryksun]

Here are a couple of workarounds for the crash in Windows.

The default stack reservation size is a field in the PE/COFF header, which you can edit using editbin.exe, e.g.:

editbin /stack:[size_in_bytes] "path\to\python.exe"

The distributed python.exe has a 20000000 byte stack reservation. I changed it to 3 MiB and was able to run generated.py. You can also pre-compile it on a thread with a larger stack, e.g.:

    >>> import threading
    >>> from compileall import compile_file
    >>> threading.stack_size(2**20 * 3)
    0
    >>> t = threading.Thread(target=compile_file, args=('generated.py',))
    >>> t.start()
    >>> Compiling 'generated.py'...

[serhiy-storchaka]

The PR resolved the stack overflow in dfs(), however it now fails in the stackdepth() routine (technically, the stackdepth_walk() helper).

Indeed. The compiler crashes for longer sequences on Linux too. I'm trying to rewrite stackdepth_walk() too, but it is much harder.

[serhiy-storchaka]

Updated patch makes stackdepth() not consuming the C stack for recursion. The new code is not strictly equivalent to the old code, but I think they should produce the same results in common cases (the existing stack depth calculation algorithm is not free from bugs, see bpo-24340).

Since this change is not trivial, I think it should be made it only in master. In maintained versions it is safer to change build options on Windows to produce the executable with larger stack.

[serhiy-storchaka]

Ned, Benjamin, what do you think about backporting this change to 3.6 and 2.7? On one hand, the change is not trivial and looks like a new feature. On other hand, this can be considered as a platform specific bug, the compiler works with a large generated code on Linux, but crashes on Windows.

I don't know how to increase the stack size on Windows, but if it is an option, it looks preferable to me on 2.7 and 3.6.

[ned-deily]

I agree with Antoine's comment on the PR: this seems like this should only go into 3.7. From the description here, it sounds like this is an edge-case problem that hasn't come up before as an issue. Let's do the right thing in master (for 3.7) and try to come up with a workaround for 3.6.x (like increasing the stack size). And doing that does not prevent us from deciding later to backport to 3.6.x once we have some experience with the changes in master.

[serhiy-storchaka]

New changeset 782d6fe by Serhiy Storchaka in branch 'master':
bpo-31113: Get rid of recursion in the compiler for normal control flow. (bpo-3015)
782d6fe

[serhiy-storchaka]

Thank you for your review Antoine. I have merged the PR since resolving bpo-24340 allowed to simplify the code for the stack depth calculation.