Re: [PATCH 3/4] lib: vsprintf: Optimize put_dec_trunc8

[Denys Vlasenko]

On Tue, Sep 25, 2012 at 1:44 PM, George Spelvin <linux@xxxxxxxxxxx> 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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/