4
\$\begingroup\$

I wrote a class which can time and compare functions.

I already posted it here once before, and got great suggestions from @rolfl, which I have added to my code.

As before, I'm interested in any and all suggestions you might have (for example code design, accuracy of measurement, usability, naming, commenting, etc).

The revised Timing code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.IntFunction;

/**
 * A timing class.
 *
 * Timings are run in chunks. For each chunk, the input is gathered before-hand.
 */
public class Timing {

    private List<TimingObject> functionsToTime;

    /**
     * amount of chunks to run.
     */
    private int amountChunks = 1_000;

    /**
     * amount of runs per chunk.
     */
    private int amountRunsPerChunk = 1_000;

    public Timing() {
        functionsToTime = new ArrayList<>();
    }

    /**
     * adds a new function which will be timed.
     *
     * @param <R> return type of functionToTime (irrelevant)
     * @param <T> input type of functionToTime (same as return type of
     * inputConverter)
     * @param functionToTime a function expecting input of type T, returning
     * output of any type (R)
     * @param inputConverter converts the loop variable to type T and passes it
     * to functionToTime
     * @param name name of the function (used for output)
     */
    public <R, T> void add(Function<R, T> functionToTime, IntFunction<T> inputConverter, String name) {
        functionsToTime.add(new TimingObject(functionToTime, inputConverter, name));
    }

    /**
     * sets how many chunks should be run.
     *
     * The total amount of how often the given functions should be run when
     * timed is amountChunks * amountRunsPerChunk.
     *
     * @param amountChunks amountChunks
     */
    public void setAmountChunks(int amountChunks) {
        this.amountChunks = amountChunks;
    }

    /**
     * sets how often the function is run per chunk.
     *
     * The total amount of how often the given functions should be run when
     * timed is amountChunks * amountRunsPerChunk.
     *
     * @param amountRunsPerChunk amountRunsPerChunk
     */
    public void setAmountRunsPerChunk(int amountRunsPerChunk) {
        this.amountRunsPerChunk = amountRunsPerChunk;
    }

    /**
     * performs the actual timing for all given functions.
     */
    public void time() {
        for (int chunks = 0; chunks < amountChunks; chunks++) {
            // run a chunk of tests on this timingObject:
            for (TimingObject timingObject : functionsToTime) {
                // generate input:
                ArrayList input = new ArrayList<>();
                for (int runs = 0; runs < amountRunsPerChunk; runs++) {
                    input.add(timingObject.inputConverter.apply((chunks * amountRunsPerChunk) + runs));
                }
                // run with input:
                long[] times = timeRuns(timingObject, input);
                timingObject.addTimeChunk(times);
            }
            Collections.shuffle(functionsToTime); // randomize functions each time
        }

        for (TimingObject timingObject : functionsToTime) {
            timingObject.processTimes();
        }
    }

    /**
     * runs a chunk of functions, timing each one.
     *
     * @param <T> input type
     * @param timingObject timingObject
     * @param input list of input for functions
     * @return array of times
     */
    private <T> long[] timeRuns(TimingObject timingObject, ArrayList<T> input) {
        long[] times = new long[input.size()];
        for (int i = 0; i < input.size(); i++) {
            long start = System.nanoTime();
            timingObject.function.apply(input.get(i));
            times[i] = System.nanoTime() - start;
        }
        return times;
    }

    /**
     * passes the result of the timing to the given consumer.
     *
     * @param consumer consumer
     * @param sort how to sort the result
     */
    public void output(Consumer<String> consumer, Sort sort) {
        switch (sort) {
            case ASC:
                Collections.sort(functionsToTime,
                        (TimingObject t1, TimingObject t2) -> (int) (t1.meanTime - t2.meanTime));
                break;
            case DESC:
                Collections.sort(functionsToTime,
                        (TimingObject t1, TimingObject t2) -> (int) (t2.meanTime - t1.meanTime));
                break;
            case NAME:
                Collections.sort(functionsToTime,
                        (TimingObject t1, TimingObject t2) -> t1.name.compareTo(t2.name));
                break;
            default:
                break;
        }

        FormatedTableBuilder formater = new FormatedTableBuilder();
        formater.addLine(new String[]{"name", "per call (mean, ns)", "per call (median, ns)", "95th percentile (ns)", "total (ms)"});
        formater.add(functionsToTime, (TimingObject timing) -> new String[]{
            timing.name,
            String.valueOf(timing.getMeanTime()),
            String.valueOf(timing.getMedianTime()),
            String.valueOf(timing.getPercentile(95)),
            String.valueOf(timing.getMeanTime() * timing.times.size() / 1000000000.0)
        });
        consumer.accept(formater.format());
    }

    private class TimingObject {

        private Function function;
        private IntFunction inputConverter;
        private String name;
        private long meanTime;
        private List<Long> times;

