report benchmarking regressions

[lsf37]

see also Bamboo/sel4bench/regressions

Will need #75 before this makes sense, and might make sense to fuse into that action as an option.

[lsf37]

With the data in https://github.com/seL4/sel4bench-results/ this is now possible to implement and show as part of the GitHub summary.

My initial idea for this would be the following:

• show the condensed version of the results or maybe just (mean, stddev) for all metrics tracked there with diff to the last run in sel4bench-results as an ascii table in the normal log. In the normal log, because each run will have a table with about 40 rows, and that would be too big for a GitHub summary output on the overall job.

• additionally, implement an automated check for regression/improvement to the last run with some significance threshold that we pick, and only show benchmarks results that exceed those in the overall GitHub summary job page when all jobs have finished. Since this is only one page at the end, it should not crowd out any other failure messages, and when nothing changes, there should be no output at all (we could also have a short "no significant changes" note when nothing has changed in any benchmark).

This only really helps us if we actually look at the sel4bench page. We could also make this fail the job (after deployment etc is done), but that feels a bit strong.

For longer-term graphs, I propose to generate some simple GitHub pages html on the sel4bench-results repo, separate from this per run summary here.

[Indanz]

It would be nice that if for hw-bench tagged PRs, you get the sel4bench results summary and also a diff compared to the last website/master results. I would like to know the min, mean, max and stddev values. Your first proposal pretty much sounds like this.

The problem of automated regression checking is that it's hard to set the threshold correctly. Maybe have two checks, one against the previous run and one for the results e.g. 6 months ago, to catch slowly declining performance.

Ideally, there would be a way to add comments to the result webpage where we can explain why some performance change happened, so there is a place where our analyses are collected. That could range from "upgraded distro and compilers" to the FPU changes or a bugfix that slows things down, but is necessary, or just different configuration options (e.g. fastpath signals enabled or not).

[lsf37]

It would be nice that if for hw-bench tagged PRs, you get the sel4bench results summary and also a diff compared to the last website/master results. I would like to know the min, mean, max and stddev values. Your first proposal pretty much sounds like this.

Yes, that should be quite doable.

The problem of automated regression checking is that it's hard to set the threshold correctly.

It is, I'll try around a bit to see which values would have triggered at which previous bumps in the graphs. We can always tweak them when they fire too often (the opposite is harder to notice). I was thinking something like a combination of "outside stddev (or 2*stddev?) and over a specific % threshold", with the threshold probably individual to the metric, stored in the metrics.yml so it can easily be changed. I might start with 1% globally and then increase the thresholds for the tests where that would fire all the time because of noise.

I noticed that the median is a lot more stable on some of benchmarks than the mean. Maybe that was just the few that I happened to see, but it's worth checking. If yes, then it might be worth triggering on that one instead (when available). Not sure about the statistical validity of that, will have to read up on it.

Maybe have two checks, one against the previous run and one for the results e.g. 6 months ago, to catch slowly declining performance.

Good idea.

Ideally, there would be a way to add comments to the result webpage where we can explain why some performance change happened, so there is a place where our analyses are collected. That could range from "upgraded distro and compilers" to the FPU changes or a bugfix that slows things down, but is necessary, or just different configuration options (e.g. fastpath signals enabled or not).

That could actually be quite possible if we add another yml file that maps specific run IDs and maybe benchmark key(s) to comments. That could even be displayed in the graphs if we want (might be too noisy, not sure). It'd be fairly easy to add a comment to that file if there is a significant change that we're not aiming to fix/mitigate, and we'd have a record of what happened why.

[midnightveil]

Fwiw, prior work: these comments: rust-lang/rust#158043 (comment) (plus the linked url https://perf.rust-lang.org/compare.html?start=693b3e4c6e4e686cb9878c1722ad26858b5f1d2a&end=c1b22f44c3f30e186b829de95f59740c3a690aba&stat=instructions:u, although this one is boring because therr was no change. I just picked the latest PR).

That could actually be quite possible if we add another yml file that maps specific run IDs and maybe benchmark key(s) to comments

Yeah, this was my plan for our sDDF benchmark work, and also why i chose this particular graph label since people have used it before (I believe some LLVM and rust perf regression websites used it)

(In fact: I realise now I could point those grapsh at sel4bench-reaults, adjust the parsing and these would auto-update).

[Indanz]

I noticed that the median is a lot more stable on some of benchmarks than the mean. Maybe that was just the few that I happened to see, but it's worth checking. If yes, then it might be worth triggering on that one instead (when available). Not sure about the statistical validity of that, will have to read up on it.

This makes sense. The best way to look at sel4bench tests is as a measurement in a noisy environment with random other stuff happening, like IRQs. The tests do their best to minimise the noise by pre-running and making things cache hot, so by nature it tries to measure the best case performance. That's why I usually only look at minimum values, especially for simple tests like the IPC ones. More complicated, messy tests are less clear, but there too the same applies: random (timer) IRQs can mess up the timing a lot. Taking the median value filters out those spikes.

That could actually be quite possible if we add another yml file that maps specific run IDs and maybe benchmark key(s) to comments

That would work. Another way would be to have annotated git tags in the sel4bench or manifest git repo, but that would work less well for environment changes.

[lsf37]

Ok, I've been reading up on statistics a little bit, and our case is unsurprisingly pretty standard with a few standard solutions. The main question we want to answer for flagging a new test is "how high is the probability that any difference in mean that we're seeing is real? (vs noise)". This specific question has a complicated answer (but maybe doable, more below), but there is one with an easy answer.

