From: "Wiles, Keith" <keith.wiles@intel.com>
To: "Mattias Rönnblom" <mattias.ronnblom@ericsson.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: Sat, 20 Apr 2019 21:08:05 +0000 [thread overview]
Message-ID: <EEB37E32-4A14-442E-96BF-12AA76CF1C51@intel.com> (raw)
Message-ID: <20190420210805.osDagDBIqgKPX3C1B0uGBK9LjOC6zydHHuf0ppkFJt8@z> (raw)
In-Reply-To: <20190419212138.17422-3-mattias.ronnblom@ericsson.com>
> On Apr 19, 2019, at 5:21 PM, Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
>
> Add a function rte_rand_max() which generates an uniformly distributed
> pseudo-random number less than a user-specified upper bound.
>
> The commonly used pattern rte_rand() % SOME_VALUE, in addition to
> being slow, also creates biased results if SOME_VALUE is not a power
> of 2. This bias is very small for small SOME_VALUE, but increases
> linearly with larger SOME_VALUE.
>
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> ---
> lib/librte_eal/common/include/rte_random.h | 16 ++++++++++++++++
> lib/librte_eal/common/rte_random.c | 20 ++++++++++++++++++++
> lib/librte_eal/rte_eal_version.map | 1 +
> 3 files changed, 37 insertions(+)
>
> diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
> index 66dfe8ae7..053912168 100644
> --- a/lib/librte_eal/common/include/rte_random.h
> +++ b/lib/librte_eal/common/include/rte_random.h
> @@ -47,6 +47,22 @@ rte_srand(uint64_t seedval);
> uint64_t
> rte_rand(void);
>
> +/**
> + * Generates a pseudo-random number less than upper_bound.
> + *
> + * This function returns an uniformly distributed (unbiased) random
> + * number lower than a user-specified maximum value.
> + *
> + * If called from lcore threads, this function is thread-safe.
> + *
> + * @param upper_bound
> + * The upper bound of the generated number.
> + * @return
> + * A pseudo-random value between 0 and (upper_bound-1).
> + */
> +uint64_t
> +rte_rand_max(uint64_t upper_bound);
> +
> #ifdef __cplusplus
> }
> #endif
> diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> index 288e7b8c5..bf9240470 100644
> --- a/lib/librte_eal/common/rte_random.c
> +++ b/lib/librte_eal/common/rte_random.c
> @@ -131,6 +131,26 @@ rte_rand(void)
> return __rte_rand_lfsr258(state);
> }
>
> +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 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?
> +
> + return res;
> +}
> +
> RTE_INIT(rte_rand_init)
> {
> rte_srand(rte_get_timer_cycles());
> diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
> index 0d60668fa..8f5b8c6a6 100644
> --- a/lib/librte_eal/rte_eal_version.map
> +++ b/lib/librte_eal/rte_eal_version.map
> @@ -367,6 +367,7 @@ EXPERIMENTAL {
> rte_mp_sendmsg;
> rte_option_register;
> rte_rand;
> + rte_rand_max;
> rte_realloc_socket;
> rte_service_lcore_attr_get;
> rte_service_lcore_attr_reset_all;
> --
> 2.17.1
>
Regards,
Keith
next prev parent reply other threads:[~2019-04-20 21:08 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 [this message]
2019-04-20 21:08 ` Wiles, Keith
2019-04-21 19:05 ` Mattias Rönnblom
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=EEB37E32-4A14-442E-96BF-12AA76CF1C51@intel.com \
--to=keith.wiles@intel.com \
--cc=dev@dpdk.org \
--cc=mattias.ronnblom@ericsson.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).