[dpdk-dev] [RFC v2 2/2] eal: introduce random generator function with upper bound
Mattias Rönnblom
mattias.ronnblom at ericsson.com
Sun Apr 21 21:05:36 CEST 2019
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.
More information about the dev
mailing list