tests/qht-bench: Adjust rate computation and comparisons

Message ID 20200620214551.447392-1-richard.henderson@linaro.org
State New
Headers show
Series
  • tests/qht-bench: Adjust rate computation and comparisons
Related show

Commit Message

Richard Henderson June 20, 2020, 9:45 p.m.
Use <= comparisons vs the threshold, so that threshold UINT64_MAX
is always true, corresponding to rate 1.0 being unity.  Simplify
do_threshold scaling to 2**64, with a special case for 1.0.

Cc: Emilio G. Cota <cota@braap.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>

---
 tests/qht-bench.c | 15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)

-- 
2.25.1

Comments

Emilio G. Cota June 21, 2020, 9:28 p.m. | #1
On Sat, Jun 20, 2020 at 14:45:51 -0700, Richard Henderson wrote:
> Use <= comparisons vs the threshold, so that threshold UINT64_MAX

> is always true, corresponding to rate 1.0 being unity.  Simplify

> do_threshold scaling to 2**64, with a special case for 1.0.

> 

> Cc: Emilio G. Cota <cota@braap.org>

> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>

> ---

>  tests/qht-bench.c | 15 +++++++++++----

>  1 file changed, 11 insertions(+), 4 deletions(-)

> 

> diff --git a/tests/qht-bench.c b/tests/qht-bench.c

> index eb88a90137..21b1b7de82 100644

> --- a/tests/qht-bench.c

> +++ b/tests/qht-bench.c

> @@ -132,7 +132,7 @@ static void do_rz(struct thread_info *info)

