Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Stack overflow with large program #75296

Closed
wheerd mannequin opened this issue Aug 3, 2017 · 23 comments
Closed

Stack overflow with large program #75296

wheerd mannequin opened this issue Aug 3, 2017 · 23 comments
Assignees
Labels
3.7 (EOL) end of life interpreter-core (Objects, Python, Grammar, and Parser dirs) OS-windows type-crash A hard crash of the interpreter, possibly with a core dump

Comments

@wheerd
Copy link
Mannequin

wheerd mannequin commented Aug 3, 2017

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
    Copy link
    Mannequin Author

    wheerd mannequin commented Aug 3, 2017

    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.

    @wheerd wheerd mannequin added interpreter-core (Objects, Python, Grammar, and Parser dirs) OS-windows type-crash A hard crash of the interpreter, possibly with a core dump labels Aug 3, 2017
    @scoder
    Copy link
    Contributor

    scoder commented Aug 3, 2017

    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
    Copy link
    Mannequin Author

    wheerd mannequin commented Aug 3, 2017

    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
    Copy link
    Contributor

    scoder commented Aug 4, 2017

    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
    Copy link
    Contributor

    scoder commented Aug 4, 2017

    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
    Copy link
    Mannequin Author

    wheerd mannequin commented Aug 4, 2017

    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
    Copy link
    Member

    pitrou commented Aug 4, 2017

    I'm not an expert in the compiler myself.

    @terryjreedy
    Copy link
    Member

    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
    Copy link
    Member

    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
    Copy link
    Member

    pitrou commented Aug 5, 2017

    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
    Copy link
    Mannequin Author

    wheerd mannequin commented Aug 6, 2017

    @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
    Copy link
    Contributor

    jkloth commented Aug 6, 2017

    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
    Copy link
    Member

    pitrou commented Aug 6, 2017

    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
    Copy link
    Member

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

    @jkloth
    Copy link
    Contributor

    jkloth commented Aug 7, 2017

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

    @brettcannon
    Copy link
    Member

    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
    Copy link
    Contributor

    eryksun commented Aug 7, 2017

    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
    Copy link
    Member

    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
    Copy link
    Member

    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 serhiy-storchaka added the 3.7 (EOL) end of life label Aug 8, 2017
    @serhiy-storchaka
    Copy link
    Member

    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
    Copy link
    Member

    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 serhiy-storchaka self-assigned this Jan 3, 2018
    @serhiy-storchaka
    Copy link
    Member

    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
    Copy link
    Member

    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.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    3.7 (EOL) end of life interpreter-core (Objects, Python, Grammar, and Parser dirs) OS-windows type-crash A hard crash of the interpreter, possibly with a core dump
    Projects
    None yet
    Development

    No branches or pull requests

    8 participants