[Python-Dev] Speed of test_sort.py

[Tim Peters]

[Guido, mixing test_longexp w/ the new test_sort]
> It's about the same on my Linux box (system time is CPU time spent in
> the kernel):

Dang!  I was more than half hoping it was a Windows glitch.

> test_longexp alone takes 1.92 user + 0.22 system seconds.
> test_sort alone takes 1.71 user + 0.01 system seconds.
> test_sort + test_longexp takes 3.62 user + 0.18 system seconds.
> test_longexp + test_sort takes 38.05 user and 0.34 system seconds!!!
>
> I'll see if I can get this to run under a profiler.

It's intriguing, but I have to do other things today.  Here's a
self-contained test case that allows to vary REPS from the command line:

"""
import sys
from time import clock as now

def do_shuffle(x):
    import random
    random.shuffle(x)

def do_longexp(REPS):
    l = eval("[" + "2," * REPS + "]")
    assert len(l) == REPS

def do_sort(x):
    x.sort(lambda x, y: cmp(x, y))
    # Doing x.sort(cmp) instead, there's no slowdown, so it's not just
    # that there's an explicit comparison function.

x = range(1000)
do_shuffle(x)

REPS = 65580
if len(sys.argv) > 1:
    REPS = int(sys.argv[1])

t1 = now()
do_longexp(REPS)
t2 = now()
do_sort(x)
t3 = now()

print "At REPS=%d, longexp %.2g sort %.2g" % (REPS, t2-t1, t3-t2)
"""

On my box, the time it takes for the sort appears, after a certain point, to
grow quadratically(!) in the REPS value (these timings were hasty and not on
a quiet box, so only gross conclusions are justified):

C:\Code\python\PCbuild>python temp.py 1
At REPS=1, longexp 0.00021 sort 0.027

At REPS=1, longexp 0.00018 sort 0.036
At REPS=10, longexp 0.00035 sort 0.053
At REPS=100, longexp 0.002 sort 0.028
At REPS=1000, longexp 0.039 sort 0.073
At REPS=10000, longexp 0.47 sort 0.45
At REPS=20000, longexp 0.89 sort 0.44
At REPS=40000, longexp 1.5 sort 1.3
At REPS=80000, longexp 2.5 sort 5.9
At REPS=160000, longexp 5 sort 22