From:   "Zhuo, Qiuxu" <qiuxu.zhuo@intel.com>
To:     "paulmck@kernel.org" <paulmck@kernel.org>
CC:     "Joel Fernandes (Google)" <joel@joelfernandes.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        "Frederic Weisbecker" <frederic@kernel.org>,
        Lai Jiangshan <jiangshanlai@gmail.com>,
        "linux-doc@vger.kernel.org" <linux-doc@vger.kernel.org>,
        "rcu@vger.kernel.org" <rcu@vger.kernel.org>,
        "urezki@gmail.com" <urezki@gmail.com>
Subject: RE: [PATCH v3] rcu: Add a minimum time for marking boot as completed
Thread-Topic: [PATCH v3] rcu: Add a minimum time for marking boot as completed
Thread-Index: AQHZThiYp3MlrzfqvEWnd0vYLxlOHa7pzeSAgAOQlXCAAHskAIABB5EggACT3wCAAxGoYA==
Date:   Thu, 9 Mar 2023 15:17:09 +0000
Message-ID: <IA1PR11MB61714CDAF82F337B0A384BAA89B59@IA1PR11MB6171.namprd11.prod.outlook.com>
References: <20230303213851.2090365-1-joel@joelfernandes.org>
 <20230304010251.GD1301832@paulmck-ThinkPad-P17-Gen-1>
 <IA1PR11MB617141A98ADB1F301FCA07E589B69@IA1PR11MB6171.namprd11.prod.outlook.com>
 <20230306144950.GR1301832@paulmck-ThinkPad-P17-Gen-1>
 <IA1PR11MB61710CDB2B6B47118832770E89B79@IA1PR11MB6171.namprd11.prod.outlook.com>
 <20230307152226.GG1301832@paulmck-ThinkPad-P17-Gen-1>
In-Reply-To: <20230307152226.GG1301832@paulmck-ThinkPad-P17-Gen-1>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?5dPi7bXSrryd1Pm7u3/aGrJyAXqubH3Rh4rJvVjc4B+xAaTVIn8PH6y79+J+?=
 =?us-ascii?Q?1+K3ofchtuWPoEpiL7jFBFf9Ltq92G689ZZFEOF+mCYeYP6KazVRfsFapS6D?=
 =?us-ascii?Q?LhIPsgcRjWcF3dxuvCdnZmHhCfbI/WVq3sK0VcMSvzVauUDhz/V9CpaMj2ay?=
 =?us-ascii?Q?LULoIowQpnu2qSCkFQVlBX6X+McuAJ+DwmW9EFrGTHOsFrugzx/0RUHndtog?=
 =?us-ascii?Q?WtLtzbHvmcc7iPhlfQFxl5N7PUvsk3gieqBys2m5XLv4LUpOoi3UQPKrJRwt?=
 =?us-ascii?Q?HemIp4bDck9axB28WifzcoHAki9FYJk6wvfWC26jYlBqie34F4uQz3kroYhe?=
 =?us-ascii?Q?FocurxLhe9l6/eTVsIx7sH4k4RnXCy8QeApyoRUId4DaygZ3jlGIRxtaQyEY?=
 =?us-ascii?Q?jhtv1VerLiAFgYgb5ohT93cp7Powd/2bntStwF+Q0Zpc6Tg0gDm+v/Vkt8Ua?=
 =?us-ascii?Q?TUYyvWKjuV/06QYCKLqrXl8EcuF4+ASmopJVI7txPuIxGLlk1SKhnaj0tr+K?=
 =?us-ascii?Q?e46nw5/+2wlxYOd2kcUzwNjQuuIXomXzx9Kv0MvPYK7DE+5INrioC3fCWYro?=
 =?us-ascii?Q?GBPhotEXCYOi3WGqxKlyRUke3g6KO0xT83HqxcPfPBO5yQmo7nwdjQCusqIN?=
 =?us-ascii?Q?/b6jmwFoWWXQ3BxAtvVILd7yEALjz+wjSRLI1hlckr0aOmpzZKoTECf7HTyf?=
 =?us-ascii?Q?qPYC74600Ze7RBuf2fgkQEWqXmLRNELmUoGBdK9SGtYyVhIt0okJwsqG8C+z?=
 =?us-ascii?Q?Ot11rvdG8z3X7lMYWGQ3N6zKLMWUOwyD2eti2AVLDBWhULJSXPgXJVuvztbe?=
 =?us-ascii?Q?+9RTcN86uArOEcTwNmferruFozVuipICccQYfqM8QFFumV0gbzN9Jba3N4Tp?=
 =?us-ascii?Q?gKTwhzThHH+o7GdtnmvG/Usb3PDK+HpoFruk3wNbLRW499MxNqtQgYkia0u+?=
 =?us-ascii?Q?9H9o1E9OnShu/gXMs93seRPT3neQt0mYl3BsXiyAhXRuOyFfV/6l/1NjB7bG?=
 =?us-ascii?Q?ypDiTfULTwBR7/8kdImoBstyosodfW+EhMJDuUB+UpvJrfL1Bdd5eOxpQgnh?=
 =?us-ascii?Q?9t74nMN20mODKnK24xkHwd/K2MA8Yn0BhhRwOJFr16Q9BL4AEO3+vzTDDGwx?=
 =?us-ascii?Q?WPSJ0ewqV1khIRR+Zhpj7hsEzKwZZz2kks9KhAXPTPM/GylCuqKlg2eGRmQc?=
 =?us-ascii?Q?tUznjHPo1EfimXzGGqb3bBuSguNTj1mpZEqz06GNYx6vGxEhPHAOcBfgiIB0?=
 =?us-ascii?Q?pKyQfZcRjpGY4mWLxY0zvYXfa9mhbfWgLjzplPv4vWXT7rGjrUu1aY8eaNq4?=
 =?us-ascii?Q?FShBu+zfG/6a+SxwPlSxu9LlmP3QJ8bHgrnv9X2LDq3QmNKQx0vuPMg2C9Aj?=
 =?us-ascii?Q?mYdc9NGFt2gUe5VXp7PnDex8YuvEd9C2HUARCcIoVIHrRwqthfVnS7xCqr92?=
 =?us-ascii?Q?rLuSaGP9smw+vsAoysSESrliiIPLWBjuRRDEIJEfM43gzkT47brE4+AUdzmQ?=
 =?us-ascii?Q?8eQgpuXMwWTuIhTqPrcEQxNHng2q9MEKThfa08mvMJ0CXLqTPohrmW0psWSx?=
 =?us-ascii?Q?XlQ9ksLGHZeyaW1i6vTfVblz6AVgCyH+wuISxT6Y?=
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: IA1PR11MB6171.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: c182a681-4191-47a5-eae8-08db20b15a23
X-MS-Exchange-CrossTenant-originalarrivaltime: 09 Mar 2023 15:17:09.6035
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: fag8ZJNfHEyR5oGY63JizfSJpXSO9m5KJjgJjutz3a9AXgAlgDjmbvZuZXYws2WGjEcd2Qe6oQCH0e/OkvPy+g==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SJ2PR11MB7646
X-OriginatorOrg: intel.com
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

