Performance MeasurementPerformance AnalysisSome Uses Of Performance AnalysisLimitations of AnalysisSlide 5Memory HierarchySlide 7Slide 8Performance Measurement NeedsSlide 10Timing In JavaShortcomingAccurate TimingAccuracySlide 15Slide 16What Went Wrong?The FixTime Shared SystemBad Way To TimePerformance MeasurementPerformance AnalysisPaper and pencil.Don’t need a working computer program or even a computer.Some Uses Of Performance Analysisdetermine practicality of algorithmpredict run time on large instancecompare 2 algorithms that have different asymptotic complexitye.g., O(n) and O(n2)Limitations of AnalysisDoesn’t account for constant factors.but constant factor may dominate1000n vs n2and we are interested only inn < 1000Limitations of AnalysisModern computers have a hierarchical memory organization with different access time for memory at different levels of the hierarchy.Memory HierarchyRL1L2MAINALU8-32 32KB 512KB 512MB1C 2C 10C 100CLimitations of AnalysisOur analysis doesn’t account for this difference in memory access times.Programs that do more work may take less time than those that do less work.Performance MeasurementMeasure actual time on an actual computer.What do we need?Performance Measurement Needs programming language working program computer compiler and options to use javac -oPerformance Measurement Needsdata to use for measurement worst-case data best-case data average-case datatiming mechanism --- clockTiming In Javalong startTime = System.currentTimeMillis();// gives time in milliseconds since 1/1/1970 GMT// code to be timed comes herelong elapsedTime = System.currentTimeMillis() - startTime;ShortcomingClock accuracy assume 100 millisecondsRepeat work many times to bring total time to be >= 1 secondAccurate Timinglong startTime = System.currentTimeMillis();long counter;do { counter++; doSomething(); } while (System.currentTimeMillis() - startTime < 1000)long elapsedTime = System.currentTimeMillis() - startTime;float timeForMethod = ((float) elapsedTime)/counter;AccuracyNow accuracy is 10%.first reading may be just about to change to startTime + 100second reading may have just changed to finishTimeso finishTime - startTime is off by 100msAccuracyfirst reading may have just changed to startTimesecond reading may be about to change to finishTime + 100so finishTime - startTime is off by 100msAccuracyExamining remaining cases, we gettrueElapsedTime = finishTime - startTime +- 100msTo ensure 10% accuracy, requireelapsedTime = finishTime – startTime >= 1secWhat Went Wrong?long startTime = System.currentTimeMillis();long counter;do { counter++; InsertionSort.insertionSort(a); } while (System.currentTimeMillis() - startTime < 1000)long elapsedTime = System.currentTimeMillis() - startTime;float timeForMethod = ((float) elapsedTime)/counter;The Fixlong startTime = System.currentTimeMillis();long counter;do { counter++; // put code to initialize a[] here InsertionSort.insertionSort(a); } while (System.currentTimeMillis() - startTime < 1000)Time Shared SystemUNIX time MyProgramBad Way To Timedo { counter++; startTime = System.currentTimeMillis(); doSomething(); elapsedTime += System.currentTimeMillis() - startTime; } while (elapsedTime <