Assignment 4

VisualVM Profiler

  1. If you are using the school computer, you can skip this step.
    Download VisualVM 1.3.9 here, and then extract somewhere on your computer.

  2. From where you extracted the files, go into the /bin folder, then run visualvm.exe.
    If you are using the school computers, just open up a terminal/cmd and enter visualvm to run the program.

  3. If it's your first time using it, go to Tools > Plugins.



  4. In the Available Plugins, you should see "Startup Profiler", which you should install.



  5. Once the plugin is installed, you will see a new button (like a clock) in the menu bar at the top. Click it.



  6. In the popup dialogue, leave the default settings (Java8, 64bit, port 5140) and click Continue, then click Continue again. This will show all three parts of the dialogue (shown below).
  7. There are two textboxes here. The first one is pre-filled with red text which you should replace with your class names (eg. A4Q5 and Sorting). Clear the second box, since we want Java's sorting algorithm to be included (it's part of java.*).



  8. The text box has a long string in it. Click "Copy to Clipboard".
  9. Click "Profile". If it's your first time, it was ask to calibrate, which you should agree to. Make sure you allow the firewall connection.



  10. Once it's done, you will end up with a screen that says "Connecting to VM...". Leave this screen open, as it's waiting for you to run your Java program. You have to do this first, before you run your Java program.



  11. In terminal/cmd, navigate to your compiled Java files. Run your program as usual, but with the copied string as a flag. Just in case.... make sure you already compiled your program.
    For example: java -agentpath...\lib,5140 A4Q5 <arraySize> [numArrays]



  12. At this point you should see a bunch of stuff happen, and after a while your program terminates and VisualVM will show the time spent on each method in your classes. Most of these are warnings you can ignore, as long as you see the results in VisualVM.



  13. At the bottom of VisualVM, you can search for "sort", which will pull up your Sorting class methods plus Java's sort() method.



  14. Look at the TOTAL TIME for your methods. Read the Submethods section below for explanation.

Submethods

For Q1-Q4 (and bonus), you have to make sure you use the method signatures shown in the assignment. Beyond that, it is up to you whether you put everything in one function, or have many submethods. For example, the lecture notes contain the heap sort within one method. Alternatively, you can have a dedicated Heap class, with seperate methods to insert, build-max-heap, and delete.

In the VisualVM profiler, you should always look at the Total Time for each of your sorting methods. The Self Time is the time spent only within the specified method, whereas the Total Time will include the time used on any submethod calls. If you did not use any submethods, then Total Time will be equal to Self Time. For example, look at Java's sort() method above. It has 69ms total time, but only 1.31ms self time. The rest of the time is spent on the call to DualPivotQuicksort(), which has 67.7ms total time. However, this method only has 19.7ms self time, while another 47.9ms is spent in further calls to DualPivotQuicksort() with a different method signature.

Q4/Q6 Analysis

Like the previous assignment, you are expected to explain the results you got from testing your algorithm implementations. However, unlike the previous assignment, it would be hard to calculate the theoretical values. In A3, we counted running cost by the number of comparisons made. However, in A4, we look at the actual running time. Of course, the time is dependent on your hardware, or your implementation. For example, let's say I got a result of 1000ms, and n = 128. Without knowing the constant (eg. hardware), I wouldn't know if it was c*n = 1000, or (cn)^2 = 1000. As such, it is difficult to determine the growth rates based on the results.

Instead, you want to compare the algorithms with each other. Explain why certain algorithms might be faster/slower, especially if they are not exclusively faster/slower. If one algorithm is faster for n=128, but slower for n=1024, be sure to explain why. When comparing quicksort, explain why the improved version and bonus versions are in fact improved, rather than simply saying "they are faster." It's all about justifying your answers to show what you know.

Java's sort() method, as seen above, uses a Dual-Pivot Quicksort. You can read more about it here.

Random.nextInt()

When you randomly generate numbers for Q5 and Q6 to populate your arrays, you can use the Random.nextInt() method. Although nextInt() can take an integer as a parameter to denote the range of the random numbers, it is fine to call nextInt() without any parameters. This will generate integers within the full (default) possible range.

Copying Arrays

Ideally, in iteration you would create one array, then pass the same array into each sorting algorithm. This ensures your results are consistent. However, if you create one array and pass in the same array (reference) to each sorting algorithm, then the first one would sort it before passing it on. Instead, every time you want to test a sorting algorithm, you need to first create a deep copy of the original array. This means you not only copy the reference, but actually create a new array and copy each value. You can either do this manually with a for loop, or you can use a built-in method for this. Examples include Object.clone(), System.arraycopy(), or Arrays.copyOf().