Should benchmarkings be done at all? What is the point?

Question

I am reading a paper which compares algorithm A versus algorithm B.

It shows that algorithm A is faster than algorithm B via benchmarking that shows the CPU time.

What is the point of this? Any benchmarking is going to be dependent on the particular implementation. The benchmarking says nothing about the intrinsic speed of algorithm A versus algorithm B -- all it tells us that the implementation of algorithm A happened to be faster than the implementation of algorithm B.

So what is the point of that? I'd even go as far as saying such information is downright misleading, since it is making an assertive claim (A is faster than B) when in fact such a claim is wholly dependent on the coding and optimizing-abilities of the author of the code.

This mistake is something I am particularly seeing in statistics, where a lot of authors implement their code in R, and R-code can be notoriously faster or slower dependent on the smallest of changes (e.g. vectorization or using compiled base R functions), hence it is very very easy to write an implementation of an algorithm that happens to be suboptimal compared to another algorithm, even if that algorithm would be faster if it were implemented in a better way.

Answer 1

Yes, benchmarking should be done. I make this claim as an Editor, Author, and Reviewer. Below, I represent these roles' stances slightly hyperbolically.

But let me strongman your argument first. In addition to the following claims

The benchmarking says nothing about the intrinsic speed of algorithm A versus algorithm B -- all it tells us that the implementation of algorithm A happened to be faster than the implementation of algorithm B.

[...] it is making an assertive claim (A is faster than B) when in fact such a claim is wholly dependent on the coding and optimizing-abilities of the author of the code.

I think you might agree with or even implicitly make an additional claim:

If Algorithm A has clear theoretical advantages of Algorithm B, then it is not necessary to compare the two in practice. For instance, if Algorithm A runs in O(N) time and Algorithm B runs in O(N^2) time then it is pointless to compare them.

Would you rather:

1. Live in a world in which authors implement their algorithms and make their code available for use by normal humans?
2. Or do you prefer to live in a world in which authors make "brilliant" advances but never bother to code them up, leaving that as an "exercise for the reader"?

I prefer the first world. When I have a problem, the best thing for me is to look in the literature, find a lucid write-up with a link to a Github repo, and then to go and download a well-commented source code to use as a library in my work. It may take a few rounds of theory to get to this point, but I think it's an objectively better world state.

How do I bring about this world as an Editor? By requiring authors to submit code along with their papers.

How do I bring about this world as an Author? By making my code available and raking in the citations.

As a Reviewer: by recommending revision and rejection for papers without implementations.

---

Another question. Would you rather:

1. Live in a world in which it's clear which code you should use.

2. A world in which every author claims their code is the best code and it's left as an "exercise for the reader" to verify these claims.

I prefer the first world.

As an Editor, every paper I get claims to have solved X better than any other paper ever. It is my job to protect your time by serving as the first line of defense against a wave of BS (conversely: to protect your time by helping good work get seen). Sometimes this is easy. The authors reduce an $O(N^2)$ solution to $O(N)$. Other times everything is $O(N)$.

In this latter case, I have a few choices: accept every well-written paper that claims that for theoretical reasons their work is better, reject all new papers because the status quo is clearly good enough, or ask authors to benchmark.

This last option puts the burden of proof on authors to support their claims and, importantly, it encourages them to write decently performant implementations because they know that I will be asking future authors to use their work as a baseline.

Thus, by consistently requesting benchmark comparisons, I encourage authors to (a) implement their code, (b) contextualize their implementation versus the status quo, and (c) constrain the claims they make about their work by reality.

As an Editor I could require authors to rewrite other folks' code to make a "fair" comparison. But I can't trust them to be fair: they are not motivated to do this work and very well might miss something. Thus, I ask only for improvement in new work. If older works didn't get their implementation details right that's just too bad for them.

As an Editor, I am a volunteer. I am overworked. I get dozens of papers a week. Wouldn't it be nice if there was a simple way to determine if they meet the bar for further publication?

As a reviewer, I prefer the first world. I am a volunteer. I am over-worked. I want to do a nominally good job, but I don't have the time or incentive to do a great job. Wait, there's a benchmark? Problem solved.

An an author, I prefer the first world as well. Every paper in my background section claims it's the best paper ever. To differentiate my work from that sea of noise, I use benchmarks to demonstrate in a clear and compelling way that my claims are true.

---

tl;dr Editors and Reviewers and Readers are all incentivized to want benchmarks. Authors should be as well, but they have a conflict of interest since they want to maximize their number of publications by minimizing the work put into each. Editors and Reviewers provide the excuse Authors needs to do things right.

---

You're right that R makes it easy to write slow, crappy code. But this is the very reason benchmarking is important: it's the only mechanism we have for ratcheting performance forward.

Answer 2

Benchmarks are useful, but not benchmark tells the whole story. There are many useful benchmarks. For example, the Julia microbenchmarks are an interesting case of an isolating benchmark: it tries to change one thing at a time. The best example of this is the Fibonacci benchmark. The benchmark is a recursive algorithm. It's a terrible way to compute Fibonacci numbers, but that's not what it's testing: it's testing specifically how different language deal with recursion. It's not the final statement of course on performance of a language, or even of how well a language does with recursion, but it's one data point from which to build a story.

