1#! /usr/bin/env python
2
3"""Tool for measuring execution time of small code snippets.
4
5This module avoids a number of common traps for measuring execution
6times.  See also Tim Peters' introduction to the Algorithms chapter in
7the Python Cookbook, published by O'Reilly.
8
9Library usage: see the Timer class.
10
11Command line usage:
12    python timeit.py [-n N] [-r N] [-s S] [-t] [-c] [-h] [--] [statement]
13
14Options:
15  -n/--number N: how many times to execute 'statement' (default: see below)
16  -r/--repeat N: how many times to repeat the timer (default 3)
17  -s/--setup S: statement to be executed once initially (default 'pass')
18  -t/--time: use time.time() (default on Unix)
19  -c/--clock: use time.clock() (default on Windows)
20  -v/--verbose: print raw timing results; repeat for more digits precision
21  -h/--help: print this usage message and exit
22  --: separate options from statement, use when statement starts with -
23  statement: statement to be timed (default 'pass')
24
25A multi-line statement may be given by specifying each line as a
26separate argument; indented lines are possible by enclosing an
27argument in quotes and using leading spaces.  Multiple -s options are
28treated similarly.
29
30If -n is not given, a suitable number of loops is calculated by trying
31successive powers of 10 until the total time is at least 0.2 seconds.
32
33The difference in default timer function is because on Windows,
34clock() has microsecond granularity but time()'s granularity is 1/60th
35of a second; on Unix, clock() has 1/100th of a second granularity and
36time() is much more precise.  On either platform, the default timer
37functions measure wall clock time, not the CPU time.  This means that
38other processes running on the same computer may interfere with the
39timing.  The best thing to do when accurate timing is necessary is to
40repeat the timing a few times and use the best time.  The -r option is
41good for this; the default of 3 repetitions is probably enough in most
42cases.  On Unix, you can use clock() to measure CPU time.
43
44Note: there is a certain baseline overhead associated with executing a
45pass statement.  The code here doesn't try to hide it, but you should
46be aware of it.  The baseline overhead can be measured by invoking the
47program without arguments.
48
49The baseline overhead differs between Python versions!  Also, to
50fairly compare older Python versions to Python 2.3, you may want to
51use python -O for the older versions to avoid timing SET_LINENO
52instructions.
53"""
54
55import gc
56import sys
57import time
58try:
59    import itertools
60except ImportError:
61    # Must be an older Python version (see timeit() below)
62    itertools = None
63
64__all__ = ["Timer"]
65
66dummy_src_name = "<timeit-src>"
67default_number = 1000000
68default_repeat = 3
69
70if sys.platform == "win32":
71    # On Windows, the best timer is time.clock()
72    default_timer = time.clock
73else:
74    # On most other platforms the best timer is time.time()
75    default_timer = time.time
76
77# Don't change the indentation of the template; the reindent() calls
78# in Timer.__init__() depend on setup being indented 4 spaces and stmt
79# being indented 8 spaces.
80template = """
81def inner(_it, _timer%(init)s):
82    %(setup)s
83    _t0 = _timer()
84    for _i in _it:
85        %(stmt)s
86    _t1 = _timer()
87    return _t1 - _t0
88"""
89
90def reindent(src, indent):
91    """Helper to reindent a multi-line statement."""
92    return src.replace("\n", "\n" + " "*indent)
93
94def _template_func(setup, func):
95    """Create a timer function. Used if the "statement" is a callable."""
96    def inner(_it, _timer, _func=func):
97        setup()
98        _t0 = _timer()
99        for _i in _it:
100            _func()
101        _t1 = _timer()
102        return _t1 - _t0
103    return inner
104
105class Timer:
106    """Class for timing execution speed of small code snippets.
107
108    The constructor takes a statement to be timed, an additional
109    statement used for setup, and a timer function.  Both statements
110    default to 'pass'; the timer function is platform-dependent (see
111    module doc string).
112
113    To measure the execution time of the first statement, use the
114    timeit() method.  The repeat() method is a convenience to call
115    timeit() multiple times and return a list of results.
116
117    The statements may contain newlines, as long as they don't contain
118    multi-line string literals.
119    """
120
121    def __init__(self, stmt="pass", setup="pass", timer=default_timer):
122        """Constructor.  See class doc string."""
123        self.timer = timer
124        ns = {}
125        if isinstance(stmt, basestring):
126            # Check that the code can be compiled outside a function
127            if isinstance(setup, basestring):
128                compile(setup, dummy_src_name, "exec")
129                compile(setup + '\n' + stmt, dummy_src_name, "exec")
130            else:
131                compile(stmt, dummy_src_name, "exec")
132            stmt = reindent(stmt, 8)
133            if isinstance(setup, basestring):
134                setup = reindent(setup, 4)
135                src = template % {'stmt': stmt, 'setup': setup, 'init': ''}
136            elif hasattr(setup, '__call__'):
137                src = template % {'stmt': stmt, 'setup': '_setup()',
138                                  'init': ', _setup=_setup'}
139                ns['_setup'] = setup
140            else:
141                raise ValueError("setup is neither a string nor callable")
142            self.src = src # Save for traceback display
143            code = compile(src, dummy_src_name, "exec")
144            exec code in globals(), ns
145            self.inner = ns["inner"]
146        elif hasattr(stmt, '__call__'):
147            self.src = None
148            if isinstance(setup, basestring):
149                _setup = setup
150                def setup():
151                    exec _setup in globals(), ns
152            elif not hasattr(setup, '__call__'):
153                raise ValueError("setup is neither a string nor callable")
154            self.inner = _template_func(setup, stmt)
155        else:
156            raise ValueError("stmt is neither a string nor callable")
157
158    def print_exc(self, file=None):
159        """Helper to print a traceback from the timed code.
160
161        Typical use:
162
163            t = Timer(...)       # outside the try/except
164            try:
165                t.timeit(...)    # or t.repeat(...)
166            except:
167                t.print_exc()
168
169        The advantage over the standard traceback is that source lines
170        in the compiled template will be displayed.
171
172        The optional file argument directs where the traceback is
173        sent; it defaults to sys.stderr.
174        """
175        import linecache, traceback
176        if self.src is not None:
177            linecache.cache[dummy_src_name] = (len(self.src),
178                                               None,
179                                               self.src.split("\n"),
180                                               dummy_src_name)
181        # else the source is already stored somewhere else
182
183        traceback.print_exc(file=file)
184
185    def timeit(self, number=default_number):
186        """Time 'number' executions of the main statement.
187
188        To be precise, this executes the setup statement once, and
189        then returns the time it takes to execute the main statement
190        a number of times, as a float measured in seconds.  The
191        argument is the number of times through the loop, defaulting
192        to one million.  The main statement, the setup statement and
193        the timer function to be used are passed to the constructor.
194        """
195        if itertools:
196            it = itertools.repeat(None, number)
197        else:
198            it = [None] * number
199        gcold = gc.isenabled()
200        gc.disable()
201        try:
202            timing = self.inner(it, self.timer)
203        finally:
204            if gcold:
205                gc.enable()
206        return timing
207
208    def repeat(self, repeat=default_repeat, number=default_number):
209        """Call timeit() a few times.
210
211        This is a convenience function that calls the timeit()
212        repeatedly, returning a list of results.  The first argument
213        specifies how many times to call timeit(), defaulting to 3;
214        the second argument specifies the timer argument, defaulting
215        to one million.
216
217        Note: it's tempting to calculate mean and standard deviation
218        from the result vector and report these.  However, this is not
219        very useful.  In a typical case, the lowest value gives a
220        lower bound for how fast your machine can run the given code
221        snippet; higher values in the result vector are typically not
222        caused by variability in Python's speed, but by other
223        processes interfering with your timing accuracy.  So the min()
224        of the result is probably the only number you should be
225        interested in.  After that, you should look at the entire
226        vector and apply common sense rather than statistics.
227        """
228        r = []
229        for i in range(repeat):
230            t = self.timeit(number)
231            r.append(t)
232        return r
233
234def timeit(stmt="pass", setup="pass", timer=default_timer,
235           number=default_number):
236    """Convenience function to create Timer object and call timeit method."""
237    return Timer(stmt, setup, timer).timeit(number)
238
239def repeat(stmt="pass", setup="pass", timer=default_timer,
240           repeat=default_repeat, number=default_number):
241    """Convenience function to create Timer object and call repeat method."""
242    return Timer(stmt, setup, timer).repeat(repeat, number)
243
244def main(args=None, _wrap_timer=None):
245    """Main program, used when run as a script.
246
247    The optional 'args' argument specifies the command line to be parsed,
248    defaulting to sys.argv[1:].
249
250    The return value is an exit code to be passed to sys.exit(); it
251    may be None to indicate success.
252
253    When an exception happens during timing, a traceback is printed to
254    stderr and the return value is 1.  Exceptions at other times
255    (including the template compilation) are not caught.
256
257    '_wrap_timer' is an internal interface used for unit testing.  If it
258    is not None, it must be a callable that accepts a timer function
259    and returns another timer function (used for unit testing).
260    """
261    if args is None:
262        args = sys.argv[1:]
263    import getopt
264    try:
265        opts, args = getopt.getopt(args, "n:s:r:tcvh",
266                                   ["number=", "setup=", "repeat=",
267                                    "time", "clock", "verbose", "help"])
268    except getopt.error, err:
269        print err
270        print "use -h/--help for command line help"
271        return 2
272    timer = default_timer
273    stmt = "\n".join(args) or "pass"
274    number = 0 # auto-determine
275    setup = []
276    repeat = default_repeat
277    verbose = 0
278    precision = 3
279    for o, a in opts:
280        if o in ("-n", "--number"):
281            number = int(a)
282        if o in ("-s", "--setup"):
283            setup.append(a)
284        if o in ("-r", "--repeat"):
285            repeat = int(a)
286            if repeat <= 0:
287                repeat = 1
288        if o in ("-t", "--time"):
289            timer = time.time
290        if o in ("-c", "--clock"):
291            timer = time.clock
292        if o in ("-v", "--verbose"):
293            if verbose:
294                precision += 1
295            verbose += 1
296        if o in ("-h", "--help"):
297            print __doc__,
298            return 0
299    setup = "\n".join(setup) or "pass"
300    # Include the current directory, so that local imports work (sys.path
301    # contains the directory of this script, rather than the current
302    # directory)
303    import os
304    sys.path.insert(0, os.curdir)
305    if _wrap_timer is not None:
306        timer = _wrap_timer(timer)
307    t = Timer(stmt, setup, timer)
308    if number == 0:
309        # determine number so that 0.2 <= total time < 2.0
310        for i in range(1, 10):
311            number = 10**i
312            try:
313                x = t.timeit(number)
314            except:
315                t.print_exc()
316                return 1
317            if verbose:
318                print "%d loops -> %.*g secs" % (number, precision, x)
319            if x >= 0.2:
320                break
321    try:
322        r = t.repeat(repeat, number)
323    except:
324        t.print_exc()
325        return 1
326    best = min(r)
327    if verbose:
328        print "raw times:", " ".join(["%.*g" % (precision, x) for x in r])
329    print "%d loops," % number,
330    usec = best * 1e6 / number
331    if usec < 1000:
332        print "best of %d: %.*g usec per loop" % (repeat, precision, usec)
333    else:
334        msec = usec / 1000
335        if msec < 1000:
336            print "best of %d: %.*g msec per loop" % (repeat, precision, msec)
337        else:
338            sec = msec / 1000
339            print "best of %d: %.*g sec per loop" % (repeat, precision, sec)
340    return None
341
342if __name__ == "__main__":
343    sys.exit(main())
344