> 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=
.
>=20
> That single standard deviation means that you have 68% confidence that th=
e
> 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=20
difference between a and b.=20

> > The calculated standard deviations are via:
> > https://www.gigacalculator.com/calculators/standard-deviation-calculat
> > or.php
>=20
> Fair enough.  Formulas are readily available as well, and most spreadshee=
ts
> support standard deviation.
>=20
> [...]
>
> > > 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.
>=20
> 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.=20

> >    35/48 b's data points are less than 0.1 less than a's median.
> >    For a's binomial distribution P(X >=3D 35) =3D 0.1%, where p=3D0.5.
> >    So, we have strong confidence that b is 100ms faster than a.
>=20
> 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 t=
o
> 8.95 in this experiment does give some pause.  These are after all suppos=
edly
> 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 differ=
ent
> CPU clock frequency?

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

      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 tha=
n=20
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.
>=20
> In contrast, the median of the old b is 8.2, which gives extreme confiden=
ce.
> So let's be conservative and use the large-set median.
>=20
> In real life, additional procedures would be needed to estimate the
> confidence in the median, which turns oout to be nontrivial.  When I appl=
y

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 enou=
gh=20
difference between a and b, right?

> The easiest way to estimate bounds on the median is to "bootstrap", but t=
hat
> 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 =3D 8.9 - 0.4 =3D 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 =3D 7/48
> > =3D 0.1458
> This is only 85.4% significant, so...
>=20
> >    For a's binomial distribution P(X >=3D 24) =3D 0.0%, where p=3D0.145=
8.
> >    So, looks like we have confidence that b is 400ms faster than a.
>=20
> ...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.=20

>=20
> Plus, you really should select the speedup and only then take the
> measurements.  Otherwise, you end up fitting noise.
>=20
> However, assuming identical tests setups, you really can calculate the me=
dian
> from the full data set.
>=20
> >    The calculated cumulative binomial distributions P(X) is via:
> >
> > https://www.gigacalculator.com/calculators/binomial-probability-calcul
> > ator.php
>=20
> The maxima program's binomial() function agrees with it, so good.  ;-)
>=20
> >    I apologize if this analysis/discussion bored some of you. ;-)
>=20
> 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.=20

> But I am good with the 98.3% confidence in a 100ms improvement.
>=20
> 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.=20

-Qiuxu