Should timings be included in answers where appropriate?

Question

For many of the questions I've looked at, I see people saying that the algorithms or parts of the implementation will be 'slow', but no one seems to follow this up with performance figures for a 'typical' run of their favorite algorithm and/or implementation. If you're going to criticize the run-time/efficiency of code, shouldn't you be giving examples of how well a good implementation performs? Wouldn't knowing these numbers help the OP, or at least give them something against which to test?

I understand that if you give this kind of feedback you might also need to specify your computer type, memory size, operating system (maybe), and programming language (if different than what the OP used in their posted code).

Answer 1

Short answer: Yes, you should always include timings when talking about performance.

This is because measurement of performance is a vital first step in improving it: you can't fix what you don't measure. It's clear from the way questions about performance are phrased, that many programmers are not in the habit of preparing repeatable test cases, measuring performance on those test cases, and evaluating the impact of changes to the algorithm or the code. People learn from example, so it's important for us to set a good example, by showing how to prepare test cases, and by taking and reporting performance measurements.

The actual numbers from those measurements are not particularly important: of course they depend on details of hardware. But usually one is interested in performance ratios: how much faster the code is after it is changed, and in many cases performance ratios are portable between hardware setups.

Some example answers where explicit timings were important:

• Solving 15 puzzle — note that the whole behaviour of the program had to be adjusted so that it could be tested with repeatability.
• Fastest way to iterate over Numpy array — this shows why the big-O approach is only part of the story and why constant factors do matter: here I show how to get more than 1000 times speedup without changing the big-O complexity of the algorithm.
• Given an array find any three numbers which sum to zero — here we have two algorithms each of which performs better than the other on some distributions of inputs.

Answer 2

Short answer: No, I don't think that timings of implementations are necessary for a good performance review of an implementation, I think it makes the most sense to let the OP perform their measurements. And for algorithms, an answer should talk about their big-O time complexity, but not specific timings.

Long answer: Timing of specific code depends on way too many variables, you mentioned some of them, others include compiler (and its options), the data used for testing (their size, but possibly also their “shape”), and how does the piece of code under review fit into the whole program (does it just call the code over and over, or does it also do other things? this can matter especially in multi-threaded programs).

Performing good timings may also be relatively hard (you need to produce the test data, the OP almost never gives those) and time consuming.

So, I think that producing timings would take too much time and effort for the answerer (reviews can already take quite some time, we don't want to make them even more time-consuming) and they might not be very useful to the OP.

As for algorithms, their timing would provide even less useful information (because an algorithm can be implemented in different way, with different performance characteristics). But there is a better option to compare performance of algorithms: determining their time (and possibly also memory) complexity, using the big-O notation.

Time complexity of an algorithm is (usually) much easier to figure out and it doesn't depend on any of the variables timing does, so it doesn't suffer any of the problems mentioned above.