15 213 Great Reality 4 There s more to performance than asymptotic complexity Code Optimization October 3 2000 Constant factors matter too Topics Machine Independent Optimizations Code motion Reduction in strength Common subexpression sharing Machine Dependent Optimizations Pointer code Unrolling Enabling instruction level parallelism Advice class11 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 class11 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 00 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 class11 ppt 3 CS 213 F 00 class11 ppt 4 CS 213 F 00 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 int ni for j a ni for i 0 i n i for j 0 j n j a n i j b j 0 i n i n i 0 j n j j b j Machine Independent Opts Cont Reductions 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 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 Keep data in registers rather than memory Compilers have trouble making this optimization class11 ppt 5 CS 213 F 00 class11 ppt Machine Independent Opts Cont Share Common Subexpressions 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 class11 ppt j n n 1 1 left right Important Tools Accurately compute time taken by code Most modern machines have built in cycle counters Profile procedure calling frequencies Unix tool gprof Custom built tools E g L4 cache simulator Observation Generating assembly code Lets you see what optimizations compiler can make Understand capabilities limitations of particular compiler 1 multiplication i n 7 CS 213 F 00 Measurement 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 6 CS 213 F 00 class11 ppt 8 CS 213 F 00 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 Procedure Compute sum of all elements of integer vector Store result at destination location Vector data structure and operations defined via abstract data type Pentium II III Performance Clock Cycles Element 40 3 Compiled g class11 ppt 28 6 Compiled O2 9 CS 213 F 00 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 class11 ppt 11 CS 213 F 00 Vector ADT length data 0 1 2 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 class11 ppt 10 CS 213 F 00 Move vec length Call Out of Loop void combine2 vec ptr v int dest int i int len vec length v dest 0 for i 0 i len i int val get vec element v i val dest val Optimization Move call to vec length out of inner loop Value does not change from one iteration to next Code motion CPE 20 2 Compiled O2 vec length requires only constant time but significant overhead class11 ppt 12 CS 213 F 00 Convert Loop To Goto Form Code Motion Example 2 Procedure to Convert String to Lower Case void lower char s int i 0 if i strlen s goto done loop if s i A s i Z s i A a i if i strlen s goto loop done void lower char s int i for i 0 i strlen s i if s i A s i Z s i A a CPU Seconds Original 10000 100 1 0 01 0 0001 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 strlen executed every iteration strlen linear in length of string Must scan string until finds 0 Overall performance is quadratic CPU time quadruples every time double string length class11 ppt 13 class11 ppt CS 213 F 00 CS 213 F 00 Optimization Blocker Procedure Calls Improving Performance Why couldn t the compiler move vec len or strlen out of the inner loop void lower char s int i int len strlen s for i 0 i len i if s i A s i Z s i A a Procedure May Have Side Effects i e 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 len or strlen 10000 CPU Seconds 14 100 1 Original New 0 01 0 0001 Linker may overload with different version Unless declared static Interprocedural optimization is not used extensively due …
View Full Document
Unlocking...