Messages in this thread
 From Denys Vlasenko <> Date Wed, 18 Mar 2015 01:52:55 +0100 Subject Re: [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:0.089 / U:1.680 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site