[Python-Dev] Joys of Optimization

[Raymond Hettinger]

[Extract from my earlier post]
>> C:\python24\python timedictiter.py
>>
>> C:\pydev>\python23\python timedictiter.py
>> 3.44381233343 items()
>> 
>> C:\pydev>\python22\python timedictiter.py
>> 2.99887443638 items()


[Brett]
> Interesting how items() slowed down between 2.2 and 2.3 
> but is now a sliver faster than 2.2 was.

Actually, items() stayed the same between 2.2 and 2.3, it was the
underlying dictionary that changed.  For 2.3, I made mid-sized
dictionaries more sparse.  There were fewer collisions, improved lookup
time, and fewer resize operations.  The trade-off for this tune-up was
increased memory utilization and slower dictionary iteration (see
Objects/dictnotes.txt for details).

When I optimized iteration for Py2.4, we got all the speed back without
having to trade-away the benefits of sparsity.  To see the improvement,
fill a dictionary with random keys and then time "for k in keylist: k in
d".  You'll see an improvement between Py2.2 and Py2.3.  Also, there is
a similar speedup in "for k in nonkeys: k in d".  IOW, failed searches
also run faster.


Raymond Hettinger


P.S.  If you're wondering what the length transparency checkins were all
about, look at these new timings:

C:\pydev>\python24\python timedictiter.py
0.384519519268 list(d.iterkeys())
0.377146784224 list(d.itervalues())
1.188094839 list(d.iteritems())

C:\pydev>\python23\python timedictiter.py
2.12341976902 list(d.iterkeys())
2.30316046196 list(d.itervalues())
3.10405387284 list(d.iteritems())