Re: [PATCH 1/1] vsprintf: optimize decimal conversion (again)

From: Andrew Morton
Date: Mon Mar 26 2012 - 15:51:28 EST

On Mon, 26 Mar 2012 20:51:24 +0200
Denys Vlasenko <vda.linux@xxxxxxxxxxxxxx> wrote:

> commit 01a2904d31d2373886f489429ec662c9be64a6ab
> Author: Denys Vlasenko <vda.linux@xxxxxxxxxxxxxx>
> Date: Mon Mar 26 20:40:53 2012 +0200
> vsprintf: optimize decimal conversion (again)
> Previous code was using optimizations which were developed
> to work well even on narrow-word CPUs (by today's standards).
> But Linux runs only on 32-bit and wider CPUs. We can use that.
> First: using 32x32->64 multiply and trivial 32-bit shift,
> we can correctly divide by 10 much larger numbers, and thus
> we can print groups of 9 digits instead of groups of 5 digits.
> Next: there are two algorithms to print larger numbers.
> One is generic: divide by 1000000000 and repeatedly print
> groups of (up to) 9 digits. It's conceptually simple,
> but requires an (unsigned long long) / 1000000000 division.
> Second algorithm splits 64-bit unsigned long long into 16-bit chunks,
> manipulates them cleverly and generates groups of 4 decimal digits.
> It so happens that it does NOT require long long division.
> If long is > 32 bits, division of 64-bit values is relatively easy,
> and we will use the first algorithm.
> If long long is > 64 bits (strange architecture with VERY large long long),
> second algorithm can't be used, and we again use the first one.
> Else (if long is 32 bits and long long is 64 bits) we use second one.
> And third: there is a simple optimization which takes fast path
> not only for zero as was done before, but for all one-digit numbers.
> In all tested cases new code is faster than old one, in many cases by 30%,
> in few cases by more than 50% (for example, on x86-32, conversion of 12345678).
> Code growth is ~0 in 32-bit case and ~130 bytes in 64-bit case.

This patch is so nutty that I like it.

> +#if BITS_PER_LONG != 32 || (~(0ULL)>>1) != ((1ULL<<63)-1)

What's this for?

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at