        public TimingObject(Function function, IntFunction inputConverter, String name) {
            this.function = function;
            this.inputConverter = inputConverter;
            this.name = name;
            this.times = new ArrayList<>();
        }

        public void addTimeChunk(long[] timeChunk) {
            for (int i = 0; i < timeChunk.length; i++) {
                times.add(timeChunk[i]);
            }
        }

        public void processTimes() {
            Statistics.removeWorstAndBest(times); // also sorts
            meanTime = (long) Statistics.calculateMean(times);
        }

        public long getMeanTime() {
            return meanTime;
        }

        public long getMedianTime() {
            return (long) Statistics.calculateMedian(times);
        }

        public long getPercentile(int percentile) {
            return (long) Statistics.percentile(times, percentile);
        }

    }

    public static enum Sort {

        ASC, DESC, NAME
    }
}

Statistics class

import java.util.Collections;
import java.util.List;

public class Statistics {

    private static final int REMOVE_BEST_PERCENT = 10;
    private static final int REMOVE_WORST_PERCENT = 10;

    /**
     * removes the x lowest and x highest values from the list.
     *
     * Also sorts the list ascending.
     *
     * @param list list
     */
    public static void removeWorstAndBest(List<Long> list) {
        // sort ascending
        Collections.sort(list,
                (Long l1, Long l2) -> (int) (l1 - l2));

        // remove x worst and x best results
        int originalSize = list.size();
        list.subList(list.size() - (REMOVE_BEST_PERCENT * originalSize / 100),
                originalSize).clear();
        list.subList(0,
                (REMOVE_WORST_PERCENT * originalSize / 100)).clear();
    }

    /**
     * returns the mean of the list.
     *
     * @param list list
     * @return mean
     */
    public static double calculateMean(final List<Long> list) {
        double mean = 0;
        final int length = list.size();
        for (int i = 0; i < length; i++) {
            mean += list.get(i) / (double) length;
        }
        return mean;
    }

    /**
     * returns the median of the list.
     *
     * Expects a sorted list.
     *
     * @param list list
     * @return median
     */
    public static double calculateMedian(List<Long> list) {
        return list.get(list.size() / 2);
    }

    /**
     * returns the
     *
     * Expects a sorted list.
     *
     * @param list list
     * @param percentile percentile
     * @return percentile
     */
    public static double percentile(List<Long> list, int percentile) {
        int rank = (int) Math.ceil((percentile / 100) * list.size());
        return list.get(rank);
    }
}

Example Output

Timing of a couple of functions which reverse a string:

name                    per call (mean, ns)     per call (median, ns)     95th percentile (ns)     total (ms)     
reverseArray            126                     124                       95                       0.1008         
reverseBuilder          134                     132                       103                      0.1072         
reverseIt               138                     131                       111                      0.1104         
reverseStack            842                     835                       757                      0.6736         
reverseStackBuilder     478                     471                       425                      0.3824
\$\endgroup\$
3
  • \$\begingroup\$ Do you have somewhere the implementation of formater.add ? \$\endgroup\$ – janos Oct 2 '14 at 20:41
  • \$\begingroup\$ A simple example demonstrating how to use this would be nice \$\endgroup\$ – janos Oct 2 '14 at 21:16
  • \$\begingroup\$ formater.add as well as example usages can be found in the questions linked above (original timing class and align string for output). \$\endgroup\$ – tim Oct 18 '14 at 19:37
2
\$\begingroup\$

Make more fields immutable

There are several fields that could have been final, for example these:

public class Timing {
    private List<TimingObject> functionsToTime;
    // ...

private class TimingObject {
    private Function function;
    private IntFunction inputConverter;
    private String name;
    private List<Long> times;
    // ...

Make everything final that you can.

Use more for-each loops

Somewhat oddly, you left a few old-fashioned for (;;)style loops that could be rewritten using for-each, for example in TimingObject.addTimeChunk:

for (int i = 0; i < timeChunk.length; i++) {
    times.add(timeChunk[i]);
}

And in Statistics:

for (int i = 0; i < length; i++) {
    mean += list.get(i) / (double) length;
}

Simpler initialization

If you move the initialization of Timing.functionsToTime to declaration, you can get rid of the constructor, making the code slightly shorter.

private List<TimingObject> functionsToTime = new ArrayList<>();

Raw types

There is a raw ArrayList in Timing.time:

ArrayList input = new ArrayList<>();
for (int runs = 0; runs < amountRunsPerChunk; runs++) {
    input.add(timingObject.inputConverter.apply((chunks * amountRunsPerChunk) + runs));
}

It would be better to use ArrayList<Object> instead, or there might be an even better way.

Redundant parentheses

There are a couple parentheses that are really redundant, for example:

list.subList(0, (REMOVE_WORST_PERCENT * originalSize / 100)).clear();

int rank = (int) Math.ceil((percentile / 100) * list.size());
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.