From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <dev-bounces@dpdk.org>
Received: from dpdk.org (dpdk.org [92.243.14.124])
	by dpdk.space (Postfix) with ESMTP id 98E74A05D3
	for <public@inbox.dpdk.org>; Mon, 22 Apr 2019 06:38:08 +0200 (CEST)
Received: from [92.243.14.124] (localhost [127.0.0.1])
	by dpdk.org (Postfix) with ESMTP id B5AA31B1EE;
	Mon, 22 Apr 2019 06:38:06 +0200 (CEST)
Received: from mga17.intel.com (mga17.intel.com [192.55.52.151])
 by dpdk.org (Postfix) with ESMTP id D230B4CA7
 for <dev@dpdk.org>; Mon, 22 Apr 2019 06:38:04 +0200 (CEST)
X-Amp-Result: SKIPPED(no attachment in message)
X-Amp-File-Uploaded: False
Received: from orsmga003.jf.intel.com ([10.7.209.27])
 by fmsmga107.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;
 21 Apr 2019 21:38:02 -0700
X-ExtLoop1: 1
X-IronPort-AV: E=Sophos;i="5.60,380,1549958400"; d="scan'208";a="144592220"
Received: from fmsmsx106.amr.corp.intel.com ([10.18.124.204])
 by orsmga003.jf.intel.com with ESMTP; 21 Apr 2019 21:33:03 -0700
Received: from fmsmsx114.amr.corp.intel.com (10.18.116.8) by
 FMSMSX106.amr.corp.intel.com (10.18.124.204) with Microsoft SMTP Server (TLS)
 id 14.3.408.0; Sun, 21 Apr 2019 21:33:02 -0700
Received: from fmsmsx117.amr.corp.intel.com ([169.254.3.26]) by
 FMSMSX114.amr.corp.intel.com ([169.254.6.228]) with mapi id 14.03.0415.000;
 Sun, 21 Apr 2019 21:33:02 -0700
From: "Wiles, Keith" <keith.wiles@intel.com>
To: =?iso-8859-1?Q?Mattias_R=F6nnblom?= <mattias.ronnblom@ericsson.com>
CC: "dev@dpdk.org" <dev@dpdk.org>, "stephen@networkplumber.org"
 <stephen@networkplumber.org>
Thread-Topic: [dpdk-dev] [RFC v2 2/2] eal: introduce random generator
 function with upper bound
Thread-Index: AQHU+HU6QoHfz9YxXUS0jvb0DcAh1aZHmAZ+
Date: Mon, 22 Apr 2019 04:33:01 +0000
Message-ID: <4440C41D-23E4-4A46-8C8A-3AA2ECB59C40@intel.com>
References: <20190408123029.6701-1-mattias.ronnblom@ericsson.com>
 <20190419212138.17422-1-mattias.ronnblom@ericsson.com>
 <20190419212138.17422-3-mattias.ronnblom@ericsson.com>
 <EEB37E32-4A14-442E-96BF-12AA76CF1C51@intel.com>,
 <06bef528-e195-0d42-d4e9-f26e5c9880cd@ericsson.com>
In-Reply-To: <06bef528-e195-0d42-d4e9-f26e5c9880cd@ericsson.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: 
X-MS-TNEF-Correlator: 
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: Re: [dpdk-dev] [RFC v2 2/2] eal: introduce random generator
 function with upper bound
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
 <mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://mails.dpdk.org/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://mails.dpdk.org/listinfo/dev>,
 <mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>
Message-ID: <20190422043301.AoXvN1X5cUa0Mfa7bRs25bntzAZhMHeFLZ6QgOK4D4o@z>



Sent from my iPhone

> On Apr 21, 2019, at 2:05 PM, Mattias R=F6nnblom <mattias.ronnblom@ericsso=
n.com> wrote:
>=20
> On 2019-04-20 23:08, Wiles, Keith wrote:
>=20
>>> +uint64_t __rte_experimental
>>> +rte_rand_max(uint64_t upper_bound)
>>> +{
>>> +    uint8_t zeros;
>>> +    uint64_t mask =3D ~((uint64_t)0);
>>> +    uint64_t res;
>>> +
>>> +    if (upper_bound < 2)
>>> +        return 0;
>>> +
>>> +    zeros =3D __builtin_clzll(upper_bound);
>>> +    mask >>=3D zeros;
>>> +
>>> +    do {
>>> +        res =3D rte_rand() & mask;
>>> +    } while (unlikely(res >=3D upper_bound));
>> My concern here is the numbers of times this loop could be executed as t=
he upper bound could be just over a power of 2 and it is a large number mea=
ning the number of values above upper max and the power of 2 could be huge.=
 Am I looking this loop correctly. If my thought process is correct it coul=
d take a long time to get a value less tha n upper max, correct?
>=20
> If the number of values over the limit is huge, so is the value range bel=
ow it.
>=20
>> If every thing aligns in a bad way it could be a large number of loops a=
nd cause all kinds of problems. What could be done here or is this a non-is=
sue?
>=20
> Formally, the execution has no upper bound, but in practice I think this =
is a non-issue.
>=20
> The cycle cost of an iteration of the loop (including the rte_rand() call=
) is ~10 cc. With the worst-case upper_limit, the probability of having to =
redo the rte_rand() call is ~0.5, for every iteration. This is with a pseud=
o-random number generator featuring an uniform distribution.
>=20
> Let's assume we care about determinism, and we have a system which suffer=
s a catastrophic failure if the rte_rand_max() latency is more than 10k clo=
ck cycles. The system performs 10M rte_rand_max() calls per second.
>=20
> The probability of this system running for a year without any rte_rand_ma=
x()-related crashes is:
> 0.99999999999999999999999999999999999999999999999999999999999999999999999=
999999999999999999999999999999999999999999999999999999999999999999999999999=
999999999999999999999999999999999999999999999999999999999999999999999999999=
999999999999999999999999999999999999999999999999999999999999999997056859852=
6
>=20
> So crashes due to excessive rte_rand_max() latency may occur, but this ri=
sk is dwarfed by that of the system being hit by an asteroid.
>=20
> (Btw, I doubt even the people in our sales force have seen that many nine=
s before.)
>=20
> From a performance point of view, the high-loop-count cases are rare enou=
gh not to pose a serious threat. For example, being forced to redo rte_rand=
() more than five times is only a ~3% risk.

Even a few loops can have an effect on performance when we are talking abou=
t micro-seconds plus it leads to indeterminate results. The numbers you rep=
orted here are interesting, but I would be happier if you added a limit to =
the loop. If you state the likely hood of doing 5 loops is only 3% then add=
ing a loop limit would be reasonable, right?