CS 105 Tour of the Black Holes of Computing Code Optimization and Performance Chapter 5 perf01 ppt Topics Machine independent optimizations Code motion Reduction in strength Common subexpression sharing Understanding processor optimization Translation of instructions into operations Out of order execution Tuning Identifying performance bottlenecks Branches Machine dependent optimizations Advice Caches and Blocking Pointer code Loop unrolling Enabling instruction level parallelism 2 CS 105 Speed and optimization Programmer Choice of algorithm Intelligent coding Compiler 3 Choice of instructions Moving code Reordering code Strength reduction Must be faithful to original program Processor Pipelining Multiple execution units Memory accesses Branches Caches Rest of system Uncontrollable CS 105 Great Reality 4 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 4 How programs are compiled and executed How to measure program performance and identify bottlenecks How to improve performance without destroying code modularity generality readability CS 105 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 5 Potential memory aliasing Potential procedure side effects CS 105 Limitations of Optimizing Compilers Operate Under Fundamental Constraint Must not cause any change in program behavior under any possible condition Often prevents making optimizations that 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 6 CS 105 New Topic 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 7 for i int ni for j a ni 0 i n i n i 0 j n j j b j CS 105 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 8 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 cmpl ebx ecx jl L40 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 scaled by 4 p b j p scaled by 4 j j n reversed loop if j n CS 105 Reduction in Strength Replace costly operation with simpler one Shift add instead of multiply or divide 16 x x 4 Utility is 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 for i 0 i n i for j 0 j n j a n i j b j 9 int ni 0 for i 0 i n i for j 0 j n j a ni j b j ni n CS 105 Make Use of Registers Reading and writing registers much faster than reading writing memory Limitation 10 Compiler not always able to determine whether variable can be held in register Possibility of aliasing See example later CS 105 Machine Independent Opts Cont 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 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 11 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 1 multiplication i n i 1 i 1 n i 1 i 1 n i n CS 105 Example 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 12 CS 105 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 13 Compute sum of all elements of vector Store result at destination location What s the Big O of this code CS 105 Time Scales Absolute Time Typically use nanoseconds 10 9 seconds Time scale of computer instructions Picoseconds coming soon Clock Cycles Most computers controlled by high frequency clock signal Typical range 1 3 GHz 1 3 109 cycles per second Clock period 1 ns to 0 3 ns 14 CS 105 Cycles Per Element Convenient way to express performance of program that operators on vectors or lists Length n T CPE n overhead vsum1 Slope 4 0 vsum2 Slope 3 5 15 CS 105 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 16 42 06 Compiled g 31 25 Compiled O2 CS 105 Move vec length Call Out of Loop Optimization 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 Move call to vec length out of inner loop Value does not change from one iteration to next Code motion CPE 20 66 Compiled O2 vec length requires only constant time but significant overhead 17 CS 105 Code Motion Example 2 Procedure to Convert String to Lowercase void lower char s int i for i 0 i strlen s i if s i A s i Z s …
View Full Document
Unlocking...