Assume that we have a baseline software B and a new prototype P that I want to compare with B. Ideally, I want to show that P performs some orders of magnitude or X times faster than B (on average).

I have m queries/problems that I run on each software with a timeout T. I record the raw running times $b_1,\dots,b_m$ of B and $t_1,\dots,t_m$ of P. It could be that for some (few) problems B is still faster than P, moreover it could be that there are very short times such as 0.01s or considerably longer ones, for instance, 3000s. Now my question is, what is a good measure to compare the performance of B and P quantitatively on average?

A straightforward (but probably crude) measure could be just computing the average running times $b_a = \frac{1}{m}\sum_{i=1}^m b_i$ and $t_a = \frac{1}{m}\sum_{i=1}^m t_i$, and taking $\frac{b_a}{t_a}$.

A variation of this measure is taking the average of times when both systems didn't timeout and counting the number of timeouts, although not sure how to get just one measure from these four values.

These two measures do not address one my concern related to the variance in the values of the times. For instance, for $m=2$, $b_1=2500$s, $t_1=8$s, $b_2=2000$s and $t_2=1000$s, the first measure is 4.4643. Does it mean that P performs on average 4 times faster? Would it be more reasonable to take the average of the normalised times $\frac{1}{m}\sum_{i=1}^m \frac{b_i}{t_i}$? In this case it would be equal 157.25 and, seems to me, would better reflect the performance gains.

And again, a question is how to take timeouts into account properly.

I am sure that there should be standard approaches to comparing performance of two systems(for instance, databases), but I wasn't able to find anything quickly. I would also be grateful to see an explanation why one measure is better than the other, and what are the standard measures (at least on the scientific community).

  • $\begingroup$ I am afraid that, as you must have realized, performance depends on so many factors many of which are changing constantly that standardized measures are far and between. It is often unrealistic to compress all the cases into a few numbers. Performance can also be very subjective as in perceived performance. $\endgroup$ – Apass.Jack Jun 26 at 16:33

The general answer is of course: "It depends on the problem and the final utilization of your software".

The first question you should answer is what makes a given version query time so variable ? Is it query dependent ? Does the software have some buffering between queries ? Maybe a ressource variable availability ?

Generally the performance of an algorithm is evaluated considering the worst query possible. Let's take an example, you need an algorithm to find where a function change of sign:

You may loop on all points one by one or do a binary search. The former would sometimes performs faster if the searched point is one of the first. Nevertheless, in worst case it has to analyse all points whereas the latter finds the solution in logarithmic time.

Now if you have a timeout, the main metric you have is how many timeouts gets each solution. Maybe you even can identify what queries lead to timeout for each algorithm. In my opinion, there is no sense to compare average query time if some algorithm gets timeout more often.

  • $\begingroup$ Basically, I run a number of MILP problems using a linear solver. The two versions are different encodings, the newer implementing various optimisation heuristics. It happens that for some problems the prototype is very fast (so the heuristics really help in this case), while for other not so much. $\endgroup$ – Elena Jun 26 at 14:58
  1. Compare only cases when both systems don't timeout
  2. Add separate metrics of timeout %
  • 1
    $\begingroup$ OK but you know we're looking for answers with more detail than this. Why would this be a good way of comparing the performance of the two systems? $\endgroup$ – David Richerby Jun 26 at 14:34

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.