Lab 6: Benchmarking
Overview
In this assignment, you develop a code to benchmark several implementations of specific
tasks on the List
interface.
Assignment
.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 listindexedContains
— Iterating through the list using an index (callingget()
) to find a matchcontains
— Determining if a value is in the list usingcontains()
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:
java.util.LinkedList
— the implementation. Other valid options:java.util.ArrayList
,datastructures.ArrayList
,datastructures.LinkedList
, anddatastructures.LinkedListTurbo
addToFront
— the operation. Other valid options:indexedContains
andcontains
- 10000000 — the largest list size to benchmark
- 5 — the dividing factor used to reduce 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 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:
runBenchmarks(String listType, String operation, int size, int divisor, int numberOfTests)
that returns an array oflong
s 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.
Integer
s,
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:
- Graph the results of the benchmarking experiments.
Acknowledgement
This laboratory assignment, developed by Dr. Chris Taylor.