From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <SRS0+FTTI=SX=ericsson.com=mattias.ronnblom@lysator.liu.se>
Received: from mail.lysator.liu.se (mail.lysator.liu.se [130.236.254.3])
by dpdk.org (Postfix) with ESMTP id 52B771B489
for <dev@dpdk.org>; Sun, 21 Apr 2019 21:05:40 +0200 (CEST)
Received: from mail.lysator.liu.se (localhost [127.0.0.1])
by mail.lysator.liu.se (Postfix) with ESMTP id B84BE40003
for <dev@dpdk.org>; Sun, 21 Apr 2019 21:05:39 +0200 (CEST)
Received: by mail.lysator.liu.se (Postfix, from userid 1004)
id A009B40014; Sun, 21 Apr 2019 21:05:39 +0200 (CEST)
X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on
bernadotte.lysator.liu.se
X-Spam-Level:
X-Spam-Status: No, score=-1.0 required=5.0 tests=ALL_TRUSTED
autolearn=disabled version=3.4.1
X-Spam-Score: -1.0
Received: from [192.168.1.59] (host-95-192-230-180.mobileonline.telia.com
[95.192.230.180])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by mail.lysator.liu.se (Postfix) with ESMTPSA id 6546D40003;
Sun, 21 Apr 2019 21:05:37 +0200 (CEST)
To: "Wiles, Keith" <keith.wiles@intel.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>,
"stephen@networkplumber.org" <stephen@networkplumber.org>
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>
From: =?UTF-8?Q?Mattias_R=c3=b6nnblom?= <mattias.ronnblom@ericsson.com>
Message-ID: <06bef528-e195-0d42-d4e9-f26e5c9880cd@ericsson.com>
Date: Sun, 21 Apr 2019 21:05:36 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
Thunderbird/60.6.1
MIME-Version: 1.0
In-Reply-To: <EEB37E32-4A14-442E-96BF-12AA76CF1C51@intel.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
X-Virus-Scanned: ClamAV using ClamSMTP
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>
X-List-Received-Date: Sun, 21 Apr 2019 19:05:40 -0000
On 2019-04-20 23:08, Wiles, Keith wrote:
>> +uint64_t __rte_experimental
>> +rte_rand_max(uint64_t upper_bound)
>> +{
>> + uint8_t zeros;
>> + uint64_t mask = ~((uint64_t)0);
>> + uint64_t res;
>> +
>> + if (upper_bound < 2)
>> + return 0;
>> +
>> + zeros = __builtin_clzll(upper_bound);
>> + mask >>= zeros;
>> +
>> + do {
>> + res = rte_rand() & mask;
>> + } while (unlikely(res >= upper_bound));
>
> My concern here is the numbers of times this loop could be executed as the upper bound could be just over a power of 2 and it is a large number meaning 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 could take a long time to get a value less tha n upper max, correct?
>
If the number of values over the limit is huge, so is the value range
below it.
> If every thing aligns in a bad way it could be a large number of loops and cause all kinds of problems. What could be done here or is this a non-issue?
Formally, the execution has no upper bound, but in practice I think this
is a non-issue.
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 pseudo-random number generator featuring an uniform distribution.
Let's assume we care about determinism, and we have a system which
suffers a catastrophic failure if the rte_rand_max() latency is more
than 10k clock cycles. The system performs 10M rte_rand_max() calls per
second.
The probability of this system running for a year without any
rte_rand_max()-related crashes is:
0.999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999970568598526
So crashes due to excessive rte_rand_max() latency may occur, but this
risk is dwarfed by that of the system being hit by an asteroid.
(Btw, I doubt even the people in our sales force have seen that many
nines before.)
From a performance point of view, the high-loop-count cases are rare
enough not to pose a serious threat. For example, being forced to redo
rte_rand() more than five times is only a ~3% risk.
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 7A238A05D3
for <public@inbox.dpdk.org>; Sun, 21 Apr 2019 21:05:42 +0200 (CEST)
Received: from [92.243.14.124] (localhost [127.0.0.1])
by dpdk.org (Postfix) with ESMTP id 0B0FA1B4C0;
Sun, 21 Apr 2019 21:05:41 +0200 (CEST)
Received: from mail.lysator.liu.se (mail.lysator.liu.se [130.236.254.3])
by dpdk.org (Postfix) with ESMTP id 52B771B489
for <dev@dpdk.org>; Sun, 21 Apr 2019 21:05:40 +0200 (CEST)
Received: from mail.lysator.liu.se (localhost [127.0.0.1])
by mail.lysator.liu.se (Postfix) with ESMTP id B84BE40003
for <dev@dpdk.org>; Sun, 21 Apr 2019 21:05:39 +0200 (CEST)
Received: by mail.lysator.liu.se (Postfix, from userid 1004)
id A009B40014; Sun, 21 Apr 2019 21:05:39 +0200 (CEST)
X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on
bernadotte.lysator.liu.se
X-Spam-Level:
X-Spam-Status: No, score=-1.0 required=5.0 tests=ALL_TRUSTED
autolearn=disabled version=3.4.1
X-Spam-Score: -1.0
Received: from [192.168.1.59] (host-95-192-230-180.mobileonline.telia.com
[95.192.230.180])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by mail.lysator.liu.se (Postfix) with ESMTPSA id 6546D40003;
Sun, 21 Apr 2019 21:05:37 +0200 (CEST)
To: "Wiles, Keith" <keith.wiles@intel.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>,
"stephen@networkplumber.org" <stephen@networkplumber.org>
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>
From: =?UTF-8?Q?Mattias_R=c3=b6nnblom?= <mattias.ronnblom@ericsson.com>
Message-ID: <06bef528-e195-0d42-d4e9-f26e5c9880cd@ericsson.com>
Date: Sun, 21 Apr 2019 21:05:36 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
Thunderbird/60.6.1
MIME-Version: 1.0
In-Reply-To: <EEB37E32-4A14-442E-96BF-12AA76CF1C51@intel.com>
Content-Type: text/plain; charset="UTF-8"; format="flowed"
Content-Language: en-US
Content-Transfer-Encoding: 7bit
X-Virus-Scanned: ClamAV using ClamSMTP
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: <20190421190536.c5tq0LaRWcDAK-rTkesp7Y2CwJgGT08zcX8UByBsfgY@z>
On 2019-04-20 23:08, Wiles, Keith wrote:
>> +uint64_t __rte_experimental
>> +rte_rand_max(uint64_t upper_bound)
>> +{
>> + uint8_t zeros;
>> + uint64_t mask = ~((uint64_t)0);
>> + uint64_t res;
>> +
>> + if (upper_bound < 2)
>> + return 0;
>> +
>> + zeros = __builtin_clzll(upper_bound);
>> + mask >>= zeros;
>> +
>> + do {
>> + res = rte_rand() & mask;
>> + } while (unlikely(res >= upper_bound));
>
> My concern here is the numbers of times this loop could be executed as the upper bound could be just over a power of 2 and it is a large number meaning 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 could take a long time to get a value less tha n upper max, correct?
>
If the number of values over the limit is huge, so is the value range
below it.
> If every thing aligns in a bad way it could be a large number of loops and cause all kinds of problems. What could be done here or is this a non-issue?
Formally, the execution has no upper bound, but in practice I think this
is a non-issue.
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 pseudo-random number generator featuring an uniform distribution.
Let's assume we care about determinism, and we have a system which
suffers a catastrophic failure if the rte_rand_max() latency is more
than 10k clock cycles. The system performs 10M rte_rand_max() calls per
second.
The probability of this system running for a year without any
rte_rand_max()-related crashes is:
0.999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999970568598526
So crashes due to excessive rte_rand_max() latency may occur, but this
risk is dwarfed by that of the system being hit by an asteroid.
(Btw, I doubt even the people in our sales force have seen that many
nines before.)
From a performance point of view, the high-loop-count cases are rare
enough not to pose a serious threat. For example, being forced to redo
rte_rand() more than five times is only a ~3% risk.