[Python-Dev] collections module

[Bob Ippolito]

On Jan 13, 2004, at 12:14 PM, Guido van Rossum wrote:

>> [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) 
>> PyList_New(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 <wink>.
>>
>> If someone wants to run with this, be my guest.  There may be other 
>> holes
>> (c.f. PyList_New 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?

Mac OS X 10.3.2, gcc (GCC) 3.3 20030304 (Apple Computer, Inc. build 
1495), dual g5 2ghz w/ 1gb ram, ./configure --disable-framework

before	after
0.38		0.29
0.36		0.26
0.36		0.26
0.36		0.27
0.36		0.26
0.36		0.26
0.36		0.26
0.36		0.26
0.36		0.27
0.36		0.26

Mac OS X 10.3.2, gcc (GCC) 3.3 20030304 (Apple Computer, Inc. build 
1495), dvi titanium powerbook g4 1ghz w/ 1gb ram, ./configure 
--disable-framework

before	after
0.78		0.57
0.74		0.53
0.73		0.53
0.74		0.52
0.73		0.52
0.76		0.53
0.73		0.53
0.75		0.53
0.75		0.53
0.75		0.52

So it seems that the 2ghz g5 is about twice as fast as the 1ghz g4 for 
Python (when running TIm's test), and that either way you save about 
25% with Tim's patch.

-bob
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2357 bytes
Desc: not available
Url : http://mail.python.org/pipermail/python-dev/attachments/20040113/7c6d47d1/smime.bin