Hacker News Reader

Comment by cperciva | Hacker News Reader

This reminds me of a different "rule of 3": If you want to compare two things (e.g., "is my new code faster than my old code"), a very simple approach is to measure each three times. If the all three measurements of X are smaller than all three measurements of Y, you have X < Y with 95% confidence.

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.

View on HN

I agree that based on combination (n! / k!(n-k)!) it seems to be 1 in 20, but when you think of it as running A and B and checking if X or Y is faster 3 times, then you get 1 in 8. Quite a big difference. Where does it come from? Am I doing something wrong? I mean combination approach counts same time results as a win but given enough time precision we could skip this scenario.

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.

Let's say there are 6 trials -- name them x1, x2, x3, y1, y2, y3.

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.

You're right. I actually edited before you replied. Should have deleted it or preferably think more before typing. But now it's forever.

I'm glad you kept it. The explanation was enlightening to me.

Man, I wish I understood frequentist statistics to know if your reasoning makes sense. Bayesianly, if O = "the XXXYYY ordering", and F = "algo B is faster than algo" A, then

    P(F|O) = P(O|F) * P(F) / P(O)

then... what? There isn't even a clear P(O|F) likelihood without making assumptions about the process' noise. If the measurement is very noisy compared to the gain, then XXXYYY is just dumb luck, and doesn't tell you anything. If there is no noise at all, then just getting XY is enough to make a decision.

The OP is making some short cuts. 1/(6 choose 3) means that they start with the assumption that every possible ordering is equally likely. If that is the case, then the odds that XXXYYY pops out is 5%. What happens if we change our assumption? Let's assume that XXXYYY is more likely. This would imply that algo B is faster than algo A. If we assume that any of the other (or all of the other) combinations are more likely, then this reduces the odds that XXXYYY would pop out.

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.

> they start with the assumption that every possible ordering is equally likely

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.

> then XXXYYY is just dumb luck

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.

Let me explain it in a Bayesian way. The Bayesian approach would be to consider a whole bunch of hypotheses about how much better Y does than X (and vice-versa), and a prior distribution over how likely you think each is a-priori. Then for each sample S, you update the probability of each hypothesis H by multiplying its probability by P(S|H), then re-normalize.

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.

“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.”

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.

Yes: for that reason and others the whole approach doesn't make much sense from a Bayesian perspective. I was trying to point that out by running with it.

> There isn't even a clear P(O|F) likelihood without making assumptions about the process' noise.

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.

Going down this rabbit hole eventually leads you to nonparametric statistical tests, e.g. Mann-Whitney-U and so on.

Right. And those are also more powerful (and don't need any knowledge of the distribution of measurement errors).

I mentioned the "three old and three new" test because it's simple, not because it's powerful.

more powerful in the statistical sense? I though non-parametric tests were usually less powerful than those where a certain distribution is assumed.

You would be surprised what number of samples does to the tests. Take t-test -- the most powerful test to check if means of 2 equivariant Gaussians differ. If you compare the asymptotic efficiency of Mann-Whiney (a distribution free test) relative to t-test is around 0.96. Of course in practice you will not have infinite samples. It then comes down when do these asymptotics kick in. Unfortunately that depends on the distribution.

That depends on whether the assumed error distribution is accurate. Obviously, if the distribution is known, you will do better by incorporating it. But assuming Gaussian errors when the data doesn't match can lead to bad analyses.

My personal favourite quick-and-dirty trick: A quick way to estimate any distribution's median is to draw 5 random samples. There's a >90% chance that the median is between the biggest and the smallest value.

The final bit is complete bunkum for an unknown distribution. Whether the distribution is monotonic and if not, how symmetric, is the major determinant of occurrence of such result. Giving a flat number is completely bogus.

I don't understand what you mean. It doesn't actually matter what shape the distribution takes. That figure is derived entirely from what the "median" means, i.e. a random sample has 50% chance of being greater than the median, and 50% chance of being lower than it.

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.

I wish the people constantly complaining how n=20,000 is "far too small a sample size to call this science" (for every empirical study) would take not. Effect size matters!

An absence of statistical training is dangerous. A little statistical training remains dangerous, but gets annoying as well

Is this a good method to use while trying out a lot of ideas? Usually when I am optimizing code, most of the ideas don't work out and performance remains roughly the same (or so I think - I don't really know and want a better workflow here).

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.

sqlite famously squeezed out a ~40% performance improvement (I think from v3 to v4?) by just combining tons of micro-optimizations of this kind where it wasn't obvious if each change even made an improvement. They measured the performance with cachegrind in order to identify very small improvements that get lost in the normal measurement noise.

Also check fishcooking: http://tests.stockfishchess.org/tests which is how Stockfish became the indisputably strongest chess engine: Everyone can commit patches which are then tested in thousands of games, and if they make Stockfish stronger, they are accepted.

That’s a really awesome idea. Also, maybe a few of the performance boosts in the final combination are mutualistic, but if measured independently would not make a difference.

I would love to read more about this. Do you have a link?

https://www.sqlite.org/cpu.html

Statistics is a tricky beast. If 3 runs gives you a 95% chance that your change is an improvement, and you use this process on ten different improvements, there's a 40% chance that at least one of them is bogus.

Would love to see a refutation from a downvoter.

I believe you have it right. Odds that all changes are improvements in 10 changes is: (.95)^10 Odds that at least one change is not improvement is: 1-(.95)^10 = 0.40

One could probably make an argument that not all trials are independent, but not sure what else down-voters saw.

It is not a good method to use in that case.

> If the all three measurements of X are smaller than all three measurements of Y, you have X < Y with 95% confidence.

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.

That's the case when you think the measurement noise is only positive. But are there kinds of noise that reduce your benchmark time?

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.

The way I think about it is that benchmarks include deterministic operations (that happen every time) and nondeterministic operations (that don't). And all of these numbers are positive, since there are few things in the world that take negative time.

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.

In the specific case of code, it is worth noting that runs are typically not independent, because of caching.

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.

This is incorrect: there's no reason to expect that X and Y will each appear 3 times in 6 trials if their probabilities are equal. If all 3 measurements of X are smaller than all 3 measurements of Y, then you have X < Y with confidence 1 - 1/8 or 87.5% confidence. You'd need at least 5 measurements to be 95% confident.

You're not considering the right probability space. We have 3 measurements of X and 3 of Y. The question is the distribution on orderings of these six measurements. If X and Y come from the same distribution then all orderings are equally likely.

Ah, I failed to consider that. The original post is correct.

I'm also having trouble with this. On the face of it the quick and dirty "XXXYYY" test outlined above looks good but are these two following statements consistent? ie are the run times of X (new code) and Y (old code) really from the same distribution.

"is my new code faster than my old code"

"If X and Y come from the same distribution then all orderings are equally likely"

I'm thinking of it as a statistical hypothesis test. The null hypothesis is that they come from the same distribution. Under that hypothesis, there's only a 0.05 chance of seeing three X tests all below three Y tests. So if we see this, we can probably reject the null.

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.

Well, you’re the one measuring each three times. So this should always be the case?

Reply on news.ycombinator.com