From: David Laight <David.Laight@ACULAB.COM>
To: "'Crt Mori'" <cmo@melexis.com>, Peter Zijlstra <peterz@infradead.org>
Cc: Jonathan Cameron <jic23@kernel.org>,
Ingo Molnar <mingo@kernel.org>,
Andrew Morton <akpm@linux-foundation.org>,
Kees Cook <keescook@chromium.org>,
Rusty Russell <rusty@rustcorp.com.au>,
Ian Abbott <abbotti@mev.co.uk>,
"Larry Finger" <Larry.Finger@lwfinger.net>,
Niklas Soderlund <niklas.soderlund+renesas@ragnatech.se>,
Thomas Gleixner <tglx@linutronix.de>,
Krzysztof Kozlowski <krzk@kernel.org>,
Masahiro Yamada <yamada.masahiro@socionext.com>,
"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
"linux-iio@vger.kernel.org" <linux-iio@vger.kernel.org>,
Joe Perches <joe@perches.com>
Subject: RE: [PATCH v10 1/3] lib: Add strongly typed 64bit int_sqrt
Date: Wed, 20 Dec 2017 16:46:25 +0000 [thread overview]
Message-ID: <c3462afd27d14c8684ee33ef6623a31a@AcuMS.aculab.com> (raw)
In-Reply-To: <CAKv63uuL9+xzF7KruhYwSY68-M0=aJSvJOr5Y0vVBiX8ebqfeg@mail.gmail.com>
From: Crt Mori
> Sent: 20 December 2017 16:17
>
> On 20 December 2017 at 17:00, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Wed, Dec 20, 2017 at 02:39:26PM +0000, David Laight wrote:
> >
> >> With minor changes it ought to be possible to remove most of the
> >> 64bit arithmetic and shifts.
> >>
> >> If you care about performance then using 32 bit maths will be much faster.
> >
> > Some, u64 add/sub/shift isn't exactly expensive, but yes, I also
> > indicated that improvement is possible. At the very least y can be made
> > a u32 I suppose.
>
> OK, is there any more easy optimizations you see?
I think this version works.
It doesn't have the optimisation for small values.
unsigned int sqrt64(unsigned long long x)
{
unsigned int x_hi = x >> 32;
unsigned int b = 0;
unsigned int y = 0;
unsigned int i;
for (i = 0; i < 32; i++) {
b <<= 2;
b |= x_hi >> 30;
x_hi <<= 2;
if (i == 15)
x_hi = x;
y <<= 1;
if (b > y)
b -= ++y;
}
return y;
}
Put it through cc -O3 -m32 -c -o sqrt64.o sqrt64.c and then objdump sqrt64.o
and compare to that of your version.
David
next prev parent reply other threads:[~2017-12-20 16:46 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-12-20 14:20 [PATCH v10 1/3] lib: Add strongly typed 64bit int_sqrt Crt Mori
2017-12-20 14:39 ` David Laight
2017-12-20 15:41 ` Crt Mori
2017-12-20 16:00 ` Peter Zijlstra
2017-12-20 16:17 ` Crt Mori
2017-12-20 16:46 ` David Laight [this message]
2017-12-20 17:19 ` Joe Perches
2017-12-21 10:02 ` David Laight
2017-12-20 17:30 ` Crt Mori
2017-12-21 10:08 ` David Laight
2017-12-21 10:59 ` David Laight
2017-12-21 11:43 ` David Laight
2017-12-21 13:17 ` Crt Mori
2017-12-21 13:56 ` David Laight
2017-12-21 14:11 ` Peter Zijlstra
2017-12-21 14:48 ` David Laight
2017-12-22 13:44 ` Crt Mori
2018-01-09 15:18 ` Crt Mori
2018-01-12 9:41 ` David Laight
2018-01-15 8:17 ` Crt Mori
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=c3462afd27d14c8684ee33ef6623a31a@AcuMS.aculab.com \
--to=david.laight@aculab.com \
--cc=Larry.Finger@lwfinger.net \
--cc=abbotti@mev.co.uk \
--cc=akpm@linux-foundation.org \
--cc=cmo@melexis.com \
--cc=jic23@kernel.org \
--cc=joe@perches.com \
--cc=keescook@chromium.org \
--cc=krzk@kernel.org \
--cc=linux-iio@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=niklas.soderlund+renesas@ragnatech.se \
--cc=peterz@infradead.org \
--cc=rusty@rustcorp.com.au \
--cc=tglx@linutronix.de \
--cc=yamada.masahiro@socionext.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).