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

[Bob Ippolito]

On Mar 2, 2004, at 11:54 AM, Guido van Rossum wrote:

>>>> 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.

Well it's already true to some small extent because of the recursion 
depth limit.  Though, this has only been a problem for me once, and I 
rewrote it as a large ugly iterative version.

-bob