lkml.org 
[lkml]   [2012]   [Mar]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Date
    SubjectRe: [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/

    \
     
     \ /
      Last update: 2012-03-26 21:59    [W:5.839 / U:0.012 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site