[pypy-dev] Cross-post from python-ideas: Compressing the stack on the fly

Maciej Fijalkowski fijall at gmail.com
Tue May 28 14:28:02 CEST 2013 

On Tue, May 28, 2013 at 2:24 PM, Ram Rachum <ram at rachum.com> wrote:
> Thanks for your critique, Bart.
>
> One counter-point I'd like to make to your third argument, which I had to
> make over at python-ideas as well: I am not advocating recursive
> programming. There is no need to convince me that the loop version of the
> algorithm is superior to the recursive version. The reason I care about
> optimizing recursive algorithms is because sometimes these algorithms are
> forced on you, and when they are, you want them to be as efficient as
> possible.
>
> There's the example of the `pickle` module. In Python, pickling is
> recursive. I had a case where a program of mine failed to run because it
> involved pickling an object that referenced a large number of small objects
> that referenced each other. I had no choice except using recursion, because
> Python's `pickle` uses recursion. (Except of course writing my own pickle
> module...)
>
> So I want recursive algorithm to be faster not because I'd like to use them,
> but because I want them to be faster when I'm forced to use them.

stackless does allow you to have deep recursion by copying the stack away FYI.

>
>
> On Tue, May 28, 2013 at 3:12 PM, Bart Wiegmans <bartwiegmans at gmail.com>
> wrote:
>>
>> Hi Ram,
>>
>> That is a daring idea, really. But since you asked it, I will tell you
>> what I think.
>>
>> I think it is a bad idea.
>>
>> First of all, the complexity of implementation. I see two 'obvious'
>> implementations of your idea, which is a): an 'on-line' stack
>> compressor, which will slow down functions calls farther than they are
>> already (in CPython, anyway), or b): a 'just-in-time' stack compressor
>> that is initiated when the 1000th stack frame is reached. I can
>> imagine this happening in-place, but it won't be efficient.
>> Now consider what happens when an exception is raised from the bottom
>> to the top.Or worse, from the bottom to somewhere-in-the-middle.
>>
>> The second point concerns the possible gains. Suppose your recursive
>> factorial stack is compressed. At the very least, any compression
>> algorithm must store the decreasing integer that is multiplied. (You
>> might get away with detecting the pattern, but don't count on it). At
>> best, you might run your recursive algorithm a bit longer, but it will
>> overflow eventually. In other words, on a machine with a finite stack
>> size, the algorithm is *wrong*. The correct recursive implementation
>> looks like this:
>>
>> def factorial(x):
>>      def recursive(x, c):
>>           if x <= 1:
>>               return c
>>           return recursive(x-1, x * c)
>>       return recursive(x, 1)
>>
>> Which doesn't need to  store the decreasing x on any stack, and is
>> thus a prime candidate for TCO.
>>
>> The third point concerns the reason why python does not have TCO in
>> the first place. I've read Guido's blog as well, and in my opinion,
>> he's wrong to make such a distinction between what are essentially
>> nearly identical processes: jumping to new code locations. As it is,
>> however, he's dictator. In python, you're simply not /supposed/ to use
>> deep recursive algorithms. It is considered un-pythonic.
>>
>> Nevertheless, I like the style of your idea :-).
>>
>> Kind regards,
>> Bart Wiegmans
>>
>>
>>
>> 2013/5/28  <pypy-dev-request at python.org>:
>> > Send pypy-dev mailing list submissions to
>> >         pypy-dev at python.org
>> >
>> > To subscribe or unsubscribe via the World Wide Web, visit
>> >         http://mail.python.org/mailman/listinfo/pypy-dev
>> > or, via email, send a message with subject or body 'help' to
>> >         pypy-dev-request at python.org
>> >
>> > You can reach the person managing the list at
>> >         pypy-dev-owner at python.org
>> >
>> > When replying, please edit your Subject line so it is more specific
>> > than "Re: Contents of pypy-dev digest..."
>> >
>> >
>> > Today's Topics:
>> >
>> >    1. Cross-post from python-ideas: Compressing the stack on    the
>> >       fly (Ram Rachum)
>> >    2. pypy (Samir Tigrine)
>> >
>> >
>> > ----------------------------------------------------------------------
>> >
>> > Message: 1
>> > Date: Mon, 27 May 2013 13:39:01 +0300
>> > From: Ram Rachum <ram at rachum.com>
>> > To: pypy-dev at python.org
>> > Subject: [pypy-dev] Cross-post from python-ideas: Compressing the
>> >         stack on        the fly
>> > Message-ID:
>> >
>> > <CANXboVaE_HsQt0CQhJwBwNOL8F+qPzCLbZZsdoLLQZvY4nSx=A at mail.gmail.com>
>> > Content-Type: text/plain; charset="iso-8859-1"
>> >
>> > Hi guys,
>> >
>> > I made a post on the Python-ideas mailing list that I was told might be
>> > relevant to Pypy. I've reproduced the original email below. Here is the
>> > thread on Python-ideas with all the
>> >
>> > discussion.<https://groups.google.com/forum/?fromgroups#!topic/python-ideas/hteGSNTyC_4>
>> >
>> > --------------
>> >
>> > Hi everybody,
>> >
>> > Here's an idea I had a while ago. Now, I'm an ignoramus when it comes to
>> > how programming languages are implemented, so this idea will most likely
>> > be
>> > either (a) completely impossible or (b) trivial knowledge.
>> >
>> > I was thinking about the implementation of the factorial in Python. I
>> > was
>> > comparing in my mind 2 different solutions: The recursive one, and the
>> > one
>> > that uses a loop. Here are example implementations for them:
>> >
>> > def factorial_recursive(n):
>> >     if n == 1:
>> >         return 1
>> >     return n * factorial_recursive(n - 1)
>> >
>> > def factorial_loop(n):
>> >     result = 1
>> >     for i in range(1, n + 1):
>> >         result *= i
>> >     return result
>> >
>> > I know that the recursive one is problematic, because it's putting a lot
>> > of
>> > items on the stack. In fact it's using the stack as if it was a loop
>> > variable. The stack wasn't meant to be used like that.
>> >
>> > Then the question came to me, why? Maybe the stack could be built to
>> > handle
>> > this kind of (ab)use?
>> >
>> > I read about tail-call optimization on Wikipedia. If I understand
>> > correctly, the gist of it is that the interpreter tries to recognize, on
>> > a
>> > frame-by-frame basis, which frames could be completely eliminated, and
>> > then
>> > it eliminates those. Then I read Guido's blog post explaining why he
>> > doesn't want it in Python. In that post he outlined 4 different reasons
>> > why
>> > TCO shouldn't be implemented in Python.
>> >
>> > But then I thought, maybe you could do something smarter than
>> > eliminating
>> > individual stack frames. Maybe we could create something that is to the
>> > current implementation of the stack what `xrange` is to the old-style
>> > `range`. A smart object that allows access to any of a long list of
>> > items
>> > in it, without actually having to store those items. This would solve
>> > the
>> > first argument that Guido raises in his post, which I found to be the
>> > most
>> > substantial one.
>> >
>> > What I'm saying is: Imagine the stack of the interpreter when it runs
>> > the
>> > factorial example above for n=1000. It has around 1000 items in it and
>> > it's
>> > just about to explode. But then, if you'd look at the contents of that
>> > stack, you'd see it's embarrassingly regular, a compression algorithm's
>> > wet
>> > dream. It's just the same code location over and over again, with a
>> > different value for `n`.
>> >
>> > So what I'm suggesting is an algorithm to compress that stack on the
>> > fly.
>> > An algorithm that would detect regularities in the stack and instead of
>> > saving each individual frame, save just the pattern. Then, there
>> > wouldn't
>> > be any problem with showing informative stack trace: Despite not storing
>> > every individual frame, each individual frame could still be accessed,
>> > similarly to how `xrange` allow access to each individual member without
>> > having to store each of them.
>> >
>> > Then, the stack could store a lot more items, and tasks that currently
>> > require recursion (like pickling using the standard library) will be
>> > able
>> > to handle much deeper recursions.
>> >
>> > What do you think?
>> >
>> >
>> > Ram.
>> > -------------- next part --------------
>> > An HTML attachment was scrubbed...
>> > URL:
>> > <http://mail.python.org/pipermail/pypy-dev/attachments/20130527/5723bc1f/attachment-0001.html>
>> >
>> > ------------------------------
>> >
>> > Message: 2
>> > Date: Tue, 28 May 2013 11:19:53 +0200
>> > From: Samir Tigrine <tigrine.samir at gmail.com>
>> > To: pypy-dev at python.org
>> > Subject: [pypy-dev] pypy
>> > Message-ID:
>> >
>> > <CAC3411-qcKUED5YrXQ6P5O7boN46tTR+a3-htQjiDWr3wZhmFg at mail.gmail.com>
>> > Content-Type: text/plain; charset="iso-8859-1"
>> >
>> > Hello
>> >
>> > now I intend to use pypy
>> >
>> > It is compatible with zope ?
>> >
>> > cordially
>> > -------------- next part --------------
>> > An HTML attachment was scrubbed...
>> > URL:
>> > <http://mail.python.org/pipermail/pypy-dev/attachments/20130528/5832754f/attachment-0001.html>
>> >
>> > ------------------------------
>> >
>> > Subject: Digest Footer
>> >
>> > _______________________________________________
>> > pypy-dev mailing list
>> > pypy-dev at python.org
>> > http://mail.python.org/mailman/listinfo/pypy-dev
>> >
>> >
>> > ------------------------------
>> >
>> > End of pypy-dev Digest, Vol 25, Issue 39
>> > ****************************************
>> _______________________________________________
>> pypy-dev mailing list
>> pypy-dev at python.org
>> http://mail.python.org/mailman/listinfo/pypy-dev
>
>
>
> _______________________________________________
> pypy-dev mailing list
> pypy-dev at python.org
> http://mail.python.org/mailman/listinfo/pypy-dev
>

More information about the pypy-dev mailing list