RE: [PATCH v3] rcu: Add a minimum time for marking boot as completed

Zhuo, Qiuxu
2023-03-09T15:31:16Z

> From: Paul E. McKenney <paulmck@kernel.org>
> [...]
> >
> > a's standard deviation is ~0.4.
> > b's standard deviation is ~0.5.
> >
> > a's average 9.0 is at the upbound of the standard deviation of b's [8.0, 9].
> > So, the measurements should be statistically significant to some degree.
>
> That single standard deviation means that you have 68% confidence that the
> difference is real. This is not far above the 50% leval of random noise.
> 95% is the lowest level that is normally considered to be statistically
> significant.

95% means there is no overlap between two standard deviations of a
and two standard deviations of b.

This relies on either much less noise during testing or a big enough
difference between a and b.

> > The calculated standard deviations are via:
> > https://www.gigacalculator.com/calculators/standard-deviation-calculat
> > or.php
>
> Fair enough. Formulas are readily available as well, and most spreadsheets
> support standard deviation.
>
> [...]
>
> > > Why don't you try applying this approach to the new data? You will
> > > need the general binomial formula.
> >
> > Thank you Paul for the suggestion.
> > I just tried it, but not sure whether my analysis was correct ...
> >
> > Analysis 1:
> > a's median is 8.9.
>
> I get 8.95, which is the average of the 24th and 25th members of a in
> numerical order.

Yes, it should be 8.95. Thanks for correcting me.

> > 35/48 b's data points are less than 0.1 less than a's median.
> > For a's binomial distribution P(X >= 35) = 0.1%, where p=0.5.
> > So, we have strong confidence that b is 100ms faster than a.
>
> I of course get quite a bit stronger confidence, but your 99.9% is good
> enough. And I get even stronger confidence going in the other direction.
> However, the fact that a's median varies from 8.7 in the old experiment to
> 8.95 in this experiment does give some pause. These are after all supposedly
> drawn from the same distribution. Or did you use a different machine or
> different OS version or some such in the two sets of measurements?
> Different time of day and thus different ambient temperature, thus different
> CPU clock frequency?

All the testing setups were identical except for the testing time.

Old a median : 8.7
New a median : 8.95

Old b median : 8.2
New b median : 8.45

I'm a bit surprised that both new medians are exactly greater 0.25 more than
the old medians. Coincidence?

> Assuming identical test setups, let's try the old value of 8.7 from old a to new
> b. There are 14 elements in new b greater than 8.6, for a probability of
> 0.17%, or about 98.3% significance. This is still OK.
>
> In contrast, the median of the old b is 8.2, which gives extreme confidence.
> So let's be conservative and use the large-set median.
>
> In real life, additional procedures would be needed to estimate the
> confidence in the median, which turns oout to be nontrivial. When I apply

Luckily, I could just simply pick up the medians in numerical order in this case. ;-)

> this sort of technique, I usually have all data from each sample being on one
> side of the median of the other, which simplifies things. ;-)

I like all data points are on one side of the median of the other ;-)

But this also relies on either much less noise during testing or a big enough
difference between a and b, right?

> The easiest way to estimate bounds on the median is to "bootstrap", but that
> works best if you have 1000 samples and can randomly draw 1000 sub-
> samples each of size 10 from the larger sample and compute the median of
> each. You can sort these medians and obtain a cumulative distribution.

Good to know "bootstap".

> But you have to have an extremely good reason to collect data from 1000
> boots, and I don't believe we have that good of a reason.
>

1000 boots, Oh my ...
No. No. I don't have a good reason for that ;-)

> > Analysis 2:
> > a's median - 0.4 = 8.9 - 0.4 = 8.5.
> > 24/48 b's data points are less than 0.4 less than a's median.
> > The probability that a's data points are less than 8.5 is p = 7/48
> > = 0.1458
> This is only 85.4% significant, so...
>
> > For a's binomial distribution P(X >= 24) = 0.0%, where p=0.1458.
> > So, looks like we have confidence that b is 400ms faster than a.
>
> ...we really cannot say anything about 400ms faster. Again, you need 95%
> and preferably 99% to really make any sort of claim. You probably need
> quite a few more samples to say much about 200ms, let alone 400ms.

OK. Thanks for correcting me.

>
> Plus, you really should select the speedup and only then take the
> measurements. Otherwise, you end up fitting noise.
>
> However, assuming identical tests setups, you really can calculate the median
> from the full data set.
>
> > The calculated cumulative binomial distributions P(X) is via:
> >
> > https://www.gigacalculator.com/calculators/binomial-probability-calcul
> > ator.php
>
> The maxima program's binomial() function agrees with it, so good. ;-)
>
> > I apologize if this analysis/discussion bored some of you. ;-)
>
> Let's just say that it is a lot simpler when you are measuring larger
> differences in data with tighter distributions. Me, I usually just say "no" to
> drawing any sort of conclusion from data sets that overlap this much.
> Instead, I might check to see if there is some random events adding noise to
> the boot duration, eliminate that, and hopefully get data that is easier to
> analyze.

Agree.

> But I am good with the 98.3% confidence in a 100ms improvement.
>
> So if Joel wishes to make this point, he should feel free to take both of your
> datasets and use the computation with the worse mean.

Thank you so much Paul for your patience and detailed comments.

-Qiuxu