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

[Guido van Rossum]

> > > The drawback is that recursive functions would be slower now.
> > 
> > How come?
> 
> With the current freelist approach, there can be a large pool of
> pre-made frames available for each level of recursion.  On the
> plus side, this means fewer calls to malloc().  On the minus side,
> the pooled frames are generic to any code block and take a long
> time to initialize.
> 
> The patch eliminates the freelist in favor of keeping a single
> pre-made frame for each code block.  In addition to saving 
> a call to malloc(), the advantage is that the pre-made frame
> is custom to the code block and only half of fields need to
> be updated each time the code block is called.  
> 
> This is a nice net win for normal code blocks.  However, recursive
> functions use up their one pre-made frame on the first level of
> recursion.  On subsequent calls, they have to call malloc() resulting
> in a net slowdown.
> 
> As is, the patch is slim and elegant.  However, it could built
> out to have both a code block specific pre-made frame and a freelist.
> The patch would then be much larger and somewhat ugly, but it would
> avoid the speed loss for recursive functions.
> 
> Armin's quick and dirty timings for the current patch show a 10%
> speedup for non-recursive functions and a 20% slowdown of 
> recursive functions.
> 
> The question is whether to clutter the patch in order to save the
> 20% on recursive functions.

Yes, I think it's worth the extra effort.  The last thing we need is
feeding the meme that recursion is a feature that should be avoided.

--Guido van Rossum (home page: http://www.python.org/~guido/)