Lab 6: Benchmarking

Overview

In this assignment, you develop a code to benchmark several implementations of specific tasks on the List interface.

Video introduction for the lab

Assignment

Due to the large size of .jar files, please do not commit these to your repository.

You must write a command line program that will produce benchmark data for the following List implementations:

Your program should produce benchmark data for the following operations:

Details

The goal of this assignment is to be able to generate benchmark results that allow you to generate graphs that show the amount of time it takes for each of the list implementations to complete the desired operations as a function of the number of elements stored in the list. Your command line program should have the following interface:

java -jar lab6username.jar java.util.LinkedList addToFront 10000000 5 7

Here the arguments are:

In this case, the program should produce results for benchmarking adding one element to the front of the java.util.LinkedList when the list has 1000000, 2000000, 400000, 80000, 16000, 3200, and 640. The output should consist of a tab-separated list of times in nanoseconds. Use format("%,d ns", time) to add thousands separators (9,877 instead of 9877). You can measure the amount of time the operation takes by calling System.nanoTime() immediately before performing the operation to be benchmarked and immediately after. The difference in times represents the time required to complete the operation.

You must create two classes: Benchmarker which contains your main() method and ListBenchmark which must contain two public class methods:

You should decompose the code required to implement the required functionality into multiple private methods in the ListBenchmark class.

When benchmarking, create a list of integers and add the appropriate number of random integer values.

To do the benchmarks, you'll need to create data structures and populate them with lots of integer values. It can take a long time to add all of these elements if you do it one at a time. We recommend that you create an array of Integers, numbers of the desired size. For the classes in the datastructures package, use the constructor that accepts an array to populate the data structure. For the classes in the java.util package, use the constructor that accepts a Collection by passing it Arrays.asList(numbers).

In addition, you must determine appropriate command line arguments for the indexedContains and contains operations on all five data structure implementations. You should use a starting size of 10,000,000 unless the test take more than an hour to run. If the benchmarking result is over one hour, adjust the command line arguments so that the benchmark for the largest list size takes at least 10 seconds but no more than a hour.

java -jar lab6username.jar java.util.LinkedList indexedContains 10000000 5 7

produced a longest time of 312,211,582,193ns. Add this information to the README.md file in the form of:

java.util.LinkedList indexedContains 10000000 5 7 [312,211,582,192 ns]

Just For Fun

Ambitious students may wish to:

Acknowledgement

This laboratory assignment, developed by Dr. Chris Taylor.

See your professor's instructions for details on submission guidelines and due dates.