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:

the java.util.ArrayList implementation
the java.util.LinkedList implementation
the datastructures.ArrayList implementation
the datastructures.LinkedList implementation
the datastructures.LinkedListTurbo implementation

Your program should produce benchmark data for the following operations:

addToFront — Adding to the front of the list
indexedContains — Iterating through the list using an index (calling get()) to find a match
contains — Determining if a value is in the list using contains()

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 100 5 7

Here the arguments are:

java.util.LinkedList — the implementation. Other valid options: java.util.ArrayList, datastructures.ArrayList, datastructures.LinkedList, and datastructures.LinkedListTurbo
addToFront — the operation. Other valid options: indexedContains and contains
100 — the smallest list size to benchmark
5 — the multiplicative factor used to increase the list size for additional benchmarks
7 — the total number of benchmark runs

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 100, 500, 2,500, 12,500, 62,500, 312,500, and 1,562,500. 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:

runBenchmarks(String listType, String operation, int size, int multiplier, int numberOfTests) that returns an array of longs containing the time, in nanoseconds, required for each benchmark to complete.
getHelp() returns a string with text describing the required command line arguments.

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 command line arguments for the indexedContains and contains operations on all five data structure implementations on a maximum size input of \( 10^7 \) or a smaller input size that produces a benchmark time of at least 10 seconds and no more than 1 hour. For example, if

java -jar lab6username.jar java.util.LinkedList indexedContains 100 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 100 5 7 [312,211,582,192 ns]

Just For Fun

Ambitious students may wish to:

Graph the results of the benchmarking experiments.

Acknowledgement

This laboratory assignment, developed by Dr. Chris Taylor.

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