classification
Title: Python crashes with mutually recursive code
Type: crash Stage: resolved
Components: Interpreter Core Versions: Python 3.7, Python 3.6
process
Status: closed Resolution: wont fix
Dependencies: Superseder:
Assigned To: Nosy List: eric.smith, jbakker, mark.dickinson, shamon51, terry.reedy, vstinner
Priority: normal Keywords:

Created on 2017-11-14 09:02 by shamon51, last changed 2017-11-22 19:36 by terry.reedy. This issue is now closed.

Files
File name Uploaded Description Edit
KAKURU.py shamon51, 2017-11-14 09:02 PY file
KAKURU.py shamon51, 2017-11-14 16:12
Messages (18)
msg306190 - (view) Author: Shimon Malachi Cohen (shamon51) * Date: 2017-11-14 09:02
Dear Friends,
It seems that I manage to find a problem with Python ... version 3.6.3
Attached is a PY file designed to solve a puzzle: see function makeGame1

To find a solution run: doFind() 
>>> doFind()

----> counter: 11735841 rec depth: 2367
86792-719
72581-938
916-398--
--9378-97
3985-4859
27-2879--
--819-698
937-69782
812-78561
----> counter: 29203691
>>> 

It takes a few seconds to come up with a solution (deep recursive exhaustive search)
if you switch between lines 109 <==> 110 then it restart Python !?!?!?!?! (see below)

>>> doFind()

=============================== RESTART: Shell ===============================
>>> 

Dr. Shimon Cohen 
shamon51@gmail.com
msg306191 - (view) Author: Shimon Malachi Cohen (shamon51) * Date: 2017-11-14 09:04
lines 209 <==> 210
msg306201 - (view) Author: Eric V. Smith (eric.smith) * (Python committer) Date: 2017-11-14 12:38
Can you reproduce this with a much smaller example?
msg306202 - (view) Author: Shimon Malachi Cohen (shamon51) * Date: 2017-11-14 12:48
Not really...
Did you see the "restart" ?

On Nov 14, 2017 2:38 PM, "Eric V. Smith" <report@bugs.python.org> wrote:

>
> Eric V. Smith <eric@trueblade.com> added the comment:
>
> Can you reproduce this with a much smaller example?
>
> ----------
> nosy: +eric.smith
>
> _______________________________________
> Python tracker <report@bugs.python.org>
> <https://bugs.python.org/issue32022>
> _______________________________________
>
msg306214 - (view) Author: Eric V. Smith (eric.smith) * (Python committer) Date: 2017-11-14 14:31
That's too much code for me to run without analyzing it first. If I have time, I'll look at it.
msg306220 - (view) Author: Shimon Malachi Cohen (shamon51) * Date: 2017-11-14 16:12
Here is another simple example - Simple? the game board ==> is small 
see attached PY file
run ==> doFind()
msg306469 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2017-11-18 05:25
The RESTART line means that you ran this in IDLE and that your program crashed the separate (sub)process that was running your code.  When IDLE notices this, it starts a new subprocess.

To test whether this is an IDLE-only problem, I ran your code without IDLE.

C:\Users\Terry>python -i -m tem
>>> doFind()
R 6 12
R 12 22
R 21 32
C 10 21
C 13 22
C 16 23

and quickly got the the Windows 'Program has stopped running' box, with no Python error message.  Ditto when run on 3.7.0a2.

Since this is not an IDLE issue, I revised the title.
msg306470 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2017-11-18 05:27
It is possible that this is a duplicate of an existing crash report, but I am not familiar with such at all.  With only the standard, non-specific  error message, it is hard to search ;-).  What OS are you using?
msg306471 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2017-11-18 05:29
I believe I used the 2nd version of kakuru.py.
msg306473 - (view) Author: Shimon Malachi Cohen (shamon51) * Date: 2017-11-18 06:09
Cool, thanks!

On Nov 18, 2017 5:29 AM, "Terry J. Reedy" <report@bugs.python.org> wrote:

