14.1 Performance3Running TimeCharles Babbage (1864)“As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise - By what course of calculation can these results be arrived at by the machine in the shortest time?” – Charles BabbageAnalytic Enginehow many times do youhave to turn the crank?4The ChallengeQ. Will my program be able to solve a large practical problem?Key insight. [Knuth 1970s] Use the scientific method to understand performance.compiledebugon test casessolve problemsin practice5Scientific MethodScientific method.•Observe some feature of the natural world.•Hypothesize a model that is consistent with the observations.•Predict events using the hypothesis.•Verify the predictions by making further observations.•Validate by repeating until the hypothesis and observations agree.Principles. •Experiments must be reproducible;•Hypotheses must be falsifiable.6Reasons to Analyze AlgorithmsPredict performance.•Will my program finish?•When will my program finish?Compare algorithms.•Will this change make my program faster?•How can I make my program faster?Basis for inventing new ways to solve problems.•Enables new technology.•Enables new research.7Algorithmic SuccessesDiscrete Fourier transform.•Break down waveform of N samples into periodic components.•Applications: DVD, JPEG, MRI, astrophysics, ….•Brute force: N2 steps.•FFT algorithm: N log N steps, enables new technology.Freidrich Gauss18058Algorithmic SuccessesN-body Simulation.•Simulate gravitational interactions among N bodies.•Brute force: N2 steps.•Barnes-Hut: N log N steps, enables new research.Andrew AppelPU '819Example: Three-Sum ProblemThree-sum problem. Given N integers, find triples that sum to 0.Application. Deeply related to problems in computational geometry.Q. How would you write a program to solve the problem?% more 8ints.txt30 -30 -20 -10 40 0 10 5% java ThreeSum < 8ints.txt 4 30 -30 0 30 -20 -10-30 -10 40-10 0 1010Three-Sumpublic class ThreeSum{ // Return number of distinct triples (i, j, k) // such that (a[i] + a[j] + a[k] == 0) public static int count(int[] a) { int N = a.length; int cnt = 0; for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) for (int k = j+1; k < N; k++) if (a[i] + a[j] + a[k] == 0) cnt++; return cnt; } public static void main(String[] args) { int[] a = StdArrayIO.readInt1D(); StdOut.println(count(a)); }} all possible triples i < j < kEmpirical Analysis12Empirical AnalysisEmpirical analysis. Run the program for various input sizes.1. Time in seconds on Jan 18, 2010 running Linux on Sun-Fire-X4100 with 16GB RAM 2. Time in seconds in 1970 running MVT on IBM 360/50 with 256 KB RAM (estimate)Ntime (1970) 1time (2010) 2500620.031,0005310.262,00043222.164,0003437717.188,000265438137.7613StopwatchQ. How to time a program?A. A stopwatch.14StopwatchQ. How to time a program?A. A Stopwatch object.public class Stopwatch{ private final long start; public Stopwatch() { start = System.currentTimeMillis(); } public double elapsedTime() { return (System.currentTimeMillis() - start) / 1000.0; }} 15StopwatchQ. How to time a program?A. A Stopwatch object.public static void main(String[] args){ int[] a = StdArrayIO.readInt1D(); Stopwatch timer = new Stopwatch(); StdOut.println(count(a)); StdOut.println(timer.elapsedTime());}Data analysis. Plot running time vs. input size N.Q. How does running time grow as a function of input size N ?Hypothesis: Running times on different computers differ by a constant factorData Analysis162000 4000 80001005015000input size Ntime (seconds)20102000 4000 800020000010000030000000input size Ntime (seconds)1970Data analysis. Plot running time vs. input size N on a log-log scaleHypothesis: Running time grows as the cube of the input size: a N 3Data Analysis17NT(N)lg(N)lg(T(N))1,0000.2610-1.92,0002.16111.14,00017.18124.18,000137.76137.110lg (N)lg(time)11 12 131-24732lg (T(N)) = 3 lg N + aT(N) = a N 3machine-dependentconstant factorstraight line of slope 318Prediction and verificationHypothesis. Running time is about a N 3 for input of size N.Q. How to estimate a ?A. Solve for it!Refined hypothesis. Running time is about 2.7 ! 10 –10 ! N 3 seconds.Prediction. 1,100 seconds for N = 16,000.Observation.validates hypothesis!Ntime (seconds)160001110.73137.76 = a ! 80003󲰛 a = 2.7 ! 10 –10NT(N)1,0000.262,0002.164,00017.188,000137.76Doubling hypothesis. Quick two-step method for prediction.Hypothesis: T(2N)/T(N) approaches a constant.Step 1: Run program, doubling input size, to find the constant19Doubling hypothesisNT(N)ratio5000.03-1,0000.267.882,0002.168.434,00017.187.968,000137.767.96seems to converge to 816,0001102832,00088168......512,00036112957Step 2: Extrapolate to predict next entries137.76*8Consistent with power law hypothesis a(2N)b / aNb = 2b(exponent is lg of ratio)Admits more functions Ex. T(N) = N lg N a(2N lg 2N) / aN lg N = 2 + 1/(lg N) ! 2 1102*88816*84TEQ on Performance 1 Let F(N) be the running time of program Mystery for input N.Observation: Q. Predict the running time for N = 128,00020public static Mystery{ ... int N = Integer.parseInt(args[0]); ...}NT(N)ratio1,00042,0001544,0006048,0002404TEQ on Performance 2 Let F(N) be the running time of program Mystery for input N.Observation: Q. Order of growth of the running time?21public static Mystery{ ... int N = Integer.parseInt(args[0]); ...}NT(N)ratio1,00042,0001544,0006048,0002404Mathematical Analysis23Mathematical models for running timeTotal running time: sum of cost ! frequency for all operations.•Need to analyze program to determine set of operations.•Cost depends on machine, compiler.•Frequency depends on algorithm, input data.In principle, accurate mathematical models are available. Donald Knuth1974 Turing Award24Example: 1-sumQ. How many instructions as a function of N?int count = 0;for (int i = 0; i < N; i++) if (a[i] == 0) count++;operationfrequencyvariable declaration2assignment statement2less than compareN + 1equal to compareNarray accessNincrement≤ 2 Nbetween N (no zeros)and 2N (all zeros)25Example: 2-sumQ. How many instructions as a function of N?int count = 0;for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (a[i] + a[j] == 0)