ML09: Measuring Running Time in Python & R

Which timer stands out?

Read time: 15 min
Python code on Colab: https://bit.ly/37zaRLj

Time complexity matters in Data Structure. Similarly, execution time matters in implementing any program though we don’t really care about the exactly big O of a program in practice. We start from main concepts and Python implementation to R implementation.

Outline

(1) Two Types of “Time”
1–1 Absolute Time
1–2 Relative Time

(2) Definitions of Major Terms
2–1 Civil Time
2–2 Clock
2–3 Counter
2–4 CPU Time
2–5 Process Time
2–6 Real Time
2–7 System Time
2–8 Wallclock
2–9 Elapsed Time / Elapsed Real Time

(3) Measuring Execution Time in Python
3–1 time.perf_counter() vs. time.process_time()
3–2 A Special Use Case
3–3 Another Tool in Python: timeit()
3–4 %timeit
3–5 Conclusion

(4) Measuring Execution Time in R
4–1 An Use Case
4–2 Sys.time( )
4–3 proc.time( )
4–4 system.time( )
4–5 Conclusion

(5) Conclusion of Timers in Python & R
(6) Execution Environment
(7) References

Figure 1: Funny running scene in Hunter × Hunter. (Source)

(1) Two Types of “Time” [1]

1–1 Absolute Time

Absolute time is the “real-world time”, Returned by time.time() in Python. (i.e. so-called wall clock time in some special contexts.)

It is maintained by the dedicated hardware on most computers, the RTC (real-time clock) circuit is normally battery powered so the system keeps track of real time between power ups. This “real-world time” is also subject to modifications based on your location (time-zones) and season (daylight savings) or expressed as an offset from UTC (also known as GMT or Zulu time).

1–2 Relative Time

Relative time is has no defined relationship to real-world time, in the sense that the relationship is system and implementation specific, returned by time.perf_counter() and time.process_time() in Python.

It can be used only to measure time intervals, i.e. a unit-less value which is proportional to the time elapsed between two instants. This is mainly used to evaluate relative performance (e.g. whether this version of code runs faster than that version of code).

On modern systems, it is measured using a CPU counter which is monotonically increased at a frequency related to CPU’s hardware clock. The counter resolution is highly dependent on the system’s hardware, the value cannot be reliably related to real-world time or even compared between systems in most cases. Furthermore, the counter value is reset every time the CPU is powered up or reset.

(2) Definitions of Major Terms [2]

There are a few tricky terms we have to go through before moving forward.

2–1 Civil Time

Time of day; external to the system. 10:45:13am is a Civil time; 45 seconds is not. Provided by existing function time.localtime() and time.gmtime(). Not changed by this PEP.

2–2 Clock

An instrument for measuring time. Different clocks have different characteristics; for example, a clock with nanosecond <precision> may start to <drift> after a few minutes, while a less precise clock remained accurate for days. This PEP is primarily concerned with clocks which use a unit of seconds.

2–3 Counter

A clock which increments each time a certain event occurs. A counter is strictly monotonic, but not a monotonic clock. It can be used to generate a unique (and ordered) timestamp, but these timestamps cannot be mapped to <civil time>; tick creation may well be bursty, with several advances in the same millisecond followed by several days without any advance.

2–4 CPU Time

According to Wikipedia, CPU time (or process time) is the amount of time for which a central processing unit (CPU) was used for processing instructions of a computer program or operating system, as opposed to elapsed time, which includes for example, waiting for input/output (I/O) operations or entering low-power (idle) mode. The CPU time is measured in clock ticks or seconds. [3]

A measure of how much CPU effort has been spent on a certain task. CPU seconds are often normalized (so that a variable number can occur in the same actual second). CPU seconds can be important when profiling, but they do not map directly to user response time, nor are they directly comparable to (real time) seconds.

2–5 Process Time

Time elapsed since the process began. It is typically measured in <CPU time> rather than <real time>, and typically does not advance while the process is suspended.

2–6 Real Time

Time in the real world. This differs from <Civil time> in that it is not <adjusted>, but they should otherwise advance in lockstep. It is not related to the “real time” of “Real Time [Operating] Systems.” It is sometimes called “wall clock time” to avoid that ambiguity; unfortunately, that introduces different ambiguities.

2–7 System Time

Time as represented by the Operating System.

2–8 Wallclock

What the clock on the wall says. This is typically used as a synonym for <real time>; unfortunately, wall time is itself ambiguous.

2–9 Elapsed Time / Elapsed Real Time

In contrast, elapsed real time (or simply real time, or wall-clock time) is the time taken from the start of a computer program until the end as measured by an ordinary clock. Elapsed real time includes I/O time, any multitasking delays, and all other types of waits incurred by the program. [3][4]

(3) Measuring Execution Time in Python

3–1 time.perf_counter() VS. time.process_time()

time.perf_counter() → float value of time in seconds