>  {

>      struct thread_stats *stats = &info->stats;

>  

> -    if (info->r < resize_threshold) {

> +    if (info->r <= resize_threshold) {

>          size_t size = info->resize_down ? resize_min : resize_max;

>          bool resized;


This works, but only because info->r cannot be 0 since xorshift never
returns it. (xorshift returns a random number in the range [1, u64max],
a fact that I missed when I wrote this code.)
If r were 0, then we would resize even if resize_threshold == 0.0.

I think it will be easier to reason about this if we rename info->r
to info->seed, and then have a local r = info->seed - 1. Then we can keep
the "if random < threshold" form (and its negated "if random >= threshold"
as below), which (at least to me) is intuitive provided that random's range
is [0, threshold), e.g. [0.0, 1.0) with drand48(3).

> @@ -154,7 +154,7 @@ static void do_rw(struct thread_info *info)

>      uint32_t hash;

>      long *p;

>  

> -    if (info->r >= update_threshold) {

> +    if (info->r > update_threshold) {

>          bool read;

>  

>          p = &keys[info->r & (lookup_range - 1)];

> @@ -281,11 +281,18 @@ static void pr_params(void)

>  

>  static void do_threshold(double rate, uint64_t *threshold)

>  {

> +    /*

> +     * For 0 <= rate <= 1, scale to fit in a uint64_t.

> +     *

> +     * For rate == 1, returning UINT64_MAX means 100% certainty: all

> +     * uint64_t will match using <=.  The largest representable value

> +     * for rate less than 1 is 0.999999999999999889; scaling that

> +     * by 2**64 results in 0xfffffffffffff800.

> +     */

>      if (rate == 1.0) {

>          *threshold = UINT64_MAX;

>      } else {

> -        *threshold = (rate * 0xffff000000000000ull)

> -                   + (rate * 0x0000ffffffffffffull);

> +        *threshold = rate * 0x1p64;


I'm sorry this caused a breakage for some integration tests; I thought
this was fixed in May with:
  https://lists.nongnu.org/archive/html/qemu-devel/2020-05/msg01477.html

Just for my own education, why isn't nextafter needed here?

Thanks,
		Emilio
Emilio G. Cota June 23, 2020, 1:57 a.m. | #2
Cc'ing Philippe, who authored the fix for this in May as I mention below.

		Emilio

On Sun, Jun 21, 2020 at 17:28:25 -0400, Emilio G. Cota wrote:
> On Sat, Jun 20, 2020 at 14:45:51 -0700, Richard Henderson wrote:

> > Use <= comparisons vs the threshold, so that threshold UINT64_MAX

> > is always true, corresponding to rate 1.0 being unity.  Simplify

> > do_threshold scaling to 2**64, with a special case for 1.0.

> > 

> > Cc: Emilio G. Cota <cota@braap.org>

> > Signed-off-by: Richard Henderson <richard.henderson@linaro.org>

> > ---

> >  tests/qht-bench.c | 15 +++++++++++----

> >  1 file changed, 11 insertions(+), 4 deletions(-)

> > 

> > diff --git a/tests/qht-bench.c b/tests/qht-bench.c

> > index eb88a90137..21b1b7de82 100644

> > --- a/tests/qht-bench.c

> > +++ b/tests/qht-bench.c

> > @@ -132,7 +132,7 @@ static void do_rz(struct thread_info *info)

> >  {

> >      struct thread_stats *stats = &info->stats;

> >  

> > -    if (info->r < resize_threshold) {

> > +    if (info->r <= resize_threshold) {

> >          size_t size = info->resize_down ? resize_min : resize_max;

> >          bool resized;

> 

> This works, but only because info->r cannot be 0 since xorshift never

> returns it. (xorshift returns a random number in the range [1, u64max],

> a fact that I missed when I wrote this code.)

> If r were 0, then we would resize even if resize_threshold == 0.0.

> 

> I think it will be easier to reason about this if we rename info->r

> to info->seed, and then have a local r = info->seed - 1. Then we can keep

> the "if random < threshold" form (and its negated "if random >= threshold"

> as below), which (at least to me) is intuitive provided that random's range

> is [0, threshold), e.g. [0.0, 1.0) with drand48(3).

> 

> > @@ -154,7 +154,7 @@ static void do_rw(struct thread_info *info)

> >      uint32_t hash;

> >      long *p;

> >  

> > -    if (info->r >= update_threshold) {

> > +    if (info->r > update_threshold) {

> >          bool read;

> >  

> >          p = &keys[info->r & (lookup_range - 1)];

> > @@ -281,11 +281,18 @@ static void pr_params(void)

> >  

> >  static void do_threshold(double rate, uint64_t *threshold)

> >  {

> > +    /*

> > +     * For 0 <= rate <= 1, scale to fit in a uint64_t.

> > +     *

> > +     * For rate == 1, returning UINT64_MAX means 100% certainty: all

> > +     * uint64_t will match using <=.  The largest representable value

> > +     * for rate less than 1 is 0.999999999999999889; scaling that

> > +     * by 2**64 results in 0xfffffffffffff800.

> > +     */

> >      if (rate == 1.0) {

> >          *threshold = UINT64_MAX;

> >      } else {

> > -        *threshold = (rate * 0xffff000000000000ull)

> > -                   + (rate * 0x0000ffffffffffffull);

> > +        *threshold = rate * 0x1p64;

> 

> I'm sorry this caused a breakage for some integration tests; I thought

> this was fixed in May with:

>   https://lists.nongnu.org/archive/html/qemu-devel/2020-05/msg01477.html

> 

> Just for my own education, why isn't nextafter needed here?

> 

> Thanks,

> 		Emilio
Richard Henderson June 23, 2020, 10:37 p.m. | #3
On 6/21/20 2:28 PM, Emilio G. Cota wrote:
>> -    if (info->r < resize_threshold) {

>> +    if (info->r <= resize_threshold) {

>>          size_t size = info->resize_down ? resize_min : resize_max;

>>          bool resized;

> 

> This works, but only because info->r cannot be 0 since xorshift never

> returns it. (xorshift returns a random number in the range [1, u64max],

> a fact that I missed when I wrote this code.)

> If r were 0, then we would resize even if resize_threshold == 0.0.

> 

> I think it will be easier to reason about this if we rename info->r

> to info->seed, and then have a local r = info->seed - 1. Then we can keep

> the "if random < threshold" form (and its negated "if random >= threshold"

> as below), which (at least to me) is intuitive provided that random's range

> is [0, threshold), e.g. [0.0, 1.0) with drand48(3).


Fair enough.

>>  static void do_threshold(double rate, uint64_t *threshold)

>>  {

>> +    /*

>> +     * For 0 <= rate <= 1, scale to fit in a uint64_t.

>> +     *

>> +     * For rate == 1, returning UINT64_MAX means 100% certainty: all

>> +     * uint64_t will match using <=.  The largest representable value

>> +     * for rate less than 1 is 0.999999999999999889; scaling that

>> +     * by 2**64 results in 0xfffffffffffff800.

>> +     */

>>      if (rate == 1.0) {

>>          *threshold = UINT64_MAX;

>>      } else {

>> -        *threshold = (rate * 0xffff000000000000ull)

>> -                   + (rate * 0x0000ffffffffffffull);

>> +        *threshold = rate * 0x1p64;

> 

> I'm sorry this caused a breakage for some integration tests; I thought

> this was fixed in May with:

>   https://lists.nongnu.org/archive/html/qemu-devel/2020-05/msg01477.html

> 

> Just for my own education, why isn't nextafter needed here?


I hoped I was being clear in the comment, but re-reading, it doesn't finish the
thought.

We have removed 1.0, so the rate values are between 0 and nextafter(1, 0) =
0x1.fffffffffffff00000p-1 = 0.999999999999999889.

Scaling by 2**64 results in an exact extract of the 53-bit mantessa, evenly
spread across 0 to 0xfffffffffffff800.  Plus 1.0 -> UINT64_MAX, which we could
consider off-by-one its "proper" value.

If we scale by nextafter(0x1p64, 0), then the values are spread across 0 to
0xfffffffffffff000.  The gap is twice as large between 1.0 and nextafter(1, 0).


r~

Patch

diff --git a/tests/qht-bench.c b/tests/qht-bench.c
index eb88a90137..21b1b7de82 100644
--- a/tests/qht-bench.c
+++ b/tests/qht-bench.c
@@ -132,7 +132,7 @@  static void do_rz(struct thread_info *info)
 {
     struct thread_stats *stats = &info->stats;
 
-    if (info->r < resize_threshold) {
+    if (info->r <= resize_threshold) {
         size_t size = info->resize_down ? resize_min : resize_max;
         bool resized;
 
@@ -154,7 +154,7 @@  static void do_rw(struct thread_info *info)
     uint32_t hash;
     long *p;
 
-    if (info->r >= update_threshold) {
+    if (info->r > update_threshold) {
         bool read;
 
         p = &keys[info->r & (lookup_range - 1)];
@@ -281,11 +281,18 @@  static void pr_params(void)
 
 static void do_threshold(double rate, uint64_t *threshold)
 {
+    /*
+     * For 0 <= rate <= 1, scale to fit in a uint64_t.
+     *
+     * For rate == 1, returning UINT64_MAX means 100% certainty: all
+     * uint64_t will match using <=.  The largest representable value
+     * for rate less than 1 is 0.999999999999999889; scaling that
+     * by 2**64 results in 0xfffffffffffff800.
+     */
     if (rate == 1.0) {
         *threshold = UINT64_MAX;
     } else {
-        *threshold = (rate * 0xffff000000000000ull)
-                   + (rate * 0x0000ffffffffffffull);
+        *threshold = rate * 0x1p64;
     }
 }