4
$\begingroup$

I am comparing several different algorithms for navigation applications. Since I may possibly be publishing a paper comparing the performance of these algorithms with each other, I was wondering the best way to go about measuring performance.

As far as I know, there are two ways to compare performance: writing the code in a compiled language like C and measuring the time of execution, or counting the number of FLOPS. However, I am aware that different processors have different capabilities which results in different execution times on different platforms.

These algorithms will be implemented on low-cost embedded systems (the main application is satellites, where low power is key).

So in summary: what is the scientifically accepted way of comparing the performance of different algorithms?

$\endgroup$
  • $\begingroup$ Our reference questions may be of interest. $\endgroup$ – Raphael Dec 15 '15 at 8:32
  • 3
    $\begingroup$ If this is only about "how do I perform running-time experiments in a scientific way", I recommend McGeoch's book. $\endgroup$ – Raphael Dec 15 '15 at 8:34
6
$\begingroup$

There is no single answer. The answer depends upon the specific situation you are in. It's not that there is a single scientifically accepted way of evaluating performance. Instead, a paper should be driven by the claims you want to make. First, figure out what claims you want to make about your scheme. Then, figure out what evidence is needed to support those claims.

For instance, perhaps you would like to claim that your scheme is fast enough to deploy on low-cost embedded systems. Well, then your next step is to make that claim more precise: what counts as fast enough? how do you know? what specific systems do you mean? Then, you can evaluate performance on those systems, by that metric, and assess whether it is fast enough.

Or maybe you would like to claim that your scheme is faster than previously published approaches. Your next step would be to make that more precise: which previous approaches are you going to compare to? on what platform? with what workload? And then you'd evaluate on those platforms.

The right metric to use for performance will depend on your specific situation. For some, maybe it is wall-clock time. For others, maybe it is energy consumption (power). For still others, maybe it is guaranteed low-latency, or memory usage, or something else entirely.

In short: there is no single scientifically accepted method. Instead, think of science as (a) being precise about what claims you are making, and then (b) providing appropriate evidence to support those claims. What constitutes "appropriate evidence" will depend upon your specific situation. You can often look to other publications in your field to see what evaluation method they used, as initially guidance, but ultimately this is a matter of critical thinking: evaluating evidence in a logical, careful, thoughtful manner.

$\endgroup$
  • $\begingroup$ Agreed. There is formal analysis of abstract cost measures on one end of the spectrum and experiments on running times on the other end, and several things in between. All can be "scientific" but answer different questions. $\endgroup$ – Raphael Dec 15 '15 at 8:33
2
$\begingroup$

There are basically two ways to do it, big-O, and actual measurement.

Big-O matters if the size of the input dataset can become quite large. That's when you want O(1), O(n), or O(n log n). If the size of the dataset is more predictable, big-O becomes less important compared to actual times.

Regardless of big-O, there are constant factors, and it is generally under-appreciated how large those can be. (In an academic sense, a factor of 50 might not be important, but in real time, it's a different story.)

It's hard to compare different algorithms in real time, because it depends on how well they've been optimized. Often the same algorithm can be optimized several different ways, compounding its speed, and that's before the compiler's optimizer does its job. If I can give an example, here's a case where the same algorithm had multiple optimizations performed against it, reducing its time by a factor of 730. (People who have done serious performance tuning on real software are not too surprised by such a ratio.)

Only when an algorithm has been carefully tuned (which in general you cannot assume has been done) can its execution time be compared with another.

$\endgroup$
0
$\begingroup$

The paper should include both:

  • a theoretical estimate of the time complexity, based on a count of a representative operation (like FP arithmetic operation, swap of two elements, comparisons...);

  • an empirical measurement, preferably obtained for different problem sizes and realistic data distributions. The platform used to perform the test should be one which is popular in the corresponding application domain.

For top quality results, I recommend to run different problems for each size and provide the standard deviation in addition to average running time. (This is too rarely done.)

$\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.