pie: floating point fixes
cover pie: floating point fixes
A couple of small untested changes to address some issues found while reviewing usage of random in DPDK.
The PIE code should get rexamined in later release. It should not be exposing internal algorithm, that makes it brittle for ABI.
Also, no code in DPDK should ever be doing floating point math in the data path!
Stephen Hemminger (2):
rte_pie: remove unnecessary floating point
rte_pie: fix incorrect floating point math
lib/sched/rte_pie.h | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-)
Signature · 1 line
2.35.1
PATCH 1/2 rte_pie: remove unnecessary floating point
The qdelay variable is derived from and compared to 64 bit value so it doesn't have to be floating point.
--- lib/sched/rte_pie.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/sched/rte_pie.h +1 -1
@@ -218,7 +218,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) {uint64_t rand_value; -double qdelay = pie_cfg->qdelay_ref *0.5 ; +uint64_t qdelay = pie_cfg->qdelay_ref /2 ;/* PIE is active but the queue is not congested: return 0 */ if (((pie->qdelay_old < qdelay) && (pie->drop_prob < 0.2)) ||
Signature · 1 line
2.35.1
PATCH 2/2 rte_pie: fix incorrect floating point math
In reply to Stephen HemmingerThe function rte_pie_drop was attempting to do a random probability drop, but because of incorrect usage of fixed point divide it would always return 1.
Change to use multiply to compute the probability.
--- lib/sched/rte_pie.h | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)
lib/sched/rte_pie.h +1 -4
@@ -217,7 +217,6 @@ __rte_experimental _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) { - uint64_t rand_value; uint64_t qdelay = pie_cfg->qdelay_ref / 2;/* PIE is active but the queue is not congested: return 0 */
@@ -240,9 +239,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg,if (pie->accu_prob >=8.5 )return 1 ; - rand_value =rte_rand ()/RTE_RAND_MAX ; - -if ((double )rand_value < pie->drop_prob) { +if (rte_rand () < (uint64_t )RTE_RAND_MAX * pie->drop_prob) { pie->accu_prob =0 ;return 1 ; }
Signature · 1 line
2.35.1
Quoted 7 lines
From: Stephen Hemminger [mailto:[email protected]]
Sent: Tuesday, 24 May 2022 20.46A couple of small untested changes to address some issues found while reviewing usage of random in DPDK.
The PIE code should get rexamined in later release.
Untested fixes to seemingly untested code. What's not to like? ;-)
Quoted 2 lines
It should not be exposing internal algorithm, that makes it brittle for ABI.
Agree. Just look at the mempool... an increasing amount of its internals are getting elevated to public API, so other code can understand and use its internals instead of going through its API. (My current pet peeve.)
Quoted 3 lines
Also, no code in DPDK should ever be doing floating point math in the data path!
+1
Quoted 4 lines
Stephen Hemminger (2):
rte_pie: remove unnecessary floating point
rte_pie: fix incorrect floating point math
This looks much better than what it replaces, so...
v2 cover pie: fix random number issues
In reply to Stephen HemmingerAlternate way to fix PIE use of random by introducing a fast way to get a random floating point number. It ends up not needing floating point math.
Stephen Hemminger (3):
random: add rte_rand_float()
rte_pie: remove unnecessary floating point
rte_pie: fix incorrect floating point math
app/test/test_rand_perf.c | 7 +++++++ doc/guides/rel_notes/release_22_07.rst | 5 +++++ lib/eal/common/rte_random.c | 21 +++++++++++++++++++++ lib/eal/include/rte_random.h | 17 +++++++++++++++++ lib/eal/version.map | 1 + lib/sched/rte_pie.h | 7 ++----- 6 files changed, 53 insertions(+), 5 deletions(-)
Signature · 1 line
2.35.1
PATCH v2 1/3 random: add rte_rand_float()
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to erand48_r in the standard library.
--- app/test/test_rand_perf.c | 7 +++++++ doc/guides/rel_notes/release_22_07.rst | 5 +++++ lib/eal/common/rte_random.c | 21 +++++++++++++++++++++ lib/eal/include/rte_random.h | 17 +++++++++++++++++ lib/eal/version.map | 1 + 5 files changed, 51 insertions(+)
app/test/test_rand_perf.c +7 -0
@@ -20,6 +20,7 @@ static volatile uint64_t vsum;enum rand_type { rand_type_64, + rand_type_float, rand_type_bounded_best_case, rand_type_bounded_worst_case };
@@ -30,6 +31,8 @@ rand_type_desc(enum rand_type rand_type)switch (rand_type) {case rand_type_64:return "Full 64-bit [rte_rand()]" ; +case rand_type_float: +return "Floating point [rte_rand_float()]" ;case rand_type_bounded_best_case:return "Bounded average best-case [rte_rand_max()]" ;case rand_type_bounded_worst_case:
@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=rte_rand_float () *UINT64_MAX ; +break ;case rand_type_bounded_best_case: sum +=rte_rand_max (BEST_CASE_BOUND );break ;
@@ -83,6 +89,7 @@ test_rand_perf(void)printf ("Pseudo-random number generation latencies:\n" );test_rand_perf_type (rand_type_64); +test_rand_perf_type (rand_type_float);test_rand_perf_type (rand_type_bounded_best_case);test_rand_perf_type (rand_type_bounded_worst_case);
doc/guides/rel_notes/release_22_07.rst +5 -0
@@ -104,6 +104,11 @@ New Features * ``RTE_EVENT_QUEUE_ATTR_WEIGHT`` * ``RTE_EVENT_QUEUE_ATTR_AFFINITY`` +* ** Added function get random floating point number.** + + Added the function ``rte_rand_float()`` to provide a pseudo-random + floating point number. + Removed Items -------------
lib/eal/common/rte_random.c +21 -0
@@ -6,6 +6,7 @@#include <x86intrin.h> #endif #include <unistd.h> +#include <ieee754.h> #include <rte_branch_prediction.h> #include <rte_cycles.h>
@@ -173,6 +174,26 @@ rte_rand_max(uint64_t upper_bound)return res; } +double +rte_rand_float (void ) +{ +struct rte_rand_state *state =__rte_rand_get_state (); +union ieee754_double u = { + .ieee = { + .negative =0 , + .exponent =IEEE754_DOUBLE_BIAS , + }, + }; +uint64_t val; + +/* Take 64 bit random value and put it into the mantissa */ + val =__rte_rand_lfsr258 (state); + u.ieee.mantissa0 = val >>32 ;/* only 20 bits used */ + u.ieee.mantissa1 = (uint32_t )val; + +return u.d -1.0 ; +} +static uint64_t __rte_random_initial_seed (void ) {
lib/eal/include/rte_random.h +17 -0
@@ -65,6 +65,23 @@ rte_rand(void);uint64_t rte_rand_max (uint64_t upper_bound); +/** +* @warning +* @b EXPERIMENTAL: this API may change without prior notice +* +* Generates a pseudo-random floating point number. +* +* This function returns a nonnegative double-precison floating random +* number uniformly distributed over the interval [0.0, 1.0). +* +* If called from lcore threads, this function is thread-safe. +* +* @return +* A pseudo-random value between 0 and 1.0. +*/ +__rte_experimental +double rte_rand_float(void); + #ifdef __cplusplus }#endif
lib/eal/version.map +1 -0
@@ -422,6 +422,7 @@ EXPERIMENTAL { rte_intr_type_set; # added in 22.07 + rte_rand_float; rte_thread_get_affinity_by_id; rte_thread_self; rte_thread_set_affinity_by_id;
Signature · 1 line
2.35.1
Re: [RFT v2 1/3] random: add rte_rand_float()
Quoted 140 lines · Stephen Hemminger
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to
erand48_rin the standard library.Signed-off-by Stephen Hemminger <[email protected]>--- app/test/test_rand_perf.c | 7 +++++++ doc/guides/rel_notes/release_22_07.rst | 5 +++++ lib/eal/common/rte_random.c | 21 +++++++++++++++++++++ lib/eal/include/rte_random.h | 17 +++++++++++++++++ lib/eal/version.map | 1 + 5 files changed, 51 insertions(+)app/test/test_rand_perf.c +7
-0@@ -20,6 +20,7 @@ static volatile uint64_t vsum;enum rand_type { rand_type_64, + rand_type_float, rand_type_bounded_best_case, rand_type_bounded_worst_case };@@ -30,6 +31,8 @@ rand_type_desc(enum rand_type rand_type)switch (rand_type) {case rand_type_64:return "Full 64-bit [rte_rand()]" ; +case rand_type_float: +return "Floating point [rte_rand_float()]" ;case rand_type_bounded_best_case:return "Bounded average best-case [rte_rand_max()]" ;case rand_type_bounded_worst_case:@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=rte_rand_float () *UINT64_MAX ; +break ;case rand_type_bounded_best_case: sum +=rte_rand_max (BEST_CASE_BOUND );break ;@@ -83,6 +89,7 @@ test_rand_perf(void)printf ("Pseudo-random number generation latencies:\n" );test_rand_perf_type (rand_type_64); +test_rand_perf_type (rand_type_float);test_rand_perf_type (rand_type_bounded_best_case);test_rand_perf_type (rand_type_bounded_worst_case);doc/guides/rel_notes/release_22_07.rst +5
-0@@ -104,6 +104,11 @@ New Features * ``RTE_EVENT_QUEUE_ATTR_WEIGHT`` * ``RTE_EVENT_QUEUE_ATTR_AFFINITY`` +* ** Added function get random floating point number.** + + Added the function ``rte_rand_float()`` to provide a pseudo-random + floating point number. + Removed Items -------------lib/eal/common/rte_random.c +21
-0@@ -6,6 +6,7 @@#include <x86intrin.h> #endif #include <unistd.h> +#include <ieee754.h> #include <rte_branch_prediction.h> #include <rte_cycles.h> @@ -173,6 +174,26 @@ rte_rand_max(uint64_t upper_bound)return res; } +double +rte_rand_float (void ) +{ +struct rte_rand_state *state =__rte_rand_get_state (); +union ieee754_double u = { + .ieee = { + .negative =0 , + .exponent =IEEE754_DOUBLE_BIAS , + }, + }; +uint64_t val; + +/* Take 64 bit random value and put it into the mantissa */ + val =__rte_rand_lfsr258 (state); + u.ieee.mantissa0 = val >>32 ;/* only 20 bits used */ + u.ieee.mantissa1 = (uint32_t )val; + +return u.d -1.0 ; +} +static uint64_t __rte_random_initial_seed (void ) {lib/eal/include/rte_random.h +17
-0@@ -65,6 +65,23 @@ rte_rand(void);uint64_t rte_rand_max (uint64_t upper_bound); +/** +* @warning +* @b EXPERIMENTAL: this API may change without prior notice +* +* Generates a pseudo-random floating point number. +* +* This function returns a nonnegative double-precison floating random +* number uniformly distributed over the interval [0.0, 1.0). +* +* If called from lcore threads, this function is thread-safe. +* +* @return +* A pseudo-random value between 0 and 1.0. +*/ +__rte_experimental +double rte_rand_float(void); + #ifdef __cplusplus }#endif lib/eal/version.map +0
-0
lib/eal/version.map EXPERIMENTAL { · line 425
Quoted 4 lines
lib/eal/version.map +1
-0@@ -422,6 +422,7 @@ EXPERIMENTAL { rte_intr_type_set; # added in 22.07 + rte_rand_float;
Niggle - is there an alignment issue on the line above?
Quoted 3 lines
lib/eal/version.map +0
-0rte_thread_get_affinity_by_id; rte_thread_self; rte_thread_set_affinity_by_id;
Signature · 1 line
Regards, Ray K
Re: [RFT v2 1/3] random: add rte_rand_float()
In reply to Stephen HemmingerQuoted 4 lines · Stephen Hemminger
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to
erand48_rin the standard library.
Seems like a good addition to the API.
Quoted 69 lines
Signed-off-by Stephen Hemminger <[email protected]>--- app/test/test_rand_perf.c | 7 +++++++ doc/guides/rel_notes/release_22_07.rst | 5 +++++ lib/eal/common/rte_random.c | 21 +++++++++++++++++++++ lib/eal/include/rte_random.h | 17 +++++++++++++++++ lib/eal/version.map | 1 + 5 files changed, 51 insertions(+)app/test/test_rand_perf.c +7
-0@@ -20,6 +20,7 @@ static volatile uint64_t vsum;enum rand_type { rand_type_64, + rand_type_float, rand_type_bounded_best_case, rand_type_bounded_worst_case };@@ -30,6 +31,8 @@ rand_type_desc(enum rand_type rand_type)switch (rand_type) {case rand_type_64:return "Full 64-bit [rte_rand()]" ; +case rand_type_float: +return "Floating point [rte_rand_float()]" ;case rand_type_bounded_best_case:return "Bounded average best-case [rte_rand_max()]" ;case rand_type_bounded_worst_case:@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=rte_rand_float () *UINT64_MAX ; +break ;case rand_type_bounded_best_case: sum +=rte_rand_max (BEST_CASE_BOUND );break ;@@ -83,6 +89,7 @@ test_rand_perf(void)printf ("Pseudo-random number generation latencies:\n" );test_rand_perf_type (rand_type_64); +test_rand_perf_type (rand_type_float);test_rand_perf_type (rand_type_bounded_best_case);test_rand_perf_type (rand_type_bounded_worst_case);doc/guides/rel_notes/release_22_07.rst +5
-0@@ -104,6 +104,11 @@ New Features * ``RTE_EVENT_QUEUE_ATTR_WEIGHT`` * ``RTE_EVENT_QUEUE_ATTR_AFFINITY`` +* ** Added function get random floating point number.** + + Added the function ``rte_rand_float()`` to provide a pseudo-random + floating point number. + Removed Items -------------lib/eal/common/rte_random.c +0
-0
lib/eal/common/rte_random.c line 10
Quoted 5 lines
lib/eal/common/rte_random.c +1
-0@@ -6,6 +6,7 @@#include <x86intrin.h> #endif #include <unistd.h> +#include <ieee754.h>
Is this API available in FreeBSD? In Windows?
Quoted 12 lines
lib/eal/common/rte_random.c +6
-0#include <rte_branch_prediction.h> #include <rte_cycles.h> @@ -173,6 +174,26 @@ rte_rand_max(uint64_t upper_bound)return res; } +double +rte_rand_float (void ) +{ +struct rte_rand_state *state =__rte_rand_get_state (); +union ieee754_double u = { + .ieee = {
lib/eal/common/rte_random.c rte_rand_max(uint64_t upper_bound) · line 192
Quoted 10 lines
lib/eal/common/rte_random.c +10
-0+ .negative = 0, + .exponent = IEEE754_DOUBLE_BIAS, + }, + }; +uint64_t val; + +/* Take 64 bit random value and put it into the mantissa */ + val =__rte_rand_lfsr258 (state); + u.ieee.mantissa0 = val >>32 ;/* only 20 bits used */ + u.ieee.mantissa1 = (uint32_t )val;
Why do you have a cast here, and not for mantissa0? Both will incur a 64->32 conversion, assuming unsigned int is 32-bit (which it is on all platforms DPDK supports?).
The naive implementation (i.e., (double)rte_rand() / (double)UINT64_MAX) would cost a floating point multiplication. That's why you access the underlying IEEE754 bits directly. Correct?
Quoted 22 lines
lib/eal/common/rte_random.c +4
-0+ +return u.d -1.0 ; +} +static uint64_t __rte_random_initial_seed (void ) {lib/eal/include/rte_random.h +7
-0@@ -65,6 +65,23 @@ rte_rand(void);uint64_t rte_rand_max (uint64_t upper_bound); +/** +* @warning +* @b EXPERIMENTAL: this API may change without prior notice +* +* Generates a pseudo-random floating point number. +* +* This function returns a nonnegative double-precison floating random
lib/eal/include/rte_random.h rte_rand(void); · line 84
Quoted 10 lines
lib/eal/include/rte_random.h +10
-0+* number uniformly distributed over the interval [0.0, 1.0). +* +* If called from lcore threads, this function is thread-safe. +* +* @return +* A pseudo-random value between 0 and 1.0. +*/ +__rte_experimental +double rte_rand_float(void); +
Newline after "double" missing.
I would call it something else than "float", in particular since it doesn't return "float" but a "double" type floating point value.
rte_drand() maybe? Short, but might be confused with rte_rand(), given the visual similarity. I still I would still prefer that over rte_rand_double().
Quoted 15 lines
lib/eal/include/rte_random.h +0
-0#ifdef __cplusplus }#endif lib/eal/version.map +1
-0@@ -422,6 +422,7 @@ EXPERIMENTAL { rte_intr_type_set; # added in 22.07 + rte_rand_float; rte_thread_get_affinity_by_id; rte_thread_self; rte_thread_set_affinity_by_id;
RE: [RFT v2 1/3] random: add rte_rand_float()
Quoted 30 lines
From: Mattias Rönnblom [mailto:[email protected]]
Sent: Wednesday, 25 May 2022 16.46Quoted 5 lines · Stephen Hemminger
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to
erand48_rin the standard library.Quoted 7 lines
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Generates a pseudo-random floating point number.
+ *
+ * This function returns a nonnegative double-precison floatingrandom
lib/eal/include/rte_random.h rte_rand(void); · line 84
Quoted 10 lines
+ * number uniformly distributed over the interval [0.0, 1.0).
+ *
+ * If called from lcore threads, this function is thread-safe.
+ *
+ * @return
+ * A pseudo-random value between 0 and 1.0.
+ */lib/eal/include/rte_random.h +3
-0+__rte_experimental +double rte_rand_float(void); +Newline after "double" missing.
Quoted 6 lines
I would call it something else than "float", in particular since it doesn't return "float" but a "double" type floating point value.
rte_drand()maybe? Short, but might be confused withrte_rand(), given the visual similarity. I still I would still prefer that overrte_rand_double().
Although we use foo32() and foo64() for many functions returning uint32_t/uint64_t, I don't think we need a common (and preferably short) postfix for functions returning double. Such functions should be rare.
So:
+1 to rte_drand() - it resembles drand48() in stdlib.h.
Re: [RFT v2 1/3] random: add rte_rand_float()
In reply to Mattias RönnblomQuoted 103 lines · On Wed, 25 May 2022 14:45:37 +0000 Mattias Rönnblom…
Quoted 4 lines · Stephen Hemminger
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to
erand48_rin the standard library.Seems like a good addition to the API.
Quoted 69 lines
Signed-off-by Stephen Hemminger <[email protected]>--- app/test/test_rand_perf.c | 7 +++++++ doc/guides/rel_notes/release_22_07.rst | 5 +++++ lib/eal/common/rte_random.c | 21 +++++++++++++++++++++ lib/eal/include/rte_random.h | 17 +++++++++++++++++ lib/eal/version.map | 1 + 5 files changed, 51 insertions(+)app/test/test_rand_perf.c +7
-0@@ -20,6 +20,7 @@ static volatile uint64_t vsum;enum rand_type { rand_type_64, + rand_type_float, rand_type_bounded_best_case, rand_type_bounded_worst_case };@@ -30,6 +31,8 @@ rand_type_desc(enum rand_type rand_type)switch (rand_type) {case rand_type_64:return "Full 64-bit [rte_rand()]" ; +case rand_type_float: +return "Floating point [rte_rand_float()]" ;case rand_type_bounded_best_case:return "Bounded average best-case [rte_rand_max()]" ;case rand_type_bounded_worst_case:@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=rte_rand_float () *UINT64_MAX ; +break ;case rand_type_bounded_best_case: sum +=rte_rand_max (BEST_CASE_BOUND );break ;@@ -83,6 +89,7 @@ test_rand_perf(void)printf ("Pseudo-random number generation latencies:\n" );test_rand_perf_type (rand_type_64); +test_rand_perf_type (rand_type_float);test_rand_perf_type (rand_type_bounded_best_case);test_rand_perf_type (rand_type_bounded_worst_case);doc/guides/rel_notes/release_22_07.rst +5
-0@@ -104,6 +104,11 @@ New Features * ``RTE_EVENT_QUEUE_ATTR_WEIGHT`` * ``RTE_EVENT_QUEUE_ATTR_AFFINITY`` +* ** Added function get random floating point number.** + + Added the function ``rte_rand_float()`` to provide a pseudo-random + floating point number. + Removed Items -------------lib/eal/common/rte_random.c +0
-0lib/eal/common/rte_random.c line 10
Quoted 5 lines
lib/eal/common/rte_random.c +1
-0@@ -6,6 +6,7 @@#include <x86intrin.h> #endif #include <unistd.h> +#include <ieee754.h> Is this API available in FreeBSD? In Windows?
Quoted 18 lines
lib/eal/common/rte_random.c +12
-0#include <rte_branch_prediction.h> #include <rte_cycles.h> @@ -173,6 +174,26 @@ rte_rand_max(uint64_t upper_bound)return res; } +double +rte_rand_float (void ) +{ +struct rte_rand_state *state =__rte_rand_get_state (); +union ieee754_double u = { + .ieee = { + .negative =0 , + .exponent =IEEE754_DOUBLE_BIAS , + }, + }; +uint64_t val; +
Quoted 8 lines
lib/eal/common/rte_random.c rte_rand_max(uint64_t upper_bound) · line 192
Quoted 4 lines
lib/eal/common/rte_random.c +4
-0+/* Take 64 bit random value and put it into the mantissa */ + val =__rte_rand_lfsr258 (state); + u.ieee.mantissa0 = val >>32 ;/* only 20 bits used */ + u.ieee.mantissa1 = (uint32_t )val;Why do you have a cast here, and not for mantissa0? Both will incur a 64->32 conversion, assuming unsigned int is 32-bit (which it is on all platforms DPDK supports?).
Yes, cast there is unnecessary. A little concerned that some compiler might complain about loss of precision.
Quoted 4 lines
The naive implementation (i.e., (double)rte_rand() / (double)UINT64_MAX) would cost a floating point multiplication. That's why you access the underlying IEEE754 bits directly. Correct?
Yes, avoiding floating point math, and directly setting bits keeps full precision.
Re: [RFT v2 1/3] random: add rte_rand_float()
In reply to Mattias RönnblomQuoted 6 lines · On Wed, 25 May 2022 14:45:37 +0000 Mattias Rönnblom…
I would call it something else than "float", in particular since it doesn't return "float" but a "double" type floating point value.
rte_drand()maybe? Short, but might be confused withrte_rand(), given the visual similarity. I still I would still prefer that overrte_rand_double().
The corresponding standard library routine is drand48(). With that convention it would be rte_drand().
PATCH v2 2/3 rte_pie: remove unnecessary floating point
In reply to Stephen HemmingerThe qdelay variable is derived from and compared to 64 bit value so it doesn't have to be floating point.
--- lib/sched/rte_pie.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/sched/rte_pie.h +1 -1
@@ -218,7 +218,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) {uint64_t rand_value; -double qdelay = pie_cfg->qdelay_ref *0.5 ; +uint64_t qdelay = pie_cfg->qdelay_ref /2 ;/* PIE is active but the queue is not congested: return 0 */ if (((pie->qdelay_old < qdelay) && (pie->drop_prob < 0.2)) ||
Signature · 1 line
2.35.1
PATCH v2 3/3 rte_pie: fix incorrect floating point math
In reply to Stephen HemmingerThe function rte_pie_drop was attempting to do a random probability drop, but because of incorrect usage of fixed point divide it would always return 1.
Change to use new rte_rand_float() instead.
--- lib/sched/rte_pie.h | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)
lib/sched/rte_pie.h +1 -4
@@ -217,7 +217,6 @@ __rte_experimental _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) { - uint64_t rand_value; uint64_t qdelay = pie_cfg->qdelay_ref / 2;/* PIE is active but the queue is not congested: return 0 */
@@ -240,9 +239,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg,if (pie->accu_prob >=8.5 )return 1 ; - rand_value =rte_rand ()/RTE_RAND_MAX ; - -if ((double )rand_value < pie->drop_prob) { +if (rte_rand_float () < pie->drop_prob) { pie->accu_prob =0 ;return 1 ; }
Signature · 1 line
2.35.1
v3 cover introduce random floating point function
In reply to Stephen HemmingerIntroduce a new random number function to get a floating point value. Then use it to fix PIE scheduler.
v3
- rename to rte_drand() and other review feedback
- fix warnings with some compilers in test code
Stephen Hemminger (3):
random: add rte_drand() funciton
rte_pie: remove unnecessary floating point
rte_pie: fix incorrect floating point math
app/test/test_rand_perf.c | 7 +++++++ doc/guides/rel_notes/release_22_07.rst | 5 +++++ lib/eal/common/rte_random.c | 24 ++++++++++++++++++++++++ lib/eal/include/rte_random.h | 18 ++++++++++++++++++ lib/eal/version.map | 1 + lib/sched/rte_pie.h | 7 ++----- 6 files changed, 57 insertions(+), 5 deletions(-)
Signature · 1 line
2.35.1
PATCH v3 1/3 random: add rte_drand() funciton
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to drand() in the standard library.
--- app/test/test_rand_perf.c | 7 +++++++ doc/guides/rel_notes/release_22_07.rst | 5 +++++ lib/eal/common/rte_random.c | 24 ++++++++++++++++++++++++ lib/eal/include/rte_random.h | 18 ++++++++++++++++++ lib/eal/version.map | 1 + 5 files changed, 55 insertions(+)
app/test/test_rand_perf.c +7 -0
@@ -20,6 +20,7 @@ static volatile uint64_t vsum;enum rand_type { rand_type_64, + rand_type_float, rand_type_bounded_best_case, rand_type_bounded_worst_case };
@@ -30,6 +31,8 @@ rand_type_desc(enum rand_type rand_type)switch (rand_type) {case rand_type_64:return "Full 64-bit [rte_rand()]" ; +case rand_type_float: +return "Floating point [rte_drand()]" ;case rand_type_bounded_best_case:return "Bounded average best-case [rte_rand_max()]" ;case rand_type_bounded_worst_case:
@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=1000. *rte_drand (); +break ;case rand_type_bounded_best_case: sum +=rte_rand_max (BEST_CASE_BOUND );break ;
@@ -83,6 +89,7 @@ test_rand_perf(void)printf ("Pseudo-random number generation latencies:\n" );test_rand_perf_type (rand_type_64); +test_rand_perf_type (rand_type_float);test_rand_perf_type (rand_type_bounded_best_case);test_rand_perf_type (rand_type_bounded_worst_case);
doc/guides/rel_notes/release_22_07.rst +5 -0
@@ -104,6 +104,11 @@ New Features * ``RTE_EVENT_QUEUE_ATTR_WEIGHT`` * ``RTE_EVENT_QUEUE_ATTR_AFFINITY`` +* ** Added function get random floating point number.** + + Added the function ``rte_drand()`` to provide a pseudo-random + floating point number. + Removed Items -------------
lib/eal/common/rte_random.c +24 -0
@@ -6,6 +6,7 @@#include <x86intrin.h> #endif #include <unistd.h> +#include <ieee754.h> #include <rte_branch_prediction.h> #include <rte_cycles.h>
@@ -173,6 +174,29 @@ rte_rand_max(uint64_t upper_bound)return res; } +double +rte_drand (void ) +{ +struct rte_rand_state *state =__rte_rand_get_state (); +union ieee754_double u = { + .ieee = { + .negative =0 , + .exponent =IEEE754_DOUBLE_BIAS , + }, + }; +uint64_t val; + +/* Take 64 bit random value and put it into the mantissa +* This uses direct access to IEEE format to avoid doing +* any direct floating point math here. +*/ + val =__rte_rand_lfsr258 (state); + u.ieee.mantissa0 = val >>32 ; + u.ieee.mantissa1 = val; + +return u.d -1.0 ; +} +static uint64_t __rte_random_initial_seed (void ) {
lib/eal/include/rte_random.h +18 -0
@@ -65,6 +65,24 @@ rte_rand(void);uint64_t rte_rand_max (uint64_t upper_bound); +/** +* @warning +* @b EXPERIMENTAL: this API may change without prior notice +* +* Generates a pseudo-random floating point number. +* +* This function returns a nonnegative double-precision floating random +* number uniformly distributed over the interval [0.0, 1.0). +* +* The generator is not cryptographically secure. +* If called from lcore threads, this function is thread-safe. +* +* @return +* A pseudo-random value between 0 and 1.0. +*/ +__rte_experimental +double rte_drand(void); + #ifdef __cplusplus }#endif
lib/eal/version.map +1 -0
@@ -422,6 +422,7 @@ EXPERIMENTAL { rte_intr_type_set; # added in 22.07 + rte_drand; rte_thread_get_affinity_by_id; rte_thread_self; rte_thread_set_affinity_by_id;
Signature · 1 line
2.35.1
PATCH v3 2/3 rte_pie: remove unnecessary floating point
In reply to Stephen HemmingerThe qdelay variable is derived from and compared to 64 bit value so it doesn't have to be floating point.
--- lib/sched/rte_pie.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/sched/rte_pie.h +1 -1
@@ -218,7 +218,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) {uint64_t rand_value; -double qdelay = pie_cfg->qdelay_ref *0.5 ; +uint64_t qdelay = pie_cfg->qdelay_ref /2 ;/* PIE is active but the queue is not congested: return 0 */ if (((pie->qdelay_old < qdelay) && (pie->drop_prob < 0.2)) ||
Signature · 1 line
2.35.1
PATCH v3 3/3 rte_pie: fix incorrect floating point math
In reply to Stephen HemmingerThe function rte_pie_drop was attempting to do a random probability drop, but because of incorrect usage of fixed point divide it would always return 1.
Change to use new rte_drand() instead.
--- lib/sched/rte_pie.h | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)
lib/sched/rte_pie.h +1 -4
@@ -217,7 +217,6 @@ __rte_experimental _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) { - uint64_t rand_value; uint64_t qdelay = pie_cfg->qdelay_ref / 2;/* PIE is active but the queue is not congested: return 0 */
@@ -240,9 +239,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg,if (pie->accu_prob >=8.5 )return 1 ; - rand_value =rte_rand ()/RTE_RAND_MAX ; - -if ((double )rand_value < pie->drop_prob) { +if (rte_drand () < pie->drop_prob) { pie->accu_prob =0 ;return 1 ; }
Signature · 1 line
2.35.1
v4 cover introduce random floating point function
In reply to Stephen HemmingerIntroduce a new random number function to get a floating point value. Then use it to fix PIE scheduler.
v4
- use slower divide method in rte_drand() if library does not have ieee754 (FreeBSD and Windows?)
- fix some typos
v3
- rename to rte_drand() and other review feedback
- fix warnings with some compilers in test code
Stephen Hemminger (3):
random: add rte_drand() function
rte_pie: remove unnecessary floating point
rte_pie: fix incorrect floating point math
app/test/test_rand_perf.c | 7 +++++ doc/guides/rel_notes/release_22_07.rst | 5 ++++ lib/eal/common/rte_random.c | 41 ++++++++++++++++++++++++++ lib/eal/include/rte_random.h | 18 +++++++++++ lib/eal/meson.build | 3 ++ lib/eal/version.map | 1 + lib/sched/rte_pie.h | 7 ++--- 7 files changed, 77 insertions(+), 5 deletions(-)
Signature · 1 line
2.35.1
PATCH v4 1/3 random: add rte_drand() function
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to drand() in the standard library.
--- app/test/test_rand_perf.c | 7 +++++ doc/guides/rel_notes/release_22_07.rst | 5 ++++ lib/eal/common/rte_random.c | 41 ++++++++++++++++++++++++++ lib/eal/include/rte_random.h | 18 +++++++++++ lib/eal/meson.build | 3 ++ lib/eal/version.map | 1 + 6 files changed, 75 insertions(+)
app/test/test_rand_perf.c +7 -0
@@ -20,6 +20,7 @@ static volatile uint64_t vsum;enum rand_type { rand_type_64, + rand_type_float, rand_type_bounded_best_case, rand_type_bounded_worst_case };
@@ -30,6 +31,8 @@ rand_type_desc(enum rand_type rand_type)switch (rand_type) {case rand_type_64:return "Full 64-bit [rte_rand()]" ; +case rand_type_float: +return "Floating point [rte_drand()]" ;case rand_type_bounded_best_case:return "Bounded average best-case [rte_rand_max()]" ;case rand_type_bounded_worst_case:
@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=1000. *rte_drand (); +break ;case rand_type_bounded_best_case: sum +=rte_rand_max (BEST_CASE_BOUND );break ;
@@ -83,6 +89,7 @@ test_rand_perf(void)printf ("Pseudo-random number generation latencies:\n" );test_rand_perf_type (rand_type_64); +test_rand_perf_type (rand_type_float);test_rand_perf_type (rand_type_bounded_best_case);test_rand_perf_type (rand_type_bounded_worst_case);
doc/guides/rel_notes/release_22_07.rst +5 -0
@@ -104,6 +104,11 @@ New Features * ``RTE_EVENT_QUEUE_ATTR_WEIGHT`` * ``RTE_EVENT_QUEUE_ATTR_AFFINITY`` +* ** Added function get random floating point number.** + + Added the function ``rte_drand()`` to provide a pseudo-random + floating point number. + Removed Items -------------
lib/eal/common/rte_random.c +41 -0
53 lines not on this page · raw message
lib/eal/include/rte_random.h +18 -0
@@ -65,6 +65,24 @@ rte_rand(void);uint64_t rte_rand_max (uint64_t upper_bound); +/** +* @warning +* @b EXPERIMENTAL: this API may change without prior notice +* +* Generates a pseudo-random floating point number. +* +* This function returns a nonnegative double-precision floating random +* number uniformly distributed over the interval [0.0, 1.0). +* +* The generator is not cryptographically secure. +* If called from lcore threads, this function is thread-safe. +* +* @return +* A pseudo-random value between 0 and 1.0. +*/ +__rte_experimental +double rte_drand(void); + #ifdef __cplusplus }#endif
lib/eal/meson.build +3 -0
@@ -32,3 +32,6 @@ endif if cc.has_function('getentropy', prefix : '#include <unistd.h>') cflags += '-DRTE_LIBEAL_USE_GETENTROPY' endif +if cc.has_header_symbol('ieee754.h', 'union ieee754_double') + cflags += '-DRTE_LIBEAL_USE_IEEE754' +endif
lib/eal/version.map +1 -0
@@ -422,6 +422,7 @@ EXPERIMENTAL { rte_intr_type_set; # added in 22.07 + rte_drand; rte_thread_get_affinity_by_id; rte_thread_self; rte_thread_set_affinity_by_id;
Signature · 1 line
2.35.1
Re: [PATCH v4 1/3] random: add rte_drand() function
Quoted 5 lines · Stephen Hemminger
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to
drand()in the standard library.Signed-off-by Stephen Hemminger <[email protected]>
Quoted 9 lines
--- app/test/test_rand_perf.c | 7 +++++ doc/guides/rel_notes/release_22_07.rst | 5 ++++ lib/eal/common/rte_random.c | 41 ++++++++++++++++++++++++++ lib/eal/include/rte_random.h | 18 +++++++++++ lib/eal/meson.build | 3 ++ lib/eal/version.map | 1 + 6 files changed, 75 insertions(+)
Re: [PATCH v4 1/3] random: add rte_drand() function
In reply to Stephen HemmingerQuoted 36 lines · Stephen Hemminger
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to
drand()in the standard library.Signed-off-by Stephen Hemminger <[email protected]>--- app/test/test_rand_perf.c | 7 +++++ doc/guides/rel_notes/release_22_07.rst | 5 ++++ lib/eal/common/rte_random.c | 41 ++++++++++++++++++++++++++ lib/eal/include/rte_random.h | 18 +++++++++++ lib/eal/meson.build | 3 ++ lib/eal/version.map | 1 + 6 files changed, 75 insertions(+)app/test/test_rand_perf.c +3
-0@@ -20,6 +20,7 @@ static volatile uint64_t vsum;enum rand_type { rand_type_64, + rand_type_float, rand_type_bounded_best_case, rand_type_bounded_worst_case };@@ -30,6 +31,8 @@ rand_type_desc(enum rand_type rand_type)switch (rand_type) {case rand_type_64:return "Full 64-bit [rte_rand()]" ; +case rand_type_float: +return "Floating point [rte_drand()]" ;case rand_type_bounded_best_case:return "Bounded average best-case [rte_rand_max()]" ;case rand_type_bounded_worst_case:
app/test/test_rand_perf.c test_rand_perf_type(enum rand_type rand_type) · line 62
Quoted 5 lines
app/test/test_rand_perf.c +2
-0@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=1000. *rte_drand ();
Including this floating point multiplication will lead to an overestimation of rte_drand() latency.
You could refactor this function to be a macro, and pass the return type to as a parameter to this macro. I did just that, and on both an AMD 5900X and a Cortex-A72 it didn't add more than ~5%, so I don't think it's necessary.
Quoted 60 lines
app/test/test_rand_perf.c +2
-0+break ;case rand_type_bounded_best_case: sum +=rte_rand_max (BEST_CASE_BOUND );break ;@@ -83,6 +89,7 @@ test_rand_perf(void)printf ("Pseudo-random number generation latencies:\n" );test_rand_perf_type (rand_type_64); +test_rand_perf_type (rand_type_float);test_rand_perf_type (rand_type_bounded_best_case);test_rand_perf_type (rand_type_bounded_worst_case);doc/guides/rel_notes/release_22_07.rst +5
-0@@ -104,6 +104,11 @@ New Features * ``RTE_EVENT_QUEUE_ATTR_WEIGHT`` * ``RTE_EVENT_QUEUE_ATTR_AFFINITY`` +* ** Added function get random floating point number.** + + Added the function ``rte_drand()`` to provide a pseudo-random + floating point number. + Removed Items -------------lib/eal/common/rte_random.c +17
-0@@ -6,6 +6,9 @@#include <x86intrin.h> #endif #include <unistd.h> +#ifdef RTE_LIBEAL_USE_IEEE754 +#include <ieee754.h> +#endif #include <rte_branch_prediction.h> #include <rte_cycles.h> @@ -173,6 +176,44 @@ rte_rand_max(uint64_t upper_bound)return res; } +double +rte_drand (void ) +{ +struct rte_rand_state *state =__rte_rand_get_state (); +uint64_t rand64 =__rte_rand_lfsr258 (state); +#ifdef RTE_LIBEAL_USE_IEEE754 +union ieee754_double u = { + .ieee = { + .negative =0 , + .exponent =IEEE754_DOUBLE_BIAS , + }, + }; + +/* Take 64 bit random value and put it into the mantissa
lib/eal/common/rte_random.c rte_rand_max(uint64_t upper_bound) · line 202
Quoted 10 lines
lib/eal/common/rte_random.c +10
-0+* This uses direct access to IEEE format to avoid doing +* any direct floating point math here. +*/ + u.ieee.mantissa0 = rand64 >>32 ; + u.ieee.mantissa1 = rand64; + +return u.d -1.0 ; +#else +/* Slower method requiring floating point divide +*
Do you know how much slower? I ran rand_perf_test on two of my systems.
AMD 5900X Pi4 (ARM Cortex-A72) IEEE754 version 12 1.19 Non-IEEE754 version 11 1.16 Naive version* 24 1.16
* (double)rte_rand() / (double)UINT64_MAX
Numbers are TSC cycles/op.
Surprisingly, it seems like the IEEE754 version is slower on both of these machines.
Do you have a machine (or a different use case) where the supposedly more optimized version actually runs faster?
lib/eal/common/rte_random.c rte_rand_max(uint64_t upper_bound) · line 210
Quoted 8 lines
lib/eal/common/rte_random.c +8
-0+* The double mantissa only has 53 bits, so we uniformly mask off the +* high 11 bits and then floating-point divide by 2^53 to achieve a +* result in [0, 1). +* +* We are not allowed to emit 1.0, so denom must be one greater than +* the possible range of the preceeding step. +*/ +static const uint64_t denom = (uint64_t )1 <<53 ;
Remove "static const". Surely, this can't make a difference (at least not in a positive direction).
Quoted 61 lines
lib/eal/common/rte_random.c +6
-0+ + rand64 &= denom -1 ; +return (double )rand64 / denom; +#endif +} +static uint64_t __rte_random_initial_seed (void ) {lib/eal/include/rte_random.h +18
-0@@ -65,6 +65,24 @@ rte_rand(void);uint64_t rte_rand_max (uint64_t upper_bound); +/** +* @warning +* @b EXPERIMENTAL: this API may change without prior notice +* +* Generates a pseudo-random floating point number. +* +* This function returns a nonnegative double-precision floating random +* number uniformly distributed over the interval [0.0, 1.0). +* +* The generator is not cryptographically secure. +* If called from lcore threads, this function is thread-safe. +* +* @return +* A pseudo-random value between 0 and 1.0. +*/ +__rte_experimental +double rte_drand(void); + #ifdef __cplusplus }#endif lib/eal/meson.build +3
-0@@ -32,3 +32,6 @@ endif if cc.has_function('getentropy', prefix : '#include <unistd.h>') cflags += '-DRTE_LIBEAL_USE_GETENTROPY' endif +if cc.has_header_symbol('ieee754.h', 'union ieee754_double') + cflags += '-DRTE_LIBEAL_USE_IEEE754' +endiflib/eal/version.map +1
-0@@ -422,6 +422,7 @@ EXPERIMENTAL { rte_intr_type_set; # added in 22.07 + rte_drand; rte_thread_get_affinity_by_id; rte_thread_self; rte_thread_set_affinity_by_id;
Re: [PATCH v4 1/3] random: add rte_drand() function
Quoted 10 lines · On Thu, 26 May 2022 15:20:29 +0200 Mattias Rönnblom <[email protected]>…
app/test/test_rand_perf.c test_rand_perf_type(enum rand_type rand_type) · line 62
Quoted 6 lines
app/test/test_rand_perf.c +2
-0@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=1000. *rte_drand ();Including this floating point multiplication will lead to an overestimation of
rte_drand()latency.
Quoted 4 lines
You could refactor this function to be a macro, and pass the return type to as a parameter to this macro. I did just that, and on both an AMD 5900X and a Cortex-A72 it didn't add more than ~5%, so I don't think it's necessary.
The test is not doing anything useful with the result. It is just a way to exercise the code.
Macros are evil, have little or no typechecking and should be avoided.
Re: [PATCH v4 1/3] random: add rte_drand() function
In reply to Mattias RönnblomQuoted 13 lines · On Thu, 26 May 2022 15:20:29 +0200 Mattias Rönnblom <[email protected]>…
lib/eal/common/rte_random.c rte_rand_max(uint64_t upper_bound) · line 202
Quoted 3 lines
lib/eal/common/rte_random.c +3
-0+#else +/* Slower method requiring floating point divide +* Do you know how much slower? I ran
rand_perf_teston two of my systems.AMD 5900X Pi4 (ARM Cortex-A72) IEEE754 version 12 1.19 Non-IEEE754 version 11 1.16 Naive version* 24 1.16* (double)rte_rand() / (double)UINT64_MAX
Quoted 7 lines
Numbers are TSC cycles/op.
Surprisingly, it seems like the IEEE754 version is slower on both of these machines.
Do you have a machine (or a different use case) where the supposedly more optimized version actually runs faster?
The direct method is based off the concept used by glibc and others and the divide (including spelling error) are from FreeBSD.
Be careful with micro benchmarks. A better one would be do rte_drand() compared with something to check whether it is in range.
Re: [PATCH v4 1/3] random: add rte_drand() function
In reply to Mattias RönnblomQuoted 124 lines · On Thu, 26 May 2022 15:20:29 +0200 Mattias Rönnblom <[email protected]>…
Quoted 36 lines · Stephen Hemminger
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to
drand()in the standard library.Signed-off-by Stephen Hemminger <[email protected]>--- app/test/test_rand_perf.c | 7 +++++ doc/guides/rel_notes/release_22_07.rst | 5 ++++ lib/eal/common/rte_random.c | 41 ++++++++++++++++++++++++++ lib/eal/include/rte_random.h | 18 +++++++++++ lib/eal/meson.build | 3 ++ lib/eal/version.map | 1 + 6 files changed, 75 insertions(+)app/test/test_rand_perf.c +3
-0@@ -20,6 +20,7 @@ static volatile uint64_t vsum;enum rand_type { rand_type_64, + rand_type_float, rand_type_bounded_best_case, rand_type_bounded_worst_case };@@ -30,6 +31,8 @@ rand_type_desc(enum rand_type rand_type)switch (rand_type) {case rand_type_64:return "Full 64-bit [rte_rand()]" ; +case rand_type_float: +return "Floating point [rte_drand()]" ;case rand_type_bounded_best_case:return "Bounded average best-case [rte_rand_max()]" ;case rand_type_bounded_worst_case:app/test/test_rand_perf.c test_rand_perf_type(enum rand_type rand_type) · line 62
Quoted 5 lines
app/test/test_rand_perf.c +2
-0@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=1000. *rte_drand ();Including this floating point multiplication will lead to an overestimation of
rte_drand()latency.You could refactor this function to be a macro, and pass the return type to as a parameter to this macro. I did just that, and on both an AMD 5900X and a Cortex-A72 it didn't add more than ~5%, so I don't think it's necessary.
Quoted 60 lines
app/test/test_rand_perf.c +2
-0+break ;case rand_type_bounded_best_case: sum +=rte_rand_max (BEST_CASE_BOUND );break ;@@ -83,6 +89,7 @@ test_rand_perf(void)printf ("Pseudo-random number generation latencies:\n" );test_rand_perf_type (rand_type_64); +test_rand_perf_type (rand_type_float);test_rand_perf_type (rand_type_bounded_best_case);test_rand_perf_type (rand_type_bounded_worst_case);doc/guides/rel_notes/release_22_07.rst +5
-0@@ -104,6 +104,11 @@ New Features * ``RTE_EVENT_QUEUE_ATTR_WEIGHT`` * ``RTE_EVENT_QUEUE_ATTR_AFFINITY`` +* ** Added function get random floating point number.** + + Added the function ``rte_drand()`` to provide a pseudo-random + floating point number. + Removed Items -------------lib/eal/common/rte_random.c +17
-0@@ -6,6 +6,9 @@#include <x86intrin.h> #endif #include <unistd.h> +#ifdef RTE_LIBEAL_USE_IEEE754 +#include <ieee754.h> +#endif #include <rte_branch_prediction.h> #include <rte_cycles.h> @@ -173,6 +176,44 @@ rte_rand_max(uint64_t upper_bound)return res; } +double +rte_drand (void ) +{ +struct rte_rand_state *state =__rte_rand_get_state (); +uint64_t rand64 =__rte_rand_lfsr258 (state); +#ifdef RTE_LIBEAL_USE_IEEE754 +union ieee754_double u = { + .ieee = { + .negative =0 , + .exponent =IEEE754_DOUBLE_BIAS , + }, + }; + +/* Take 64 bit random value and put it into the mantissa lib/eal/common/rte_random.c rte_rand_max(uint64_t upper_bound) · line 202
Quoted 10 lines
lib/eal/common/rte_random.c +10
-0+* This uses direct access to IEEE format to avoid doing +* any direct floating point math here. +*/ + u.ieee.mantissa0 = rand64 >>32 ; + u.ieee.mantissa1 = rand64; + +return u.d -1.0 ; +#else +/* Slower method requiring floating point divide +* Do you know how much slower? I ran
rand_perf_teston two of my systems.
Quoted 8 lines
AMD 5900X Pi4 (ARM Cortex-A72) IEEE754 version 12 1.19 Non-IEEE754 version 11 1.16 Naive version* 24 1.16* (double)rte_rand() / (double)UINT64_MAX
Numbers are TSC cycles/op.
On AMD Ryzen 7 both versions take 9 cycles/op with the rand_perf_autotest So it is a toss up.
The 754 version is:
ubfx r1, r1, #0, #20
orr r3, r1, #1069547520 << mantissa0
mov r2, r0
orr r3, r3, #3145728
vmov.f64 d0, #1.0e+0
vmov d16, r2, r3
vsub.f64 d0, d16, d0 << return u.d - 1.0Note: the compiler is doing smart optimization on the divide version. It knows that since denominator is fixed value it can use multiply.
vmov d16, r0, r1
vmul.f64 d0, d16, d0PATCH v4 2/3 rte_pie: remove unnecessary floating point
In reply to Stephen HemmingerThe qdelay variable is derived from and compared to 64 bit value so it doesn't have to be floating point.
--- lib/sched/rte_pie.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/sched/rte_pie.h +1 -1
@@ -218,7 +218,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) {uint64_t rand_value; -double qdelay = pie_cfg->qdelay_ref *0.5 ; +uint64_t qdelay = pie_cfg->qdelay_ref /2 ;/* PIE is active but the queue is not congested: return 0 */ if (((pie->qdelay_old < qdelay) && (pie->drop_prob < 0.2)) ||
Signature · 1 line
2.35.1
PATCH v4 3/3 rte_pie: fix incorrect floating point math
In reply to Stephen HemmingerThe function rte_pie_drop was attempting to do a random probability drop, but because of incorrect usage of fixed point divide it would always return 1.
Change to use new rte_drand() instead.
--- lib/sched/rte_pie.h | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)
lib/sched/rte_pie.h +1 -4
@@ -217,7 +217,6 @@ __rte_experimental _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) { - uint64_t rand_value; uint64_t qdelay = pie_cfg->qdelay_ref / 2;/* PIE is active but the queue is not congested: return 0 */
@@ -240,9 +239,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg,if (pie->accu_prob >=8.5 )return 1 ; - rand_value =rte_rand ()/RTE_RAND_MAX ; - -if ((double )rand_value < pie->drop_prob) { +if (rte_drand () < pie->drop_prob) { pie->accu_prob =0 ;return 1 ; }
Signature · 1 line
2.35.1
RE: [PATCH v4 0/3] introduce random floating point function
In reply to Stephen HemmingerQuoted 29 lines
From: Stephen Hemminger [mailto:[email protected]]
Sent: Wednesday, 25 May 2022 22.31Introduce a new random number function to get a floating point value. Then use it to fix PIE scheduler.
v4
- use slower divide method inrte_drand()if library does not have ieee754 (FreeBSD and Windows?)
- fix some typosv3
- rename torte_drand()and other review feedback
- fix warnings with some compilers in test codeStephen Hemminger (3):
random: addrte_drand()function
rte_pie: remove unnecessary floating point
rte_pie: fix incorrect floating point mathapp/test/test_rand_perf.c | 7 +++++ doc/guides/rel_notes/release_22_07.rst | 5 ++++ lib/eal/common/rte_random.c | 41 ++++++++++++++++++++++++++ lib/eal/include/rte_random.h | 18 +++++++++++ lib/eal/meson.build | 3 ++ lib/eal/version.map | 1 + lib/sched/rte_pie.h | 7 ++--- 7 files changed, 77 insertions(+), 5 deletions(-)
Quoted 3 lines
--
2.35.1
v5 cover introduce random floating point function
In reply to Stephen HemmingerIntroduce a new random number function to get a floating point value. Then use it to fix PIE scheduler.
v5
- use divide method (similar to FreeBSD)
it takes same number of cycles (after optimization) and works on all platforms.
Stephen Hemminger (3):
random: add rte_drand() function
rte_pie: remove unnecessary floating point
rte_pie: fix incorrect floating point math
Stephen Hemminger (3):
random: add rte_drand() function
rte_pie: remove unnecessary floating point
rte_pie: fix incorrect floating point math
app/test/test_rand_perf.c | 7 +++++++ doc/guides/rel_notes/release_22_07.rst | 5 +++++ lib/eal/common/rte_random.c | 19 +++++++++++++++++++ lib/eal/include/rte_random.h | 18 ++++++++++++++++++ lib/eal/version.map | 1 + lib/sched/rte_pie.h | 7 ++----- 6 files changed, 52 insertions(+), 5 deletions(-)
Signature · 1 line
2.35.1
PATCH v5 1/3 random: add rte_drand() function
The PIE code and other applications can benefit from having a fast way to get a random floating point value. This new function is equivalent to drand() in the standard library.
--- app/test/test_rand_perf.c | 7 +++++++ doc/guides/rel_notes/release_22_07.rst | 5 +++++ lib/eal/common/rte_random.c | 19 +++++++++++++++++++ lib/eal/include/rte_random.h | 18 ++++++++++++++++++ lib/eal/version.map | 1 + 5 files changed, 50 insertions(+)
app/test/test_rand_perf.c +7 -0
@@ -20,6 +20,7 @@ static volatile uint64_t vsum;enum rand_type { rand_type_64, + rand_type_float, rand_type_bounded_best_case, rand_type_bounded_worst_case };
@@ -30,6 +31,8 @@ rand_type_desc(enum rand_type rand_type)switch (rand_type) {case rand_type_64:return "Full 64-bit [rte_rand()]" ; +case rand_type_float: +return "Floating point [rte_drand()]" ;case rand_type_bounded_best_case:return "Bounded average best-case [rte_rand_max()]" ;case rand_type_bounded_worst_case:
@@ -55,6 +58,9 @@ test_rand_perf_type(enum rand_type rand_type)case rand_type_64: sum +=rte_rand ();break ; +case rand_type_float: + sum +=1000. *rte_drand (); +break ;case rand_type_bounded_best_case: sum +=rte_rand_max (BEST_CASE_BOUND );break ;
@@ -83,6 +89,7 @@ test_rand_perf(void)printf ("Pseudo-random number generation latencies:\n" );test_rand_perf_type (rand_type_64); +test_rand_perf_type (rand_type_float);test_rand_perf_type (rand_type_bounded_best_case);test_rand_perf_type (rand_type_bounded_worst_case);
doc/guides/rel_notes/release_22_07.rst +5 -0
@@ -104,6 +104,11 @@ New Features * ``RTE_EVENT_QUEUE_ATTR_WEIGHT`` * ``RTE_EVENT_QUEUE_ATTR_AFFINITY`` +* ** Added function get random floating point number.** + + Added the function ``rte_drand()`` to provide a pseudo-random + floating point number. + Removed Items -------------
lib/eal/common/rte_random.c +19 -0
@@ -173,6 +173,25 @@ rte_rand_max(uint64_t upper_bound)return res; } +double +rte_drand (void ) +{ +static const uint64_t denom = (uint64_t )1 <<53 ; +uint64_t rand64 =rte_rand (); + +/* +* The double mantissa only has 53 bits, so we uniformly mask off the +* high 11 bits and then floating-point divide by 2^53 to achieve a +* result in [0, 1). +* +* We are not allowed to emit 1.0, so denom must be one greater than +* the possible range of the preceding step. +*/ + + rand64 &= denom -1 ; +return (double )rand64 / denom; +} +static uint64_t __rte_random_initial_seed (void ) {
lib/eal/include/rte_random.h +18 -0
@@ -65,6 +65,24 @@ rte_rand(void);uint64_t rte_rand_max (uint64_t upper_bound); +/** +* @warning +* @b EXPERIMENTAL: this API may change without prior notice +* +* Generates a pseudo-random floating point number. +* +* This function returns a nonnegative double-precision floating random +* number uniformly distributed over the interval [0.0, 1.0). +* +* The generator is not cryptographically secure. +* If called from lcore threads, this function is thread-safe. +* +* @return +* A pseudo-random value between 0 and 1.0. +*/ +__rte_experimental +double rte_drand(void); + #ifdef __cplusplus }#endif
lib/eal/version.map +1 -0
@@ -422,6 +422,7 @@ EXPERIMENTAL { rte_intr_type_set; # added in 22.07 + rte_drand; rte_thread_get_affinity_by_id; rte_thread_self; rte_thread_set_affinity_by_id;
Signature · 1 line
2.35.1
PATCH v5 2/3 rte_pie: remove unnecessary floating point
In reply to Stephen HemmingerThe qdelay variable is derived from and compared to 64 bit value so it doesn't have to be floating point.
--- lib/sched/rte_pie.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/sched/rte_pie.h +1 -1
@@ -218,7 +218,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) {uint64_t rand_value; -double qdelay = pie_cfg->qdelay_ref *0.5 ; +uint64_t qdelay = pie_cfg->qdelay_ref /2 ;/* PIE is active but the queue is not congested: return 0 */ if (((pie->qdelay_old < qdelay) && (pie->drop_prob < 0.2)) ||
Signature · 1 line
2.35.1
RE: [PATCH v5 2/3] rte_pie: remove unnecessary floating point
Quoted 35 lines
-----Original Message-----
From: Stephen Hemminger <[email protected]>
Sent: Thursday, May 26, 2022 9:27 PM
To: [email protected]
Cc: Stephen Hemminger <[email protected]>; Dumitrescu, Cristian <[email protected]>; Singh, Jasvinder <[email protected]>; Wojciech Liguzinski <[email protected]>
Subject: [PATCH v5 2/3]rte_pie: remove unnecessary floating pointThe qdelay variable is derived from and compared to 64 bit value so it doesn't have to be floating point.
Fixes 44c730b0e379 ("sched: add PIE based congestion management")Signed-off-by Stephen Hemminger <[email protected]>--- lib/sched/rte_pie.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/sched/rte_pie.h +1
-2@@ -218,7 +218,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) {uint64_t rand_value; -double qdelay = pie_cfg->qdelay_ref *0.5 ; +uint64_t qdelay = pie_cfg->qdelay_ref /2 ;/* PIE is active but the queue is not congested: return 0 */ if (((pie->qdelay_old < qdelay) && (pie->drop_prob < 0.2)) || --
Quoted 1 line
2.35.1
Hi Stephen,
Thanks for your proposed fix. It looks good to me, but since Jasvinder handled the PIE integration, I am going to defer this for his review once he comes back from vacation, just to make sure I am not missing anything here.
Regards,
Cristian
RE: [PATCH v5 2/3] rte_pie: remove unnecessary floating point
In reply to Stephen HemmingerQuoted 35 lines
-----Original Message-----
From: Stephen Hemminger <[email protected]>
Sent: Thursday, May 26, 2022 9:27 PM
To: [email protected]
Cc: Stephen Hemminger <[email protected]>; Dumitrescu, Cristian <[email protected]>; Singh, Jasvinder <[email protected]>; Wojciech Liguzinski <[email protected]>
Subject: [PATCH v5 2/3]rte_pie: remove unnecessary floating pointThe qdelay variable is derived from and compared to 64 bit value so it doesn't have to be floating point.
Fixes 44c730b0e379 ("sched: add PIE based congestion management")Signed-off-by Stephen Hemminger <[email protected]>--- lib/sched/rte_pie.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/sched/rte_pie.h index renamed from lib/sched/rte_pie.h +0
-0
02a987f54ad1..3e2c1ef46721100644lib/sched/rte_pie.h +1
-2@@ -218,7 +218,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) {uint64_t rand_value; -double qdelay = pie_cfg->qdelay_ref *0.5 ; +uint64_t qdelay = pie_cfg->qdelay_ref /2 ;/* PIE is active but the queue is not congested: return 0 */ if (((pie->qdelay_old < qdelay) && (pie->drop_prob < 0.2)) || --
Quoted 1 line
2.35.1
PATCH v5 3/3 rte_pie: fix incorrect floating point math
In reply to Stephen HemmingerThe function rte_pie_drop was attempting to do a random probability drop, but because of incorrect usage of fixed point divide it would always return 1.
Change to use new rte_drand() instead.
--- lib/sched/rte_pie.h | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)
lib/sched/rte_pie.h +1 -4
@@ -217,7 +217,6 @@ __rte_experimental _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) { - uint64_t rand_value; uint64_t qdelay = pie_cfg->qdelay_ref / 2;/* PIE is active but the queue is not congested: return 0 */
@@ -240,9 +239,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg,if (pie->accu_prob >=8.5 )return 1 ; - rand_value =rte_rand ()/RTE_RAND_MAX ; - -if ((double )rand_value < pie->drop_prob) { +if (rte_drand () < pie->drop_prob) { pie->accu_prob =0 ;return 1 ; }
Signature · 1 line
2.35.1
RE: [PATCH v5 3/3] rte_pie: fix incorrect floating point math
Quoted 48 lines
-----Original Message-----
From: Stephen Hemminger <[email protected]>
Sent: Thursday, May 26, 2022 9:27 PM
To: [email protected]
Cc: Stephen Hemminger <[email protected]>; Dumitrescu, Cristian <[email protected]>; Singh, Jasvinder <[email protected]>; Wojciech Liguzinski <[email protected]>
Subject: [PATCH v5 3/3]rte_pie: fix incorrect floating point mathThe function
rte_pie_dropwas attempting to do a random probability drop, but because of incorrect usage of fixed point divide it would always return 1.Change to use new
rte_drand()instead.Fixes 44c730b0e379 ("sched: add PIE based congestion management")Signed-off-by Stephen Hemminger <[email protected]>--- lib/sched/rte_pie.h | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)lib/sched/rte_pie.h +1
-5@@ -217,7 +217,6 @@ __rte_experimental _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) { - uint64_t rand_value; uint64_t qdelay = pie_cfg->qdelay_ref / 2;/* PIE is active but the queue is not congested: return 0 */ @@ -240,9 +239,7 @@ _rte_pie_drop(const struct rte_pie_config *pie_cfg,if (pie->accu_prob >=8.5 )return 1 ; - rand_value =rte_rand ()/RTE_RAND_MAX ; - -if ((double )rand_value < pie->drop_prob) { +if (rte_drand () < pie->drop_prob) { pie->accu_prob =0 ;return 1 ; } --
Quoted 1 line
2.35.1
Hi Stephen,
Thanks for your proposed fix. It looks good to me, but since Jasvinder handled the PIE integration, I am going to defer this for his review once he comes back from vacation, just to make sure I am not missing anything here.
Regards,
Cristian
RE: [PATCH v5 3/3] rte_pie: fix incorrect floating point math
In reply to Stephen HemmingerQuoted 47 lines
-----Original Message-----
From: Stephen Hemminger <[email protected]>
Sent: Thursday, May 26, 2022 9:27 PM
To: [email protected]
Cc: Stephen Hemminger <[email protected]>; Dumitrescu, Cristian <[email protected]>; Singh, Jasvinder <[email protected]>; Wojciech Liguzinski <[email protected]>
Subject: [PATCH v5 3/3]rte_pie: fix incorrect floating point mathThe function
rte_pie_dropwas attempting to do a random probability drop, but because of incorrect usage of fixed point divide it would always return 1.Change to use new
rte_drand()instead.Fixes 44c730b0e379 ("sched: add PIE based congestion management")Signed-off-by Stephen Hemminger <[email protected]>--- lib/sched/rte_pie.h | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)lib/sched/rte_pie.h index renamed from lib/sched/rte_pie.h +0
-0
3e2c1ef46721..528f2ea878e8100644lib/sched/rte_pie.h +0
-1@@ -217,7 +217,6 @@ __rte_experimental _rte_pie_drop(const struct rte_pie_config *pie_cfg, struct rte_pie *pie) { - uint64_t rand_value; uint64_t qdelay = pie_cfg->qdelay_ref / 2; /* PIE is active but the queue is not congested: return 0 */ @@ -240,9 +239,7 @@ _rte_pie_drop(const struct
rte_pie_config*pie_cfg,lib/sched/rte_pie.h +1
-4if (pie->accu_prob >=8.5 )return 1 ; - rand_value =rte_rand ()/RTE_RAND_MAX ; - -if ((double )rand_value < pie->drop_prob) { +if (rte_drand () < pie->drop_prob) { pie->accu_prob =0 ;return 1 ; } --
Quoted 1 line
2.35.1
Re: [PATCH v5 0/3] introduce random floating point function
In reply to Stephen Hemminger26/05/2022 22:26, Stephen Hemminger:
Quoted 4 lines
Stephen Hemminger (3):
random: addrte_drand()function
rte_pie: remove unnecessary floating point
rte_pie: fix incorrect floating point math
Series applied, thanks.