2.4. Benchmarking

Speed vs. complexity.

Time

Let us define a static nested class Time under PriorityQueueTest that stores runtimes for the add() and remove() methods in any PQ:

static class Time {
    long add = 0;
    long remove = 0;
}

What is the advantage of defining static nested class over non-static nested class?

Runtime Estimation

Let us define addRuntime() that estimates the runtime for add() and remove()for a particular PQ:

<T extends Comparable<T>> void addRuntime(AbstractPriorityQueue<T> queue, Time time, List<T> keys) {
    long st, et;

    // runtime for add()
    st = System.currentTimeMillis();
    keys.forEach(queue::add);
    et = System.currentTimeMillis();
    time.add += et - st;

    // runtime for remove()
    st = System.currentTimeMillis();
    while (!queue.isEmpty()) queue.remove();
    et = System.currentTimeMillis();
    time.remove += et - st;
}

• L5-8: estimates the runtime for add():

  • L5: gets the snapshot of the starting time using currentTimeMillis().
  • L7: gets the snapshot of the ending time using currentTimeMillis().
  • L8: accumulates the runtime to times.add.

• L11-14: estimates the runtime for remove().

Is the approach using currentTimeMillis() a proper way of benchmarking the speed?

We then define benchmark() that estimates the speeds of multiple PQs using the same lists of keys by calling addRuntime():

<T extends Comparable<T>> Time[] benchmark(AbstractPriorityQueue<T>[] queues, int size, int iter, Supplier<T> sup) {
    Time[] times = Stream.generate(Time::new).limit(queues.length).toArray(Time[]::new);

    for (int i = 0; i < iter; i++) {
        List<T> keys = Stream.generate(sup).limit(size).collect(Collectors.toList());
        for (int j = 0; j < queues.length; j++)
            addRuntime(queues[j], times[j], keys);
    }

    return times;
}

• L1: method declaration:

  • AbstractPriorityQueue[]: It is unusual to declare an array of objects involving generics in Java (you will see the unique use case of it in the testSpeedAux() method).

  • Supplier: passes a function as a parameter that returns a key of the generic type T.
• L2: generates an array of Time using several stream operations. The dimension of times[] is the same as the dimension of queues such that times[i] accumulates the speeds taken by the queue[i], respectively.

  • generate(): creates a stream specified by the supplier.
  • limit(): creates a stream with a specific size.
  • toArray(): returns an array of the specific type.
• L4: benchmarks the PQs multiple times as specified by iter.

• L5: generates the list of keys specified by the supplier sup.

• L6-7: estimate the runtimes by using the same list of keys for each PQ.

Why do we need to benchmark the priority queues multiple times?

Benchmark

Let us define testSpeedAux() that takes multiple PQs and prints out the benchmarking results:

@SafeVarargs
final void testRuntime(AbstractPriorityQueue<Integer>... queues) {
    final int begin_size = 1000;
    final int end_size = 10000;
    final int inc = 1000;
    final Random rand = new Random();

    for (int size = begin_size; size <= end_size; size += inc) {
        // JVM warm-up
        benchmark(queues, size, 10, rand::nextInt);
        // benchmark all priority queues with the same keys
        Time[] times = benchmark(queues, size, 1000, rand::nextInt);

        StringJoiner joiner = new StringJoiner("\t");
        joiner.add(Integer.toString(size));
        joiner.add(Arrays.stream(times).map(t -> Long.toString(t.add)).collect(Collectors.joining("\t")));
        joiner.add(Arrays.stream(times).map(t -> Long.toString(t.remove)).collect(Collectors.joining("\t")));
        System.out.println(joiner.toString());
    }
}

• L1: annotates safeVarargs indicating that this method takes vararg parameters.
• L2: declares a final method that cannot be overridden by its subclasses.

  • It can take a 0-to-many number of abstract PQs.

  • The type of queues is AbstractPriorityQueue<Integer>[] such that it can be directly passed to the benchmark() method.

• L5: creates a random generator.
• L8: benchmarks different sizes of PQs.

• L10: warms up the Java Virtual Machine (JVM) before the actual benchmarking.

  • rand::nextnt that is equivalent to the lambda expression of () -> rand.nextInt().

• L12: benchmarks add() and remove() in the PQs.

• L14-18: prints the benchmark results.

  • L14: uses StringJoiner to concatenate strings with the specific delimiter.
  • L16: exercise.

Why is it recommended to declare the method final if it takes vararg parameters? Why does JVM need to be warmed-up before the actual benchmarking? Why should you use StringJoiner instead of concatenating strings with the + operator?

Speed Comparison

The followings show runtime comparisons between LazyPQ, EagerPQ, and BinaryHeap:

https://www.slideshare.net/jchoi7s/dsajava-binary-heap-benchmarks-238005098