Messages in this thread | | | Date | Thu, 5 Feb 2015 10:43:33 -0800 | Subject | Re: [PATCH] lib/int_sqrt.c: Optimize square root function | From | Anshul Garg <> |
| |
On Thu, Feb 5, 2015 at 10:33 AM, Linus Torvalds <torvalds@linux-foundation.org> wrote: > On Thu, Feb 5, 2015 at 10:20 AM, Linus Torvalds > <torvalds@linux-foundation.org> wrote: >> >> Hmm. I did that too [..] > > Side note: one difference in our results (apart from possibly just CPU > uarch details) is that my loop goes to 100M to make it easier to just > time it. Which means that my load essentially had about three more > iterations over nonzero data. > > Linus
I have also done the same testing on 100 million numbers. Attaching source codes.
Below is the result ::
int_sqrt_old - current int_sqrt_new - With proposed change
anshul@ubuntu:~/kernel_latest/sqrt$ time ./int_sqrt_old
real 0m41.895s user 0m36.490s sys 0m0.365s
anshul@ubuntu:~/kernel_latest/sqrt$ time ./int_sqrt_new
real 0m39.491s user 0m36.495s sys 0m0.338s
I have run this test on Intel(R) Core(TM) i3-4000M CPU @ 2.40GHz VMWare Machine. Please check if i am doing anything wrong.
NOTE :: I have not used gcc optimizations while compilation. With O2 level optimization proposed solution is taking more time. /* * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com> * * Based on the shift-and-subtract algorithm for computing integer * square root from Guy L. Steele. */
#include <stdio.h> /** * int_sqrt - rough approximation to sqrt * @x: integer of which to calculate the sqrt * * A very rough approximation to the sqrt() function. */ #define BITS_PER_LONG (8*sizeof(long))
unsigned long int_sqrt(unsigned long x) { unsigned long b, m, y = 0;
if (x <= 1) return x;
m = 1UL << (BITS_PER_LONG - 2); while (m != 0) { b = y + m; y >>= 1;
if (x >= b) { x -= b; y += m; } m >>= 2; }
return y; }
int main() { unsigned long n = 1; for(;n<=100000000;++n) int_sqrt(n); return 0; } /* * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com> * * Based on the shift-and-subtract algorithm for computing integer * square root from Guy L. Steele. */
#include <stdio.h>
#define BITS_PER_LONG (8*sizeof(long))
/** * int_sqrt - rough approximation to sqrt * @x: integer of which to calculate the sqrt * * A very rough approximation to the sqrt() function. */ unsigned long int_sqrt(unsigned long x) { unsigned long b, m, y = 0;
if (x <= 1) return x;
m = 1UL << (BITS_PER_LONG - 2);
while(m > x ) m >>= 2;
while (m != 0) { b = y + m; y >>= 1;
if (x >= b) { x -= b; y += m; } m >>= 2; }
return y; }
int main() { unsigned long n = 1; for(;n<=100000000;++n) int_sqrt(n); return 0; }
| |