Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CALwzidn_4EyKA-AekPqwk2+1+0Yd3ONsTdKx73bfpzZkyXj++w@mail.gmail.com>
References: <87mw1q9jqw.fsf@Equus.decebal.nl> <mailman.121.1430385051.3680.python-list@python.org> <87383hj4zj.fsf@elektro.pacujo.net> <87d22lx38x.fsf@Equus.decebal.nl> <55432557$0$12994$c3e8da3$5496439d@news.astraweb.com> <87383fo062.fsf@Equus.decebal.nl> <87egmzl4yr.fsf@elektro.pacujo.net> <mailman.4.1430558719.12865.python-list@python.org> <87a8xnl2r6.fsf@elektro.pacujo.net> <mi2b49$pip$1@dont-email.me> <mailman.9.1430565706.12865.python-list@python.org> <mi2cjc$uq2$1@dont-email.me> <87383fkxy0.fsf@elektro.pacujo.net> <CALwzidn_4EyKA-AekPqwk2+1+0Yd3ONsTdKx73bfpzZkyXj++w@mail.gmail.com>
Date: Sun, 3 May 2015 01:55:44 +1000
Subject: Re: Python is not bad ;-)
From: Chris Angelico <rosuav@gmail.com>
Cc: Python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.14.1430582153.12865.python-list@python.org>
Lines: 31
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:89776

On Sun, May 3, 2015 at 1:45 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Sat, May 2, 2015 at 5:42 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> Christian Gollwitzer <auriocus@gmx.de>:
>>
>>> That's why I still think it is a microoptimization, which helps only
>>> in some specific cases.
>>
>> It isn't done for performance. It's done to avoid a stack overflow
>> exception.
>
> If your tree is balanced, then the number of items you would need to
> have to get a stack overflow exception would be approximately 2 **
> 1000, which you can't possibly hope to fit into memory.
>
> If your tree is unbalanced and you're getting a stack overflow
> exception, then maybe you should think about balancing it.

That's assuming it's a search tree, where you *can* just "think about
balancing it". What if it's a parse tree? Let's say you're walking the
AST of a Python module, looking for all functions that contain 'yield'
or 'yield from' (ie generator functions). To do that, you need to walk
the entire depth of the tree, no matter how far that goes. I'm not
sure how complex a piece of code would have to be to hit 1000, but it
wouldn't be hard to have each level of tree cost you two or three
stack entries, so that could come down to just a few hundred.

However, while that _is_ more likely to produce an unbalanced tree,
it's also that much less capable of being converted into tail
recursion.

ChrisA