The Golden Rules of optimization Good Algorithms Rule a The best and most important way of optimizing a program is using good algorithms E.g. O(n*log)rather than O(n2) However we still need lower level optimization to get more of our programs a In addition, asymptotic complexity is not always an appropriate metric of efficiency a Hidden constant may be misleading E.g. a linear time algorithm than runs in 100*n+100 time is slower than a cubic time algorithm than runs in n3+10 time if the problem size is small Fa|2011 Advanced Compiler Techniques
6 Fall 2011 “Advanced Compiler Techniques” The Golden Rules of Optimization Good Algorithms Rule ◼ The best and most important way of optimizing a program is using good algorithms ◼ E.g. O(n*log) rather than O(n2 ) ◼ However, we still need lower level optimization to get more of our programs ◼ In addition, asymptotic complexity is not always an appropriate metric of efficiency ◼ Hidden constant may be misleading ◼ E.g. a linear time algorithm than runs in 100*n+100 time is slower than a cubic time algorithm than runs in n 3+10 time if the problem size is small
Asymptotic Complexity Hidden Constants Hidden Contants 3000 2500 2000 100n+100 1500 n’nn+10 1000 500 0 0 5 10 15 Problem size Fa|2011 Advanced Compiler Techniques 7
7 Fall 2011 “Advanced Compiler Techniques” Asymptotic Complexity Hidden Constants Hidden Contants 0 500 1000 1500 2000 2500 3000 0 5 10 15 Problem Size Execution Time 100*n+100 n*n*n+10
General Optimization Techniques Strength reduction Use the fastest version of an operation ■Eg instead of instead of Common sub expression elimination Eliminate redundant calculations ■Eg double x=d大(1im/max)大sx; double y=d *(lim max)*sy double depth =d (lim/ max double x= depth大sx; double depth Fa|2011 Advanced Compiler Techniques 8
8 Fall 2011 “Advanced Compiler Techniques” General Optimization Techniques ◼ Strength reduction ◼ Use the fastest version of an operation ◼ E.g. x >> 2 instead of x / 4 x << 1 instead of x * 2 ◼ Common sub expression elimination ◼ Eliminate redundant calculations ◼ E.g. double x = d * (lim / max) * sx; double y = d * (lim / max) * sy; double depth = d * (lim / max); double x = depth * sx; double y = depth * sy;
General Optimization Techniques Code motion Invariant expressions should be executed only once E.g for (int 0; 1< xlength; 1++) x[i] * Math PI Math Cos( double picosy= Math. PI Math cos(y) for (int i=0; i<x length; i++) 区[i]*= piCOs Fa|2011 Advanced Compiler techniques
9 Fall 2011 “Advanced Compiler Techniques” General Optimization Techniques ◼ Code motion ◼ Invariant expressions should be executed only once ◼ E.g. for (int i = 0; i < x.length; i++) x[i] *= Math.PI * Math.cos(y); double picosy = Math.PI * Math.cos(y); for (int i = 0; i < x.length; i++) x[i] *= picosy;
General Optimization Techniques Loop unrolling The overhead of the loop control code can be reduced by executing more than one iteration in the body of the loop. E. g double picosy Math. PI Math cos (y)i for(int 0; i< x length i++) 1 piCOs double picosy Math PI Math cos(y) for (int i =0;i length; i + 2)t x[i]大= piCOS A efficient“+1” In array x[i+1]大= piCOs; indexing is required Fa|2011 Advanced Compiler techniques
10 Fall 2011 “Advanced Compiler Techniques” General Optimization Techniques ◼ Loop unrolling ◼ The overhead of the loop control code can be reduced by executing more than one iteration in the body of the loop. E.g. double picosy = Math.PI * Math.cos(y); for (int i = 0; i < x.length; i++) x[i] *= picosy; double picosy = Math.PI * Math.cos(y); for (int i = 0; i < x.length; i += 2) { x[i] *= picosy; x[i+1] *= picosy; } A efficient “+1” in array indexing is required