When going to the larger scope of scientific computing, you correctly point out that there are many things to assess. Again, every benchmark is only one data point in the whole story. For example, this benchmark of ODE solver performance between SciPy, Julia, R (deSolve), Fortran, and C++ and this one between DifferentialEquations.jl and torchdiffeq are an integrative benchmark: it says, at the end of the day, with all of the choices these libraries have made, how do these libraries perform? From this you can see that, if someone did benchmark CVODE vs something they wrote in MATLAB, they would lose by 100x just because of pure performance differences in the language, and so it's likely not an interesting way to show that an algorithm is "good".

So at the end of the day, if you want to make very clear that your algorithm is good, I think you need to have a good high performance implementation. If you do this and then show that this set of algorithms outperforms the standard methods people generally utilize, then I think you're set. Hence at the end of the day:

hence it is very very easy to write an implementation of an algorithm that happens to be suboptimal compared to another algorithm, even if that algorithm would be faster if it were implemented in a better way.

I think you do have to compare to a real known software that if you want to convince anyone that your method is good, otherwise it's just "possibly good". Always compare to C++ and Fortran, otherwise you are leaving doubt.

But of course that's bringing in implementation details, which probably have more of an impact on real-world performance than most numerical analysts would like to hear. My favorite example of this is that BDF integrators usually take quite small steps in comparison to other methods for stiff ODE solvers, and thus is because of the instability of their higher orders and their large truncation cocefficients. The reason why CVODE is fast isn't because of these properties, but rather it's because it does a very good job at keeping its already factorized Jacobians between different time steps and detecting Newton iteration divergence. I can tell you that if you don't do this well, CVODE will be around 30x faster than a naive implicit Runge-Kutta implementation, even though the IRK can be taking larger timesteps, just because it's doing so many more factorizations. What's the better algorithm? It can be hard to tell without optimizing the implementation! How well can the larger timesteps of the IRK, with its multiple stages, compare to a BDF? That's something that (to me) is an open issue, and without fully optimizing a code (whatever that means) you cannot answer it. And that means it's still just a single data point, because at the end of the day you don't know if either code is actually "optimized", or how other hardware will effect the results!

But if you can't write optimal code (it is time consuming), you can still add knowledge to the literature. Of course it will have caveats, but a trained reader takes this into account while reading. For example, it turns out that implicit ODE solvers spend a lot of their time in matrix factorization kernels which are generally BLAS calls, so they tend to have less "language overhead" in comparison to a Runge-Kutta method when called from a "slow" language like MATLAB/Python/R. For this reason you can find that the overhead of an implicit solver vs explicit solver is less in these languages, simply due to language behavior, which makes something like LSODA a good default in a higher level language. In fact, it will win some benchmarks "that it shouldn't" because of this behavior. Just knowing this is enough for me to "correct for this effect" when reading the literature, so if you show some IRK does as well as MATLAB's ode15s, I will be surprised and would want to look deeper into it. Is it definitely better? No, but it has some evidence that says it might be a good idea.

So what can you do? Whatever you can.

Answer 3

All benchmarks are valid in some context, the problem is that authors of benchmarks frequently do not provide the context in which to meaningfully interpret the output of their benchmarks.

The context of a benchmark is the thing it measures and all the steps taken to ensure it actually measures the thing it claims and not something else. A benchmark should measure one thing well and carefully control all variables which might influence that measurement. Then the author of that benchmark should communicate all of the steps they took to ensure that their benchmark measures what they claim, and not something else. Ideally this should be communicated simultaneously in two ways:

1. Plain-language prose that can be understood by the intended audience. In a perfect world someone should be able to understand what was done without looking at the code, but this isn't always possible.
2. Source code, build scripts, and run scripts to reproduce results and ideally to generate new results in different contexts.

Furthermore numerical results of an algorithm should always accompanied by all relevant information that may have influenced it: environment, programming language, operating system, hardware. Be as specific as possible. If your operating system is "Ubuntu" you should specify the version. If you have an "Intel Xeon" processor, you should specify its SKU. If you used a development version of a library cloned from GitHub, you should precisely specify the most recent commit on your version.

In the specific case you mentioned stats algorithms implemented in R. That's perfectly meaningful to implement and compare, but if no effort was spent to control for performance idiosyncrasies of R then the conclusions from the benchmark should reflect this - because it's not measuring algorithm quality alone, but implementation + algorithm quality together. In my opinion that doesn't make it useless, just weaker.

The above constraints might make benchmarking seem impossible to do but that is not so. Just narrow the scope of the benchmark and make weaker conclusions about the results from the benchmark until it does satisfy the above constraints. Or spend more time strengthening the benchmark so that you can draw more sweeping conclusions.

I think this should make it clear that no single benchmark can make everybody happy. Since you have to single out one thing to measure and control everything else, you're going to leave out some segments of your potential audience. For example a benchmark that is intended to measure performance differences between computing hardware vendors shouldn't be used to compare different programming languages.

In brief: a benchmark has to be accompanied by a clear statement of what it measures and a "proof" that it actually does measure what is claimed so that other people can understand and scrutinize the methodology.

Answer 4

Not an answer, just a plot for a first look, an overview, of one thorough benchmark from Mittelmann: 8 LP solvers (commercial and open-source) $\times$ two methods (simplex and IP) $\times$ 2 dozen test cases.

(There must be as many kinds of benchmarks for algorithms and software —
for yourself, for academic journals, "free", write-only ... —
as for food: fast food, slow food, home cooking, cheap, expensive, sugary, papery ...;
hence the HUGE range of cookbooks / of benchmarks.)