Messages in this thread | | | From | Denys Vlasenko <> | Date | Mon, 26 Mar 2012 21:56:38 +0200 | Subject | Re: [PATCH 1/1] vsprintf: optimize decimal conversion (again) |
| |
On Mon, Mar 26, 2012 at 9:51 PM, Andrew Morton <akpm@linux-foundation.org> wrote: > On Mon, 26 Mar 2012 20:51:24 +0200 > Denys Vlasenko <vda.linux@googlemail.com> wrote: > >> commit 01a2904d31d2373886f489429ec662c9be64a6ab >> Author: Denys Vlasenko <vda.linux@googlemail.com> >> 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?
The second check should be just BITS_PER_LONG_LONG != 64, but we don't have BITS_PER_LONG_LONG.
-- vda -- 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/
| |