Cross-post from python-ideas: Compressing the stack on the fly

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@python.org>:

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@gmail.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. On Tue, May 28, 2013 at 3:12 PM, Bart Wiegmans <bartwiegmans@gmail.com>wrote:
participants (3)
-
Bart Wiegmans
-
Maciej Fijalkowski
-
Ram Rachum