From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by dpdk.org (Postfix) with ESMTP id D230B4CA7 for ; 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" To: =?iso-8859-1?Q?Mattias_R=F6nnblom?= CC: "dev@dpdk.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> , <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="iso-8859-1" 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 22 Apr 2019 04:38:05 -0000 Sent from my iPhone > On Apr 21, 2019, at 2:05 PM, Mattias R=F6nnblom 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? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by dpdk.space (Postfix) with ESMTP id 98E74A05D3 for ; 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 ; 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" To: =?iso-8859-1?Q?Mattias_R=F6nnblom?= CC: "dev@dpdk.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> , <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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Message-ID: <20190422043301.AoXvN1X5cUa0Mfa7bRs25bntzAZhMHeFLZ6QgOK4D4o@z> Sent from my iPhone > On Apr 21, 2019, at 2:05 PM, Mattias R=F6nnblom 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?