lkml.org 
[lkml]   [2015]   [Mar]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Date
    SubjectRe: [RFC] lib/vsprintf.c: Even faster decimal conversion
    On Wed, Mar 18, 2015 at 1:50 AM, Denys Vlasenko
    <vda.linux@googlemail.com> wrote:
    > On Sat, Feb 21, 2015 at 12:51 AM, Rasmus Villemoes
    > <linux@rasmusvillemoes.dk> wrote:
    >> The most expensive part of decimal conversion is the divisions by 10
    >> (albeit done using reciprocal multiplication with appropriately chosen
    >> constants). I decided to see if one could eliminate around half of
    >> these multiplications by emitting two digits at a time, at the cost of
    >> a 200 byte lookup table, and it does indeed seem like there is
    >> something to be gained, especially on 64 bits.
    > ...
    > ...
    >> +char *put_dec_trunc8(char *buf, unsigned r)
    >> {
    >> + unsigned q;
    >> +
    >> + /* 1 <= r < 10^8 */
    >> + if (r < 100)
    >> + goto out_r;
    >> +
    >> + /* 100 <= r < 10^8 */
    >> + q = (r * (u64)0x28f5c29) >> 32;
    >> + *((u16 *)buf) = decpair[r - 100*q];
    >> + buf += 2;
    >> +
    >> + /* 1 <= q < 10^6 */
    >> + if (q < 100)
    >> + goto out_q;
    >> +
    >> + /* 100 <= q < 10^6 */
    >> + r = (q * (u64)0x28f5c29) >> 32;
    >> + *((u16 *)buf) = decpair[q - 100*r];
    >> + buf += 2;
    >> +
    >> + /* 1 <= r < 10^4 */
    >> + if (r < 100)
    >> + goto out_r;
    >> +
    >> + /* 100 <= r < 10^4 */
    >> + q = (r * 0x147b) >> 19;
    >> + *((u16 *)buf) = decpair[r - 100*q];
    >> + buf += 2;
    >> +out_q:
    >> + /* 1 <= q < 100 */
    >> + r = q;
    >> +out_r:
    >> + /* 1 <= r < 100 */
    >> + *((u16 *)buf) = decpair[r];
    >> + buf += 2;
    >> + if (buf[-1] == '0')
    >> + buf--;
    >> return buf;
    >> }
    >
    > Your code does four 16-bit stores.

    I quoted wrong part of your email.
    Of course, I meant put_dec_full8(), not put_dec_trunc8().

    > The version below does two 32-bit ones instead,
    > and it is also marginally smaller.
    >
    > char *put_dec_full8(char *buf, unsigned r)
    > {
    > unsigned q;
    > u32 v;
    >
    > /* 0 <= r < 10^8 */
    > q = (r * (u64)0x28f5c29) >> 32;
    > v = (u32)decpair[r - 100*q] << 16;
    >
    > /* 0 <= q < 10^6 */
    > r = (q * (u64)0x28f5c29) >> 32;
    > v = v | decpair[q - 100*r];
    > ((u32*)buf)[0] = v;
    >
    > /* 0 <= r < 10^4 */
    > q = (r * 0x147b) >> 19;
    > v = (u32)decpair[r - 100*q] << 16;
    >
    > /* 0 <= q < 100 */
    > v = v | decpair[q];
    > ((u32*)buf)[1] = v;
    >
    > return buf + 8;
    > }
    >
    > It may be faster not only because of having fewer stores,
    > but because on x86, this code (moving 16-bit halves):
    >
    > movw decpair(%ebx,%ebx), %dx
    > movw %dx, 4(%eax)
    > movw decpair(%ecx,%ecx), %dx
    > movw %dx, 6(%eax)
    >
    > suffers from register merge stall when 16-bit value
    > is read into lower part of %edx. 32-bit code
    > has no such stalls:
    >
    > movzwl decpair(%ebx,%ebx), %edx
    > sall $16, %edx
    > movzwl decpair(%ecx,%ecx), %ecx
    > orl %ecx, %edx
    > movl %edx, 4(%eax)
    >
    >
    > Before you ask:
    > I didn't manage to extend this trick to a code
    > with one 64-bit store which is not larger.


    \
     
     \ /
      Last update: 2015-03-18 02:01    [W:4.435 / U:0.000 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site