Lab: Performance Experiments

Objective

Your goal for this lab is to experiment with different implementations of the NaturalNumber kernel and of the power function and compare their performance. In particular, you will use two implementations of the NaturalNumber kernel (NaturalNumber1L and NaturalNumber2) and the two implementations of the power method you have encountered before (a slow, iterative one and a fast recursive one). So while comparing the various observed timing functions, remember that you are trying to understand how each implementation impacts the performance of the code being timed and what other factors affect the execution time.

Setup

Follow these steps to set up a project for this lab.

Create a new Eclipse project by copying ProjectTemplate. Name the new project PerformanceExperiments.
Open the src folder of this project and then open (default package). As a starting point you can use any of the Java files. Rename it NaturalNumber1LFastPower and delete the other files from the project.
Follow the link to NaturalNumber1LFastPower.java, select all the code on that page and copy it to the clipboard; then open the NaturalNumber1LFastPower.java file in Eclipse and paste the code to replace the file contents. Save the file.

Method

Take a look at the code provided. Note the following:
- NaturalNumber1LFastPower extends NaturalNumber1L and, as a result, it inherits a "fast" implementation of the power function;
- the main method times the performance of the power method of NaturalNumber1LFastPower by using an object of this type (note that, following the single point of control over change principle, the type NaturalNumber1LFastPower is used in only one place and newInstance is employed to guarantee that other objects will all have the same dynamic type);
- the main method uses a new component, Stopwatch, to time the execution of each call to the power method: look at the documentation to understand how it is being used and be sure to ask an instructor if you have any questions.
Make sure you understand what the main method does.
Run the program and enter 7 as the value of n. You can copy and paste the output data to a text file to save it. You can easily create a file in the data folder in your project by right-clicking on the data folder in the Package Explorer view and selecting New > File.

You can plot the data (the power p along the x axis and the time along the y axis) by hand, but it is more convenient to use a spreadsheet program such as Microsoft Excel. If you are using your own computer and do not have such a program, you should use (share) one of the computers in the lab for this activity. On the lab computers, you can find Excel in the Start Menu.

Here are some brief instructions on how to use Excel. If you have never used a spreadsheet application before and are having problems, just ask one of the instructors for help.

Task	Instructions
Enter Data	Copy the output of the program (except the first input line) to the clipboard; click on cell A1 in a clear worksheet and then click on the small down arrow below the Paste button in the top-left corner of the window and select Paste Special.... (Don't click the Paste button itself because it will paste all the data in one column.) In the window that pops up, select Text (not HTML or Unicode Text) and click OK. [If, the data is pasted all in one column, select the data, switch to the Data tab, click on Text to Columns and in the wizard pages select Delimited, then Tab and Space, and click Finish.]
Generate Chart	Select all the cells you pasted (including the column labels). Click on the Insert tab at the top of the window. In the Ribbon toolbar, under Charts, find the Insert Scatter icon, click on it, and select the Scatter with Smooth Lines icon. A chart of your data should be displayed.
Extend Chart	If you paste a new column of data (times) to the right of the last column (e.g., paste the timings for a different value of n and the same values for p in column C), you can include the new data in the same chart by clicking in the chart, this will highlight the cells containing the data displayed in the chart. Then drag the bottom right corner of the box around the displayed data to include the new column. That's it! The chart should now display the new data. If this does not work, you can just select all the data and follow the steps above to create a new chart.

Now that we have a chart of the execution time for the fast power using NaturalNumber1L, let's time the same fast implementation of power using a different implementation of the kernel, NaturalNumber2. Copy NaturalNumber1LFastPower.java to NaturalNumber2FastPower.java. Open NaturalNumber2FastPower.java in the editor and replace extends NaturalNumber1L in the first line of the class with extends NaturalNumber2. This way you will now time the fast power using NaturalNumber2 instead of NaturalNumber1L. To be sure, double check in the main method that n is instantiated with NaturalNumber2FastPower's constructor.
Run the NaturalNumber2FastPower program and again enter 7 as the value of n. You can save your output to the same file or a new file. In any case, copy and paste the new data in the spreadsheet. Since the first column lists the same values of the power p as for the previous timing experiment, you should only paste the column of time data in column C of the spreadsheet. This can be accomplished by pasting the new data in columns C and D and then deleting column C (right-click on the header of column C—the cell labeled C—and select Delete or Delete Columns from the drop-down menu). Then follow the instructions above to either extend the chart to include the new data or to create a new chart with both timing functions. You may want to rename the two labels "t" to something like "t1L" and "t2" so that it will be easy to distinguish them in the chart.
Compare the two timing functions and discuss with a classmate what you observe.
For the rest of the lab, we will use only NaturalNumber2. The next step is to compare the performance of the fast implementation of power with a slow implementation. First select or create a new worksheet in your spreadsheet document (in Excel, there should already be three sheets, so you can just select a blank one by clicking on the Sheet2 tab at the bottom-left of the window). Copy and paste the data generated by NaturalNumber2FastPower into the new sheet; make sure you do not use the first set of numbers from NaturalNumber1LFastPower.
Copy NaturalNumber2FastPower.java to NaturalNumber2SlowPower.java. Open NaturalNumber2SlowPower.java in the editor and paste the following method above the main method.
```
@Override
public void power(int p) {
    assert p >= 0 : "Violation of: p >= 0";
    if (p == 0) {
        this.setFromInt(1); // 0 ^ (0) = 1, by definition
    } else if (p > 1) {
        NaturalNumber originalThis = this.newInstance();
        originalThis.copyFrom(this);
        for (int i = 1; i < p; i++) {
            this.multiply(originalThis);
        }
    }
}
```
Note that this is an instance method and the number being raised to the p power is called this. This implementation overrides the one inherited from NaturalNumber2 and it is the one that will be timed here. To be sure, double check in the main method that n is instantiated with NaturalNumber2SlowPower's constructor. Also observe that the code of the slow power uses the newInstance method whenever it needs to create a new NaturalNumber object and this way it guarantees that all the NaturalNumber objects will be of dynamic type NaturalNumber2SlowPower.
Run the NaturalNumber2SlowPower program and again enter 7 as the value of n. You can save your output to the same file or a new file. In any case, copy and paste the new data in the spreadsheet so that you have three columns: the column of the power values p, the column of the times for the fast power t2 fast, and the column of the times for the slow power t2 slow.
Create a chart to compare the two timing functions. Compare them and discuss with a classmate what you observe.
Now run again NaturalNumber2FastPower and NaturalNumber2SlowPower and use a 2-digit value for n, e.g., 19. Generate a new chart to compare these results. How do these timing functions compare to the timing functions for the fast and slow implementation of power using n = 7? You may want to generate a chart with all four timing functions to make a direct comparison.
Depending on the speed of the computer you are using (and how patient you are), you may want to try with bigger values of n, say three digits, and then possibly four or more. Can you predict with any confidence what kind of execution times you should expect based on the performance behavior you have observed for smaller values of n?

Additional Activities

There are other dimensions along which to explore and compare the performance of the fast and slow implementations of power. Here are some other possibilities:

Experiment with other values of n and with different ranges and increments for the values of p.
For fixed values of p, vary n over a range of values and plot the observed timing functions.
Combine your experiments and vary both p and n in some carefully chosen ranges and then plot the results as a surface in 3D (Excel can do that; just find the Surface icon among the Charts options under the Insert tab).