linux-kernel - Re: [PATCH 3/4] lib: vsprintf: Optimize put_dec

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAK1hOcP5uuQafdQRmiAtLMMOos2ZZuOYU8qZgdg6LANfWdAjiw@mail.gmail.com>
Date:	Tue, 25 Sep 2012 15:00:49 +0200
From:	Denys Vlasenko <vda.linux@...glemail.com>
To:	George Spelvin <linux@...izon.com>
Cc:	mpn@...gle.com, hughd@...gle.com, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 3/4] lib: vsprintf: Optimize put_dec_trunc8

On Tue, Sep 25, 2012 at 1:44 PM, George Spelvin <linux@...izon.com> wrote:
> Thanks to Denys Vlasenko for sending me his benchmarking code.
>
> I went and hacked on it to ransomize the numbers being converted more,
> since repeatedly converting the same number underestimates the number
> of branch mispredictions.
>
> Then I tried computing the number of digits beforehand, as mentioned
> in my earlier message, and it came out slightly slower.  The code is:
>
> static noinline_for_stack
> char *put_dec_trunc8(char *buf, unsigned n)
> {
>         static unsigned const pow10[9] = { 0, 10, 100, 1000, 10000, 100000,
>                                          1000000, 10000000, 100000000 };
>         unsigned digits = (19 * fls(n) + 6) >> 6;  /* Valid for < 44 bits */

fls() itself may be more expensive than a few jumps.

> But!  With more extensive refactoring of the number() code, computing
> the number of digits at the beginning can eliminate the entire business
> of formatting into tmp[] and copying backward.  We'll first compute the
> number of digits, check for buffer overflow, insert the printf padding,
> and then call the number-formatting code, passing the number of digits in.
>
> It seems plausible that the resultant simplification will produce a
> speedup.
>
> I'm going to experiment with that.  Denys, since I'm playing in your sandbox,
> do you have any violent objections to that?

I don't object.

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