Re: [PATCH v2] sched/cputime: make scale_stime() more precise

[Oleg Nesterov <oleg@redhat.com>]

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.GA30620@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.