CMPSC 311 – Introduction to Systems Programming
Introduction to Profiling
Suman Saha
(Slides are mostly by Professors Patrick McDaniel and )
Copyright By PowCoder代写 加微信 powcoder
CMPSC 311 – Introduction to Systems Programming
Program Performance
• Programs run only as well as the code you write
• Poor code often runs poorly
• Crashes or generates incorrect output (bugs) • Is laggy, jittery or slow (inefficient code)
• Too slow on real inputs (data processing)
• Not-reactive enough to be usable (interfaces)
CMPSC 311 – Introduction to Systems Programming
Optimization
• Optimization is the process where you take an existing program and alter it to remove inefficiencies.
• Change algorithms
• Restructure code
• Redesign data structures • Refactor code
Career Notes:
1. Learning to optimize your code is essential to becoming a professional programmer.
2. Optimizing code is a phase of development you don’t experience in school.
3. You will spend a good deal of your professional life optimizing existing code
without changing its function.
CMPSC 311 – Introduction to Systems Programming
Don’t optimize prematurely
• The first rule of optimization is: • Don’t do it.
• The second rule of optimization (for experts only): • Don’t do it yet. Measure twice, optimize once.
• It is far, far easier to make a correct program fast than it is to make a fast program correct
CMPSC 311 – Introduction to Systems Programming
Premature optimization is the root of all…
• “Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil (quoting ). Yet we should not pass up our opportunities in that critical 3%.”
CMPSC 311 – Introduction to Systems Programming
Example Inefficient Code
uint64_t prod_one(uint64_t a, uint64_t b) { uint64_t out = 0; for(uint64_ti=0;i
prod_one [1] prod_two [3]
0.00 0.00 1/1
[3] 0.0 0.00 0.00 1 prod_two [3]
———————————————–
0.00 0.00 1/1 ———————————————–
CMPSC 311 – Introduction to Systems Programming
Optimization revisited …
• When optimizing, you focus on modules
of the program which implement the features and processing of the program.
• Which parts of the program you select depends on what parts are running the most.
• then, focus on those parts which take up the most time.
• Profiling tells us where to spend our time.
Module E, 5
Module D, 10
Module C, 20
Module B, 20
Module A, 45
CMPSC 311 – Introduction to Systems Programming
Amdahl’s Law
• Amdahl’s law models the maximum performance gain that can be expected by improving part of the system, i.e., what can we expect in terms of improvement.
• Consider
• k is the percentage of total execution time spent in the optimized module(s).
• s is the execution time expressed in terms of a n-factor speedup (2X, 3X…), which can be found as
s = original execution time improved execution time
CMPSC 311 – Introduction to Systems Programming
Amdahl’s Law (cont.)
• The overall speedup T of the program is expressed : T=1
• Intuition:
• 1 k is the part of the program that unchanged
• ks is the ratio of altered program size to speedup
( 1 k ) + ks
CMPSC 311 – Introduction to Systems Programming
Amdahl’s Law (example)
• Assume that a module A of a program is optimized.
• A represents 45% of the run time of the program.
• The optimization reduces the runtime of module from 750ms to 50ms.
• What is the program speedup?
CMPSC 311 – Introduction to Systems Programming
Amdahl’s Law (example)
• Assume that a module A of a program is optimized.
• A represents 45% of the run time of the program.
• The optimization reduces the runtime of module from
750ms to 50ms.
s = 750/50 = 15
T= 1.45=1 =1.724 (1 .45)+ 15 .55+.03
• What is the program speedup? (A: 1.724X)
CMPSC 311 – Introduction to Systems Programming
A more complex example
CMPSC 311 – Introduction to Systems Programming
A even more complex example:
• Assume another system: we have 4 modules each being measured before and after optimization
Before Optimization (usec)
Optimization (usec)
• Now suppose that the runtime of the original execution is 2000 usec, what is the speedup?
( 1 k ) + ks
CMPSC 311 – Introduction to Systems Programming
What is going on?
#include
#define SIZE 35000
int main(void) {
uint64_t **a = malloc(SIZE * sizeof(uint64_t *)); for (int i = 0; i < SIZE; ++i)
a[i] = malloc(SIZE * sizeof(uint64_t));
uint64_t sum = 0;
for (int i = 0; i < SIZE; ++i)
for (int j = 0; j < SIZE; ++j) sum += a[i][j];
printf("sum is %ld\n", sum);
return 0; }}
$ gcc –Wall –O2 c.c –o c $ time ./c
real 0m1.560s
user 0m1.060s sys 0m0.500s
#include
#define SIZE 35000
int main(void) {
uint64_t **a = malloc(SIZE * sizeof(uint64_t *)); for (int i = 0; i < SIZE; ++i)
a[i] = malloc(SIZE * sizeof(uint64_t));
uint64_t sum = 0;
for (int i = 0; i < SIZE; ++i)
for (int j = 0; j < SIZE; ++j) sum += a[j][i];
printf("sum is %ld\n", sum); return 0;
$ gcc -Wall -O2 c.c -o c $ time ./c
real 0m14.543s user 0m13.597s sys 0m0.948s
CMPSC 311 - Introduction to Systems Programming
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com