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

Christian Tismer tismer at stackless.com
Wed Mar 3 16:29:30 EST 2004

Armin Rigo wrote:

> Hello Christian,
> On Wed, Mar 03, 2004 at 07:24:23PM +0100, Christian Tismer wrote:
>>What's bad about my proposal?
>>In short: No frame cache in the code object.
>>Have a small array of chains of cached frames.
>>Index this by the address of the code object modulo some
>>prime which is the array size.
> Oh, I missed the part about chaining cached frames.  Read-reading your
> proposal, it seems that there can be at most one cached frame per hash value.  
> This also raises the question of how bad hash collisions could degrade
> performance if you're unlucky.  I was trying to work around these two problems
> based on your proposal but couldn't get something clean...

How that?
For every hash value, I get a slot in the array.
That slot has a chain of all cached frames for that hash value.
On hash collision:
- we could either walk through the slot and free frames until
   we either find a matching frame and create a new one if
   we don't find it
- we could instead assign a unique number to each code object
   and let that array grow. Variants are possible, of course.

Completely different approach without an extra array:
Put all code objects into a doubly linked list.
Maintain a chain of zombie frames for every code object.
 From time to time, walk through all the code objects
and clear their caches.

Again different approach:
Maintain a chain of zombie frames for every code object.
Furthermore, make code object garbage collected objects,
this is probably not so expensive?
Then make code objects clear their zombie cache on every
n'th (for some reasonable n) call of inquiry.
This saves us from maintaining an extra linked list,
but might be a little bit slower, since there is more gc work.

ciao - chris

Christian Tismer             :^)   <mailto:tismer at stackless.com>
Mission Impossible 5oftware  :     Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9a     :    *Starship* http://starship.python.net/
14109 Berlin                 :     PGP key -> http://wwwkeys.pgp.net/
work +49 30 89 09 53 34  home +49 30 802 86 56  mobile +49 173 24 18 776
PGP 0x57F3BF04       9064 F4E1 D754 C2FF 1619  305B C09C 5A3B 57F3 BF04
      whom do you want to sponsor today?   http://www.stackless.com/

More information about the Python-Dev mailing list