DPDK patches and discussions
 help / color / mirror / Atom feed
From: "Mattias Rönnblom" <mattias.ronnblom@ericsson.com>
To: "Wiles, Keith" <keith.wiles@intel.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>,
	"stephen@networkplumber.org" <stephen@networkplumber.org>
Subject: Re: [dpdk-dev] [RFC v2 2/2] eal: introduce random generator function with upper bound
Date: Sun, 21 Apr 2019 21:05:36 +0200	[thread overview]
Message-ID: <06bef528-e195-0d42-d4e9-f26e5c9880cd@ericsson.com> (raw)
Message-ID: <20190421190536.c5tq0LaRWcDAK-rTkesp7Y2CwJgGT08zcX8UByBsfgY@z> (raw)
In-Reply-To: <EEB37E32-4A14-442E-96BF-12AA76CF1C51@intel.com>

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.

  parent reply	other threads:[~2019-04-21 19:05 UTC|newest]

Thread overview: 137+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-04-05 13:45 [dpdk-dev] [RFC] eal: make rte_rand() MT safe Mattias Rönnblom
2019-04-05 13:45 ` Mattias Rönnblom
2019-04-05 13:51 ` Mattias Rönnblom
2019-04-05 13:51   ` Mattias Rönnblom
2019-04-05 14:28   ` Bruce Richardson
2019-04-05 14:28     ` Bruce Richardson
2019-04-05 14:56     ` Mattias Rönnblom
2019-04-05 14:56       ` Mattias Rönnblom
2019-04-05 16:57 ` Stephen Hemminger
2019-04-05 16:57   ` Stephen Hemminger
2019-04-05 18:04   ` Mattias Rönnblom
2019-04-05 18:04     ` Mattias Rönnblom
2019-04-05 20:50     ` Stephen Hemminger
2019-04-05 20:50       ` Stephen Hemminger
2019-04-06  5:52       ` Mattias Rönnblom
2019-04-06  5:52         ` Mattias Rönnblom
2019-04-08 12:30       ` [dpdk-dev] [RFC 1/3] Replace lrand48-based rte_rand with LFSR generator Mattias Rönnblom
2019-04-08 12:30         ` Mattias Rönnblom
2019-04-08 12:30         ` [dpdk-dev] [RFC 2/3] Add 32-bit version of rte_rand Mattias Rönnblom
2019-04-08 12:30           ` Mattias Rönnblom
2019-04-08 12:30         ` [dpdk-dev] [RFC 3/3] Introduce random generator functions with upper bound Mattias Rönnblom
2019-04-08 12:30           ` Mattias Rönnblom
2019-04-08 12:47         ` [dpdk-dev] [RFC 1/3] Replace lrand48-based rte_rand with LFSR generator Mattias Rönnblom
2019-04-08 12:47           ` Mattias Rönnblom
2019-04-19 21:21         ` [dpdk-dev] [RFC v2 0/2] Pseudo-number generation improvements Mattias Rönnblom
2019-04-19 21:21           ` Mattias Rönnblom
2019-04-19 21:21           ` [dpdk-dev] [RFC v2 1/2] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-04-19 21:21             ` Mattias Rönnblom
2019-04-22 11:34             ` Neil Horman
2019-04-22 11:34               ` Neil Horman
2019-04-22 14:49               ` Stephen Hemminger
2019-04-22 14:49                 ` Stephen Hemminger
2019-04-22 15:52               ` Mattias Rönnblom
2019-04-22 15:52                 ` Mattias Rönnblom
2019-04-22 17:44                 ` Mattias Rönnblom
2019-04-22 17:44                   ` Mattias Rönnblom
2019-04-23 11:33                   ` Neil Horman
2019-04-23 11:33                     ` Neil Horman
2019-04-23 17:13                     ` Mattias Rönnblom
2019-04-23 17:13                       ` Mattias Rönnblom
2019-04-24 11:37                       ` Neil Horman
2019-04-24 11:37                         ` Neil Horman
2019-04-23 15:31                   ` Stephen Hemminger
2019-04-23 15:31                     ` Stephen Hemminger
2019-04-23 17:17                     ` Mattias Rönnblom
2019-04-23 17:17                       ` Mattias Rönnblom
2019-04-24  7:52                       ` Mattias Rönnblom
2019-04-24  7:52                         ` Mattias Rönnblom
2019-04-24 12:33                         ` [dpdk-dev] [RFC v3 0/2] Pseudo-random number generation improvements Mattias Rönnblom
2019-04-24 12:33                           ` Mattias Rönnblom
2019-04-24 12:33                           ` [dpdk-dev] [RFC v3 1/2] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-04-24 12:33                             ` Mattias Rönnblom
2019-05-08 20:12                             ` Stephen Hemminger
2019-05-08 20:12                               ` Stephen Hemminger
2019-05-08 20:30                               ` Mattias Rönnblom
2019-05-08 20:30                                 ` Mattias Rönnblom
2019-05-09  1:10                                 ` Stephen Hemminger
2019-05-09  1:10                                   ` Stephen Hemminger
2019-05-14  9:20                                   ` [dpdk-dev] [PATCH 0/6] Pseudo-random number generation improvements Mattias Rönnblom
2019-05-14  9:20                                     ` Mattias Rönnblom
2019-05-14  9:20                                     ` [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-05-14  9:20                                       ` Mattias Rönnblom
2019-05-14  9:32                                       ` Mattias Rönnblom
2019-05-14  9:32                                         ` Mattias Rönnblom
2019-05-14 14:16                                       ` Neil Horman
2019-05-14 14:16                                         ` Neil Horman
2019-05-14 14:53                                         ` Mattias Rönnblom
2019-05-14 14:53                                           ` Mattias Rönnblom
2019-05-17 19:27                                           ` Neil Horman
2019-05-17 20:57                                             ` Bruce Richardson
2019-05-17 21:10                                             ` Mattias Rönnblom
2019-05-19 18:32                                               ` Neil Horman
2019-05-14 15:27                                       ` Stephen Hemminger
2019-05-14 15:27                                         ` Stephen Hemminger
2019-05-14  9:20                                     ` [dpdk-dev] [PATCH 2/6] eal: add pseudo-random number generation performance test Mattias Rönnblom
2019-05-14  9:20                                       ` Mattias Rönnblom
2019-05-14  9:20                                     ` [dpdk-dev] [PATCH 3/6] eal: improve entropy for initial PRNG seed Mattias Rönnblom
2019-05-14  9:20                                       ` Mattias Rönnblom
2019-05-14  9:36                                       ` Mattias Rönnblom
2019-05-14  9:36                                         ` Mattias Rönnblom
2019-05-14  9:39                                         ` Bruce Richardson
2019-05-14  9:39                                           ` Bruce Richardson
2019-05-14 11:58                                           ` Mattias Rönnblom
2019-05-14 11:58                                             ` Mattias Rönnblom
2019-05-14  9:37                                       ` Bruce Richardson
2019-05-14  9:37                                         ` Bruce Richardson
2019-05-14  9:20                                     ` [dpdk-dev] [PATCH 4/6] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-05-14  9:20                                       ` Mattias Rönnblom
2019-05-14  9:20                                     ` [dpdk-dev] [PATCH 5/6] eal: add bounded PRNG performance tests Mattias Rönnblom
2019-05-14  9:20                                       ` Mattias Rönnblom
2019-05-14  9:20                                     ` [dpdk-dev] [PATCH 6/6] eal: add pseudo-random number generation to MAINTAINERS Mattias Rönnblom
2019-05-14  9:20                                       ` Mattias Rönnblom
2019-05-16 17:55                                     ` [dpdk-dev] [PATCH v2 0/6] Pseudo-random number generation improvements Mattias Rönnblom
2019-05-16 17:55                                       ` [dpdk-dev] [PATCH v2 1/6] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-05-16 17:55                                       ` [dpdk-dev] [PATCH v2 2/6] eal: add pseudo-random number generation performance test Mattias Rönnblom
2019-05-16 17:55                                       ` [dpdk-dev] [PATCH v2 3/6] eal: improve entropy for initial PRNG seed Mattias Rönnblom
2019-05-16 17:55                                       ` [dpdk-dev] [PATCH v2 4/6] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-05-16 17:55                                       ` [dpdk-dev] [PATCH v2 5/6] eal: add bounded PRNG performance tests Mattias Rönnblom
2019-05-16 17:55                                       ` [dpdk-dev] [PATCH v2 6/6] eal: add PRNG to MAINTAINERS and release notes Mattias Rönnblom
2019-05-16 20:35                                       ` [dpdk-dev] [PATCH v2 0/6] Pseudo-random number generation improvements Bruce Richardson
2019-06-05 10:43                                         ` [dpdk-dev] [PATCH v3 " Mattias Rönnblom
2019-06-05 10:43                                           ` [dpdk-dev] [PATCH v3 1/6] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-06-05 10:43                                           ` [dpdk-dev] [PATCH v3 2/6] eal: add pseudo-random number generation performance test Mattias Rönnblom
2019-06-27 21:23                                             ` Thomas Monjalon
2019-06-28  8:20                                               ` Mattias Rönnblom
2019-06-05 10:43                                           ` [dpdk-dev] [PATCH v3 3/6] eal: improve entropy for initial PRNG seed Mattias Rönnblom
2019-06-05 10:43                                           ` [dpdk-dev] [PATCH v3 4/6] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-06-05 10:43                                           ` [dpdk-dev] [PATCH v3 5/6] eal: add bounded PRNG performance tests Mattias Rönnblom
2019-06-05 10:44                                           ` [dpdk-dev] [PATCH v3 6/6] eal: add PRNG to MAINTAINERS and release notes Mattias Rönnblom
2019-06-27 21:27                                             ` Thomas Monjalon
2019-06-28  8:17                                               ` Mattias Rönnblom
2019-06-15 12:23                                           ` [dpdk-dev] [PATCH v3 0/6] Pseudo-random number generation improvements Mattias Rönnblom
2019-06-28  9:01                                           ` [dpdk-dev] [PATCH v4 0/5] " Mattias Rönnblom
2019-06-28  9:01                                             ` [dpdk-dev] [PATCH v4 1/5] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-06-28  9:01                                             ` [dpdk-dev] [PATCH v4 2/5] eal: add pseudo-random number generation performance test Mattias Rönnblom
2019-06-28  9:01                                             ` [dpdk-dev] [PATCH v4 3/5] eal: improve entropy for initial PRNG seed Mattias Rönnblom
2019-06-28 19:01                                               ` Ferruh Yigit
2019-06-28 20:58                                                 ` Mattias Rönnblom
2019-06-28 21:08                                                   ` [dpdk-dev] [PATCH] eal: use 32-bit RDSEED to allow 32-bit x86 usage Mattias Rönnblom
2019-06-29 12:54                                                     ` Thomas Monjalon
2019-06-28  9:01                                             ` [dpdk-dev] [PATCH v4 4/5] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-06-28  9:01                                             ` [dpdk-dev] [PATCH v4 5/5] eal: add bounded PRNG performance tests Mattias Rönnblom
2019-06-28 13:24                                             ` [dpdk-dev] [PATCH v4 0/5] Pseudo-random number generation improvements Thomas Monjalon
2019-04-24 12:33                           ` [dpdk-dev] [RFC v3 2/2] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-04-24 12:33                             ` Mattias Rönnblom
2019-04-19 21:21           ` [dpdk-dev] [RFC v2 " Mattias Rönnblom
2019-04-19 21:21             ` Mattias Rönnblom
2019-04-20 21:08             ` Wiles, Keith
2019-04-20 21:08               ` Wiles, Keith
2019-04-21 19:05               ` Mattias Rönnblom [this message]
2019-04-21 19:05                 ` Mattias Rönnblom
2019-04-22  4:33                 ` Wiles, Keith
2019-04-22  4:33                   ` Wiles, Keith
2019-04-22  7:07                   ` Mattias Rönnblom
2019-04-22  7:07                     ` Mattias Rönnblom
2019-04-22 13:19                     ` Wiles, Keith
2019-04-22 13:19                       ` Wiles, Keith

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=06bef528-e195-0d42-d4e9-f26e5c9880cd@ericsson.com \
    --to=mattias.ronnblom@ericsson.com \
    --cc=dev@dpdk.org \
    --cc=keith.wiles@intel.com \
    --cc=stephen@networkplumber.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).