Re: [PATCH] lib/int_sqrt.c: Optimize square root function

[Linus Torvalds]

Hmm. I don't disagree, but would like some more feedback.

Davidlohr - you were the person to touch this function last (commit
30493cc9dddb: "lib/int_sqrt.c: optimize square root algorithm"), and
you did so for performance reasons. And in fact, when you did that,
you removed that initial loop:

-       one = 1UL << (BITS_PER_LONG - 2);
-       while (one > op)
-               one >>= 2;

but I'm not sure that was actually all that conscious, I think the
real optimization was the changes inside the loop to make the final
real loop faster and simpler.

Also, you had performance numbers, so presumably a test harness for it
all. It probably depends a lot on the actual distribution of argument
values, of course, but it would be good to accompany the patch with
actual real numbers like lasty time.

(I'm also not entirely sure what uses int_sqrt() that ends up being so
performance-critical, so it would be good to document that too, since
that probably also matters for the "what's the normal argument range"
question..)

                           Linus


On Mon, Feb 2, 2015 at 9:12 AM, Anshul Garg <aksgarg1989@xxxxxxxxx> wrote:
> From: Anshul Garg <aksgarg1989@xxxxxxxxx>
>
> Unnecessary instructions are executing even though m is
> greater than x so added logic to make m less than equal to
> x before performing these operations.
>
> Signed-off-by: Anshul Garg <aksgarg1989@xxxxxxxxx>
> ---
>  lib/int_sqrt.c |    3 +++
>  1 file changed, 3 insertions(+)
>
> diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c
> index 1ef4cc3..64ae722 100644
> --- a/lib/int_sqrt.c
> +++ b/lib/int_sqrt.c
> @@ -22,6 +22,9 @@ unsigned long int_sqrt(unsigned long x)
>                 return x;
>
>         m = 1UL << (BITS_PER_LONG - 2);
> +
> +       while (m > x)
> +               m >>= 2;
>         while (m != 0) {
>                 b = y + m;
>                 y >>= 1;
> --
> 1.7.9.5
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> http://www.avast.com
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/