| Message ID | 20200620214551.447392-1-richard.henderson@linaro.org |
|---|---|
| State | New |
| Headers | show |
| Series | tests/qht-bench: Adjust rate computation and comparisons | expand |
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
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
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~
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; } }
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