lkml.org 
[lkml]   [2012]   [Sep]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [PATCH 2/4] lib: vsprintf: Optimize division by 10000
On Fri, Aug 3, 2012 at 7:21 AM, George Spelvin <linux@horizon.com> wrote:
> The same multiply-by-inverse technique can be used to
> convert division by 10000 to a 32x32->64-bit multiply.
>
> Signed-off-by: George Spelvin <linux@horizon.com>
> ---
> lib/vsprintf.c | 60 +++++++++++++++++++++++++++++++-------------------------
> 1 file changed, 33 insertions(+), 27 deletions(-)
>
> This is something of an RFC, I haven't benchmarked the helper
> function. But it sure cleans up the code!

Can you please do that before you send alterations
to the code which *was* benchmarked?


> +static
> +unsigned put_dec_helper4(char *buf, unsigned x)
> +{
> + uint32_t q = (x * (uint64_t)0x346DC5D7) >> 43;
> +
> + put_dec_full4(buf, x - q * 10000);
> + return q;
> }
>
> /* Based on code by Douglas W. Jones found at
> @@ -277,28 +292,19 @@ char *put_dec(char *buf, unsigned long long n)
> d3 = (h >> 16); /* implicit "& 0xffff" */
>
> q = 656 * d3 + 7296 * d2 + 5536 * d1 + ((uint32_t)n & 0xffff);
> + q = put_dec_helper4(buf, q);
> +
> + q += 7671 * d3 + 9496 * d2 + 6 * d1;
> + q = put_dec_helper4(buf+4, q);
> +
> + q += 4749 * d3 + 42 * d2;
> + q = put_dec_helper4(buf+8, q);
>
> - buf = put_dec_full4(buf, q % 10000);
> - q = q / 10000;
> -
> - d1 = q + 7671 * d3 + 9496 * d2 + 6 * d1;
> - buf = put_dec_full4(buf, d1 % 10000);
> - q = d1 / 10000;
> -
> - d2 = q + 4749 * d3 + 42 * d2;
> - buf = put_dec_full4(buf, d2 % 10000);
> - q = d2 / 10000;
> -
> - d3 = q + 281 * d3;
> - if (!d3)
> - goto done;
> - buf = put_dec_full4(buf, d3 % 10000);
> - q = d3 / 10000;
> - if (!q)
> - goto done;
> - buf = put_dec_full4(buf, q);
> - done:
> - while (buf[-1] == '0')
> + q += 281 * d3;
> + buf += 12;
> + if (q)
> + buf = put_dec_trunc8(buf, q);
> + else while (buf[-1] == '0')
> --buf;

gcc was already doing that optimization for us.
It will use a larger constant and shift, but that
changes neither size nor speed.

Moreover, put_dec_helper4 will get inlined,
so the generated assembly code will be very similar.

Here is the comparison of the x86-32 assembly
of the fragment which does "x / 10000" thing,
before and after the patch:

-01 c6 add %eax,%esi
-b8 59 17 b7 d1 mov $0xd1b71759,%eax
-f7 e6 mul %esi
-89 d3 mov %edx,%ebx
-89 f2 mov %esi,%edx
-c1 eb 0d shr $0xd,%ebx

+01 c7 add %eax,%edi
+b8 d7 c5 6d 34 mov $0x346dc5d7,%eax
+f7 e7 mul %edi
+89 55 e8 mov %edx,-0x18(%ebp)
+8b 5d e8 mov -0x18(%ebp),%ebx
+89 fa mov %edi,%edx
+89 45 e4 mov %eax,-0x1c(%ebp)
+c1 eb 0b shr $0xb,%ebx

Poor gcc got confused, and generated somewhat
worse code (spilling and immediately reloading upper
part of 32x32->64 multiply).

Please test and benchmark your changes to this code
before submitting them.

--
vda


\
 
 \ /
  Last update: 2012-09-24 11:41    [W:0.133 / U:0.720 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site