[Python-Dev] collections module (original) (raw)

Guido van Rossum guido at python.org
Tue Jan 13 12:14:22 EST 2004

[Guido] > Just in case nobody had thought of it before, couldn't the realloc() > call be avoided when roundupsize(oldsize) == roundupsize(newsize)???

[Tim]

Followup: it's not quite that easy, because (at least) PyListNew(int size) can create a list whose allocated size hasn't been rounded up.

If I "fix" that, then it's possible to get away with just one roundupsize() call on most list.insert() calls (including list.append()), while avoiding the realloc() call too. Patch attached. I timed it like so: def punchit(): from time import clock as now a = [] push = a.append start = now() for i in xrange(1000000): push(i) finish = now() return finish - start for i in range(10): print punchit() and got these elapsed times (this is Windows, so this is elapsed wall-clock time): before after ------------- -------------- 1.05227710823 1.02203188119 1.05532442716 0.569660068053 1.05461539751 0.568627533147 1.0564449622 0.569336562799 1.05964146231 0.573247959235 1.05679528655 0.568503494862 1.05569402772 0.569745553898 1.05383177727 0.569499991619 1.05528000805 0.569163914916 1.05636618113 0.570356526258 So pretty consistent here, apart from the glitch on the first "after" run, and about an 80% speedup. Yawn . If someone wants to run with this, be my guest. There may be other holes (c.f. PyListNew above), and it could sure use a comment about why it's correct (if it in fact is <0.9 wink>).

Awesome! We need timing results on some other platforms (Linux, FreeBSD, MacOSX).

Volunteers?

--Guido van Rossum (home page: http://www.python.org/~guido/)

More information about the Python-Dev mailing list