From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail.lysator.liu.se (mail.lysator.liu.se [130.236.254.3]) by dpdk.org (Postfix) with ESMTP id 52B771B489 for ; 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 ; 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" Cc: "dev@dpdk.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> From: =?UTF-8?Q?Mattias_R=c3=b6nnblom?= 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: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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: Received: from dpdk.org (dpdk.org [92.243.14.124]) by dpdk.space (Postfix) with ESMTP id 7A238A05D3 for ; 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 ; 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 ; 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" Cc: "dev@dpdk.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> From: =?UTF-8?Q?Mattias_R=c3=b6nnblom?= 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: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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.