# How to plot algorithm runtime for huge input set?

Fo my bachelor thesis, I want to compare the runtime of two algorithms. The runtime is measured by letting these algorithms run for every value in a huge input set. This input set can be partitioned into three subsets $X_1$, $X_2$, $X_3$. Each subset contains 40,000 values, the algorithms are executed once for each value. In my plot I want to have the input sets on the x-axis, and each set's runtime on the y-axis. What would be a good representation for this kind of data?

I first tried a scatter plot, but because a few values are really far outliers, the scale of the plot squashes most important values into visually indistinguishable areas. I then superimposed the lines for the mean value, with error bars for the standard deviation: This clearly demonstrated how far and few these outliers were. The non-outlier scatter values are not even recognizable under the mean value lines, which themselves aren't very distinguishable. Because these outliers are not really important for my evaluation, I decided to change my graph to only show mean values with standard deviation: These partly improve the situation, but to fit the standard deviation onto the plot, the mean values are still somewhat close. But I feel removing the error bars would be neither true to the data nor scientifically accurate. Additionally plotting the data like this makes the errors bars go below zero, which indicates a bad representation of the data, since time values below zero are obviously impossible.

How can data like this be represented better? Is showing the mean value actually a good idea in this case? Or would other characteristics like the median be better? Or even remove the say 5% from that data, that constitute the furthers outliers?

Further I have no idea what a good format for the error bars would be that would avoid the case of them going below zero. Is there something like the standard deviation above the mean value and one below that i could then plot asymmetrically?

I am both looking for insight into this particular case and resources on how to showcase data in general. In case anyone wants to try my themselves at it, I made the first 100 values of each data point available (the above graphs were made with these): http://pastebin.com/sjdPy8Np

• Could you explain how you are computing sub-nanosecond runtimes? Exactly how are you obtaining these timing measurements? – whuber Jul 18 '15 at 15:23
• What makes you believe I am computing sub nanosecond runtimes? Did you miss the 10^9 on top of the graphs? – Lukas Schmelzeisen Jul 18 '15 at 15:29
• It would be good to rule out the possibility that the outliers occurred because of extraneous system events. What happens when you re-run the timing test for the inputs that give the high outlying times? – whuber Jul 18 '15 at 21:10
• Thanks for the hint. I have verified that I only measure elapsed time for the current process and not wall-time. Even after repeated execution, the outliers still occur for exactly the same inputs. I have additionally measured number of lookups to an underlying data structure that my algorithms perform, and for the computation of the outliers the number of lookups is $10^5$ times higher than normal. I should probably find a way to explain these in my evaluation. – Lukas Schmelzeisen Jul 18 '15 at 22:20
• Investigating the reasons for the outliers may be more important and interesting than merely summarizing the results or applying some kind of statistical test to the algorithms. – whuber Jul 19 '15 at 13:11

Continuing the comment theme, you should find an explanation for your outliers to know whether to include them or segregate them. I notice that the outliers are oddly clumped. An outlier for one input set row seems to often go along with an outlier for the same row in another input set. Regarding your graph, once you've worked out the outliers issue, box plots may be a viable option. Here's a version with outliers, but using a log transform (which may be appropriate if there is a multiplicative aspect to the algorithm). That loses the within-row correlations. To emphasize those you could use the same marker symbol for values in the same row (until you run out of symbols!). Another approach is to a parallel coordinates plot, where every row is represented by a connected line. Finally, don't feel obligated to summarize all your findings in a single plot.

Btw, if you post more data, please use a computer-friendly format like CSV or JSON.

• Thanks for this answer. I remember taking a long time to figure out what you meant with each point. In the end I went with box plots. – Lukas Schmelzeisen Sep 18 '15 at 12:19

The minimum values for each input set might be the most informative. A lot of nuisance factors can slow down your benchmark, but very few can cause the code to run faster The docs for the python benchmarking module timeit say:

It’s tempting to calculate mean and standard deviation from the result vector and report these. However, this is not very useful. In a typical case, the lowest value gives a lower bound for how fast your machine can run the given code snippet; higher values in the result vector are typically not caused by variability in Python’s speed, but by other processes interfering with your timing accuracy. So the min() of the result is probably the only number you should be interested in. After that, you should look at the entire vector and apply common sense rather than statistics.

You could then turn to extreme value theory to get a more rigorous estimate of the fastest that your code can possibly run. This, however, assumes that your code and data are fixed. In other words, you'd repeat this process for $X_1, X_2 \text{ and } X_3$, and then try to do some inference on the results (e.g., compare credible intervals or something).

As an alternative, I like @xan's suggestion of plotting on a log scale. Given the domain, it might be more appropriate to use $\log_2$ instead of $\log_{10}$--each increment then corresponds to doubling the running time and might match up with some theoretical analysis of your algorithm.

• Min values are certainly an interesting characteristic that I will consider. However I'm yet unsure whether the reasoning applies, as each input value requires a different deterministic number of lookups to an underlying data structure. I think that focussing on the min values would ignore all input value that require more complex calculations. – Lukas Schmelzeisen Jul 21 '15 at 9:03
• Sure, that's sort of what I meant by "fixed." I imagine your timing as having two sources of variance: properties of the data (e.g., some sorting algorithms do particularly well or poorly with reversed or almost-sorted data) and properties of the machine (swapping, network latency, cosmic rays, etc). Once you choose a single data set, the former factors are fixed but the machine-related factors, which are presumably less interesting, remain. Taking the min might be a sensible way to deal with those. – Matt Krause Jul 21 '15 at 15:26
• All that was a long-winded way of saying that I forgot an 's': you should consider the minimum values for each data set. – Matt Krause Jul 21 '15 at 15:27

I have a strong suspicion that your raw data are not normally distributed, given that your data are right-skewed and they cannot possibly be skewed left (bounded by zero). As you mentioned, assuming normality here results in error estimates which extend below zero, which I believe is inappropriate. You may want to consider possible transformations of your raw data. There is a good CV post here and a SixSigma page here that may help you begin to thoughtfully consider these alternate approaches. 