15-213
“The course that gives CMU its
Zip!”
Code Optimization
Sept. 25, 2003
Topics
■ Machine-Independent Optimizations
■ Machine Dependent Optimizations
■ Code Profiling
class10.ppt
, Harsh Reality
There’s more to performance than asymptotic complexity
Constant factors matter too!
■ Easily see 10:1 performance range depending on how code is
written
■ Must optimize at multiple levels:
● algorithm, data representations, procedures, and loops
Must understand system to optimize performance
■ How programs are compiled and executed
■ How to measure program performance and identify bottlenecks
■ How to improve performance without destroying code
modularity and generality
15-213,
–2– F’03
,Limitations of Optimizing Compilers
Operate under fundamental constraint
■ Must not cause any change in program behavior under any possible
condition
■ Often prevents it from making optimizations when would only affect
behavior under pathological conditions.
Behavior that may be obvious to the programmer can be
obfuscated by languages and coding styles
■ e.g., Data ranges may be more limited than variable types suggest
Most analysis is performed only within procedures
■ Whole-program analysis is too expensive in most cases
Most analysis is based only on static information
■ Compiler has difficulty anticipating run-time inputs
When in doubt, the compiler must be conservative
15-213,
–3– F’03
, Machine-Independent
Optimizations
Optimizations that you or compiler should do
regardless of processor / compiler
Code Motion
■ Reduce frequency with which computation performed
● If it will always produce same result
● Especially moving code out of loop
for (i = 0; i < n; i++) {
for (i = 0; i < n; i++) int ni = n*i;
for (j = 0; j < n; j++) for (j = 0; j < n; j++)
a[n*i + j] = b[j]; a[ni + j] = b[j];
}
15-213,
–4– F’03
“The course that gives CMU its
Zip!”
Code Optimization
Sept. 25, 2003
Topics
■ Machine-Independent Optimizations
■ Machine Dependent Optimizations
■ Code Profiling
class10.ppt
, Harsh Reality
There’s more to performance than asymptotic complexity
Constant factors matter too!
■ Easily see 10:1 performance range depending on how code is
written
■ Must optimize at multiple levels:
● algorithm, data representations, procedures, and loops
Must understand system to optimize performance
■ How programs are compiled and executed
■ How to measure program performance and identify bottlenecks
■ How to improve performance without destroying code
modularity and generality
15-213,
–2– F’03
,Limitations of Optimizing Compilers
Operate under fundamental constraint
■ Must not cause any change in program behavior under any possible
condition
■ Often prevents it from making optimizations when would only affect
behavior under pathological conditions.
Behavior that may be obvious to the programmer can be
obfuscated by languages and coding styles
■ e.g., Data ranges may be more limited than variable types suggest
Most analysis is performed only within procedures
■ Whole-program analysis is too expensive in most cases
Most analysis is based only on static information
■ Compiler has difficulty anticipating run-time inputs
When in doubt, the compiler must be conservative
15-213,
–3– F’03
, Machine-Independent
Optimizations
Optimizations that you or compiler should do
regardless of processor / compiler
Code Motion
■ Reduce frequency with which computation performed
● If it will always produce same result
● Especially moving code out of loop
for (i = 0; i < n; i++) {
for (i = 0; i < n; i++) int ni = n*i;
for (j = 0; j < n; j++) for (j = 0; j < n; j++)
a[n*i + j] = b[j]; a[ni + j] = b[j];
}
15-213,
–4– F’03
