[issue2013] Long object free list optimization

[Gregory P. Smith]

Gregory P. Smith <greg at krypto.org> added the comment:

I'm attaching a slightly improved version of the longfreelist2 patch. 
It moves the important test to be first and removes the unneeded ? :
conditional.

........................
Here are some more benchmarks:
........................

--- issue2013-without-patch.txt	2008-03-22 12:18:37.000000000 -0700
+++ issue2013-longfreelist2-gps01-size-first.txt	2008-03-22
12:34:44.000000000 -0700
@@ -1,43 +1,43 @@
-3.0a3+ (py3k:61746M, Mar 22 2008, 12:12:29) 
+3.0a3+ (py3k:61746M, Mar 22 2008, 12:33:47) 
 [GCC 4.0.1 (Apple Computer, Inc. build 5367)]
 
 ./python.exe -m timeit min(range(255))
 
-100000 loops, best of 3: 17.2 usec per loop
+100000 loops, best of 3: 15.8 usec per loop
 
 ./python.exe -m timeit -s n=1000000 sum(range(n,n+10000))
 
-1000 loops, best of 3: 1.21 msec per loop
+1000 loops, best of 3: 1.22 msec per loop
 
 ./python.exe -m timeit sum(range(-32768,32768))
 
-100 loops, best of 3: 3.98 msec per loop
+100 loops, best of 3: 2.63 msec per loop
 
 ./python.exe -m timeit sum(range(-1000000,1000000))
 
-10 loops, best of 3: 296 msec per loop
+10 loops, best of 3: 273 msec per loop
 
 ./python.exe -m timeit sum(range(4000))
 
-1000 loops, best of 3: 239 usec per loop
+10000 loops, best of 3: 151 usec per loop
 
 ./python.exe -m timeit sum(list(range(4000)))
 
-1000 loops, best of 3: 360 usec per loop
+1000 loops, best of 3: 274 usec per loop
 
 ./python.exe -m timeit sum(range(10000))
 
-1000 loops, best of 3: 615 usec per loop
+1000 loops, best of 3: 382 usec per loop
 
 ./python.exe -m timeit sum(list(range(10000)))
 
-1000 loops, best of 3: 887 usec per loop
+1000 loops, best of 3: 802 usec per loop
 
 ./python.exe -m timeit sum(range(40000))
 
-100 loops, best of 3: 2.55 msec per loop
+100 loops, best of 3: 1.79 msec per loop
 
 ./python.exe -m timeit sum(range(80000))
 
-100 loops, best of 3: 6.4 msec per loop
+100 loops, best of 3: 5.77 msec per loop
 

........................
And a benchmarks of the longfreelist2 patch before my improvement:
........................

--- issue2013-without-patch.txt	2008-03-22 12:18:37.000000000 -0700
+++ issue2013-longfreelist2.txt	2008-03-22 12:19:46.000000000 -0700
@@ -1,43 +1,43 @@
-3.0a3+ (py3k:61746M, Mar 22 2008, 12:12:29) 
+3.0a3+ (py3k:61746M, Mar 22 2008, 12:18:57) 
 [GCC 4.0.1 (Apple Computer, Inc. build 5367)]
 
 ./python.exe -m timeit min(range(255))
 
-100000 loops, best of 3: 17.2 usec per loop
+100000 loops, best of 3: 16.1 usec per loop
 
 ./python.exe -m timeit -s n=1000000 sum(range(n,n+10000))
 
-1000 loops, best of 3: 1.21 msec per loop
+1000 loops, best of 3: 1.25 msec per loop
 
 ./python.exe -m timeit sum(range(-32768,32768))
 
-100 loops, best of 3: 3.98 msec per loop
+100 loops, best of 3: 2.95 msec per loop
 
 ./python.exe -m timeit sum(range(-1000000,1000000))
 
-10 loops, best of 3: 296 msec per loop
+10 loops, best of 3: 283 msec per loop
 
 ./python.exe -m timeit sum(range(4000))
 
-1000 loops, best of 3: 239 usec per loop
+1000 loops, best of 3: 177 usec per loop
 
 ./python.exe -m timeit sum(list(range(4000)))
 
-1000 loops, best of 3: 360 usec per loop
+1000 loops, best of 3: 276 usec per loop
 
 ./python.exe -m timeit sum(range(10000))
 
-1000 loops, best of 3: 615 usec per loop
+1000 loops, best of 3: 453 usec per loop
 
 ./python.exe -m timeit sum(list(range(10000)))
 
-1000 loops, best of 3: 887 usec per loop
+1000 loops, best of 3: 792 usec per loop
 
 ./python.exe -m timeit sum(range(40000))
 
-100 loops, best of 3: 2.55 msec per loop
+100 loops, best of 3: 2.03 msec per loop
 
 ./python.exe -m timeit sum(range(80000))
 
-100 loops, best of 3: 6.4 msec per loop
+100 loops, best of 3: 6.01 msec per loop
 

........................
And diffs of longfreelist2 vs longfreelist2-gps01:
........................
--- issue2013-longfreelist2.txt	2008-03-22 12:19:46.000000000 -0700
+++ issue2013-longfreelist2-gps01-size-first.txt	2008-03-22
12:34:44.000000000 -0700
@@ -1,43 +1,43 @@
-3.0a3+ (py3k:61746M, Mar 22 2008, 12:18:57) 
+3.0a3+ (py3k:61746M, Mar 22 2008, 12:33:47) 
 [GCC 4.0.1 (Apple Computer, Inc. build 5367)]
 
 ./python.exe -m timeit min(range(255))
 
-100000 loops, best of 3: 16.1 usec per loop
+100000 loops, best of 3: 15.8 usec per loop
 
 ./python.exe -m timeit -s n=1000000 sum(range(n,n+10000))
 
-1000 loops, best of 3: 1.25 msec per loop
+1000 loops, best of 3: 1.22 msec per loop
 
 ./python.exe -m timeit sum(range(-32768,32768))
 
-100 loops, best of 3: 2.95 msec per loop
+100 loops, best of 3: 2.63 msec per loop
 
 ./python.exe -m timeit sum(range(-1000000,1000000))
 
-10 loops, best of 3: 283 msec per loop
+10 loops, best of 3: 273 msec per loop
 
 ./python.exe -m timeit sum(range(4000))
 
-1000 loops, best of 3: 177 usec per loop
+10000 loops, best of 3: 151 usec per loop
 
 ./python.exe -m timeit sum(list(range(4000)))
 
-1000 loops, best of 3: 276 usec per loop
+1000 loops, best of 3: 274 usec per loop
 
 ./python.exe -m timeit sum(range(10000))
 
-1000 loops, best of 3: 453 usec per loop
+1000 loops, best of 3: 382 usec per loop
 
 ./python.exe -m timeit sum(list(range(10000)))
 
-1000 loops, best of 3: 792 usec per loop
+1000 loops, best of 3: 802 usec per loop
 
 ./python.exe -m timeit sum(range(40000))
 
-100 loops, best of 3: 2.03 msec per loop
+100 loops, best of 3: 1.79 msec per loop
 
 ./python.exe -m timeit sum(range(80000))
 
-100 loops, best of 3: 6.01 msec per loop
+100 loops, best of 3: 5.77 msec per loop

----------
nosy: +gregory.p.smith
type: feature request -> performance
versions:  -Python 2.6
Added file: http://bugs.python.org/file9817/py3k_longfreelist2-gps01.patch

__________________________________
Tracker <report at bugs.python.org>
<http://bugs.python.org/issue2013>
__________________________________