1

Imagine I am working on a C compiler. I have made some changes to the compiler's code, and am interested to know what effect these changes have on the performance of generated binaries.

I have a benchmark program, written in C, which runs for a minute or so and outputs a megaFLOPS value. I can compile this benchmark using both the original and changed compiler.

How should I run the resulting binaries in order to compare their performance? Should I simply run each binary multiple times and compare the mean megaFLOPS values? Or perhaps maximum megaFLOPS values?

The above would allow me to state by what percentage one binary is faster/slower than the other. Is there any way to use the variance of the megaFLOPS values in order to quantify confidence in my conclusion? Ideally I would like to be able to say, for example, "My changes make the benchmark run 4% faster (95% confidence)".

  • 2
    Benchmarking is statistics! – Jörg W Mittag Nov 13 '16 at 12:40
  • In addition to running the benchmark, I would be diff'ing the generated code. – Erik Eidt Nov 13 '16 at 17:00
2

If you run a series of tests of similar input size, you should calculate the average time, and the standard deviation (which is the statistical measure of the confidence you could have on the average).

When you run very heterogeneous tests, e.g. Source code of very different size, you could consider making the average on the total test suite time, instead of working with average time per sloc for the diiferent test cases.

If you're not testing the disk access performance, you could exclude the first run in order to avoid distortion due to OS caching ( especially as the very first run(be it old or new) will bear the cost of absence of cache)

Finally, in order to make a general statement about performance, you should ensure that your test case is representative of real-life diversity. If not, specify precisely the scope of your measures (your salesman will anyway make the generalisation for you ;-) )

  • +1 I would only add that it might make more sense to use the log of the time, taking the average and standard deviation of that, because differences are likely to be proportional, not additive. Then the next question is, "how different is different?". The usual measure is two standard deviations to conclude that there is a real difference. – Mike Dunlavey Nov 13 '16 at 21:21
  • @MikeDunlavey thanks for these additional interesting insights – Christophe Nov 13 '16 at 21:30
2

Problem in generalization of benchmarking results

Firstly, if you run a benchmark program, any performance you observe by running that benchmark program is likely only applicable to your benchmark program.

Standardized benchmarking programs

To compare the performance of compiler outputs (in order to make a claim on the compiler's merit), you will likely need to run many different kinds of benchmark programs. To avoid any statistical sleight-of-hand, these benchmark programs shall come from some standardized source code, or they shall be well-known implementations of well-known algorithms.

Some examples:

You need to do your best to control every possible environmental influences on the program's execution time. In other words, any influences that aren't due to differences in the generated machine code emitted from your two versions of compilers, you must try to neutralize that.

CPU

An example of such interference is the CPU's own frequency variation. On modern Intel microprocessors, you must disable SpeedStep and Turbo Boost options. You should also change the power-saving settings to minimize fluctuations in CPU execution speed. The CPU itself should have more-than-enough thermal dissipation to prevent thermal throttling.

Memory and cache

You should familiarize yourself with the performance effects of memory access patterns and caching. You might be interested in reporting cold-cache results, warm-cache results, or both; you will need to apply appropriate preparation before and during benchmarks. This is a deep topic that will require you to devise a benchmarking methodology. This methodology need to be explained in every detail to your audience so that they can attempt to replicate and verify your results and claims.

OS, other processes, virtual memory

Minimize the number of other non-essential OS processes or applications during the benchmark.

A program's execution speed may be subject to the OS influence, which may be hard to control. Whatever attempts you make, document it in the benchmarking methodology as you report your results.

Modern OS typically use over-committing, which means that a program's request for more memory may be granted without actually making those physical memory space ready for use. Instead, the memory is only made ready when the program hits that address range for the first time. You may want to benchmark multiple scenarios with respect to virtual memory, just as you do with CPU cache effects.

Does execution speed depend on a program's input data?

It depends. In most cases, assume it does.

It is tempting to assume that a program that applies a simple operation to a huge array of primitive values would have an execution speed that does not depend on the array's content. Don't make this assumption.

Reporting confidence intervals

Report the confidence intervals as very low and very high percentiles. For example, 5% percentile and 95% percentile.

Do not assume the underlying measurement distribution to be Gaussian.

Understand that there will be outliers; but do not arbitrarily reject things as outliers - they may be rare events that do affect execution performance in general (meaning that users who run your benchmark programs will have a probability of seeing those rare events as well). This is why using confidence percentiles is important: it tells people exactly what fraction of outliers you are rejecting. Users who need stricter controls on outliers can request you to report stricter percentiles, say, 99.5% percentile, or even 99.99% percentile.

If you use Gaussian assumptions, such as summarizing results as mean and variance, you are destroying the part of statistical information needed to account for outliers.

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.