Harsh Reality 15 213 There s more to performance than asymptotic complexity The course that gives CMU its Zip Code Optimization Sept 25 2003 Constant factors matter too Easily see 10 1 performance range depending on how code is written Must optimize at multiple levels Topics algorithm data representations procedures and loops Machine Independent Optimizations Machine Dependent Optimizations Code Profiling 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 F 03 2 class10 ppt Limitations of Optimizing Compilers Machine Independent Optimizations 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 Optimizations that you or compiler should do regardless of processor compiler Code Motion Reduce frequency with which computation performed e g Data ranges may be more limited than variable types suggest If it will always produce same result Especially moving code out of loop Most analysis is performed only within procedures Whole program analysis is too expensive in most cases Most analysis is based only on static information for i 0 i n i for j 0 j n j a n i j b j Compiler has difficulty anticipating run time inputs for i int ni for j a ni 0 i n i n i 0 j n j j b j When in doubt the compiler must be conservative 3 15 213 F 03 4 15 213 F 03 Reduction in Strength Compiler Generated Code Motion Most compilers do a good job with array code simple loop structures Code Generated by GCC for 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 Replace costly operation with simpler one Shift add instead of multiply or divide 0 i n i n i a ni 0 j n j b j 16 x x 4 Utility machine dependent Depends on cost of multiply or divide instruction On Pentium II or III integer multiply only requires 4 CPU cycles Recognize sequence of products 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 i n a p a i n scaled by 4 b b j p p j loop for i 0 i n i for j 0 j n j a n i j b j scaled by 4 b j scaled by 4 int ni 0 for i 0 i n i for j 0 j n j a ni j b j ni n if j n 15 213 F 03 5 Share Common Subexpressions Reuse portions of expressions Compilers often not very sophisticated in exploiting arithmetic properties 15 213 F 03 6 Time Scales Absolute Time Typically use nanoseconds 10 9 seconds Time scale of computer instructions 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 3 multiplications 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 int inj i n up val inj down val inj left val inj right val inj sum up down j n n 1 1 left right Clock Cycles Most computers controlled by high frequency clock signal Typical Range 100 MHz 108 cycles per second Clock period 10ns 2 GHz 2 X 109 cycles per second Clock period 0 5ns 1 multiplication i n i 1 i 1 n i 1 i 1 n i n Fish machines 550 MHz 1 8 ns clock period 7 15 213 F 03 8 15 213 F 03 Cycles Per Element Vector Abstract Data Type ADT Convenient way to express performance of program that operators on vectors or lists Length n T CPE n Overhead length data 0 1 2 length 1 Procedures 1000 vec ptr new vec int len 900 800 Create vector of specified length int get vec element vec ptr v int index int dest Retrieve vector element store at dest Return 0 if out of bounds 1 if successful vsum1 Slope 4 0 700 Cycles 600 500 vsum2 Slope 3 5 400 int get vec start vec ptr v Return pointer to start of vector data 300 200 Similar to array implementations in Pascal ML Java 100 E g always do bounds checking 0 0 50 100 150 200 Elements 15 213 F 03 9 Optimization Example 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 val dest val i if i vec length v goto loop done Procedure Compute sum of all elements of integer vector Store result at destination location Vector data structure and operations defined via abstract data type Inefficiency Procedure vec length called every iteration Even though result always the same Pentium II III Performance Clock Cycles Element 11 42 06 Compiled g 31 25 Compiled O2 15 213 F 03 10 15 213 F 03 12 15 213 F 03 Move vec length Call Out of Loop Optimization Blocker Procedure Calls Why couldn t compiler move vec vec len out of inner loop void combine2 vec ptr v int dest int i int length vec length v dest 0 for i 0 i length i int val get vec element v i val dest val Procedure may have side effects Alters global state each time called Function may not return same value for given arguments Depends on other parts of global state Procedure lower could interact with strlen Why doesn t compiler look at code for vec vec len len Interprocedural optimization is not used extensively due to cost Optimization Move call to vec length out of inner loop Warning Value does not change from one iteration to next Code motion Compiler treats procedure call as a black box Weak optimizations in and around them CPE 20 66 Compiled O2 vec length requires only constant time but significant overhead 15 213 F 03 13 Reduction in Strength 15 213 F 03 14 Eliminate Unneeded Memory Refs void combine3 vec ptr v int dest int i int length vec length v int data get vec start v dest 0 for i 0 i length i dest data i void combine4 vec ptr v int dest int i int length vec length v int data get vec start v int sum 0 for i 0 i length i sum data i …
View Full Document
Unlocking...