[Python-Dev] [ python-Patches-876206 ] scary frame speed hacks

[Dennis Allison]

I would be cautious about anything that slows recursive functions becasue
almost any interesting data structure traversal is recursive.  

On Mon, 1 Mar 2004, Armin Rigo wrote:

> Hello,
> 
> We are about to apply a patch that both speeds up frame allocation and make it 
> simpler by removing the frame freelist (patch #876206).
> 
> The drawback is that recursive functions would be slower now.  The two 
> alternatives that we have are thus:
> 
> 
> (1) Ignore the recursive function problem and apply the patch.
> 
> def f(n, m):
>     if n > 0 and m > 0:
>         return f(n-1, m) + f(n, m-1)
>     else:
>         return 1
> f(11, 11)
> 
> Takes 3.26s instead of just 2.64s.  This is a major speed hit (20%).  On the
> other hand, recursive functions are not so common in Python, and the patch
> simplifies the C source interestingly.
> 
> 
> (2) Don't remove the frame freelist but combine it with the new patch.
> 
> This would give the best of both worlds performance-wise, but the frame
> allocation code becomes convoluted.  It would amount to add a third way to
> allocate a frame, and all three ways give a frame with different guaranteed
> invariants (i.e. different sets of fields that we know to be already correct
> and thus don't have to initialize).
> 
> The question is whether (1) or (2) is better.
> 
> 
> Armin
> 
> 
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> http://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: http://mail.python.org/mailman/options/python-dev/allison%40sumeru.stanford.edu
>