Python: counting how many times a given line is executed

Question

Problem

For pedagogical purposes, I would like to count how many times a given line is executed in a given function without modifying or decorating it. For instance, for the function:

def binary_search(seq, x):
    (a, b) = (0, len(seq) - 1)
    while a <= b:
        m = (a + b) / 2
        if x < seq[m]:
            b = m - 1
        elif x > seq[m]:
            a = m + 1
        else:
            return m

I would just write something like this:

print count_exec(binary_search, range(100), 44, line_number = 4) 

... or even like that:

print count_exec(binary_search(range(100), 44), line = "m = (a + b) / 2")

... which both should print the number of times the 4th line is executed (which is 7). The ultimate goal is to provide an empirical approach to the complexity of any function:

Non solutions

My current solution consists in adding a function attribute:

def binary_search(seq, x):
    binary_search.count = 0 # <------------------ added
    (a, b) = (0, len(seq) - 1)
    while a <= b:
        binary_search.count += 1 # <------------- added
        m = (a + b) / 2
        if x < seq[m]:
            b = m - 1
        elif x > seq[m]:
            a = m + 1
        else:
            return m

binary_search(range(100), 44)
print binary_search.count

I guess I could create a decorated function count_this_line:

def binary_search(seq, x):
    (a, b) = (0, len(seq) - 1)
    while a <= b:
        count_this_line() # <-------------------- added
        m = (a + b) / 2
        ...

May be it is possible to decorate the function binary_search itself, but for me this counts as modifying it.

Ideas

• The standard library ast can retrieve the abstract syntax tree of any given script, and even execute it.
• I have little experience in using a Python profiler. It seems quite heavy handed for my needs. Could it be the way to go?

Answer 1

You can use the line_profiler module to do this (see docs). Note that I had to get a 3.x compatible version from a forked repo - not sure if it's merged yet.

For example. I put your binary search function in a file and then added this:

prof = profile(binary_search)
prof(range(100), 44)

This is the same thing as a @profile decorator as mentioned in the docs, but you don't have to modify the original code. I ran

kernprof.py -l binsearch.py
python -m line_profiler binsearch.py.lprof

And out popped this:

Function: binary_search at line 1
Total time: 4.1e-05 s

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     1                                           def binary_search(seq, x):
     2         1            6      6.0     14.6      (a, b) = (0, len(seq) - 1)
     3         7            8      1.1     19.5      while a <= b:
     4         7            7      1.0     17.1          m = (a + b) // 2
     5         7            8      1.1     19.5          if x < seq[m]:
     6         2            2      1.0      4.9              b = m - 1
     7         5            5      1.0     12.2          elif x > seq[m]:
     8         4            4      1.0      9.8              a = m + 1
     9                                                   else:
    10         1            1      1.0      2.4              return m

"Hits" is the number you're looking for. As a bonus you get timing information too, though that would be more accurate with many executions.

Answer 2

Following the suggestion of Jason, I have written a pure Python solution:

import line_profiler
import __builtin__
import cStringIO
import re

def profile(path, function_call, line_number):
    prof = line_profiler.LineProfiler()
    __builtin__.__dict__['profile'] = prof
    script = open(path).read()
    ns = locals()
    function_name = function_call[:function_call.index("(")]
    rex = re.compile("((?ms)^def %s.+)" % function_name)
    script = rex.sub(r"@profile\n\1\n%s" % function_call, script)
    exec(script, ns, ns)
    stream = cStringIO.StringIO()
    prof.print_stats(stream)
    s = stream.getvalue()
    stream.close()
    return int(re.search(r"(?m)^\s*%s\s*(\S*)" % (line_number+1), s).group(1))

if __name__ == "__main__":
    print profile("binary_search.py", "binary_search(range(100), 44)", 3)

It reads the source of the script containing the function to profile, decorates this one, appends the desired call to the end, executes it, dumps the stats into a string, extracts the number of hits at the given line number, and returns it as an int. It works as required, but with an important performance penalty.

Perhaps a better solution would consist in dropping the profiler, but keeping the idea of decorating and executing the source code on the fly. I'll edit my answer if I implant it.

Anyway, thank you Jason for having provided me a way out!