Great Reality 4 15 213 There s more to performance than asymptotic complexity The course that gives CMU its Zip Code Optimization I Machine Independent Optimizations Feb 11 2003 motion z Strength Reduction Induction Var Elim z Common subexpression sharing Tuning z Identifying Easily see 10 1 performance range depending on how code is written Must optimize at multiple levels data representations procedures and loops Must understand system to optimize performance Machine Independent Optimizations z Code z algorithm Topics Constant factors matter too performance bottlenecks class10 ppt 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 S 03 2 Optimizing Compilers Limitations of Optimizing Compilers Provide efficient mapping of program to machine Operate under fundamental constraint register allocation 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 code selection and ordering eliminating minor inefficiencies The Bottom Line Behavior that may be obvious to the programmer can beWhen obfuscated by do languages in doubt nothingand coding styles i e ranges The compiler must be conservative e g data may be narrower than var types suggest Don t usually improve asymptotic efficiency up to programmer to select best overall algorithm big O savings are often more important than constant factors z but Most analysis is performed only within procedures constant factors also matter Have difficulty overcoming optimization blockers Most analysis is based only on static information potential memory aliasing potential procedure side effects 3 whole program analysis is too expensive in most cases 15 213 S 03 4 Page 1 compiler has difficulty anticipating run time inputs 15 213 S 03 Compiler Generated Code Motion Machine Independent Optimizations Optimizations that should be done regardless of processor compiler Code Generated by GCC Code Motion Most compilers do a good job with array code simple loop structures for i 0 i n i int ni int p for j p for i 0 i n i for j 0 j n j a n i j b j Reduce frequency with which computation performed it will always produce same result z Especially moving code out of loop for i 0 i n i for j 0 j n j a n i j b j for i int ni for j a ni 0 i n i n i 0 j n j j b j 15 213 S 03 5 Replace costly operation with simpler one Shift add instead of multiply or divide 7 As int ni 0 for i 0 i n i for j 0 j n j a ni j b j ni n a result of Induction Variable Elimination b b j p p j loop scaled by 4 b j scaled by 4 if j n 15 213 S 03 Reading and writing registers much faster than reading writing memory Limitation Recognize sequence of products induction var analysis for i 0 i n i for j 0 j n j a n i j b j Make Use of Registers 16 x x 4 z Utility machine dependent z Depends on cost of multiply or divide instruction z On Pentium II or III integer multiply only requires 4 CPU cycles i n a p a i n scaled by 4 6 Strength Reduction n i a ni 0 j n j b j z If imull ebx eax movl 8 ebp edi leal edi eax 4 edx Inner Loop L40 movl 12 ebp edi movl edi ecx 4 eax movl eax edx addl 4 edx incl ecx jl L40 15 213 S 03 8 Page 2 Limited number of registers Compiler cannot always determine whether variable can be held in register Possibility of Aliasing See example later 15 213 S 03 Measuring Performance Time Scales Machine Independent Opts Cont Absolute Time Share Common Subexpressions Reuse portions of expressions Compilers often not very sophisticated in exploiting arithmetic properties Sum neighbors of i j up val i 1 n j down val i 1 n j left val i n j 1 right val i n j 1 sum up down left right int inj i n up val inj down val inj left val inj right val inj sum up down 3 multiplies i n i 1 n i 1 n leal 1 edx ecx imull ebx ecx leal 1 edx eax imull ebx eax imull ebx edx z 10 9 j n n 1 1 left right Most computers controlled by high frequency clock signal Typical Range z 100 MHz 108 cycles per second Clock period 10ns AKA Common Subexpression Elimination CSE 9 15 213 S 03 Especially true of programs that work on lists vectors Total time fixed overhead CPE length of list 15 213 S 03 Convenient way to express performance of a program that operates on vectors or lists Length n T CPE n Overhead Cycles for i 0 i n i 2 c i a i b i c i 1 a i 1 b i 1 vsum2 only works on even n vsum2 is an example of loop unrolling 11 Fish machines 550 MHz 1 8 ns clock period void vsum2 int n int i 2 GHz 2 X 109 cycles per second Clock period 0 5ns Cycles Per Element For many programs cycles per element CPE for i 0 i n i c i a i b i z 10 Measuring Performance void vsum1 int n int i seconds Time scale of computer instructions Clock Cycles 1 multiply i n i 1 i 1 n i 1 i 1 n i n Typically use nanoseconds 1000 900 800 700 600 500 400 300 200 100 0 vsum1 Slope 4 0 vsum2 Slope 3 5 0 15 213 S 03 12 Page 3 50 100 150 Number of Elements 200 15 213 S 03 Vector ADT length data 0 1 2 Optimization Example void combine1 vec ptr v int dest int i dest 0 for i 0 i vec length v i int val get vec element v i val dest val length 1 Procedures vec ptr new vec int len z Create vector of specified length int get vec element vec ptr v int index int dest z Retrieve vector element store at dest z Return 0 if out of bounds 1 if successful Procedure int get vec start vec ptr v z Return pointer to start of vector data int vec length v vec ptr v z Return length of vector Compute sum of all elements of vector Store result at destination location Similar to array implementations in Pascal ML Java 13 z E g always do bounds checking 15 213 S 03 Optimization Example Procedure Understanding Loop void combine1 vec ptr v int dest int i dest 0 for i 0 i vec length v i int val get vec element v i val dest val void combine1 goto vec ptr v int dest int i 0 int val dest 0 if i vec length v goto done 1 iteration loop get vec element v i …
View Full Document
Unlocking...