[Python-Dev] Re: Fast access to __builtins__

Raymond Hettinger python@rcn.com
Sun, 30 Mar 2003 22:27:07 -0500

> Raymond Hettinger <python@rcn.com>:
> > * Scanning my own sources, it looks like some of the builtins
> >    almost never appear inside loops (dir, map, filter, zip, dict, range).
> >    The ones that are in loops usually do something simple (int, str,
> >    chr, len).  Either way, builtin access never seems to dominate
> >    the running time.  OTOH, maybe that's just the way I write code.
[Greg Ewing]
> That's probably true in the large. However, sometimes one has a tight
> little loop that makes lots of calls to a builtin. I've occasionally
> improved the speed of something noticeably using the
> copy-a-builtin-to-a-local trick.

It will have to wait until Py2.4 and the issue will likely be subsumed by 
more sophisticated approaches that optimize all namespace access.  
Jeremy's DList technique looks especially promising.  Similarly, I'm
experimenting with a dict subclass that keeps its values in lists of
length one and can return the container for clients interested in fast
get or set access to the value associated with a given key.

Also, I've been working on a faster design for dictionaries that increases
overall sparseness (meaning fewer collisions) while increasing the density
of entries that fit in a single cash line (reducing the cost of a miss).  
Increasing density involves splitting the arrays of PyDictEntry into separate 
arrays of hashes, keys, and values.  Further, the entries are clustered into 
groups of up to 16 hash values that can fit in a single cache line.  This also
allows for a much tighter inner loop for the lookup function.

Raymond Hettinger