Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: Chris Angelico <rosuav@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: Detecting repeated subsequences of identical items
Date: Fri, 22 Apr 2016 01:02:27 +1000
Lines: 38
Message-ID: <mailman.16.1461250956.23626.python-list@python.org>
References: <571843f9$0$1585$c3e8da3$5496439d@news.astraweb.com> <CAHVvXxTCQT0Tp3-Pd0O5mqSMDA6s=dqj+DDTpkq1AvYoCYs-7Q@mail.gmail.com> <mailman.7.1461228807.23626.python-list@python.org> <5718c457$0$1605$c3e8da3$5496439d@news.astraweb.com> <CAHVvXxQAPP8-31Nb3vM+=O4wYpXEuH1FH3n05N59KnqpC8C0PQ@mail.gmail.com> <CAPTjJmrp7ufKa194h4RrCh0F2y0FuDqaUkcV6-B-sHDWvosdKA@mail.gmail.com> <CAHVvXxQ=qbfxZAkznhFEpyNv-7WdFYzvJiQxrOzi9Ep7zanzaA@mail.gmail.com> <CAPTjJmpa8x3r_Y0Q-gZxHk-eLUH=wh=BpSJOwBGrE=OkgStmfg@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
In-Reply-To: <CAHVvXxQ=qbfxZAkznhFEpyNv-7WdFYzvJiQxrOzi9Ep7zanzaA@mail.gmail.com>
Precedence: list
Xref: csiph.com comp.lang.python:107455

On Fri, Apr 22, 2016 at 12:30 AM, Oscar Benjamin
<oscar.j.benjamin@gmail.com> wrote:
> On 21 April 2016 at 15:12, Chris Angelico <rosuav@gmail.com> wrote:
>> On Fri, Apr 22, 2016 at 12:01 AM, Oscar Benjamin
>> <oscar.j.benjamin@gmail.com> wrote:
>>> In the recursive stack overflow case what you'll usually have is
>>>
>>> 1) A few frames leading up to the start of recursion
>>> 2) A long repetitive sequence of frames
>>> 3) A few frames at the end showing how the exception was ultimately triggered.
>>>
>>> You just need to find the cycle that makes that big long sequence.
>>
>> If the stack got overflowed, there won't usually be a part 3, as part
>> 2 is the bit that hits sys.recursionlimit (unless increasing the
>> recursion limit by a finite number would solve the problem). For other
>> exceptions, yes, this is what you'd see.
>
> If you have:
>
> def f(x):
>     return g(x+1)
>
> def g(x):
>     x = h(x)  # <-- stack can overflow inside here
>     return f(x+1)
>
> # etc.
>
> So you have a long sequence that goes f, g, f, g but at the end the
> stack can overflow while (not recursively) calling h leaving a small
> non-cyclic part at the end.

Right, good point. Forgot about that. So this situation can be
triggered by anywhere up to <cycle length> lines up. Not as helpful an
optimization now. Oh well.

ChrisA