[PATCH v2 0/2] tests/qht-bench: Adjust rate/threshold computation

[PATCH v2 0/2] tests/qht-bench: Adjust rate/threshold computation

[Richard Henderson]

Supercedes: <20200620214551.447392-1-richard.henderson@linaro.org>

Thanks for Emilio's review of v1.  I've split "seed" from "rate"
as suggested, left the comparisons alone, and expanded the comment
in do_threshold.


r~


Richard Henderson (2):
  tests/qht-bench: Adjust testing rate by -1
  tests/qht-bench: Adjust threshold computation

 tests/qht-bench.c | 40 +++++++++++++++++++++++++++++++---------
 1 file changed, 31 insertions(+), 9 deletions(-)

-- 
2.25.1

[PATCH v2 1/2] tests/qht-bench: Adjust testing rate by -1

[Richard Henderson]

Since the seed must be non-zero, subtracting 1 means puts the
rate in 0..UINT64_MAX-1, which allows the 0 and UINT64_MAX
thresholds to corrspond to 0% (never) and 100% (always).

Suggested-by: Emilio G. Cota <cota@braap.org>
Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
---
 tests/qht-bench.c | 22 +++++++++++++++-------
 1 file changed, 15 insertions(+), 7 deletions(-)

diff --git a/tests/qht-bench.c b/tests/qht-bench.c
index eb88a90137..ad885d89d0 100644
--- a/tests/qht-bench.c
+++ b/tests/qht-bench.c
@@ -25,7 +25,13 @@ struct thread_stats {
 struct thread_info {
     void (*func)(struct thread_info *);
     struct thread_stats stats;
-    uint64_t r;
+    /*
+     * Seed is in the range [1..UINT64_MAX], because the RNG requires
+     * a non-zero seed.  To use, subtract 1 and compare against the
+     * threshold with </>=.  This lets threshold = 0 never match (0% hit),
+     * and threshold = UINT64_MAX always match (100% hit).
+     */
+    uint64_t seed;
     bool write_op; /* writes alternate between insertions and removals */
     bool resize_down;
 } QEMU_ALIGNED(64); /* avoid false sharing among threads */
@@ -131,8 +137,9 @@ static uint64_t xorshift64star(uint64_t x)
 static void do_rz(struct thread_info *info)
 {
     struct thread_stats *stats = &info->stats;
+    uint64_t r = info->seed - 1;
 
-    if (info->r < resize_threshold) {
+    if (r < resize_threshold) {
         size_t size = info->resize_down ? resize_min : resize_max;
         bool resized;
 
@@ -151,13 +158,14 @@ static void do_rz(struct thread_info *info)
 static void do_rw(struct thread_info *info)
 {
     struct thread_stats *stats = &info->stats;
+    uint64_t r = info->seed - 1;
     uint32_t hash;
     long *p;
 
-    if (info->r >= update_threshold) {
+    if (r >= update_threshold) {
         bool read;
 
-        p = &keys[info->r & (lookup_range - 1)];
+        p = &keys[r & (lookup_range - 1)];
         hash = hfunc(*p);
         read = qht_lookup(&ht, p, hash);
         if (read) {
@@ -166,7 +174,7 @@ static void do_rw(struct thread_info *info)
             stats->not_rd++;
         }
     } else {
-        p = &keys[info->r & (update_range - 1)];
+        p = &keys[r & (update_range - 1)];
         hash = hfunc(*p);
         if (info->write_op) {
             bool written = false;
@@ -208,7 +216,7 @@ static void *thread_func(void *p)
 
     rcu_read_lock();
     while (!atomic_read(&test_stop)) {
-        info->r = xorshift64star(info->r);
+        info->seed = xorshift64star(info->seed);
         info->func(info);
     }
     rcu_read_unlock();
@@ -221,7 +229,7 @@ static void *thread_func(void *p)
 static void prepare_thread_info(struct thread_info *info, int i)
 {
     /* seed for the RNG; each thread should have a different one */
-    info->r = (i + 1) ^ time(NULL);
+    info->seed = (i + 1) ^ time(NULL);
     /* the first update will be a write */
     info->write_op = true;
     /* the first resize will be down */
-- 
2.25.1

[PATCH v2 2/2] tests/qht-bench: Adjust threshold computation

[Richard Henderson]

In 06c4cc3660b3, we split the multiplication in two parts to avoid
a clang warning.  But because double still rounds to 53 bits, this
does not provide additional precision beyond multiplication by
nextafter(0x1p64, 0), the largest representable value smaller
than 2**64.

However, since we have eliminated 1.0, mutiplying by 2**64 produces
a better distribution of input values to the output values.

Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
---
 tests/qht-bench.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

diff --git a/tests/qht-bench.c b/tests/qht-bench.c
index ad885d89d0..362f03cb03 100644
--- a/tests/qht-bench.c
+++ b/tests/qht-bench.c
@@ -289,11 +289,25 @@ 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.
+     *
+     * Scale by 2**64, with a special case for 1.0.
+     * The remainder of the possible values are scattered between 0
+     * and 0xfffffffffffff800 (nextafter(0x1p64, 0)).
+     *
+     * Note that we cannot simply scale by UINT64_MAX, because that
+     * value is not representable as an IEEE double value.
+     *
+     * If we scale by the next largest value, nextafter(0x1p64, 0),
+     * then the remainder of the possible values are scattered between
+     * 0 and 0xfffffffffffff000.  Which leaves us with a gap between
+     * the final two inputs that is twice as large as any other.
+     */
     if (rate == 1.0) {
         *threshold = UINT64_MAX;
     } else {
-        *threshold = (rate * 0xffff000000000000ull)
-                   + (rate * 0x0000ffffffffffffull);
+        *threshold = rate * 0x1p64;
     }
 }
 
-- 
2.25.1

Re: [PATCH v2 0/2] tests/qht-bench: Adjust rate/threshold computation

[no-reply]

Patchew URL: https://patchew.org/QEMU/20200626200950.1015121-1-richard.henderson@linaro.org/



Hi,

This series failed the docker-mingw@fedora build test. Please find the testing commands and
their output below. If you have Docker installed, you can probably reproduce it
locally.

=== TEST SCRIPT BEGIN ===
#! /bin/bash
export ARCH=x86_64
make docker-image-fedora V=1 NETWORK=1
time make docker-test-mingw@fedora J=14 NETWORK=1
=== TEST SCRIPT END ===

    raise CalledProcessError(retcode, cmd)
subprocess.CalledProcessError: Command '['sudo', '-n', 'docker', 'run', '--label', 'com.qemu.instance.uuid=cfb70a057f99414cb380e1aac7ea404b', '-u', '1003', '--security-opt', 'seccomp=unconfined', '--rm', '-e', 'TARGET_LIST=', '-e', 'EXTRA_CONFIGURE_OPTS=', '-e', 'V=', '-e', 'J=14', '-e', 'DEBUG=', '-e', 'SHOW_ENV=', '-e', 'CCACHE_DIR=/var/tmp/ccache', '-v', '/home/patchew2/.cache/qemu-docker-ccache:/var/tmp/ccache:z', '-v', '/var/tmp/patchew-tester-tmp-w3ye4819/src/docker-src.2020-06-26-16.16.29.10114:/var/tmp/qemu:z,ro', 'qemu:fedora', '/var/tmp/qemu/run', 'test-mingw']' returned non-zero exit status 2.
filter=--filter=label=com.qemu.instance.uuid=cfb70a057f99414cb380e1aac7ea404b
make[1]: *** [docker-run] Error 1
make[1]: Leaving directory `/var/tmp/patchew-tester-tmp-w3ye4819/src'
make: *** [docker-run-test-mingw@fedora] Error 2

real    4m59.023s
user    0m8.221s


The full log is available at
http://patchew.org/logs/20200626200950.1015121-1-richard.henderson@linaro.org/testing.docker-mingw@fedora/?type=message.
---
Email generated automatically by Patchew [https://patchew.org/].
Please send your feedback to patchew-devel@redhat.com

Re: [PATCH v2 2/2] tests/qht-bench: Adjust threshold computation

[Philippe Mathieu-Daudé]

On 6/26/20 10:09 PM, Richard Henderson wrote:
> In 06c4cc3660b3, we split the multiplication in two parts to avoid
> a clang warning.  But because double still rounds to 53 bits, this
> does not provide additional precision beyond multiplication by
> nextafter(0x1p64, 0), the largest representable value smaller
> than 2**64.
> 
> However, since we have eliminated 1.0, mutiplying by 2**64 produces
> a better distribution of input values to the output values.
> 
> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
> ---
>  tests/qht-bench.c | 18 ++++++++++++++++--
>  1 file changed, 16 insertions(+), 2 deletions(-)
> 
> diff --git a/tests/qht-bench.c b/tests/qht-bench.c
> index ad885d89d0..362f03cb03 100644
> --- a/tests/qht-bench.c
> +++ b/tests/qht-bench.c
> @@ -289,11 +289,25 @@ 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.
> +     *
> +     * Scale by 2**64, with a special case for 1.0.
> +     * The remainder of the possible values are scattered between 0
> +     * and 0xfffffffffffff800 (nextafter(0x1p64, 0)).
> +     *
> +     * Note that we cannot simply scale by UINT64_MAX, because that
> +     * value is not representable as an IEEE double value.
> +     *
> +     * If we scale by the next largest value, nextafter(0x1p64, 0),
> +     * then the remainder of the possible values are scattered between
> +     * 0 and 0xfffffffffffff000.  Which leaves us with a gap between
> +     * the final two inputs that is twice as large as any other.
> +     */
>      if (rate == 1.0) {
>          *threshold = UINT64_MAX;
>      } else {
> -        *threshold = (rate * 0xffff000000000000ull)
> -                   + (rate * 0x0000ffffffffffffull);
> +        *threshold = rate * 0x1p64;
>      }
>  }
>  
> 

Reviewed-by: Philippe Mathieu-Daudé <philmd@redhat.com>

Re: [PATCH v2 1/2] tests/qht-bench: Adjust testing rate by -1

[Philippe Mathieu-Daudé]

On 6/26/20 10:09 PM, Richard Henderson wrote:
> Since the seed must be non-zero, subtracting 1 means puts the
> rate in 0..UINT64_MAX-1, which allows the 0 and UINT64_MAX
> thresholds to corrspond to 0% (never) and 100% (always).
> 
> Suggested-by: Emilio G. Cota <cota@braap.org>
> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
> ---
>  tests/qht-bench.c | 22 +++++++++++++++-------
>  1 file changed, 15 insertions(+), 7 deletions(-)
> 
> diff --git a/tests/qht-bench.c b/tests/qht-bench.c
> index eb88a90137..ad885d89d0 100644
> --- a/tests/qht-bench.c
> +++ b/tests/qht-bench.c
> @@ -25,7 +25,13 @@ struct thread_stats {
>  struct thread_info {
>      void (*func)(struct thread_info *);
>      struct thread_stats stats;
> -    uint64_t r;
> +    /*
> +     * Seed is in the range [1..UINT64_MAX], because the RNG requires
> +     * a non-zero seed.  To use, subtract 1 and compare against the
> +     * threshold with </>=.  This lets threshold = 0 never match (0% hit),
> +     * and threshold = UINT64_MAX always match (100% hit).
> +     */
> +    uint64_t seed;
>      bool write_op; /* writes alternate between insertions and removals */
>      bool resize_down;
>  } QEMU_ALIGNED(64); /* avoid false sharing among threads */
> @@ -131,8 +137,9 @@ static uint64_t xorshift64star(uint64_t x)
>  static void do_rz(struct thread_info *info)
>  {
>      struct thread_stats *stats = &info->stats;
> +    uint64_t r = info->seed - 1;
>  
> -    if (info->r < resize_threshold) {
> +    if (r < resize_threshold) {
>          size_t size = info->resize_down ? resize_min : resize_max;
>          bool resized;
>  
> @@ -151,13 +158,14 @@ static void do_rz(struct thread_info *info)
>  static void do_rw(struct thread_info *info)
>  {
>      struct thread_stats *stats = &info->stats;
> +    uint64_t r = info->seed - 1;
>      uint32_t hash;
>      long *p;
>  
> -    if (info->r >= update_threshold) {
> +    if (r >= update_threshold) {
>          bool read;
>  
> -        p = &keys[info->r & (lookup_range - 1)];
> +        p = &keys[r & (lookup_range - 1)];
>          hash = hfunc(*p);
>          read = qht_lookup(&ht, p, hash);
>          if (read) {
> @@ -166,7 +174,7 @@ static void do_rw(struct thread_info *info)
>              stats->not_rd++;
>          }
>      } else {
> -        p = &keys[info->r & (update_range - 1)];
> +        p = &keys[r & (update_range - 1)];
>          hash = hfunc(*p);
>          if (info->write_op) {
>              bool written = false;
> @@ -208,7 +216,7 @@ static void *thread_func(void *p)
>  
>      rcu_read_lock();
>      while (!atomic_read(&test_stop)) {
> -        info->r = xorshift64star(info->r);
> +        info->seed = xorshift64star(info->seed);
>          info->func(info);
>      }
>      rcu_read_unlock();
> @@ -221,7 +229,7 @@ static void *thread_func(void *p)
>  static void prepare_thread_info(struct thread_info *info, int i)
>  {
>      /* seed for the RNG; each thread should have a different one */
> -    info->r = (i + 1) ^ time(NULL);
> +    info->seed = (i + 1) ^ time(NULL);
>      /* the first update will be a write */
>      info->write_op = true;
>      /* the first resize will be down */
> 

Reviewed-by: Philippe Mathieu-Daudé <philmd@redhat.com>

Re: [PATCH v2 0/2] tests/qht-bench: Adjust rate/threshold computation

[Emilio G. Cota]

On Fri, Jun 26, 2020 at 13:09:48 -0700, Richard Henderson wrote:
> Supercedes: <20200620214551.447392-1-richard.henderson@linaro.org>
> 
> Thanks for Emilio's review of v1.  I've split "seed" from "rate"
> as suggested, left the comparisons alone, and expanded the comment
> in do_threshold.

Reviewed-by: Emilio G. Cota <cota@braap.org>

for the series. Thanks a lot!

		E.

Re: [PATCH v2 0/2] tests/qht-bench: Adjust rate/threshold computation

[Alex Bennée]

Richard Henderson <richard.henderson@linaro.org> writes:

> Supercedes: <20200620214551.447392-1-richard.henderson@linaro.org>
>
> Thanks for Emilio's review of v1.  I've split "seed" from "rate"
> as suggested, left the comparisons alone, and expanded the comment
> in do_threshold.

Queued to testing/next, thanks.

>
>
> r~
>
>
> Richard Henderson (2):
>   tests/qht-bench: Adjust testing rate by -1
>   tests/qht-bench: Adjust threshold computation
>
>  tests/qht-bench.c | 40 +++++++++++++++++++++++++++++++---------
>  1 file changed, 31 insertions(+), 9 deletions(-)


-- 
Alex Bennée