[Python-Dev] [ python-Patches-876206 ] scary frame speed hacks (original) (raw)

Guido van Rossum guido at python.org
Tue Mar 2 11:54:00 EST 2004

> > 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/)

More information about the Python-Dev mailing list