[Python-Dev] Frame zombies

[Eyal Lotem]

I was just looking through the code that handles frames (as part of my
current effort to determine how to improve on CPython's performance),
when I noticed the freelist/zombie mechanism for frame allocation
handling.

While the zombie mechanism seems like a nice optimization, I believe
there can be a couple of improvements.

Currently, each code object has a zombie frame that last executed it.
This zombie is reused when that code object is re-executed in a frame.
When a frame is released, it is reassigned as the zombie of the code,
and iff the code object already has a zombie assigned to it, it places
the frame in the freelist.

If I understand correctly, this means, that the "freelist" is actually
only ever used for recursive-call frames that were released.  It also
means that these released frames will be reassigned to other code
objects in the future - in which case they will be reallocated,
perhaps unnecessarily.  "freelist" is just temporary storage for
released recursive calls. A program with no recursions will always
have an empty freelist.

What is bounding the memory consumption of this mechanism is a limit
on the number of frames in the freelist (and the fact that there is a
limited number of code objects, each of which may have an additional
zombie frame).

I believe a better way to implement this mechanism:

A. Replace the co_zombie frame with a co_zombie_freelist.
B. Remove the global freelist.

In other words, have a free list for each code object, rather than
one-per-code-object and a freelist.
This can be memory-bound by limiting the freelist size in each code object.
This can be use a bit more memory if a recursion is called just once -
and then discarded (waste for example 10 frames instead of 1), but can
save a lot of realloc calls when there is more than one recursion used
in the same program.
It is also possible to substantially increase the number of frames
stored per code-object, and then use some kind of more sophisticated
aging mechanism on the zombie freelists to periodically get rid of
unused freelists.  That kind of mechanism would mean that even in the
case of recursive calls, virtually all frame allocs are available from
the freelist.

I also believe this to be somewhat simpler, as there is only one
concept (a zombie freelist) rather than 2 (a zombie code object and a
freelist for recursive calls), and frames are never realloc'd, but
only allocated.

Should I make a patch?