15 213 Great Reality 4 There s more to performance than asymptotic complexity Code Optimization September 27 2001 Constant factors matter too Topics Machine Independent Optimizations Code motion Reduction in strength Common subexpression sharing Tuning Identifying performance bottlenecks class10 ppt 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 class10 ppt Optimizing Compilers Provide efficient mapping of program to machine register allocation code selection and ordering eliminating minor inefficiencies Don t usually improve asymptotic efficiency up to programmer to select best overall algorithm big O savings are often more important than constant factors but constant factors also matter Have difficulty overcoming optimization blockers potential memory aliasing potential procedure side effects 2 CS 213 F 01 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 e g using an int in C for what could be an enumerated type 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 class10 ppt 3 CS 213 F 01 class10 ppt 4 CS 213 F 01 Machine Independent Optimizations Optimizations you 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 j 0 j n j a n i j b j class10 ppt for i int ni for j a ni 5 0 i n i n i 0 j n j j b j CS 213 F 01 Compiler Generated Code Motion Most compilers do a good job with array code simple loop structures Code Generated by GCC 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 class10 ppt Reduction in Strength Replace costly operation with simpler one Shift add instead of multiply or divide 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 0 i n i n i a ni 0 j n j b j i n a p a i n scaled by 4 b b j p p j loop 6 scaled by 4 b j scaled by 4 if j n CS 213 F 01 Make Use of Registers Reading and writing registers much faster than reading writing memory Limitation Compiler not always able to determine whether variable can be held in register Possibility of Aliasing See example later int ni 0 for i 0 i n i for j 0 j n j a ni j b j ni n for i 0 i n i for j 0 j n j a n i j b j class10 ppt 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 7 CS 213 F 01 class10 ppt 8 CS 213 F 01 Machine Independent Opts Cont Vector ADT 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 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 class10 ppt j n n 1 1 left right 1 multiplication i n i 1 i 1 n i 1 i 1 n i n 9 CS 213 F 01 length data Procedure Compute sum of all elements of vector Store result at destination location class10 ppt 11 CS 213 F 01 length 1 Procedures vec ptr new vec int len 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 int get vec start vec ptr v Return pointer to start of vector data Similar to array implementations in Pascal ML Java E g always do bounds checking class10 ppt 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 0 1 2 10 CS 213 F 01 Time Scales Absolute Time Typically use nanoseconds 10 9 seconds Time scale of computer instructions 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 Fish machines 550 MHz 1 8 ns clock period class10 ppt 12 CS 213 F 01 Cycles Per Element Optimization Example Convenient way to express performance of program that operators on vectors or lists Length n T CPE n Overhead 1000 900 800 vsum1 Slope 4 0 Cycles 700 600 500 Procedure vsum2 Slope 3 5 400 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 Compute sum of all elements of integer vector Store result at destination location Vector data structure and operations defined via abstract data type 300 200 100 Pentium II III Performance Clock Cycles Element 0 0 50 100 150 200 42 06 Compiled g 31 25 Compiled O2 Elements class10 ppt 13 CS 213 F 01 Understanding Loop void combine1 goto vec ptr v int dest int i 0 int val dest 0 if i vec length v goto done loop get vec element v i val dest val 1 iteration i if i vec length v goto loop done Inefficiency Procedure vec length called every iteration Even though result always the same class10 ppt 15 CS 213 F 01 class10 ppt 14 CS 213 F 01 Move vec length Call Out of 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 Optimization Move call to vec length out of inner loop Value …
View Full Document
Unlocking...