The question that is easy to answer is "if the means between the two runs were equal, what is the probability p that the observed difference is due to noise?". If that probability is very small, then the hypothesis "if the means were equal" is likely wrong. The solution for that one is the Student's t-test, or with robustness against stddev changing between runs, Welch's t-test. Both can be computed from (mean, stddev, n) of the two runs, and are implemented in for instance python SciPy.

What comes out is the probability p above, and the decision to flag or not to flag is the typical p < 0.05 you see in statistics (or a lower threshold if you want to be more sure the change is significant).

How to pick the trigger threshold for p is not so simple, though. p < 0.05 does not mean there is a 95% probability the means are really different. Because the test is a conditional probability, you can't just invert it. In fact the real probability we want (that the means are different) is only loosely related and to actually compute it you need more information.

Plugging in standard assumptions (e.g. more than stddev difference for a change etc) you get values like the following: p=0.1 means about 50% probability the means are different (not significant at all), p=0.05 means only 70-75% chance that the means are different, i.e. much less than 0.05 sounds. p=0.01 is around 90%, p=0.001 is around 99%. (Makes me wonder less about how study results differ over time if everyone reports on p=0.05). These are all with random standard assumptions, though, they would not be accurate probabilities for our data.

It is possible to compute accurate probabilities if you have multiple summary data points for the same code, though. This gives you how much mean/stddev vary when you just re-run the benchmark, and with that data, you have a basis for estimating whether a new data point fits into that or not. We currently, mostly by accident do have a few such runs in the data, which seem to be even enough to . We only have them in the data, because when I backfilled, I also used partial data from unsuccessful runs, i.e. if we want to do this properly, we should actually generate them.

I might first do the standard p threshold thing, because that is easy to do and will get us something soon, and then look more into how we would generate that data and compute the actual probabilities from it.

What you can also do to improve quality is to get a better actual estimate of the real stddev of the distribution by averaging or taking the median of the stddev of multiple previous runs, assuming that the measurement rig doesn't change much. We could do that by taking the last 20 runs or so.

[lsf37]

Of course there are always more problems. If we do this naively, we have 40 configs over the different platforms times ~45 benchmarks (some configs, more some less). So 1,800 results for a single full run. If we flag these completely independently, we need an insanely good (low) false positive rate.

Not sure if my math works out here, but I think a standard p=0.05 basically says there is 1 in 20 chance of flagging an insignificant change (according to whatever method above) as significant. That means for one full run, we'd expect 90 falsely flagged results. So we'd have to pick something like p=0.0005 to just get under 1, and p=0.0001 would still mean a false positive every 5 runs or so.

If it is indeed that bad, there are things we can do and in fact overall improve detection a lot, because the results we have are not independent. E.g. generic kernel code changes would tend to show up on all platforms and configs. MCS changes would show up on all MCS configs, etc. Problem with that is that we'd actually have to analyse what is correlated and what is not, which is a lot more intelligence than what I had planned on putting into this.

Maybe I'm overestimating this, definitely need to try this out on the actual historical data.

[lsf37]

Yup, definitely a problem. If I run just Welch's t test, even with p < 0.00001, every single run ID gets flagged, many of them with almost all configs (~30) and the flags in there with extremely high confidence, e.g. p=2.79e-32. I guess that is because a single cycle difference would be flagged if stddev was 0, which it is for some of our tests (which is a problem I think).

So we either we need to know more about noise between runs or we arbitrarily add a size threshold for the change like I had originally planned.

[midnightveil]

In my mind, the issue is this: a one cycle difference from a particular PR being merged is fine. 100 PRs that each increase it by one cycle is less fine. But comparing between singular tests can't capture that, we need time windows.

The rust compiler here describes their algorithm: the significance threshold is done based on how much historical data over a set period has varied (combined with how much code changed).

So we either we need to know more about noise between runs

This.

we arbitrarily add a size threshold for the change like I had

I think this is probably fine.... I think we can always ignore things if it doesn't seem important?

[lsf37]

In my mind, the issue is this: a one cycle difference from a particular PR being merged is fine. 100 PRs that each increase it by one cycle is less fine. But comparing between singular tests can't capture that, we need time windows.

I agree that this is an issue, but I think it is a separate additional one. I'm just trying to even do the single increment with that test above.

Doing the same check against a sample that is maybe 6 months back or something like 100 runs ago should catch slow drift, because if we have 100 +1 runs then that difference will be significant.

The rust compiler here describes their algorithm: the significance threshold is done based on how much historical data over a set period has varied (combined with how much code changed).

Yes, having played a bit more with the data we have now, just the overall 18 re-runs on the same manifest gives us much better noise data. So I think we do need to start collecting that in a more targeted way.

we arbitrarily add a size threshold for the change like I had

I think this is probably fine.... I think we can always ignore things if it doesn't seem important?

Tried it out, and doing that manually is difficult. Basically, analysing the noise between runs (the method above) determines what that threshold should be, and it is very different for different benchmarks. We have some that are very noisy internally, and we have some that report extreme accuracy, but still vary pretty strongly between runs.

Combining both (past noise between runs + statistical significance test) seems pretty Ok. It still flags more than I would want (e.g. triggers when no relevant code has changed), but they are all things that also look funky when I manually look at the graphs.

I guess another way of getting more data on noise between runs is noting when no relevant code has changed (i.e. changing x86 boot code, and getting a difference flagged for RISC-V IPC). Not sure yet how we would note that, though. Maybe if we use the idea of adding labels to explain flagged runs, we could also have a flag that is a key noise, which would mean that this run for this benchmark is treated as if it was on the same code as before. Which means it would contribute to the past noise calculation without needing an explicitly repeated run.