2017-02-08.sagews

Math 152: Intro to Mathematical Software

2017-02-08

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

Lecture 13: Timing and Speed

Timing your code

Here's some code. It is intentionally naive in various ways...

def sin_sum(n):
    """
    Return the "sum"  sin(1) + sin(2) + ... + sin(n-1)
    """
    return sum(float(sin(m)) for m in xrange(1,n))

sin_sum(10000)

1.9395054106806988

Explain this code line by line:

• define function of one input

• Docstring

• sin(m) is the sage symbolic sin function

• (sin(m) for m in xrange(1,n)) is like a list comprehension but it is "lazy" so it doesn't waste memory -- you can iterate over it though.

• sum(...) iterates over its input summing it up

• float(...) converts its input to a float

Throw out a mathematical question: Is there a simple formula for $\sum_{0< m\leq n} \sin(m)$ similar to the formula $\sum_{0< m<n} m = \frac{n(n-1)}{2}$?

sin_sum(10000)  # this might feel slow if you try it!

1.939505410680705

• Is it slow?

• Or is the network (or SMC) just slow at sending the answer back?

• If it is slow, why?

There are many ways to time execution of code:

1. Very naive: use a stopwatch. Start the code running and start a stopwatch on your phone or whatever. Look at the wall clock.

2. Python: use the time module, and prints

3. Python: use the timeit module, and better prints

4. In worksheets: %time and %timeit

5. In Sage: cputime and walltime functions.

6. Using %prun in a terminal (so create a terminal and type "sage"). This is an ipython feature.

And there are also many, many ways to speed up code...

# Let's time the function in all these ways.

# 1. seems like a couple of seconds...?

# 2. time module

import time
t = time.time()   # number of seconds since "the epoch" (exercise: when was that?)
sin_sum(10000)
print "elapsed time", time.time() - t

# nice thing -- you can put time.time()'s anywhere in your code -- sort of like print statements -- for debugging performance issues..

1.939505410680705 elapsed time 23.8433499336

print time.time()

1486592141.29

3: timeit module: see https://docs.python.org/2/library/timeit.html

import timeit
timeit.timeit('sin_sum(1000)', number=50)

Error in lines 2-2 Traceback (most recent call last): File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 982, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/sage/sage-7.5/local/lib/python/timeit.py", line 237, in timeit return Timer(stmt, setup, timer).timeit(number) File "/projects/sage/sage-7.5/local/lib/python/timeit.py", line 202, in timeit timing = self.inner(it, self.timer) File "<timeit-src>", line 6, in inner NameError: global name 'sin_sum' is not defined

Hmm, let's check the documentation. Aha!

def tmp():
    return sin_sum(100)

timeit.timeit(tmp, number=500)

17.5108540058136

4: %time, %timeit commands to SMC

%time
sin_sum(10000)

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 982, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1027, in execute_with_code_decorators code = code_decorator(code) TypeError: 'module' object is not callable

# the above doesn't work because we replace %time by doing "import time".... so do this:
reset('time')

%time
sin_sum(10000)

1.939505410680705 CPU time: 11.98 s, Wall time: 21.70 s CPU time: 11.98 s, Wall time: 21.70 s

%timeit
sin_sum(1000)

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 982, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1027, in execute_with_code_decorators code = code_decorator(code) TypeError: 'module' object is not callable

reset('timeit')
%timeit
sin_sum(100)  # runs many times so give it smaller input!

125 loops, best of 3: 4.96 ms per loop

5: cputime and walltime functions

t = cputime()
sin_sum(10000)
print cputime(t)

1.939505410680705 7.456

t = walltime()
sin_sum(10000)
print walltime(t)

1.939505410680705 16.6226541996

Discuss the difference between cpu and wall time.

%md
6: Using %prun in a terminal

- +New --> Terminal.
- type `sage` to start sage.
- Define the function.
- Use `%prun sin_sum(10000)`

6: Using %prun in a terminal

• +New --> Terminal.

• type sage to start sage.

• Define the function.

• Use %prun sin_sum(10000)

Exercise: Try to make sin_sum faster and time the result in several ways. Ideas for how:

• replace m by float(m)

• replace sin by math.sin

def sin_sum(n):
    """
    Return the sum  sin(1) + sin(2) + ... + sin(n-1)
    """
    return float(sum(sin(m) for m in xrange(1,n)))

def sin_sum(n):
    """
    Return the sum  sin(1) + sin(2) + ... + sin(n-1)
    """
    return float(sum(math.sin(m) for m in xrange(1,n)))

Of course, you can also try to make the function faster using mathematical knowledge! Can you find an explicit formula for $\sum_{0< m< n} \sin(m)$?