Return the value (in fractional seconds) of a performance counter, i.e. a clock with the highest available resolution to measure a short duration. It does include time elapsed during sleep and is system-wide. The references point of the returned value is undefined, so that only the difference between the results of consecutive calls is valid. [5]

In short, time.perf_counter() returns the "absolute value of the counter" (note that it’s not “absolute value”). [1]

time.process_time() → float value of time in seconds

Return the value (in fractional seconds) of the sum of the system and user CPU time of the current process. It does not include time elapsed during sleep. It is process-wide by definition. [5]

In short,time.process_time() is a value which is derived from the CPU counter but updated only when a given process is running on the CPU and can be broken down into 'user time', which is the time when the process itself is running on the CPU, and 'system time', which is the time when the operating system kernel is running on the CPU on behalf on the process. [1]

import time as t
import numpy as np
t1 = t.process_time()
start = t.perf_counter()
for i in np.arange(0, 10**8, 1, dtype=np.int64):
    k = i * i
t2 = t.process_time()
end = t.perf_counter()
spend_1 = t2 - t1
spend_2 = end - start
print(" time.process_time(): {}".format(spend_1))
print(" time.perf_counter(): {}".format(spend_2))

Figure 2: Outcome of the 10**8 use case (left: My HP laptop) (right: Google Colab)

Run the use case above. It takes 35s~36s on my HP laptop, and it takes 26s~27s on Google Colab.

HP laptop: time.process_time() = 35.58 > 35.56 = time.perf_counter()
Colab: time.process_time() = 26.59 < 26.64 = time.perf_counter()

Figure 3: Outcome of the 10**8.5 use case (left: My HP laptop) (right: Google Colab)

Then, let’s revise the “10**8” to “10**8.5” and run the use case below. It takes 112s~113s on my HP laptop, and it takes s~s on Google Colab.

HP laptop: time.process_time() = 112.13 < 112.23 = time.perf_counter()
Colab: time.process_time() = 87.98 < 88.42 = time.perf_counter()

3–2 A Special Use Case

However, there’s somebody on GitHub found the results of time.perf_counter and time.process_time totally different. [6] The code is as follows:

from time import time, perf_counter, process_time, sleep
from datetime import datetime

def foo(n=100_000):
    z = 0
    for i in range(n):
        z+=(i%2)**2
    sleep(1.0)
    return z

for f in [time, perf_counter, process_time, datetime.now]:
    a = f()
    foo()
    b = f()
    diff = b-a
    if f==datetime.now:
        diff = diff.seconds + diff.microseconds/10**6
    print(f"{f.__name__}: {diff:.4f}")

Figure 4: Outcome on Google Colab

Before concluding which time measuring tool is better, let’s stay patient and inspect another variant tool — timeit().

3–3 Another Tool in Python: timeit()

This module provides a simple way to time small bits of Python code. It has both a Command-Line Interface as well as a callable one. It avoids a number of common traps for measuring execution times. [7]

timeit.default_timer() : The default timer, which is always time.perf_counter() .

Changed in version 3.3: time.perf_counter() is now the default timer. [7]

So, it’s actually not a new tool, it’s just a faster and convenient way to implement time.perf_counter() .

Let’s run the following snippet [8]:

def f1():
    for n in range(100):
        pass
def f2():
    n=0
    while n<100:
        n+=1
if __name__ == "__main__":
    import timeit    
    print ("Execution Time of f1 = {}".format(timeit.timeit(f1, number=100000)))
    print ("Execution Time time of f2 = {}".format(timeit.timeit(f2, number=100000)))
    %timeit f1()
    %timeit f2()

Figure 5: Outcome on Google Colab

For running more complicated code by timeit():

import timeit
code='''
def squaring(): 
    myList=[] 
    for x in range(50): 
        myList.append(sqrt(x))'''
print("Time = {}".format(timeit.timeit(stmt=code,setup="from math import sqrt",number=10000)))

Figure 6: Outcome on Google Colab

3–4 %timeit

%timeit is an Ipython magic function, which can be used to time a particular piece of code (A single execution statement, or a single method). [9]

%timeit for _ in range(1000): True

Figure 7: Outcome on Google Colab

We see how %timeit simplified our work.

import torch
import timeit
## The tensors are on CPU
a = torch.rand(100, 100)
b = torch.rand(100, 100)
%timeit a.matmul(b)
print('\n')
%timeit a.matmul(b)

Here’s what we get:

The slowest run took 86.59 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 96 µs per loop

3–5 Conclusion

We sum up what we have at hand now:

• time.perf_counter and time.process_time measure relative time. time.time() measures absolute time / real-world time.
• time.perf_counter and time.process_time all may be greater than the other one.
• A special use case shows time.perf_counter and time.process_time could be far different.
• The default timer of timeit.timeit() is time.perf_counter .

