lkml.org 
[lkml]   [2012]   [Feb]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
SubjectRe: [PATCH] Reduce the number of expensive division instructions done by _parse_integer()
From
Date
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@redhat.com>
> ---
>
> 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@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
\
 
 \ /
  Last update: 2012-02-09 17:31    [W:0.810 / U:0.208 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site