Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: Linux: Kernel

[PATCH] Reduce the number of expensive division instructions done by _parse_integer()

  

 
Linux kernel RSS feed   Index | Next | Previous | View Threaded


dhowells at redhat

Feb 9, 2012, 7:48 AM

Post #1 of 13 (68 views)
Permalink
[PATCH] Reduce the number of expensive division instructions done by _parse_integer()
_parse_integer() does one or two division instructions (which are slow) per
digit parsed to perform the overflow check.

Furthermore, these are particularly expensive examples of division instruction
as the number of clock cycles required to complete them may go up with the
position of the most significant set bit in the dividend:

if (*res > div_u64(ULLONG_MAX - val, base))

which is as maximal as possible.

Worse, on 32-bit arches, more than one of these division instructions may be
required per digit.

So, assuming we don't support a base of more than 16, skip the check if the
top nibble of the result is not set at this point.

Signed-off-by: David Howells <dhowells [at] redhat>
---

lib/kstrtox.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/lib/kstrtox.c b/lib/kstrtox.c
index 7a94c8f..f80c896 100644
--- a/lib/kstrtox.c
+++ b/lib/kstrtox.c
@@ -64,7 +64,7 @@ unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long

if (val >= base)
break;
- if (*res > div_u64(ULLONG_MAX - val, base))
+ if (unlikely(*res >> 60) && *res > div_u64(ULLONG_MAX - val, base))
overflow = 1;
*res = *res * base + val;
rv++;

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


eric.dumazet at gmail

Feb 9, 2012, 8:28 AM

Post #2 of 13 (62 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
Le jeudi 09 février 2012 à 15:48 +0000, David Howells a écrit :
> _parse_integer() does one or two division instructions (which are slow) per
> digit parsed to perform the overflow check.
>
> Furthermore, these are particularly expensive examples of division instruction
> as the number of clock cycles required to complete them may go up with the
> position of the most significant set bit in the dividend:
>
> if (*res > div_u64(ULLONG_MAX - val, base))
>
> which is as maximal as possible.
>
> Worse, on 32-bit arches, more than one of these division instructions may be
> required per digit.
>
> So, assuming we don't support a base of more than 16, skip the check if the
> top nibble of the result is not set at this point.
>
> Signed-off-by: David Howells <dhowells [at] redhat>
> ---
>
> lib/kstrtox.c | 2 +-
> 1 files changed, 1 insertions(+), 1 deletions(-)
>
> diff --git a/lib/kstrtox.c b/lib/kstrtox.c
> index 7a94c8f..f80c896 100644
> --- a/lib/kstrtox.c
> +++ b/lib/kstrtox.c
> @@ -64,7 +64,7 @@ unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long
>
> if (val >= base)
> break;
> - if (*res > div_u64(ULLONG_MAX - val, base))
> + if (unlikely(*res >> 60) && *res > div_u64(ULLONG_MAX - val, base))
> overflow = 1;
> *res = *res * base + val;
> rv++;
>
> -

You could avoid the divide and have cleaner code I think.

unsigned long long next = *res * base + val;

if (next < *res)
overflow = 1;
*res = next;


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


eric.dumazet at gmail

Feb 9, 2012, 8:42 AM

Post #3 of 13 (64 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
Le jeudi 09 février 2012 à 17:28 +0100, Eric Dumazet a écrit :

> You could avoid the divide and have cleaner code I think.
>
> unsigned long long next = *res * base + val;
>
> if (next < *res)
> overflow = 1;
> *res = next;
>

Oh well, this one is better.

unsigned long long next = *res * base;

if (next < *res)
overflow = 1;
*res = next + val;




--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


torvalds at linux-foundation

Feb 9, 2012, 8:58 AM

Post #4 of 13 (63 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
On Thu, Feb 9, 2012 at 8:28 AM, Eric Dumazet <eric.dumazet [at] gmail> wrote:
>
> You could avoid the divide and have cleaner code I think.
>
>        unsigned long long next = *res * base + val;
>
>        if (next < *res)
>                overflow = 1;
>        *res = next;

No. That pattern only works for a single addition.