In conclusion, when it comes to comparing the Execution Time of a variety of programs on a specific machine, do not adopt absolute time / real-world time methods like time.time(). As for relative time manners time.perf_counter and time.process_time , time.perf_counter seems to be more appropriate!

(4) Measuring Execution Time in R

4–1 An Use Case

arr = 0:10^6.5
t1 <- Sys.time()
for(i in 1:1000) arr2 = arr * 2
t2 <- Sys.time()
t = t2- t1 ; t
p1 <- proc.time()
for(i in 1:1000) arr2 = arr * 2
p2 <- proc.time()
p = p2- p1 ; p
system.time(for(i in 1:1000) arr2 = arr * 2)
system.time(for(i in 1:1000) arr2 = arr * 2)

Figure 9: Timers in R

We see that elapsed ≈ user + system.

4–2 Sys.time( )

Sys.time returns an absolute date-time value which can be converted to various time zones and may return different days. Sys.time returns an object of class "POSIXct". [10]

4–3 proc.time( )

proc.time returns five elements for backwards compatibility, but its print method prints a named vector of length 3. The first two entries are the total user time and system CPU times of the current R process and any child processes on which it has waited, and the third entry is the ‘real’ elapsed time since the process was started. [11]

“User CPU time” gives the CPU time spent by the current process (i.e., the current R session) and “system CPU time” gives the CPU time spent by the kernel (the operating system) on behalf of the current process. The operating system is used for things like opening files, doing input or output, starting other processes, and looking at the system clock: operations that involve resources that many processes must share. [12]

4–4 system.time( )

system.time calls the function proc.time, evaluates expr, and then calls proc.time once more, returning the difference between the two proc.time calls. [13]

4–5 Conclusion

So in R,

1. Absolute time => Sys.time( )
2. Relative time => proc.time( ), system.time( )

<Remark>
1. system.time( ) calls proc.time( )
2. In proc.time( ), we may choose “elapsed” or “user” to measure execution time depends upon different situations.

(5) Conclusion of Timers in Python & R

We conclude that for all timers in Python (like time.time()) and R (like Sys.time( )),

1. Absolute time => Sys.time( ), time.time()
2. Relative time => proc.time( ), system.time( ), time.perf_counter(), time.process_time() , timeit.timeit()
3. Relative time methods are recommended! Additionally, time.perf_counter() is probably better than time.process_time() due to the special use case we find and the fact that timeit.timeit() choose time.perf_counter() as default timer.
4. Use timeit.timeit() and %timeit (for Ipython) to simplified the timing work!

<Remark>
1. system.time( ) calls proc.time( ), whereas timeit.timeit() calls time.perf_counter().
2. In proc.time( ), we may choose “elapsed” or “user” to measure execution time depends upon different situations.
3. proc.time( ) calculate both “user CPU time” & “system CPU time” while time.perf_counter() & time.process_time() all seems to aggregate “user CPU time” & “system CPU time” together.

(6) Execution Environment

My HP laptop

1. Operating System : Microsoft Windows 10 (x64)

2. CPU : Intel i5–8250U

3. RAM : 24 GB

4. Programming language : Python 3.8.5

5. IDE : Spyder

(7) References

[1] isedev (2014). Understanding time.perf_counter( ) and time.process_time( ). Retrieved from

Understanding time.perf_counter() and time.process_time()

[2] python.org (unidentified). PEP 418 — Add monotonic time, performance counter, and process time functions. Retrieved from

PEP 418 -- Add monotonic time, performance counter, and process time functions

[3] Wikipedia (Unidentified). CPU time. Retrieved from
https://en.wikipedia.org/wiki/CPU_time

[4] Wikipedia (Unidentified). Elapsed real time. Retrieved from
https://en.wikipedia.org/wiki/Elapsed_real_time

[5] python.org (unidentified). time — Time access and conversions. Retrieved from

time - Time access and conversions - Python 3.9.1rc1 documentation

[6] Shihab-Shahriar (2020). Time computation in benchmarks: process_time( ) vs time( ), perf_counter( ), datetime.now( ). Retrieved from

Time computation in benchmarks: process_time() vs time(), perf_counter(), datetime.now() · Issue…

[7] python.org (unidentified). timeit — Measure execution time of small code snippets. Retrieved from

timeit - Measure execution time of small code snippets - Python 3.9.1rc1 documentation

[8] Yegulalp, S. (2020). How to use timeit to profile Python code. Retrieved from

How to use timeit to profile Python code

[9] mu 無 (2015). What is %timeit in python? Retrived from

What is %timeit in python?

[10] RDocumentation (Unidentified). system.time. Retrieved from

system.time

[11] RDocumentation (Unidentified). proc.time. Retrieved from

proc.time

[12] daroczig (2014). What are ‘user’ and ‘system’ times measuring in R system.time(exp) output? Retrieved from

What are 'user' and 'system' times measuring in R system.time(exp) output?

[13] daroczig (2014). system.time. Retrieved from

system.time