[Python-Dev] Joys of Optimization (original) (raw)

Raymond Hettinger raymond.hettinger at verizon.net
Fri Mar 19 00:45:49 EST 2004

[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())

More information about the Python-Dev mailing list