>
> Terry J. Reedy <tjreedy@udel.edu> added the comment:
>
> I believe I used the 2nd version of kakuru.py.
>
> ----------
>
> _______________________________________
> Python tracker <report@bugs.python.org>
> <https://bugs.python.org/issue32022>
> _______________________________________
>
msg306474 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2017-11-18 07:09
PS.  When you respond by EMail, please delete the quoted message, as it is redundant, on the web page, with the original copy above.
msg306496 - (view) Author: Jesse Bakker (jbakker) * Date: 2017-11-18 22:44
On linux x86-64 with python 3.6.3 and python 3.7.0a2+ I get a RecursionError: maximum recursion depth exceeded.
msg306568 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-11-20 17:18
I don't think that we can fix this issue. I suggest to close it as WONTFIX.


> sys.setrecursionlimit(3000)

While Python does its best to catch stack overflow, the C implementation of CPython can exhaust the stack memory (8 MB in Linux?) and then crash with a "stack overflow".

I suggest to rewrite your algorithm to reduce the maximum stack depth.

Or maybe try to find a way to extend the maximum size of the stack (is it possible without rebuilding Python?). See for example RLIMIT_STACK of the resource module on Unix.


> On linux x86-64 with python 3.6.3 and python 3.7.0a2+ I get a RecursionError: maximum recursion depth exceeded.

The exact memory usage depends on the Python version and maybe compiler flags. We reduce the stack usage in Python 3.7, search for "Stack consumption" in:

https://vstinner.github.io/contrib-cpython-2017q1.html
msg306738 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2017-11-22 17:37
> I suggest to close it as WONTFIX.

Agreed. If you use sys.setrecursionlimit, you're deliberately bypassing Python's safety mechanisms. A crash due to stack overflow shouldn't be considered a bug under these circumstances.
msg306739 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2017-11-22 17:40
I was going to suggest that this might be a documentation issue, but the existing documentation already looks sufficient to me:

> A user may need to set the limit higher when they have a program that
> requires deep recursion and a platform that supports a higher limit.
> This should be done with care, because a too-high limit can lead to a
> crash.

From https://docs.python.org/3/library/sys.html#sys.setrecursionlimit
msg306741 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-11-22 17:52
I close the issue for the reasons given in the latest comments. Sorry!
msg306742 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2017-11-22 17:52
(Oops, must be closed as "wont fix".)
msg306751 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2017-11-22 19:36
I confirmed that increasing the recursion limit can change recursion behavior on Windows.

>>> def f(): g()
...
>>> def g(): f()
...
>>> f()

With the default limit or 1000 or increase to 3000, I get a recursion error.  With the limit set to 10000, I get 'MemoryError: stack overflow'.  It is not too surprising that the more complicated code prevents getting even that.
History
Date User Action Args
2017-11-22 19:36:30terry.reedysetmessages: + msg306751
2017-11-22 17:52:26vstinnersetresolution: fixed -> wont fix
messages: + msg306742
2017-11-22 17:52:13vstinnersetstatus: open -> closed
resolution: fixed
messages: + msg306741

stage: test needed -> resolved
2017-11-22 17:40:20mark.dickinsonsetmessages: + msg306739
2017-11-22 17:37:55mark.dickinsonsetnosy: + mark.dickinson
messages: + msg306738
2017-11-20 17:18:31vstinnersetmessages: + msg306568
2017-11-19 16:00:52pitrousetnosy: + vstinner
2017-11-18 22:44:07jbakkersetnosy: + jbakker
messages: + msg306496
2017-11-18 07:09:42terry.reedysetmessages: + msg306474
2017-11-18 06:09:59shamon51setmessages: + msg306473
2017-11-18 05:29:09terry.reedysetmessages: + msg306471
2017-11-18 05:27:48terry.reedysetmessages: + msg306470
2017-11-18 05:25:12terry.reedysetnosy: + terry.reedy
title: Python problem - == RESTART: Shell ===== -> Python crashes with mutually recursive code
messages: + msg306469

versions: + Python 3.7
stage: test needed
2017-11-14 16:12:03shamon51setfiles: + KAKURU.py

messages: + msg306220
2017-11-14 14:31:53eric.smithsetmessages: + msg306214
2017-11-14 12:48:45shamon51setmessages: + msg306202
2017-11-14 12:38:37eric.smithsetnosy: + eric.smith
messages: + msg306201
2017-11-14 09:04:59shamon51setmessages: + msg306191
2017-11-14 09:02:41shamon51create