For multiplication, you can overflow *and* still be bigger than the
starting value.

You either need to do the multiplication in a wider type (which would
be the natural way to do it on many 64-bit architectures, since they
often support 64x64->128 bit multiplies, and then doing a carry-add is
trivial), or you need to check the value before the multiplication. Or
you need to have a multiply that gives you overflow information, which
most don't.

So David's patch looks ok, although if this really is
performance-critical (and I could imagine some crazy /proc or /sys
access loads where the divide really does show up very clearly) I do
think it could be even done more efficiently. But probably only if we
start doing some arch-specific stuff.

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


torvalds at linux-foundation

Feb 9, 2012, 9:08 AM

Post #5 of 13 (63 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
On Thu, Feb 9, 2012 at 8:58 AM, Linus Torvalds
<torvalds [at] linux-foundation> wrote:
>
> So David's patch looks ok, although if this really is
> performance-critical (and I could imagine some crazy /proc or /sys
> access loads where the divide really does show up very clearly) I do
> think it could be even done more efficiently. But probably only if we
> start doing some arch-specific stuff.

Looking at the code generated, the "val >> 60" thing actually does
generate a shift, and at least on x86-64, the attached patch generates
better code.

David, does this work for you? I also removed the nasty pointer
indirection crap.

Linus
Attachments: patch.diff (1.20 KB)


dhowells at redhat

Feb 9, 2012, 9:46 AM

Post #6 of 13 (63 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
Linus Torvalds <torvalds [at] linux-foundation> wrote:

> Looking at the code generated, the "val >> 60" thing actually does
> generate a shift, and at least on x86-64, the attached patch generates
> better code.

On fixed-size instruction arches, the runtime shift is probably the better
option, as simply loading 64-bit large constant would take likely take at
least four instructions - and might involve a shift anyway. On the other
hand, it seems the compiler can optimise your suggestion fairly well. In both
cases, the 64-bit arithmetic can be reduced to 32-bit arithmetic on the MSW
only on 32-bit arches.

On x86_64 we have:

400649: 48 89 d8 mov %rbx,%rax
40064c: 48 c1 e8 3c shr $0x3c,%rax
400650: 48 85 c0 test %rax,%rax
400653: 75 52 jne 4006a7 <_parse_integer+0xa7>

And on i386 we have:

8048532: 8b 54 24 14 mov 0x14(%esp),%edx
...
8048538: 89 c7 mov %eax,%edi
804853a: c1 ea 1c shr $0x1c,%edx
804853d: 85 d2 test %edx,%edx
804853f: 75 79 jne 80485ba <_parse_integer+0xda>

With your code, we have on x86_64:

40062d: 49 bf 00 00 00 00 00 movabs $0xf000000000000000,%r15
400634: 00 00 f0
...
400659: 4c 85 fb test %r15,%rbx
40065c: 75 59 jne 4006b7 <_parse_integer+0xb7>

And on i386:

804853c: 89 c7 mov %eax,%edi
804853e: f7 44 24 1c 00 00 00 testl $0xf0000000,0x1c(%esp)
8048545: f0
8048546: 75 79 jne 80485c1 <_parse_integer+0xe1>

But it will work too. And I like the pointer indirection removal as well.

I'm not sure there's a lot to choose between them, though I prefer mine as I
think it produces slightly smaller code.

Want me to wrap these changes up with my patch description?

David
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


torvalds at linux-foundation

Feb 9, 2012, 9:56 AM

Post #7 of 13 (63 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
On Thu, Feb 9, 2012 at 9:46 AM, David Howells <dhowells [at] redhat> wrote:
>
> On fixed-size instruction arches, the runtime shift is probably the better
> option, as simply loading 64-bit large constant would take likely take at
> least four instructions - and might involve a shift anyway.

Bah. The constant is hoisted out of the loop on anything that has
enough registers - and "cannot generate constants" is almost
universally associated with "fair amount of registers".

The exception to that would be architectures with small register sets,
and particularly 32-bit ones. There, the 64-bit value and the multiply
likely not only takes more registers, but also kills registers due to
a function call. On the other hand "few 32-bit registers" is mainly
32-bit 386, which has no problems with a 32-bit constant.

