[pypy-dev] Cross-post from python-ideas: Compressing the stack on the fly
Bart Wiegmans
bartwiegmans at gmail.com
Tue May 28 14:12:30 CEST 2013
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
> ****************************************
More information about the pypy-dev
mailing list