[pypy-dev] Cross-post from python-ideas: Compressing the stack on the fly
Ram Rachum
ram at rachum.com
Tue May 28 14:24:19 CEST 2013
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.
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/pypy-dev/attachments/20130528/8e1451d0/attachment-0001.html>
More information about the pypy-dev
mailing list