And even if you have "out-of-line 64-bit multiply killing registers so
that you can't hoist the constant", even then gcc knows all about
those "big constants can be expensive" and likely knows how to
optimize them.

In particular, this big constant takes two instructions to generate
even in the absolute *worst* case: one to generate the constant 15,
one to shift it left by 60 (or 28, on a 32-bit setup).

But I don't have access to some broken "I can't do constants well"
architecture to actually test. Gcc could generate crazy bad code, but
almost certainly won't.

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


dhowells at redhat

Feb 9, 2012, 10:07 AM

Post #8 of 13 (64 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
Linus Torvalds <torvalds [at] linux-foundation> wrote:

> Bah. The constant is hoisted out of the loop on anything that has
> enough registers - and "cannot generate constants" is almost
> universally associated with "fair amount of registers".

True.

Do you want me to attach my patch description to your patch, or do you want to
do that?

David
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


torvalds at linux-foundation

Feb 9, 2012, 10:08 AM

Post #9 of 13 (64 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
On Thu, Feb 9, 2012 at 10:07 AM, David Howells <dhowells [at] redhat> wrote:
>
> Do you want me to attach my patch description to your patch, or do you want to
> do that?

I'll commit it as yours and with your commentary, my changes were
purely cosmetic and just made the x86-64 inner loop look better.

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


dhowells at redhat

Feb 9, 2012, 10:50 AM

Post #10 of 13 (53 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
Linus Torvalds <torvalds [at] linux-foundation> wrote:

> > Do you want me to attach my patch description to your patch, or do you
> > want to do that?
>
> I'll commit it as yours and with your commentary, my changes were
> purely cosmetic and just made the x86-64 inner loop look better.

Thanks!

David
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


torvalds at linux-foundation

Feb 9, 2012, 11:14 AM

Post #11 of 13 (54 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
Btw, what was the load that you noticed this on?

Because quite frankly, I think we only support bases 8/10/16 in the
kernel, and if you really have some case where this all is expensive,
it might be better to simply have three different functions for the
three bases. That would turn the multiplies into constants too, and
also simplify the character tests.

That said, I can't really see how this could ever be all that hot a
function. Did you ever see it in a profile, or was this all just from
looking at the code?

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


dhowells at redhat

Feb 9, 2012, 11:23 AM

Post #12 of 13 (53 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
Linus Torvalds <torvalds [at] linux-foundation> wrote:

> Btw, what was the load that you noticed this on?
>
> Because quite frankly, I think we only support bases 8/10/16 in the
> kernel, and if you really have some case where this all is expensive,
> it might be better to simply have three different functions for the
> three bases. That would turn the multiplies into constants too, and
> also simplify the character tests.
>
> That said, I can't really see how this could ever be all that hot a
> function. Did you ever see it in a profile, or was this all just from
> looking at the code?

Just by looking at the code. I can't think of anything particularly where
this is likely to be encountered in a critical path.

David
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/


adobriyan at gmail

Feb 10, 2012, 5:50 AM

Post #13 of 13 (47 views)
Permalink
Re: [PATCH] Reduce the number of expensive division instructions done by _parse_integer() [In reply to]
On Thu, Feb 9, 2012 at 10:14 PM, Linus Torvalds
<torvalds [at] linux-foundation> wrote:

Ugh, I'm late to the party.

> Because quite frankly, I think we only support bases 8/10/16 in the
> kernel, and if you really have some case where this all is expensive,
> it might be better to simply have three different functions for the
> three bases. That would turn the multiplies into constants too, and
> also simplify the character tests.

base 2 is used to sort of autolimit input to 0/1 characters.

> That said, I can't really see how this could ever be all that hot a
> function. Did you ever see it in a profile, or was this all just from
> looking at the code?

That's why there was no such check from the beginning -- not
performance critical.
We could maintain small table from which digit overflow can happen,
but since this is already committed...

There is CONFIG_TEST_KSTRTOX, does it still passes?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo [at] vger
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Linux kernel RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.