On 05/19, Peter Zijlstra wrote:
>
> > The new implementation does the additional div64_u64_rem() but according
> > to my naive measurements it is faster on x86_64, much faster if rtime/etc
> > are big enough. See
> >
> > https://lore.kernel.org/lkml/20200123130541.ga30...@redhat.com/
>
> Right, so -m32 when ran on x86_64 CPUs isn't really fair, because then
> it still has hardware fls() for ilog2() and a massively fast mult and
> division instruction. Try and run this on a puny 32bit ARM that maybe
> has a hardware multiplier on.
OK,
> Anyway, how about we write it like the below and then when some puny
> architecture comes complaining we can use Linus' original algorithm for
> their arch implementation.
Sure, I am fine either way, but...
> +static inline u64 mul_u64_u64_div_u64(u64 a, u64 mul, u64 div)
> {
> u64 q;
>
> asm ("mulq %2; divq %3" : "=a" (q)
> - : "a" (a), "rm" ((u64)mul), "rm" ((u64)div)
> + : "a" (a), "rm" (mul), "rm" (div)
> : "rdx");
...
> +#ifndef mul_u64_u64_div_u64
> +static inline u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 c)
> +{
> + u64 res = 0, div, rem;
> + int shift;
> +
> + /* can a * b overflow ? */
> + if (ilog2(a) + ilog2(b) > 62) {
> + /*
> + * (b * a) / c is equal to
> + *
> + * (b / c) * a +
> + * (b % c) * a / c
> + *
> + * if nothing overflows. Can the 1st multiplication
> + * overflow? Yes, but we do not care: this can only
> + * happen if the end result can't fit in u64 anyway.
> + *
> + * So the code below does
> + *
> + * res = (b / c) * a;
> + * b = b % c;
> + */
> + div = div64_u64_rem(b, c, &rem);
> + res = div * a;
> + b = rem;
> +
> + shift = ilog2(a) + ilog2(b) - 62;
> + if (shift > 0) {
> + /* drop precision */
> + b >>= shift;
> + c >>= shift;
> + if (!c)
> + return res;
> + }
> + }
> +
> + return res + div64_u64(a * b, c);
> +}
Note that according to my measurements the "asm" version is slower than
the generic code above when "a * b" doesn't fit u64.
Nevermind, I agree with your version. Will you send this patch or do you
want me to make V3 ?
Oleg.
