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 Techniques6 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