Re: [Qemu-devel] [PULL 3/7] qxl: refactor rounding up to a nearest power of 2

[Radim Krčmář]

2015-03-05 10:52+0100, Markus Armbruster:
> Gerd Hoffmann <address@hidden> writes:
> 
> > From: Radim Krčmář <address@hidden>
> >
> > We already have pow2floor, mirror it and use instead of a function with
> > similar results (same in used domain), to clarify our intent.
> >
> > Signed-off-by: Radim Krčmář <address@hidden>
> > Signed-off-by: Gerd Hoffmann <address@hidden>
> [...]
> > +/* round up to the nearest power of 2 (0 if overflow) */
> 
> Callers need to check for overflow, but that's the callers' problem.

It's obvious that the return value is 0 in this case -- the correct
result would have been a multiple of the modulo, but I wanted to be
explicit about it.

> > +uint64_t pow2ceil(uint64_t value)
> > +{
> > +    uint8_t nlz = clz64(value);
> 
> You convert the value of clz64() from int to uint8_t only to promote it
> right back to int in every single use.  Please don't muddy the waters
> that way.

Ok, the down-cast might cause some runtime overhead.
(I don't understand why the return value of clz64() is 'int' --
 using the smallest sufficient data type seems clearer to me.)

> > +    if (is_power_of_2(value)) {
> > +        return value;
> > +    }
> > +    if (!nlz) {
> > +        return 0;
> > +    }
> > +    return 1ULL << (64 - nlz);
> > +}
> 
> Doesn't really mirror pow2floor() in master, because that one uses
> int64_t.  Fine with me, because my "[PATCH 0/2] Proactive pow2floor()
> fix, and dead code removal" changes pow2floor() to uint64_t.

Yeah, I didn't understand why that returned 'int64_t' either.

I understood that pow2floor() used is_power_of_2() because it expected
higher probability of numbers that already are the power, so the clunky
code was balanced by a faster common case; and I duplicated this.
(clz64() without hardware support is slow.)

> Unfortunately, the two patches conflict.
> 
> This patch's implementation of pow2ceil() is needlessly complicated,
> just like pow2floor() in master.  Simpler:
> 
>     uint64_t pow2ceil2(uint64_t value)
>     {
>         int n = clz64(value - 1);
>         return n ? 1ull << (64 - n) : 0;

Mapping 0 to 0 is probably what we would want in most uses, but I'd name
the function differently then -- the closest power of 2 bigger than (or
equal to) 0 is 1, and 2^64 == 0, so the result was mathematically
correct.

We also lose the ability to detect overflow after the call, so callers
would have to do it before, with a code like
  'passed_value > DESTINATION_TYPE_MAX / 2 + 1'

> I can rebase my patch on top of this one, and clean things up to my
> taste.

Ok, thanks!

---
If eliminating is_power_of_2() and using the ternary operator is fine,
I'd write it like this:

    unsigned nlz = clz64(value - 1);
    return !value ? 1 : (nlz ? 1ULL << (64 - nlz) : 0);

If we don't believe that the compiler can optimize, and after applying
all I know about QEMU coding style:

    int nlz;

    if (!value) {
        return 1;
    }
    nlz = clz64(value - 1);
    return n ? 1ull << (64 - n) : 0;