Code Optimization
1 Code Optimization
Outline Machine-Independent Optimization Code motion Memory optimization Suggested reading -5.2~56
2 Outline • Machine-Independent Optimization – Code motion – Memory optimization • Suggested reading – 5.2 ~ 5.6
Motivation 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
3 Motivation • 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
Motivation 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
4 Motivation • 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
5. 2 Expressing Program Performance
5 5.2 Expressing Program Performance
Time Scales P382 Absolute Time Typically use nanoseconds 10-9 seconds Time scale of computer instructions
6 Time Scales P382 • Absolute Time – Typically use nanoseconds • 10–9 seconds – Time scale of computer instructions
Time Scales Clock Cycles Most computers controlled by high frequency clock signal Typical Range 100 MHZ 108 cycles per second Clock period = 10ns ·26Hz 2 X 109 cycles per second Clock period =0.5ns
7 Time Scales • 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
CPE P383 1 void vsuml (int n) 2{ in七i 345678 for(i=0;主<n;i++) c[i]=a[i]+b[i];
8 CPE P383 1 void vsum1(int n) 2 { 3 int i; 4 5 for (i = 0; i < n; i++) 6 c[i] = a[i] + b[i]; 7 } 8
CPE P383 9/* Sum vector of n elements (n must be even)*/ 10 void vsum2 (int n) 11{ 12 int i 13 14 for(主=0;i<n;i+=2){ 15 /* Compute two elements per iteration * 16 cli= ali] bli] 17 c[i+1]=a[i+1]+b[i+1]; 18 19}
9 CPE P383 9 /* Sum vector of n elements (n must be even) */ 10 void vsum2(int n) 11 { 12 int i; 13 14 for (i = 0; i < n; i+=2) { 15 /* Compute two elements per iteration */ 16 c[i] = a[i] + b[i]; 17 c[i+1] = a[i+1] + b[i+1]; 18 } 19 }
Cycles per element Convenient way to express performance of program that operators on vectors or lists Length = n T= CPE 大n+ Overhea
10 Cycles Per Element • Convenient way to express performance of program that operators on vectors or lists • Length = n • T = CPE*n + Overhead