04_Measuring_Performance_and_Analysis
Data Structures & Algorithms
Measuring Runtime Performance
Complexity Notation
• n = input size
• f(n) = max number of steps when input has size n
• O(f(n)) = asymptotic upper bound
1 void f(int *out, const int *in, int size) {
2 int product = 1;
3 for (int i = 0; i < size; ++i)
4 product *= in[i];
5 for(int i = 0; i < size; ++i)
6 out[i] = product / in[i];
7 } // f()
f(n) = 1 + 1 + 1 + 3n + 1 + 1 + 3n = 6n + 5 = O(n)
2
Ways to measure complexity
• Analytically
– Analysis of the code itself
– Recognizing common algorithms/patterns
– Based on a recurrence relation
• Empirically
– Measure runtime programmatically
– Measure runtime using external tools
– Test on inputs of a variety of sizes
3
Measuring Runtime Programmatically
• "Programmatically" – measurements are taken
from inside the code itself
• Varies greatly depending on the language
• Many different ways to do it even just in C/C++!
4
1 #include
2
3 class Timer {
4 std::chrono::time_point
5 std::chrono::duration
6 public:
7 Timer() : cur(), elap(std::chrono::duration
8
9 void start() {
10 cur = std::chrono::system_clock::now();
11 } // start()
12
13 void stop() {
14 elap += std::chrono::system_clock::now() – cur;
15 } // stop()
16
17 void reset() {
18 elap = std::chrono::duration
19 } // reset()
20
21 double seconds() {
22 return elap.count();
23 } // seconds()
24 }; // Timer{}
25 int main() {
26 Timer t;
27 t.start();
28 doStuff1();
29 t.stop();
30 cout << "1: " << t.seconds()
31 << "s" << endl;
32
33 t.reset();
34 t.start();
35 doStuff2();
36 t.stop();
37 cout << "2: " << t.seconds()
38 << "s" << endl;
39 return 0;
40 } // main()
Measuring Time In C++11+
Example
Credit: Amir Kamil
Note: Checking time
too often will slow
down your program!
5
Let's try it!
From a web browser:
goo.gl/gONvC0
(lower g, capital ON, lower v, capital C, zero)
From a terminal:
wget goo.gl/gONvC0 -O search.cpp
6
After Downloading
• If you haven’t already, add this to your
.bash_profile:
module load gcc/6.2.0
• Compile:
g++ -std=c++1z -O3 search.cpp -o search
• Run a binary search, 1M items:
./search b 1000000
• Run a linear search, 1M items:
./search l 1000000
• Try with larger numbers!
7
• Plot actual run time versus varying input sizes
• Include a large range to accurately display trend
• Caveat: for small inputs, asymptotics may not
play out yet
Empirical Results
Algorithm A
looks linear
Algorithm A
no longer
looks linear
8
Prediction versus Experiment
• What if experimental results are worse than predictions?
– Example: results are exponential when analysis is linear
– Error in complexity analysis
– Error in coding (check for extra loops, unintended operations, etc.)
• What if experimental results are better than predictions?
– Example: results are linear when analysis is exponential
– Experiment may not have fit worst case scenario
– Error in complexity analysis
– Error in analytical measurements
– Incomplete algorithm implementation
– Algorithm implemented is better than the one analyzed
• What if experimental data match asymptotic prediction
but runs are too slow?
– Performance bug?
– Check compile options (e.g. use -O3)
– Look for optimizations to improve the constant factors
9
Data Structures & Algorithms
Measuring Runtime Performance
Data Structures & Algorithms
Runtime Analysis Tools
Using a Profiling Tool
• This won't tell you the complexity of an algorithm, but it tells
you where you program spends its time.
• Many different tools exist – you'll learn to use perf in lab.
A snapshot of a perf report generated for EECS 280 Project 2.
Image credit: Alexandra Brown
12
Measuring Runtime on Linux
If you are launching a program using command
% progName –options args
Then
% /usr/bin/time progName –options args
will produce a runtime report
0.84user 0.00system 0:00.85elapsed 99%CPU
If you’re timing a program in the current folder, use ./
% /usr/bin/time ./progName –options args
Often, you can just type time rather than /usr/bin/time.
13
Measuring Runtime on Linux
• Example: this command just wastes time by
copying zeros to the "bit bucket”
% time dd if=/dev/zero of=/dev/null
kill it with control-C
3151764+0 records in
3151764+0 records out
1613703168 bytes (1.6 GB) copied, 0.925958 s, 1.7 GB/s
Command terminated by signal 2
0.26user 0.65system 0:00.92elapsed 99%CPU
(0avgtext+0avgdata 3712maxresident)k
0inputs+0outputs (0major+285minor)pagefaults 0swaps
14
Measuring Runtime on Linux
0.26user 0.65system 0:00.92elapsed 99%CPU
• user time is spent by your program
• system time is spent by the OS on behalf of your
program
• elapsed is wall clock time - time from start to finish of
the call, including any time slices used by other
processes
• %CPU Percentage of the CPU that this job got. This is
just (user + system) / elapsed
• man time for more information
15
Using valgrind
• Suppose we want to check for memory leaks:
valgrind ./search b 1000000
• Force a leak!
– Replace return 0 with exit(0), run valgrind using
flags --leak-check=full --show-leak-kinds=all
• Who leaked that memory?
– The memory address isn’t very useful, we just know
that main() called operator new
– Recompile with -g3 instead of -O3 and run valgrind
one more time
16
Data Structures & Algorithms
Runtime Analysis Tools
Data Structures & Algorithms
Analyzing Recursion
Job Interview Question
• Implement this function
// returns x^n
int power(int x, uint32_t n);
• The obvious solution uses n - 1 multiplications
– 28 = 2*2* ... *2
• Less obvious: O(log n) multiplications
– Hint: 28 = ((22)2)2
– How does it work for 27?
• Write both solutions iteratively and recursively
19
Computing xn
1 int power(int x, uint32_t n) {
2 if (n == 0) {
3 return 1;
4 } // if
5
6 int result = x;
7 for (int i = 1; i < n; ++i) {
8 result = result * x;
9 } // for
10
11 return result;
12 } // power()
20
Analyzing Solutions
Iterative
1 int power(int x, int n) {
2 int result = 1;
3 for (int i = 0; i < n; ++i) {
4 result = result * x;
5 } // for()
6
7 return result;
8 } // power()
Recursive
9 int power(int x, int n) {
10 if (n == 0) {
11 return 1;
12 } // if()
13 return x * power(x, n - 1);
14 } // power()
• Iterative functions use loops
• A function is recursive if it calls itself
• What is the time complexity of each function?
Θ(n)
It's just a regular loop.
???
We need another
tool to analyze this.
21
Recurrence Relations
• A recurrence relation describes the way a problem
depends on a subproblem.
– A recurrence can be written for a computation:
– A recurrence can be written for the time taken:
– A recurrence can be written for the amount of memory used*:
*Non-tail recursive
22
𝑇 𝑛 = $
𝑐!
𝑇 𝑛 − 1 + 𝑐"
𝑛 == 0
𝑛 > 0
𝑥# = $ 1
𝑥 ∗ 𝑥#$”
𝑛 == 0
𝑛 > 0
𝑀 𝑛 = $
𝑐!
𝑀 𝑛 − 1 + 𝑐”
𝑛 == 0
𝑛 > 0
Solving Recurrences
• Substitution method
1. Write out T(n), T(n – 1), T(n – 2)
2. Substitute T(n – 1), T(n – 2) into T(n)
3. Look for a pattern
4. Use a summation formula
• Another way to solve recurrence equations
is the Master Method (AKA Master
Theorem)
• Recursion tree method
23
Solving Recurrences: Linear
1 int power(int x, int n) {
2 if (n == 0)
3 return 1;
4
5 return x * power(x, n – 1);
6 } // power()
24
𝑇 𝑛 = $
𝑐!
𝑇 𝑛 − 1 + 𝑐”
𝑛 == 0
𝑛 > 0
Recurrence: T(n) = T(n – 1) + c
Complexity: Θ(n)
Solving Recurrences: Logarithmic
1 int power(int x, int n) {
2 if (n == 0)
3 return 1;
4
5 int result = power(x, n / 2);
6 result *= result;
7 if (n % 2 != 0) // n is odd
8 result *= x;
9
10 return result;
11 } // power()
25
𝑇 𝑛 = +
𝑐!
𝑇
𝑛
2
+ 𝑐”
𝑛 == 0
𝑛 > 0
Recurrence: T(n) = T(n / 2) + c
Complexity: Θ(log n)
A Logarithmic Recurrence Relation
• Fits the logarithmic recursive implementation of
power()
– The power to be calculated is divided into two halves
and combined with a single multiplication
• Also fits Binary Search
– The search space is cut in half each time, and the
function recurses into only one half
à
26
Θ(log 𝑛)𝑇 𝑛 = +
𝑐!
𝑇
𝑛
2
+ 𝑐”
𝑛 == 0
𝑛 > 0
Recurrence Thought Exercises
• What if a recurrence cuts a problem into two
subproblems, and both subproblems were
recursively processed?
• What if a recurrence cuts a problem into three
subproblems and…
– Processes one piece
– Processes two pieces
– Processes three pieces
• What if there was additional, non-constant work
after the recursion?
27
Binomial Coefficient
• Binomial Coefficient – “n choose k”
• Write this function with pen and paper
• Compile and test what you’ve written
• Options
– Iterative
– Recursive
– Tail recursive
• Analyze
28
𝑛
𝑘 =
𝑛!
𝑘! 𝑛 − 𝑘 !
Data Structures & Algorithms
Analyzing Recursion