4 ms·

In my experience people think/hope that the minimum tells them the performance of their program when all noise is removed. However, this is based on the assumpt

by ltratt 7y ago

In my experience people think/hope that the minimum tells them the performance of their program when all noise is removed. However, this is based on the assumption that programs have a single performance point which, as the Stabilizer paper shows, is rarely the case on modern systems. Rather, what the minimum tells you is the behaviour of your program at one given point in the non-deterministic performance space. This might seem like a minor, perhaps even a pedantic, difference, but I have found it to be a profound observation. Imagine, for example, your program has 100 possible ASLR states: in 99 of those states it takes 1s to run and in the 1 remaining state it takes 0.8s to run. Using the minimum, you will think your program takes 0.8s to run even though there's only a 1% of chance of observing that performance in practise. That's bad, IMHO, but the problem compounds when you compare different versions of the same program. Imagine that I optimise the program such that in those 99 slow states the program now takes 0.9s to run, but in the remaining state it still takes 0.8s. The minimum will tell me that my optimisation made no difference (and thus should probably be removed) even though in 99% of cases I've improved performance by 10%.

manwe150 7y ago
It says something like "without interference, some execution path has proven to be as fast as x". This probably isn't exactly what you wanted to know (e.g. expected time), but is likely to be much faster to compute for some thing that's probably usually strongly correlated. The problem with the existence of 100 independent states is that you need a very large number of trials to get a performance measurement of each—and you're still left with the problem of statistic to reduce each to (min? mean? and how??). Attempting to take the mean with the CST should eventually work, but it might need a very long time. Instead, the minimum lets to pick whichever mode was fastest and compare the time of that mode. Sure, that might not be great for all cases, but if that's the worst problem with the benchmark suite, I'd say you're in pretty good shape. I've run into issues where the CPU appears to have memorized the random number sequence in the test data—how are you supposed to pick the better algorithm when the CPU won't let you run the 99% case under a benchmarking harness... Yeah, minimum isn't perfect, but it's at least pretty clear what it says, as long as there isn't incentive to abuse it (I might say the same about p-value vs bayesian). disclosure: worked with the author of the Julia paper cited above.
- SomeOldThrow 7y ago
  > Yeah, minimum isn't perfect, but it's at least pretty clear what it says You’ve lost me. What is the single, obvious meaning of the minimum measurement, and what are you benchmarking against, and what do you intend to get out of the benchmark? Typically the minimum just means “program ran x input as fast as y”, which doesn’t actually help with most questions about performance. If X is constant, and time is the only thing you care about, then maybe that works.
  - jcelerier 7y ago
    > which doesn’t actually help with most questions about performance. well, from a marketing standpoint it means that you are able to write OBSERVED MAXIMUM SPEED : 789634 gigabrouzoufs per second on a core i5-xxxx on your brochure, and you wouldn't be lying, and it would be better that a majority of products which don't even give an observed speed but just a theoretical one.
rrss 7y ago
That would be a very unusual performance distribution. I've seen a lot of distributions, and they included a load of right-skewed distributions, some normal distributions, but I honestly can't think of any case with a left-skewed distribution like this one.
- ltratt 7y ago
  The problem is more-or-less as bad for a normal distribution as it is for a skewed distribution (I'd have said the distribution from my examples is right skewed, not that it makes any difference to my argument): the minimum gives you no information about the distribution. As Figure 1 of [1] (bias alert: I'm a co-author) shows, it seems that, on modern systems, you can can find pretty much any distribution you want if you have enough benchmarks. [1] https://soft-dev.org/pubs/html/barrett_bolz-tereick_killick_mount_tratt__virtual_machine_warmup_blows_hot_and_cold_v6/ https://soft-dev.org/pubs/html/barrett_bolz-tereick_killick_...

by ltratt 7y ago

manwe150 7y ago

It says something like "without interference, some execution path has proven to be as fast as x". This probably isn't exactly what you wanted to know (e.g. expected time), but is likely to be much faster to compute for some thing that's probably usually strongly correlated. The problem with the existence of 100 independent states is that you need a very large number of trials to get a performance measurement of each—and you're still left with the problem of statistic to reduce each to (min? mean? and how??). Attempting to take the mean with the CST should eventually work, but it might need a very long time. Instead, the minimum lets to pick whichever mode was fastest and compare the time of that mode. Sure, that might not be great for all cases, but if that's the worst problem with the benchmark suite, I'd say you're in pretty good shape. I've run into issues where the CPU appears to have memorized the random number sequence in the test data—how are you supposed to pick the better algorithm when the CPU won't let you run the 99% case under a benchmarking harness... Yeah, minimum isn't perfect, but it's at least pretty clear what it says, as long as there isn't incentive to abuse it (I might say the same about p-value vs bayesian). disclosure: worked with the author of the Julia paper cited above.

SomeOldThrow 7y ago
> Yeah, minimum isn't perfect, but it's at least pretty clear what it says You’ve lost me. What is the single, obvious meaning of the minimum measurement, and what are you benchmarking against, and what do you intend to get out of the benchmark? Typically the minimum just means “program ran x input as fast as y”, which doesn’t actually help with most questions about performance. If X is constant, and time is the only thing you care about, then maybe that works.
- jcelerier 7y ago
  > which doesn’t actually help with most questions about performance. well, from a marketing standpoint it means that you are able to write OBSERVED MAXIMUM SPEED : 789634 gigabrouzoufs per second on a core i5-xxxx on your brochure, and you wouldn't be lying, and it would be better that a majority of products which don't even give an observed speed but just a theoretical one.

rrss 7y ago

That would be a very unusual performance distribution. I've seen a lot of distributions, and they included a load of right-skewed distributions, some normal distributions, but I honestly can't think of any case with a left-skewed distribution like this one.

ltratt 7y ago
The problem is more-or-less as bad for a normal distribution as it is for a skewed distribution (I'd have said the distribution from my examples is right skewed, not that it makes any difference to my argument): the minimum gives you no information about the distribution. As Figure 1 of [1] (bias alert: I'm a co-author) shows, it seems that, on modern systems, you can can find pretty much any distribution you want if you have enough benchmarks. [1] https://soft-dev.org/pubs/html/barrett_bolz-tereick_killick_mount_tratt__virtual_machine_warmup_blows_hot_and_cold_v6/ https://soft-dev.org/pubs/html/barrett_bolz-tereick_killick_...