* [PATCH] tests/qht-bench: Adjust rate computation and comparisons
@ 2020-06-20 21:45 Richard Henderson
2020-06-21 21:28 ` Emilio G. Cota
0 siblings, 1 reply; 4+ messages in thread
From: Richard Henderson @ 2020-06-20 21:45 UTC (permalink / raw)
To: qemu-devel; +Cc: peter.maydell, Emilio G . Cota, alex.bennee
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;
@@ -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;
}
}
--
2.25.1
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH] tests/qht-bench: Adjust rate computation and comparisons
2020-06-20 21:45 [PATCH] tests/qht-bench: Adjust rate computation and comparisons Richard Henderson
@ 2020-06-21 21:28 ` Emilio G. Cota
2020-06-23 1:57 ` Emilio G. Cota
2020-06-23 22:37 ` Richard Henderson
0 siblings, 2 replies; 4+ messages in thread
From: Emilio G. Cota @ 2020-06-21 21:28 UTC (permalink / raw)
To: Richard Henderson; +Cc: peter.maydell, alex.bennee, qemu-devel
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] tests/qht-bench: Adjust rate computation and comparisons
2020-06-21 21:28 ` Emilio G. Cota
@ 2020-06-23 1:57 ` Emilio G. Cota
2020-06-23 22:37 ` Richard Henderson
1 sibling, 0 replies; 4+ messages in thread
From: Emilio G. Cota @ 2020-06-23 1:57 UTC (permalink / raw)
To: Richard Henderson
Cc: peter.maydell, alex.bennee, qemu-devel, Philippe Mathieu-Daudé
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] tests/qht-bench: Adjust rate computation and comparisons
2020-06-21 21:28 ` Emilio G. Cota
2020-06-23 1:57 ` Emilio G. Cota
@ 2020-06-23 22:37 ` Richard Henderson
1 sibling, 0 replies; 4+ messages in thread
From: Richard Henderson @ 2020-06-23 22:37 UTC (permalink / raw)
To: Emilio G. Cota; +Cc: peter.maydell, alex.bennee, qemu-devel
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~
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2020-06-23 22:38 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-06-20 21:45 [PATCH] tests/qht-bench: Adjust rate computation and comparisons Richard Henderson
2020-06-21 21:28 ` Emilio G. Cota
2020-06-23 1:57 ` Emilio G. Cota
2020-06-23 22:37 ` Richard Henderson
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.