edit: Ah, got it, in my case 3rd result for X can be higher than the first result for Y. You said all times must be smaller.
In the case of checking if x is faster than y 3 times, you're doing x1 < y1 AND x2 < y2 AND x3 < y3.
In the case of checking if all three measurements of x are smaller than all three measurements of y, you're checking x1 < y1 AND x1 < y2 AND x1 < y3 AND x2 < y1 AND x2 < y2 AND x2 < y3 AND x3 < y1 AND x3 < y2 AND x3 < y3.
In other words, the latter case is checking whether the slowest x of three trials is faster than the fastest y of three trials.
P(F|O) = P(O|F) * P(F) / P(O)
This means that either we had it right (algo B is faster than algo A), or the result we saw was at least as unlikely as we predicted. That's what it means to have a "confidence interval".
I'll leave the Bayesian version to someone else because I don't really trust myself to do it.
If the times in each run are independent, this assumption is (for some distributions) the weakest form of "X is not faster than Y."
For a distribution where this is not the case: assume
- X always runs in 999 seconds, and
- Y runs in 1000 seconds in 99% of runs and in 0 seconds the other 1% of the time.
Then XXXYYY is a very likely ordering (~97% chance), though Y runs faster than X "on average". (Not in median or mode though.)
For a more concrete example: say you have two sorting algorithms, one that is a little slower most of the time, but worst case O(n log n), and another that is usually a bit faster but can be O(n^2) on pathological input.
That's the idea. The null hypothesis is that this is dumb luck. Here's a piece of evidence that, if this is dumb luck, is not very likely. Ergo, the odds this is just dumb luck is low and there may be a real effect here.
As the OP said, it's not meant to be used in a scientific paper, it's to let you see if you might be on the right track.
Well in this case, we're only going to consider two hypotheses. Call them H0 and H1. H0 is the "null hypothesis", and says that X and Y are exactly as fast as each other. H1 is the hypothesis that H0 is wrong and Y is totally faster than X. You'll notice that H0 is oddly specific, and H1 is ill-defined. Don't worry about it.
To start off, pick your prior distribution over H0 and H1. Pick whatever you want, because we're going to ignore it shortly.
Now some evidence comes in. Time to update! We got the ordering XXXYYY. First, let's update H0. P(XXXYYY|H0) = 1 / 6choose3 = 5%. Wow, that's not a very good update for H0. It's probably just false. For expediency, let's just toss it out.
H1 is the remaining hypothesis. H1 wins! Y is faster than X.
It only makes sense to toss H0 out if P(XXXYYY|H1) >> 5% (such that the evidence for H1 relative to H0 increases after the observation).
You are implicitly assuming that’s the case because “it makes sense”. But as the parent post mentioned, the likelihood is not defined and in particular if the noise in the observation process is large enough, P(XXXYYY|H1) may be very close to 0.05 as well.
Correct. I believe standard procedure would be to assume that time for algo A/B are normally distributed, put non-informative priors on the parameters, then integrate over the space where F is true. I think the non informative prior for a normal distribution is P(mu, sigma^2) \propto 1 / (sigma^2) - it's harder than this, because you know that the runtime of a program is > 0, and maybe you think that sigma is likely to be quite a bit less than mu. If you choose your prior wisely, I suspect you will actually get something close to 1 / 20, the added uncertainty will come from when |mu_A - mu_B| is roughly less than max(sigma_A, sigma_B), but even there, most of it will cancel out.
A normality assumption may be reasonable - if you're assuming that the run-time of the code is dominated by the addition of a bunch of independent operations that are roughly the same timescale, that's what you will get - it will fall down if there is a small number of steps which dominate (e.g. http requests or garbage collection or something). If you don't want to some kind prior with parameters like that, you need to go into non-parametric Bayesian stats, and you'll end up with a lot more uncertainty.
I mentioned the "three old and three new" test because it's simple, not because it's powerful.
A bit of maths would show that the probability that all 5 samples lie entirely above or entirely below the median (i.e. the median is NOT between the greatest and the smallest value) is 1/16. That gives you a 15/16 (= 93.75%) chance that the median is contained within the bounds.
But if you do this test repeatedly, even if the code had identical performance, you'll get a false positive 5% of the time. And depending on the spread of the timings you might not get a clear XXXYYY win even when it is indeed a minor improvement.
One could probably make an argument that not all trials are independent, but not sure what else down-voters saw.
On a multitasking system, you should use the fastest benchmark run (assuming you're running the same code on the same data in all cases, and if you're not then you're not really benchmarking). This will be the one that is least influenced by any other processing going on.
On one hand, I believe a piece of code has a true benchmark time, but we only measure noisy versions that are skewed positive due to multitasking noise. On the other hand, it seems important to make benchmark measurements in the context of the whole system. If A beats B in the best case (unloaded system), but doesn't win in the average case (taking the context into account), then that's important information.
By taking the minimum, we focus attention on the deterministic operations. This isn't likely to be realistic for production, but production won't look much like your benchmark hardware anyway.
When making code changes, deterministic operations are the part you have most influence over and have the most impact. Removing an unnecessary, deterministic operation will speed up every run, not just some of them.
It is very common for the first run to be slower. It means that by "random chance" slow-slow-slow-fast-fast-fast is more likely than fast-fast-fast-slow-slow-slow. I personally tend to discard first runs as outliers when profiling.
"is my new code faster than my old code"
"If X and Y come from the same distribution then all orderings are equally likely"
If we think X and Y distributions are both something like normal with similar variance, then we should also be able to say the chance of XXXYYY given Y is better than X is at most 0.05.
But if the distributions for X and Y can be really different, then I think you're right -- this test could be misleading! For example, say Y always takes 2 seconds, and X takes 1 second 90% of the time, but 1% of the time it takes an hour. If we run three tests of each, we'll probably only see good runs from X and conclude it's better, when it's not.
This works because the probability of the ordering XXXYYY happening by random chance is 1/(6 choose 3) = 1/20 = 5%. It's quite a weak approach -- you can get more sensitivity if you know something about the measurements (e.g., that errors are normally distributed) -- but for a quick-and-dirty verification of "this should be a big win" I find that it's very convenient.