Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1258460 > unrolled thread

[PATCH] __div64_32: implement division by multiplication for 32-bit arches

Back to article view | Back to linux.kernel

Contents

  [PATCH] __div64_32: implement division by multiplication for 32-bit arches Alexey Brodkin <Alexey.Brodkin@synopsys.com> - 2015-10-28 23:50 +0100
    Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Nicolas Pitre <nicolas.pitre@linaro.org> - 2015-10-29 00:40 +0100
      Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Alexey Brodkin <Alexey.Brodkin@synopsys.com> - 2015-10-29 08:40 +0100
      Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Nicolas Pitre <nicolas.pitre@linaro.org> - 2015-10-30 02:30 +0100
        Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Vineet Gupta <Vineet.Gupta1@synopsys.com> - 2015-10-30 06:50 +0100
          Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches Måns Rullgård <mans@mansr.com> - 2015-10-30 13:50 +0100
        Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches Måns Rullgård <mans@mansr.com> - 2015-10-30 13:50 +0100
          Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Nicolas Pitre <nicolas.pitre@linaro.org> - 2015-10-30 16:20 +0100
            Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Alexey Brodkin <Alexey.Brodkin@synopsys.com> - 2015-10-30 17:00 +0100
              Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Nicolas Pitre <nicolas.pitre@linaro.org> - 2015-10-30 18:00 +0100
                Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches Måns Rullgård <mans@mansr.com> - 2015-10-30 18:50 +0100
        Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Alexey Brodkin <Alexey.Brodkin@synopsys.com> - 2015-10-30 15:30 +0100
    Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches kbuild test robot <lkp@intel.com> - 2015-10-29 01:40 +0100
    Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches Måns Rullgård <mans@mansr.com> - 2015-10-29 14:00 +0100
      Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Alexey Brodkin <Alexey.Brodkin@synopsys.com> - 2015-10-29 14:10 +0100
        Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches Måns Rullgård <mans@mansr.com> - 2015-10-29 14:40 +0100
    Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Russell King - ARM Linux <linux@arm.linux.org.uk> - 2015-10-29 14:40 +0100
      Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Alexey Brodkin <Alexey.Brodkin@synopsys.com> - 2015-10-29 15:40 +0100
    Re: [PATCH] __div64_32: implement division by multiplication for  32-bit arches Randy Dunlap <rdunlap@infradead.org> - 2015-10-29 18:20 +0100

#1258460 — [PATCH] __div64_32: implement division by multiplication for 32-bit arches

Existing default implementation of __div64_32() for 32-bit arches unfolds
into huge routine with tons of arithmetics like +, -, * and all of them
in loops. That leads to obvious performance degradation if do_div() is
frequently used.

Good example is extensive TCP/IP traffic.
That's what I'm getting with perf out of iperf3:
 -------------->8--------------
    30.05%  iperf3   [kernel.kallsyms]        [k] copy_from_iter
    11.77%  iperf3   [kernel.kallsyms]        [k] __div64_32
     5.44%  iperf3   [kernel.kallsyms]        [k] memset
     5.32%  iperf3   [kernel.kallsyms]        [k] stmmac_xmit
     2.70%  iperf3   [kernel.kallsyms]        [k] skb_segment
     2.56%  iperf3   [kernel.kallsyms]        [k] tcp_ack
 -------------->8--------------

do_div() here is mostly used in skb_mstamp_get() to convert nanoseconds
received from local_clock() to microseconds used in timestamp.
BTW conversion itself is as simple as "/=1000".

Fortunately we already have much better __div64_32() for 32-bit ARM.
There in case of division by constant preprocessor calculates so-called
"magic number" which is later used in multiplications instead of divisions.
It's really nice and very optimal but obviously works only for ARM
because ARM assembly is involved.

Now why don't we extend the same approach to all other 32-bit arches
with multiplication part implemented in pure C. With good compiler
resulting assembly will be quite close to manually written assembly.

And that change implements that.

But there's at least 1 problem which I don't know how to solve.
Preprocessor magic only happens if __div64_32() is inlined (that's
obvious - preprocessor has to know if divider is constant or not).

But __div64_32() is already marked as weak function (which in its turn
is required to allow some architectures to provide its own optimal
implementations). I.e. addition of "inline" for __div64_32() is not an
option.

So I do want to hear opinions on how to proceed with that patch.
Indeed there's the simplest solution - use this implementation only in
my architecture of preference (read ARC) but IMHO this change may
benefit other architectures as well.

Signed-off-by: Alexey Brodkin <abrodkin@synopsys.com>
Cc: linux-snps-arc@lists.infradead.org
Cc: Vineet Gupta <vgupta@synopsys.com>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: Stephen Hemminger <shemminger@linux-foundation.org>
Cc: David S. Miller <davem@davemloft.net>
Cc: Nicolas Pitre <nico@cam.org>
Cc: Russell King <rmk+kernel@arm.linux.org.uk>
---
 lib/div64.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 128 insertions(+), 25 deletions(-)

diff --git a/lib/div64.c b/lib/div64.c
index 62a698a..3055328 100644
--- a/lib/div64.c
+++ b/lib/div64.c
@@ -23,37 +23,140 @@
 /* Not needed on 64bit architectures */
 #if BITS_PER_LONG == 32
 
+/* our own fls implementation to make sure constant propagation is fine */
+inline int __div64_fls(int bits)
+{
+	unsigned int __left = bits, __nr = 0;
+
+	if (__left & 0xffff0000)
+		__nr += 16, __left >>= 16;
+
+	if (__left & 0x0000ff00)
+		__nr +=  8, __left >>=  8;
+
+	if (__left & 0x000000f0)
+		__nr +=  4, __left >>=  4;
+
+	if (__left & 0x0000000c)
+		__nr +=  2, __left >>=  2;
+
+	if (__left & 0x00000002)
+		__nr +=  1;
+
+	return __nr;
+}
+
+/*
+ * If the divisor happens to be constant, we determine the appropriate
+ * inverse at compile time to turn the division into a few inline
+ * multiplications instead which is much faster.
+ */
 uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)
 {
-	uint64_t rem = *n;
-	uint64_t b = base;
-	uint64_t res, d = 1;
-	uint32_t high = rem >> 32;
-
-	/* Reduce the thing a bit first */
-	res = 0;
-	if (high >= base) {
-		high /= base;
-		res = (uint64_t) high << 32;
-		rem -= (uint64_t) (high*base) << 32;
-	}
+	unsigned int __r, __b = base;
 
-	while ((int64_t)b > 0 && b < rem) {
-		b = b+b;
-		d = d+d;
-	}
+	if (!__builtin_constant_p(__b) || __b == 0) {
+		/* non-constant divisor (or zero): slow path */
+		uint64_t rem = *n;
+		uint64_t b = base;
+		uint64_t res, d = 1;
+		uint32_t high = rem >> 32;
+
+		/* Reduce the thing a bit first */
+		res = 0;
+		if (high >= base) {
+			high /= base;
+			res = (uint64_t) high << 32;
+			rem -= (uint64_t) (high*base) << 32;
+		}
+
+		while ((int64_t)b > 0 && b < rem) {
+			b = b+b;
+			d = d+d;
+		}
+
+		do {
+			if (rem >= b) {
+				rem -= b;
+				res += d;
+			}
+			b >>= 1;
+			d >>= 1;
+		} while (d);
 
-	do {
-		if (rem >= b) {
-			rem -= b;
-			res += d;
+		*n = res;
+		__r = rem;
+	} else if ((__b & (__b - 1)) == 0) {
+		/*
+		 * Trivial: __b is constant and a power of 2
+		 * gcc does the right thing with this code.
+		 * Even though code is the same as above but
+		 * we make it visually as a separate path.
+		 * Still only one of these branches will survive
+		 * pre-processor stage, so let's leave it here.
+		 */
+		__r = *n;
+		__r &= (__b - 1);
+		*n /= __b;
+	} else {
+		/* Start of preprocessor calculations */
+
+		/*
+		 * Multiply by inverse of __b: *n/b = *n*(p/b)/p
+		 * We rely on the fact that most of this code gets
+		 * optimized away at compile time due to constant
+		 * propagation and only a couple inline assembly
+		 * instructions should remain. Better avoid any
+		 * code construct that might prevent that.
+		 */
+		unsigned long long __res, __x, __t, __m, __n = *n;
+		unsigned int __p;
+		/* preserve low part of *n for reminder computation */
+		__r = __n;
+		/* determine number of bits to represent __b */
+		__p = 1 << __div64_fls(__b);
+		/* compute __m = ((__p << 64) + __b - 1) / __b */
+		__m = (~0ULL / __b) * __p;
+		__m += (((~0ULL % __b + 1) * __p) + __b - 1) / __b;
+		/* compute __res = __m*(~0ULL/__b*__b-1)/(__p << 64) */
+		__x = ~0ULL / __b * __b - 1;
+		__res = (__m & 0xffffffff) * (__x & 0xffffffff);
+		__res >>= 32;
+		__res += (__m & 0xffffffff) * (__x >> 32);
+		__t = __res;
+		__res += (__x & 0xffffffff) * (__m >> 32);
+		__t = (__res < __t) ? (1ULL << 32) : 0;
+		__res = (__res >> 32) + __t;
+		__res += (__m >> 32) * (__x >> 32);
+		__res /= __p;
+		/* End of preprocessor calculations */
+
+		/* Start of run-time calculations */
+		__res = (unsigned int)__m * (unsigned int)__n;
+		__res >>= 32;
+		__res += (unsigned int)__m * (__n >> 32);
+		__t = __res;
+		__res += (unsigned int)__n * (__m >> 32);
+		__t = (__res < __t) ? (1ULL << 32) : 0;
+		__res = (__res >> 32) + __t;
+		__res += (__m >> 32) * (__n >> 32);
+		__res /= __p;
+
+		/*
+		 * The reminder can be computed with 32-bit regs
+		 * only, and gcc is good at that.
+		 */
+		{
+			unsigned int __res0 = __res;
+			unsigned int __b0 = __b;
+
+			__r -= __res0 * __b0;
 		}
-		b >>= 1;
-		d >>= 1;
-	} while (d);
+		/* End of run-time calculations */
 
-	*n = res;
-	return rem;
+		*n = __res;
+	}
+	return __r;
 }
 
 EXPORT_SYMBOL(__div64_32);
-- 
2.4.3

--
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/

[toc] | [next] | [standalone]

#1258480 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

On Thu, 29 Oct 2015, Alexey Brodkin wrote:

> Fortunately we already have much better __div64_32() for 32-bit ARM.
> There in case of division by constant preprocessor calculates so-called
> "magic number" which is later used in multiplications instead of divisions.

It's not magic, it is science.  :-)

> It's really nice and very optimal but obviously works only for ARM
> because ARM assembly is involved.
> 
> Now why don't we extend the same approach to all other 32-bit arches
> with multiplication part implemented in pure C. With good compiler
> resulting assembly will be quite close to manually written assembly.

You appear to have left out optimizations where there is no overflow to 
carry.  That, too, can be determined at compile time.

> But there's at least 1 problem which I don't know how to solve.
> Preprocessor magic only happens if __div64_32() is inlined (that's
> obvious - preprocessor has to know if divider is constant or not).
> 
> But __div64_32() is already marked as weak function (which in its turn
> is required to allow some architectures to provide its own optimal
> implementations). I.e. addition of "inline" for __div64_32() is not an
> option.

You can't inline __div64_32().  It should remain as is and used only for 
the slow path.

For the constant based optimization to work, you need to modify do_div() 
in include/asm-generic/div64.h directly.

> So I do want to hear opinions on how to proceed with that patch.
> Indeed there's the simplest solution - use this implementation only in
> my architecture of preference (read ARC) but IMHO this change may
> benefit other architectures as well.
> 
> Signed-off-by: Alexey Brodkin <abrodkin@synopsys.com>
> Cc: linux-snps-arc@lists.infradead.org
> Cc: Vineet Gupta <vgupta@synopsys.com>
> Cc: Ingo Molnar <mingo@elte.hu>
> Cc: Stephen Hemminger <shemminger@linux-foundation.org>
> Cc: David S. Miller <davem@davemloft.net>
> Cc: Nicolas Pitre <nico@cam.org>

This email address has been unused for the last 7 years. Please update 
your reference.

> Cc: Russell King <rmk+kernel@arm.linux.org.uk>
> ---
>  lib/div64.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++----------
>  1 file changed, 128 insertions(+), 25 deletions(-)
> 
> diff --git a/lib/div64.c b/lib/div64.c
> index 62a698a..3055328 100644
> --- a/lib/div64.c
> +++ b/lib/div64.c
> @@ -23,37 +23,140 @@
>  /* Not needed on 64bit architectures */
>  #if BITS_PER_LONG == 32
>  
> +/* our own fls implementation to make sure constant propagation is fine */
> +inline int __div64_fls(int bits)
> +{
> +	unsigned int __left = bits, __nr = 0;
> +
> +	if (__left & 0xffff0000)
> +		__nr += 16, __left >>= 16;
> +
> +	if (__left & 0x0000ff00)
> +		__nr +=  8, __left >>=  8;
> +
> +	if (__left & 0x000000f0)
> +		__nr +=  4, __left >>=  4;
> +
> +	if (__left & 0x0000000c)
> +		__nr +=  2, __left >>=  2;
> +
> +	if (__left & 0x00000002)
> +		__nr +=  1;
> +
> +	return __nr;
> +}

The regular fls implementation should already give you a constant result 
if provided with a constant input.  To be sure you could use:

	__p = 1 << __fls(__b);
	BUILD_BUG_ON(!__builtin_constant_p(__p));

> +/*
> + * If the divisor happens to be constant, we determine the appropriate
> + * inverse at compile time to turn the division into a few inline
> + * multiplications instead which is much faster.
> + */
>  uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)
>  {
> -	uint64_t rem = *n;
> -	uint64_t b = base;
> -	uint64_t res, d = 1;
> -	uint32_t high = rem >> 32;
> -
> -	/* Reduce the thing a bit first */
> -	res = 0;
> -	if (high >= base) {
> -		high /= base;
> -		res = (uint64_t) high << 32;
> -		rem -= (uint64_t) (high*base) << 32;
> -	}
> +	unsigned int __r, __b = base;
>  
> -	while ((int64_t)b > 0 && b < rem) {
> -		b = b+b;
> -		d = d+d;
> -	}
> +	if (!__builtin_constant_p(__b) || __b == 0) {
> +		/* non-constant divisor (or zero): slow path */
> +		uint64_t rem = *n;
> +		uint64_t b = base;
> +		uint64_t res, d = 1;
> +		uint32_t high = rem >> 32;
> +
> +		/* Reduce the thing a bit first */
> +		res = 0;
> +		if (high >= base) {
> +			high /= base;
> +			res = (uint64_t) high << 32;
> +			rem -= (uint64_t) (high*base) << 32;
> +		}
> +
> +		while ((int64_t)b > 0 && b < rem) {
> +			b = b+b;
> +			d = d+d;
> +		}
> +
> +		do {
> +			if (rem >= b) {
> +				rem -= b;
> +				res += d;
> +			}
> +			b >>= 1;
> +			d >>= 1;
> +		} while (d);
>  
> -	do {
> -		if (rem >= b) {
> -			rem -= b;
> -			res += d;
> +		*n = res;
> +		__r = rem;
> +	} else if ((__b & (__b - 1)) == 0) {
> +		/*
> +		 * Trivial: __b is constant and a power of 2
> +		 * gcc does the right thing with this code.
> +		 * Even though code is the same as above but
> +		 * we make it visually as a separate path.
> +		 * Still only one of these branches will survive
> +		 * pre-processor stage, so let's leave it here.
> +		 */
> +		__r = *n;
> +		__r &= (__b - 1);
> +		*n /= __b;
> +	} else {
> +		/* Start of preprocessor calculations */
> +
> +		/*
> +		 * Multiply by inverse of __b: *n/b = *n*(p/b)/p
> +		 * We rely on the fact that most of this code gets
> +		 * optimized away at compile time due to constant
> +		 * propagation and only a couple inline assembly
> +		 * instructions should remain. Better avoid any
> +		 * code construct that might prevent that.
> +		 */
> +		unsigned long long __res, __x, __t, __m, __n = *n;
> +		unsigned int __p;
> +		/* preserve low part of *n for reminder computation */
> +		__r = __n;
> +		/* determine number of bits to represent __b */
> +		__p = 1 << __div64_fls(__b);
> +		/* compute __m = ((__p << 64) + __b - 1) / __b */
> +		__m = (~0ULL / __b) * __p;
> +		__m += (((~0ULL % __b + 1) * __p) + __b - 1) / __b;
> +		/* compute __res = __m*(~0ULL/__b*__b-1)/(__p << 64) */
> +		__x = ~0ULL / __b * __b - 1;
> +		__res = (__m & 0xffffffff) * (__x & 0xffffffff);
> +		__res >>= 32;
> +		__res += (__m & 0xffffffff) * (__x >> 32);
> +		__t = __res;
> +		__res += (__x & 0xffffffff) * (__m >> 32);
> +		__t = (__res < __t) ? (1ULL << 32) : 0;
> +		__res = (__res >> 32) + __t;
> +		__res += (__m >> 32) * (__x >> 32);
> +		__res /= __p;
> +		/* End of preprocessor calculations */
> +
> +		/* Start of run-time calculations */
> +		__res = (unsigned int)__m * (unsigned int)__n;
> +		__res >>= 32;
> +		__res += (unsigned int)__m * (__n >> 32);
> +		__t = __res;
> +		__res += (unsigned int)__n * (__m >> 32);
> +		__t = (__res < __t) ? (1ULL << 32) : 0;
> +		__res = (__res >> 32) + __t;
> +		__res += (__m >> 32) * (__n >> 32);
> +		__res /= __p;
> +
> +		/*
> +		 * The reminder can be computed with 32-bit regs
> +		 * only, and gcc is good at that.
> +		 */
> +		{
> +			unsigned int __res0 = __res;
> +			unsigned int __b0 = __b;
> +
> +			__r -= __res0 * __b0;
>  		}
> -		b >>= 1;
> -		d >>= 1;
> -	} while (d);
> +		/* End of run-time calculations */
>  
> -	*n = res;
> -	return rem;
> +		*n = __res;
> +	}
> +	return __r;
>  }
>  
>  EXPORT_SYMBOL(__div64_32);
> -- 
> 2.4.3
> 
> --
> 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/
> 
> 
--
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/

[toc] | [prev] | [next] | [standalone]

#1258615 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

SGkgTmljb2xhcywNCg0KT24gV2VkLCAyMDE1LTEwLTI4IGF0IDE5OjMyIC0wNDAwLCBOaWNvbGFz
IFBpdHJlIHdyb3RlOg0KPiBPbiBUaHUsIDI5IE9jdCAyMDE1LCBBbGV4ZXkgQnJvZGtpbiB3cm90
ZToNCj4gDQo+ID4gRm9ydHVuYXRlbHkgd2UgYWxyZWFkeSBoYXZlIG11Y2ggYmV0dGVyIF9fZGl2
NjRfMzIoKSBmb3IgMzItYml0IEFSTS4NCj4gPiBUaGVyZSBpbiBjYXNlIG9mIGRpdmlzaW9uIGJ5
IGNvbnN0YW50IHByZXByb2Nlc3NvciBjYWxjdWxhdGVzIHNvLWNhbGxlZA0KPiA+ICJtYWdpYyBu
dW1iZXIiIHdoaWNoIGlzIGxhdGVyIHVzZWQgaW4gbXVsdGlwbGljYXRpb25zIGluc3RlYWQgb2Yg
ZGl2aXNpb25zLg0KPiANCj4gSXQncyBub3QgbWFnaWMsIGl0IGlzIHNjaWVuY2UuICA6LSkNCg0K
SW5kZWVkLCBidXQgSSB3YXMgdW5kZXIgaW1wcmVzc2lvbiB0aGF0J3MgaG93IHBlb3BsZSBjYWxs
IHRoYXQgdmFsdWUgaW4gdGhhdA0KcGFydGljdWxhciBjYXNlLiBTbyBmb3IgbWUgaXQgbG9va3Mg
YXBwcm9wcmlhdGUgaGVyZS4NCg0KPiA+IEl0J3MgcmVhbGx5IG5pY2UgYW5kIHZlcnkgb3B0aW1h
bCBidXQgb2J2aW91c2x5IHdvcmtzIG9ubHkgZm9yIEFSTQ0KPiA+IGJlY2F1c2UgQVJNIGFzc2Vt
Ymx5IGlzIGludm9sdmVkLg0KPiA+IA0KPiA+IE5vdyB3aHkgZG9uJ3Qgd2UgZXh0ZW5kIHRoZSBz
YW1lIGFwcHJvYWNoIHRvIGFsbCBvdGhlciAzMi1iaXQgYXJjaGVzDQo+ID4gd2l0aCBtdWx0aXBs
aWNhdGlvbiBwYXJ0IGltcGxlbWVudGVkIGluIHB1cmUgQy4gV2l0aCBnb29kIGNvbXBpbGVyDQo+
ID4gcmVzdWx0aW5nIGFzc2VtYmx5IHdpbGwgYmUgcXVpdGUgY2xvc2UgdG8gbWFudWFsbHkgd3Jp
dHRlbiBhc3NlbWJseS4NCj4gDQo+IFlvdSBhcHBlYXIgdG8gaGF2ZSBsZWZ0IG91dCBvcHRpbWl6
YXRpb25zIHdoZXJlIHRoZXJlIGlzIG5vIG92ZXJmbG93IHRvIA0KPiBjYXJyeS4gIFRoYXQsIHRv
bywgY2FuIGJlIGRldGVybWluZWQgYXQgY29tcGlsZSB0aW1lLg0KDQpUaGF0IG1pZ2h0IGJlIHRo
ZSBjYXNlIC0gbGV0IG1lIGxvb2sgYXQgdGhhdCBhIGJpdCBtb3JlLg0KQnV0IHRoYXQgd2FzIG5v
dCB0aGUgYmlnZ2VzdCBwcm9ibGVtLiBJIGFjdHVhbGx5IHdhbnRlZCB0byBzZW5kIGl0DQphcyBS
RkMgYnV0IGR1ZSB0byBsYXN0IG1pbnV0ZSBjaGFuZ2UgSSBtYWRlICJnaXQgcGF0aGMtZm9ybWF0
IC0xIiBhbmQNCmZvcmdvdCB0byBjaGFuZ2UgdG9waWMgZnJvbSBQQVRDSCB0byBSRkMuDQoNCj4g
PiBCdXQgdGhlcmUncyBhdCBsZWFzdCAxIHByb2JsZW0gd2hpY2ggSSBkb24ndCBrbm93IGhvdyB0
byBzb2x2ZS4NCj4gPiBQcmVwcm9jZXNzb3IgbWFnaWMgb25seSBoYXBwZW5zIGlmIF9fZGl2NjRf
MzIoKSBpcyBpbmxpbmVkICh0aGF0J3MNCj4gPiBvYnZpb3VzIC0gcHJlcHJvY2Vzc29yIGhhcyB0
byBrbm93IGlmIGRpdmlkZXIgaXMgY29uc3RhbnQgb3Igbm90KS4NCj4gPiANCj4gPiBCdXQgX19k
aXY2NF8zMigpIGlzIGFscmVhZHkgbWFya2VkIGFzIHdlYWsgZnVuY3Rpb24gKHdoaWNoIGluIGl0
cyB0dXJuDQo+ID4gaXMgcmVxdWlyZWQgdG8gYWxsb3cgc29tZSBhcmNoaXRlY3R1cmVzIHRvIHBy
b3ZpZGUgaXRzIG93biBvcHRpbWFsDQo+ID4gaW1wbGVtZW50YXRpb25zKS4gSS5lLiBhZGRpdGlv
biBvZiAiaW5saW5lIiBmb3IgX19kaXY2NF8zMigpIGlzIG5vdCBhbg0KPiA+IG9wdGlvbi4NCj4g
DQo+IFlvdSBjYW4ndCBpbmxpbmUgX19kaXY2NF8zMigpLiAgSXQgc2hvdWxkIHJlbWFpbiBhcyBp
cyBhbmQgdXNlZCBvbmx5IGZvciANCj4gdGhlIHNsb3cgcGF0aC4NCj4gDQo+IEZvciB0aGUgY29u
c3RhbnQgYmFzZWQgb3B0aW1pemF0aW9uIHRvIHdvcmssIHlvdSBuZWVkIHRvIG1vZGlmeSBkb19k
aXYoKSANCj4gaW4gaW5jbHVkZS9hc20tZ2VuZXJpYy9kaXY2NC5oIGRpcmVjdGx5Lg0KDQpJIHRo
b3VnaHQgYWJvdXQgdGhhdCBidXQgaWYgSSByZXBsYWNlIGV4aXN0aW5nIGltcGxlbWVudGF0aW9u
IG9mIGRvX2RpdigpDQp3aXRoIHByb3Bvc2VkIGhlcmUgc29tZSBhcmNoZXMgbGlrZSBTSCBhbmQg
TUlQUyB3b24ndCBiZSBhYmxlIHRvIHVzZSB0aGVpcg0Kb3duIF9fZGl2NjRfMzIoKSBpbiBkb19k
aXYoKSBhbnkgbG9uZ2VyLg0KDQpTbyBob3cgdG8gZGVhbCB3aXRoIHRoYXQgdGhlbj8NCg0KPiA+
IFNvIEkgZG8gd2FudCB0byBoZWFyIG9waW5pb25zIG9uIGhvdyB0byBwcm9jZWVkIHdpdGggdGhh
dCBwYXRjaC4NCj4gPiBJbmRlZWQgdGhlcmUncyB0aGUgc2ltcGxlc3Qgc29sdXRpb24gLSB1c2Ug
dGhpcyBpbXBsZW1lbnRhdGlvbiBvbmx5IGluDQo+ID4gbXkgYXJjaGl0ZWN0dXJlIG9mIHByZWZl
cmVuY2UgKHJlYWQgQVJDKSBidXQgSU1ITyB0aGlzIGNoYW5nZSBtYXkNCj4gPiBiZW5lZml0IG90
aGVyIGFyY2hpdGVjdHVyZXMgYXMgd2VsbC4NCj4gPiANCj4gPiBTaWduZWQtb2ZmLWJ5OiBBbGV4
ZXkgQnJvZGtpbiA8YWJyb2RraW5Ac3lub3BzeXMuY29tPg0KPiA+IENjOiBsaW51eC1zbnBzLWFy
Y0BsaXN0cy5pbmZyYWRlYWQub3JnDQo+ID4gQ2M6IFZpbmVldCBHdXB0YSA8dmd1cHRhQHN5bm9w
c3lzLmNvbT4NCj4gPiBDYzogSW5nbyBNb2xuYXIgPG1pbmdvQGVsdGUuaHU+DQo+ID4gQ2M6IFN0
ZXBoZW4gSGVtbWluZ2VyIDxzaGVtbWluZ2VyQGxpbnV4LWZvdW5kYXRpb24ub3JnPg0KPiA+IENj
OiBEYXZpZCBTLiBNaWxsZXIgPGRhdmVtQGRhdmVtbG9mdC5uZXQ+DQo+ID4gQ2M6IE5pY29sYXMg
UGl0cmUgPG5pY29AY2FtLm9yZz4NCj4gDQo+IFRoaXMgZW1haWwgYWRkcmVzcyBoYXMgYmVlbiB1
bnVzZWQgZm9yIHRoZSBsYXN0IDcgeWVhcnMuIFBsZWFzZSB1cGRhdGUgDQo+IHlvdXIgcmVmZXJl
bmNlLg0KDQpNeSBiYWQgLSBJIGJsaW5kbHkgdG9vayB0aGF0IGVtYWlsIGZyb20geW91ciBwcmVo
aXN0b3JpYyBwYXRjaA0KIltBUk1dIDM2MTEvNDogb3B0aW1pemUgZG9fZGl2KCkgd2hlbiBkaXZp
c29yIGlzIGNvbnN0YW50Ii4NCg0KLUFsZXhleQ==
--
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/

[toc] | [prev] | [next] | [standalone]

#1259155 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

On Wed, 28 Oct 2015, Nicolas Pitre wrote:

> On Thu, 29 Oct 2015, Alexey Brodkin wrote:
> 
> > Fortunately we already have much better __div64_32() for 32-bit ARM.
> > There in case of division by constant preprocessor calculates so-called
> > "magic number" which is later used in multiplications instead of divisions.
> 
> It's not magic, it is science.  :-)
> 
> > It's really nice and very optimal but obviously works only for ARM
> > because ARM assembly is involved.
> > 
> > Now why don't we extend the same approach to all other 32-bit arches
> > with multiplication part implemented in pure C. With good compiler
> > resulting assembly will be quite close to manually written assembly.

Well... not as close at least on ARM.  Maybe 2x to 3x more costly than 
the one with assembly.  Still better than 100x or so without this 
optimization.

> > But there's at least 1 problem which I don't know how to solve.
> > Preprocessor magic only happens if __div64_32() is inlined (that's
> > obvious - preprocessor has to know if divider is constant or not).
> > 
> > But __div64_32() is already marked as weak function (which in its turn
> > is required to allow some architectures to provide its own optimal
> > implementations). I.e. addition of "inline" for __div64_32() is not an
> > option.
> 
> You can't inline __div64_32().  It should remain as is and used only for 
> the slow path.
> 
> For the constant based optimization to work, you need to modify do_div() 
> in include/asm-generic/div64.h directly.

OK... I was intrigued, so I adapted my ARM code to the generic case, 
including the overflow avoidance optimizations.  Please have look and 
tell me how this works for you.

If this patch is accepted upstream, then it could be possible to 
abstract only the actual multiplication part with some architecture 
specific assembly.

diff --git a/include/asm-generic/div64.h b/include/asm-generic/div64.h
index 8f4e319334..43c3b21dca 100644
--- a/include/asm-generic/div64.h
+++ b/include/asm-generic/div64.h
@@ -32,6 +32,149 @@
 
 #elif BITS_PER_LONG == 32
 
+/* macroized fls implementation to ensure proper constant propagation */
+#define __div64_fls(bits)						\
+({								\
+	unsigned int __left = (bits), __nr = 0;			\
+	if (__left & 0xffff0000) __nr += 16, __left >>= 16;	\
+	if (__left & 0x0000ff00) __nr +=  8, __left >>=  8;	\
+	if (__left & 0x000000f0) __nr +=  4, __left >>=  4;	\
+	if (__left & 0x0000000c) __nr +=  2, __left >>=  2;	\
+	if (__left & 0x00000002) __nr +=  1;			\
+	__nr;							\
+})
+
+/*
+ * If the divisor happens to be constant, we determine the appropriate
+ * inverse at compile time to turn the division into a few inline
+ * multiplications which ought to be much faster. And yet only if compiling
+ * with a sufficiently recent gcc version to perform proper 64-bit constant
+ * propagation.
+ *
+ * (It is unfortunate that gcc doesn't perform all this internally.)
+ */
+#define __div64_const32(n, ___b)						\
+({									\
+	/*								\
+	 * Multiplication by reciprocal of b: n / b = n * (p / b) / p	\
+	 *								\
+	 * We rely on the fact that most of this code gets optimized	\
+	 * away at compile time due to constant propagation and only	\
+	 * a few multiplication instructions should remain.		\
+	 * Hence this monstrous macro (static inline doesn't always	\
+	 * do the trick for some reason).				\
+	 */								\
+	uint64_t ___res, ___x, ___t, ___m, ___n = (n);			\
+	uint32_t ___c, ___p, ___m_lo, ___m_hi, ___n_lo, ___n_hi;	\
+									\
+	/* determine number of bits to represent b */			\
+	___p = 1 << __div64_fls(___b);					\
+									\
+	/* compute m = ((p << 64) + b - 1) / b */			\
+	___m = (~0ULL / ___b) * ___p;					\
+	___m += (((~0ULL % ___b + 1) * ___p) + ___b - 1) / ___b;	\
+									\
+	/* dividend that produces one less than the highest result */	\
+	___x = ~0ULL / ___b * ___b - 1;					\
+									\
+	/* test our m with res = m * x / (p << 64) */			\
+	___res = ((___m & 0xffffffff) * (___x & 0xffffffff)) >> 32;	\
+	___t = ___res += (___m & 0xffffffff) * (___x >> 32);		\
+	___res += (___x & 0xffffffff) * (___m >> 32);			\
+	___t = (___res < ___t) ? (1ULL << 32) : 0;			\
+	___res = (___res >> 32) + ___t;					\
+	___res += (___m >> 32) * (___x >> 32);				\
+	___res /= ___p;							\
+									\
+	/* Now sanitize and optimize what we've got. */			\
+	if (~0ULL % (___b / (___b & -___b)) == 0) {			\
+		/* those cases can be simplified with: */		\
+		___n /= (___b & -___b);					\
+		___m = ~0ULL / (___b / (___b & -___b));			\
+		___p = 1;						\
+		___c = 1;						\
+	} else if (___res != ___x / ___b) {				\
+		/*							\
+		 * We can't get away without a correction to compensate	\
+		 * for bit truncation errors.  To avoid it we'd need an	\
+		 * additional bit to represent m which would overflow	\
+		 * our 64-bit variable.					\
+		 *							\
+		 * Instead we do m = p / b and n / b = (n * m + m) / p.	\
+		 */							\
+		___c = 1;						\
+		/* Compute m = (p << 64) / b */				\
+		___m = (~0ULL / ___b) * ___p;				\
+		___m += ((~0ULL % ___b + 1) * ___p) / ___b;		\
+	} else {							\
+		/*							\
+		 * Reduce m / p, and try to clear bit 31 of m when	\
+		 * possible, otherwise that'll need extra overflow	\
+		 * handling later.					\
+		 */							\
+		unsigned int ___bits = -(___m & -___m);			\
+		___bits |= ___m >> 32;					\
+		___bits = (~___bits) << 1;				\
+		/*							\
+		 * If ___bits == 0 then setting bit 31 is  unavoidable.	\
+		 * Simply apply the maximum possible reduction in that	\
+		 * case. Otherwise the MSB of ___bits indicates the	\
+		 * best reduction we should apply.			\
+		 */							\
+		if (!___bits) {						\
+			___p /= (___m & -___m);				\
+			___m /= (___m & -___m);				\
+		} else {						\
+			___p >>= __div64_fls(___bits);			\
+			___m >>= __div64_fls(___bits);			\
+		}							\
+		/* No correction needed. */				\
+		___c = 0;						\
+	}								\
+									\
+	/*								\
+	 * Now we have a combination of 2 conditions:			\
+	 *								\
+	 * 1) whether or not we need a correction (___c), and		\
+	 *								\
+	 * 2) whether or not there might be an overflow in the cross	\
+	 *    product determined by (___m & ((1 << 63) | (1 << 31))).	\
+	 *								\
+	 * Select the best way to do the m * n / (p << 64) operation.	\
+	 * From here on there will be actual runtime code generated.	\
+	 */								\
+									\
+	___m_lo = ___m;							\
+	___m_hi = ___m >> 32;						\
+	___n_lo = ___n;							\
+	___n_hi = ___n >> 32;						\
+									\
+	if (!___c) {							\
+		___res = ((uint64_t)___m_lo * ___n_lo) >> 32;		\
+	} else if (!(___m & ((1ULL << 63) | (1ULL << 31)))) {		\
+		___res = (___m + (uint64_t)___m_lo * ___n_lo) >> 32;	\
+	} else {							\
+		___res = ___m + (uint64_t)___m_lo * ___n_lo;		\
+		___t = (___res < ___m) ? (1ULL << 32) : 0;		\
+	       	___res = (___res >> 32) + ___t;				\
+	}								\
+									\
+	if (!(___m & ((1ULL << 63) | (1ULL << 31)))) {			\
+		___res += (uint64_t)___m_lo * ___n_hi;			\
+		___res += (uint64_t)___m_hi * ___n_lo;			\
+		___res >>= 32;						\
+	} else {							\
+		___t = ___res += (uint64_t)___m_lo * ___n_hi;		\
+		___res += (uint64_t)___m_hi * ___n_lo;			\
+		___t = (___res < ___t) ? (1ULL << 32) : 0;		\
+		___res = (___res >> 32) + ___t;				\
+	}								\
+									\
+	___res += (uint64_t)___m_hi * ___n_hi;				\
+									\
+	___res / ___p;							\
+})
+
 extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);
 
 /* The unnecessary pointer compare is there
@@ -41,7 +184,20 @@ extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);
 	uint32_t __base = (base);			\
 	uint32_t __rem;					\
 	(void)(((typeof((n)) *)0) == ((uint64_t *)0));	\
-	if (likely(((n) >> 32) == 0)) {			\
+	if (__builtin_constant_p(__base) &&		\
+	    (__base & (__base - 1)) == 0) {		\
+		/* constant power of 2: gcc is fine */	\
+		__rem = (n) & (__base - 1);		\
+		(n) /= __base;				\
+	} else if ((__GNUC__ >= 4) &&			\
+	    __builtin_constant_p(__base) &&		\
+	    __base != 0) {				\
+		uint32_t __res_lo, __n_lo = (n);	\
+		(n) = __div64_const32(n, __base);	\
+		/* the remainder can be computed with 32-bit regs */ \
+		__res_lo = (n);				\
+		__rem = __n_lo - __res_lo * __base;	\
+	} else if (likely(((n) >> 32) == 0)) {		\
 		__rem = (uint32_t)(n) % __base;		\
 		(n) = (uint32_t)(n) / __base;		\
 	} else 						\
--
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/

[toc] | [prev] | [next] | [standalone]

#1259220 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

+CC Claudiu: ARC gcc expert (please scroll to botom)

On Friday 30 October 2015 06:56 AM, Nicolas Pitre wrote:
> On Wed, 28 Oct 2015, Nicolas Pitre wrote:
>
>> On Thu, 29 Oct 2015, Alexey Brodkin wrote:
>>
>>> Fortunately we already have much better __div64_32() for 32-bit ARM.
>>> There in case of division by constant preprocessor calculates so-called
>>> "magic number" which is later used in multiplications instead of divisions.
>> It's not magic, it is science.  :-)
>>
>>> It's really nice and very optimal but obviously works only for ARM
>>> because ARM assembly is involved.
>>>
>>> Now why don't we extend the same approach to all other 32-bit arches
>>> with multiplication part implemented in pure C. With good compiler
>>> resulting assembly will be quite close to manually written assembly.
> Well... not as close at least on ARM.  Maybe 2x to 3x more costly than 
> the one with assembly.  Still better than 100x or so without this 
> optimization.
>
>>> But there's at least 1 problem which I don't know how to solve.
>>> Preprocessor magic only happens if __div64_32() is inlined (that's
>>> obvious - preprocessor has to know if divider is constant or not).
>>>
>>> But __div64_32() is already marked as weak function (which in its turn
>>> is required to allow some architectures to provide its own optimal
>>> implementations). I.e. addition of "inline" for __div64_32() is not an
>>> option.
>> You can't inline __div64_32().  It should remain as is and used only for 
>> the slow path.
>>
>> For the constant based optimization to work, you need to modify do_div() 
>> in include/asm-generic/div64.h directly.
> OK... I was intrigued, so I adapted my ARM code to the generic case, 
> including the overflow avoidance optimizations.  Please have look and 
> tell me how this works for you.
>
> If this patch is accepted upstream, then it could be possible to 
> abstract only the actual multiplication part with some architecture 
> specific assembly.
>
> diff --git a/include/asm-generic/div64.h b/include/asm-generic/div64.h
> index 8f4e319334..43c3b21dca 100644
> --- a/include/asm-generic/div64.h
> +++ b/include/asm-generic/div64.h
> @@ -32,6 +32,149 @@
>  
>  #elif BITS_PER_LONG == 32
>  
> +/* macroized fls implementation to ensure proper constant propagation */
> +#define __div64_fls(bits)						\
> +({								\
> +	unsigned int __left = (bits), __nr = 0;			\
> +	if (__left & 0xffff0000) __nr += 16, __left >>= 16;	\
> +	if (__left & 0x0000ff00) __nr +=  8, __left >>=  8;	\
> +	if (__left & 0x000000f0) __nr +=  4, __left >>=  4;	\
> +	if (__left & 0x0000000c) __nr +=  2, __left >>=  2;	\
> +	if (__left & 0x00000002) __nr +=  1;			\
> +	__nr;							\
> +})
> +
> +/*
> + * If the divisor happens to be constant, we determine the appropriate
> + * inverse at compile time to turn the division into a few inline
> + * multiplications which ought to be much faster. And yet only if compiling
> + * with a sufficiently recent gcc version to perform proper 64-bit constant
> + * propagation.
> + *
> + * (It is unfortunate that gcc doesn't perform all this internally.)
> + */
> +#define __div64_const32(n, ___b)						\
> +({									\
> +	/*								\
> +	 * Multiplication by reciprocal of b: n / b = n * (p / b) / p	\
> +	 *								\
> +	 * We rely on the fact that most of this code gets optimized	\
> +	 * away at compile time due to constant propagation and only	\
> +	 * a few multiplication instructions should remain.		\
> +	 * Hence this monstrous macro (static inline doesn't always	\
> +	 * do the trick for some reason).				\
> +	 */								\
> +	uint64_t ___res, ___x, ___t, ___m, ___n = (n);			\
> +	uint32_t ___c, ___p, ___m_lo, ___m_hi, ___n_lo, ___n_hi;	\
> +									\
> +	/* determine number of bits to represent b */			\
> +	___p = 1 << __div64_fls(___b);					\
> +									\
> +	/* compute m = ((p << 64) + b - 1) / b */			\
> +	___m = (~0ULL / ___b) * ___p;					\
> +	___m += (((~0ULL % ___b + 1) * ___p) + ___b - 1) / ___b;	\
> +									\
> +	/* dividend that produces one less than the highest result */	\
> +	___x = ~0ULL / ___b * ___b - 1;					\
> +									\
> +	/* test our m with res = m * x / (p << 64) */			\
> +	___res = ((___m & 0xffffffff) * (___x & 0xffffffff)) >> 32;	\
> +	___t = ___res += (___m & 0xffffffff) * (___x >> 32);		\
> +	___res += (___x & 0xffffffff) * (___m >> 32);			\
> +	___t = (___res < ___t) ? (1ULL << 32) : 0;			\
> +	___res = (___res >> 32) + ___t;					\
> +	___res += (___m >> 32) * (___x >> 32);				\
> +	___res /= ___p;							\
> +									\
> +	/* Now sanitize and optimize what we've got. */			\
> +	if (~0ULL % (___b / (___b & -___b)) == 0) {			\
> +		/* those cases can be simplified with: */		\
> +		___n /= (___b & -___b);					\
> +		___m = ~0ULL / (___b / (___b & -___b));			\
> +		___p = 1;						\
> +		___c = 1;						\
> +	} else if (___res != ___x / ___b) {				\
> +		/*							\
> +		 * We can't get away without a correction to compensate	\
> +		 * for bit truncation errors.  To avoid it we'd need an	\
> +		 * additional bit to represent m which would overflow	\
> +		 * our 64-bit variable.					\
> +		 *							\
> +		 * Instead we do m = p / b and n / b = (n * m + m) / p.	\
> +		 */							\
> +		___c = 1;						\
> +		/* Compute m = (p << 64) / b */				\
> +		___m = (~0ULL / ___b) * ___p;				\
> +		___m += ((~0ULL % ___b + 1) * ___p) / ___b;		\
> +	} else {							\
> +		/*							\
> +		 * Reduce m / p, and try to clear bit 31 of m when	\
> +		 * possible, otherwise that'll need extra overflow	\
> +		 * handling later.					\
> +		 */							\
> +		unsigned int ___bits = -(___m & -___m);			\
> +		___bits |= ___m >> 32;					\
> +		___bits = (~___bits) << 1;				\
> +		/*							\
> +		 * If ___bits == 0 then setting bit 31 is  unavoidable.	\
> +		 * Simply apply the maximum possible reduction in that	\
> +		 * case. Otherwise the MSB of ___bits indicates the	\
> +		 * best reduction we should apply.			\
> +		 */							\
> +		if (!___bits) {						\
> +			___p /= (___m & -___m);				\
> +			___m /= (___m & -___m);				\
> +		} else {						\
> +			___p >>= __div64_fls(___bits);			\
> +			___m >>= __div64_fls(___bits);			\
> +		}							\
> +		/* No correction needed. */				\
> +		___c = 0;						\
> +	}								\
> +									\
> +	/*								\
> +	 * Now we have a combination of 2 conditions:			\
> +	 *								\
> +	 * 1) whether or not we need a correction (___c), and		\
> +	 *								\
> +	 * 2) whether or not there might be an overflow in the cross	\
> +	 *    product determined by (___m & ((1 << 63) | (1 << 31))).	\
> +	 *								\
> +	 * Select the best way to do the m * n / (p << 64) operation.	\
> +	 * From here on there will be actual runtime code generated.	\
> +	 */								\
> +									\
> +	___m_lo = ___m;							\
> +	___m_hi = ___m >> 32;						\
> +	___n_lo = ___n;							\
> +	___n_hi = ___n >> 32;						\
> +									\
> +	if (!___c) {							\
> +		___res = ((uint64_t)___m_lo * ___n_lo) >> 32;		\
> +	} else if (!(___m & ((1ULL << 63) | (1ULL << 31)))) {		\
> +		___res = (___m + (uint64_t)___m_lo * ___n_lo) >> 32;	\
> +	} else {							\
> +		___res = ___m + (uint64_t)___m_lo * ___n_lo;		\
> +		___t = (___res < ___m) ? (1ULL << 32) : 0;		\
> +	       	___res = (___res >> 32) + ___t;				\
> +	}								\
> +									\
> +	if (!(___m & ((1ULL << 63) | (1ULL << 31)))) {			\
> +		___res += (uint64_t)___m_lo * ___n_hi;			\
> +		___res += (uint64_t)___m_hi * ___n_lo;			\
> +		___res >>= 32;						\
> +	} else {							\
> +		___t = ___res += (uint64_t)___m_lo * ___n_hi;		\
> +		___res += (uint64_t)___m_hi * ___n_lo;			\
> +		___t = (___res < ___t) ? (1ULL << 32) : 0;		\
> +		___res = (___res >> 32) + ___t;				\
> +	}								\
> +									\
> +	___res += (uint64_t)___m_hi * ___n_hi;				\
> +									\
> +	___res / ___p;							\
> +})
> +
>  extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);
>  
>  /* The unnecessary pointer compare is there
> @@ -41,7 +184,20 @@ extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);
>  	uint32_t __base = (base);			\
>  	uint32_t __rem;					\
>  	(void)(((typeof((n)) *)0) == ((uint64_t *)0));	\
> -	if (likely(((n) >> 32) == 0)) {			\
> +	if (__builtin_constant_p(__base) &&		\
> +	    (__base & (__base - 1)) == 0) {		\
> +		/* constant power of 2: gcc is fine */	\
> +		__rem = (n) & (__base - 1);		\
> +		(n) /= __base;				\
> +	} else if ((__GNUC__ >= 4) &&			\
> +	    __builtin_constant_p(__base) &&		\
> +	    __base != 0) {				\
> +		uint32_t __res_lo, __n_lo = (n);	\
> +		(n) = __div64_const32(n, __base);	\
> +		/* the remainder can be computed with 32-bit regs */ \
> +		__res_lo = (n);				\
> +		__rem = __n_lo - __res_lo * __base;	\
> +	} else if (likely(((n) >> 32) == 0)) {		\
>  		__rem = (uint32_t)(n) % __base;		\
>  		(n) = (uint32_t)(n) / __base;		\
>  	} else 						\
>

Claudiu, can some of this not be done in gcc itself !

-Vineet
--
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/

[toc] | [prev] | [next] | [standalone]

#1259471

Vineet Gupta <Vineet.Gupta1@synopsys.com> writes:

> Claudiu, can some of this not be done in gcc itself !

All of it could be done by gcc.  The trouble is that it isn't.

-- 
Måns Rullgård
mans@mansr.com
--
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/

[toc] | [prev] | [next] | [standalone]

#1259478

Nicolas Pitre <nicolas.pitre@linaro.org> writes:

> On Wed, 28 Oct 2015, Nicolas Pitre wrote:
>
>> On Thu, 29 Oct 2015, Alexey Brodkin wrote:
>> 
>> > Fortunately we already have much better __div64_32() for 32-bit ARM.
>> > There in case of division by constant preprocessor calculates so-called
>> > "magic number" which is later used in multiplications instead of divisions.
>> 
>> It's not magic, it is science.  :-)
>> 
>> > It's really nice and very optimal but obviously works only for ARM
>> > because ARM assembly is involved.
>> > 
>> > Now why don't we extend the same approach to all other 32-bit arches
>> > with multiplication part implemented in pure C. With good compiler
>> > resulting assembly will be quite close to manually written assembly.
>
> Well... not as close at least on ARM.  Maybe 2x to 3x more costly than 
> the one with assembly.  Still better than 100x or so without this 
> optimization.

That's more or less what I found on MIPS too.

>> > But there's at least 1 problem which I don't know how to solve.
>> > Preprocessor magic only happens if __div64_32() is inlined (that's
>> > obvious - preprocessor has to know if divider is constant or not).
>> > 
>> > But __div64_32() is already marked as weak function (which in its turn
>> > is required to allow some architectures to provide its own optimal
>> > implementations). I.e. addition of "inline" for __div64_32() is not an
>> > option.
>> 
>> You can't inline __div64_32().  It should remain as is and used only for 
>> the slow path.
>> 
>> For the constant based optimization to work, you need to modify do_div() 
>> in include/asm-generic/div64.h directly.
>
> OK... I was intrigued, so I adapted my ARM code to the generic case, 
> including the overflow avoidance optimizations.  Please have look and 
> tell me how this works for you.
>
> If this patch is accepted upstream, then it could be possible to 
> abstract only the actual multiplication part with some architecture 
> specific assembly.

Good idea.

-- 
Måns Rullgård
mans@mansr.com
--
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/

[toc] | [prev] | [next] | [standalone]

#1259571 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

[Multipart message — attachments visible in raw view] — view raw

On Fri, 30 Oct 2015, Måns Rullgård wrote:

> Nicolas Pitre <nicolas.pitre@linaro.org> writes:
> 
> > OK... I was intrigued, so I adapted my ARM code to the generic case, 
> > including the overflow avoidance optimizations.  Please have look and 
> > tell me how this works for you.
> >
> > If this patch is accepted upstream, then it could be possible to 
> > abstract only the actual multiplication part with some architecture 
> > specific assembly.
> 
> Good idea.

Could you please provide a reviewed-by or acked-by tag?


Nicolas

[toc] | [prev] | [next] | [standalone]

#1259598 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

SGkgTmljb2xhcywNCg0KT24gRnJpLCAyMDE1LTEwLTMwIGF0IDExOjE3IC0wNDAwLCBOaWNvbGFz
IFBpdHJlIHdyb3RlOg0KPiBPbiBGcmksIDMwIE9jdCAyMDE1LCBNw6VucyBSdWxsZ8OlcmQgd3Jv
dGU6DQo+IA0KPiA+IE5pY29sYXMgUGl0cmUgPG5pY29sYXMucGl0cmVAbGluYXJvLm9yZz4gd3Jp
dGVzOg0KPiA+IA0KPiA+ID4gT0suLi4gSSB3YXMgaW50cmlndWVkLCBzbyBJIGFkYXB0ZWQgbXkg
QVJNIGNvZGUgdG8gdGhlIGdlbmVyaWMgY2FzZSwgDQo+ID4gPiBpbmNsdWRpbmcgdGhlIG92ZXJm
bG93IGF2b2lkYW5jZSBvcHRpbWl6YXRpb25zLiAgUGxlYXNlIGhhdmUgbG9vayBhbmQgDQo+ID4g
PiB0ZWxsIG1lIGhvdyB0aGlzIHdvcmtzIGZvciB5b3UuDQo+ID4gPiANCj4gPiA+IElmIHRoaXMg
cGF0Y2ggaXMgYWNjZXB0ZWQgdXBzdHJlYW0sIHRoZW4gaXQgY291bGQgYmUgcG9zc2libGUgdG8g
DQo+ID4gPiBhYnN0cmFjdCBvbmx5IHRoZSBhY3R1YWwgbXVsdGlwbGljYXRpb24gcGFydCB3aXRo
IHNvbWUgYXJjaGl0ZWN0dXJlIA0KPiA+ID4gc3BlY2lmaWMgYXNzZW1ibHkuDQo+ID4gDQo+ID4g
R29vZCBpZGVhLg0KPiANCj4gQ291bGQgeW91IHBsZWFzZSBwcm92aWRlIGEgcmV2aWV3ZWQtYnkg
b3IgYWNrZWQtYnkgdGFnPw0KDQpTdXJlIQ0KDQpBY2tlZC1ieTogQWxleGV5IEJyb2RraW4gPGFi
cm9ka2luQHN5bm9wc3lzLmNvbT4NCg0KQlRXIEkgdGhvdWdodCBhYm91dCB0aGF0IG9wdGltaXph
dGlvbiBhIGJpdCBtb3JlIGFuZCBub3cgSSB0aGluaw0Kd2UgbWF5IGV2ZW4gc2tpcCBhZGRpdGlv
biBvZiBhcmNoLXNwZWNpZmljIGFzc2VtYmx5IGluc2VydGlvbnMuDQoNClRoYXQncyBiZWNhdXNl
IHRoYXQga2luZCBvZiBkaXZpc2lvbiBhcyBkaXNjdXNzZWQgbWFueSB0aW1lcw0Kc2hvdWxkIGJl
IHVzZWQgYXMgbGltaXRlZCBhcyBwb3NzaWJsZSwgaW4gb3RoZXIgd29yZHMgdGhlcmUgc2hvdWxk
IGJlDQpqdXN0IGEgdmVyeSBmZXcgdXNhZ2VzIG9mIGl0IGVzcGVjaWFsbHkgaW4gdmVyeSBmcmVx
dWVudGx5IHVzZWQgY29kZSBwYXRocy4NCkFuZCBpbiB0aGF0IGNhc2UgdGhlcmUgbWlnaHQgYmUg
bm90IG11Y2ggb2YgYmVuZWZpdCBoYXZpbmcgZG9fZGl2KCkNCmV2ZW4gZmFzdGVyIGFuZCBzbWFs
bGVyIHRoYW4gdGhlIG9uZSB3ZSdyZSBhYm91dCB0byBnZXQgd2l0aCB5b3VyIGNoYW5nZS4NCg0K
LUFsZXhleQ==
--
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/

[toc] | [prev] | [next] | [standalone]

#1259633 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

[Multipart message — attachments visible in raw view] — view raw

On Fri, 30 Oct 2015, Alexey Brodkin wrote:

> Hi Nicolas,
> 
> On Fri, 2015-10-30 at 11:17 -0400, Nicolas Pitre wrote:
> > On Fri, 30 Oct 2015, Måns Rullgård wrote:
> > 
> > > Nicolas Pitre <nicolas.pitre@linaro.org> writes:
> > > 
> > > > OK... I was intrigued, so I adapted my ARM code to the generic case, 
> > > > including the overflow avoidance optimizations.  Please have look and 
> > > > tell me how this works for you.
> > > > 
> > > > If this patch is accepted upstream, then it could be possible to 
> > > > abstract only the actual multiplication part with some architecture 
> > > > specific assembly.
> > > 
> > > Good idea.
> > 
> > Could you please provide a reviewed-by or acked-by tag?
> 
> Sure!
> 
> Acked-by: Alexey Brodkin <abrodkin@synopsys.com>
> 
> BTW I thought about that optimization a bit more and now I think
> we may even skip addition of arch-specific assembly insertions.

I'm going to do it anyway given that I already have it for ARM.  It'll 
be opt-in, so if your arch doesn't provide it then the current C 
implementation will be used by default.


Nicolas

[toc] | [prev] | [next] | [standalone]

#1259671

Nicolas Pitre <nicolas.pitre@linaro.org> writes:

> On Fri, 30 Oct 2015, Alexey Brodkin wrote:
>
>> Hi Nicolas,
>> 
>> On Fri, 2015-10-30 at 11:17 -0400, Nicolas Pitre wrote:
>> > On Fri, 30 Oct 2015, Måns Rullgård wrote:
>> > 
>> > > Nicolas Pitre <nicolas.pitre@linaro.org> writes:
>> > > 
>> > > > OK... I was intrigued, so I adapted my ARM code to the generic case, 
>> > > > including the overflow avoidance optimizations.  Please have look and 
>> > > > tell me how this works for you.
>> > > > 
>> > > > If this patch is accepted upstream, then it could be possible to 
>> > > > abstract only the actual multiplication part with some architecture 
>> > > > specific assembly.
>> > > 
>> > > Good idea.
>> > 
>> > Could you please provide a reviewed-by or acked-by tag?
>> 
>> Sure!
>> 
>> Acked-by: Alexey Brodkin <abrodkin@synopsys.com>
>> 
>> BTW I thought about that optimization a bit more and now I think
>> we may even skip addition of arch-specific assembly insertions.
>
> I'm going to do it anyway given that I already have it for ARM.  It'll 
> be opt-in, so if your arch doesn't provide it then the current C 
> implementation will be used by default.

Great.  I'll try it out on MIPS once you've posted the patch.

-- 
Måns Rullgård
mans@mansr.com
--
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/

[toc] | [prev] | [next] | [standalone]

#1259543 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

SGkgTmljb2xhcywNCg0KT24gVGh1LCAyMDE1LTEwLTI5IGF0IDIxOjI2IC0wNDAwLCBOaWNvbGFz
IFBpdHJlIHdyb3RlOg0KPiBPbiBXZWQsIDI4IE9jdCAyMDE1LCBOaWNvbGFzIFBpdHJlIHdyb3Rl
Og0KPiANCj4gPiBPbiBUaHUsIDI5IE9jdCAyMDE1LCBBbGV4ZXkgQnJvZGtpbiB3cm90ZToNCj4g
PiANCj4gPiA+IEZvcnR1bmF0ZWx5IHdlIGFscmVhZHkgaGF2ZSBtdWNoIGJldHRlciBfX2RpdjY0
XzMyKCkgZm9yIDMyLWJpdCBBUk0uDQo+ID4gPiBUaGVyZSBpbiBjYXNlIG9mIGRpdmlzaW9uIGJ5
IGNvbnN0YW50IHByZXByb2Nlc3NvciBjYWxjdWxhdGVzIHNvLWNhbGxlZA0KPiA+ID4gIm1hZ2lj
IG51bWJlciIgd2hpY2ggaXMgbGF0ZXIgdXNlZCBpbiBtdWx0aXBsaWNhdGlvbnMgaW5zdGVhZCBv
ZiBkaXZpc2lvbnMuDQo+ID4gDQo+ID4gSXQncyBub3QgbWFnaWMsIGl0IGlzIHNjaWVuY2UuICA6
LSkNCj4gPiANCj4gPiA+IEl0J3MgcmVhbGx5IG5pY2UgYW5kIHZlcnkgb3B0aW1hbCBidXQgb2J2
aW91c2x5IHdvcmtzIG9ubHkgZm9yIEFSTQ0KPiA+ID4gYmVjYXVzZSBBUk0gYXNzZW1ibHkgaXMg
aW52b2x2ZWQuDQo+ID4gPiANCj4gPiA+IE5vdyB3aHkgZG9uJ3Qgd2UgZXh0ZW5kIHRoZSBzYW1l
IGFwcHJvYWNoIHRvIGFsbCBvdGhlciAzMi1iaXQgYXJjaGVzDQo+ID4gPiB3aXRoIG11bHRpcGxp
Y2F0aW9uIHBhcnQgaW1wbGVtZW50ZWQgaW4gcHVyZSBDLiBXaXRoIGdvb2QgY29tcGlsZXINCj4g
PiA+IHJlc3VsdGluZyBhc3NlbWJseSB3aWxsIGJlIHF1aXRlIGNsb3NlIHRvIG1hbnVhbGx5IHdy
aXR0ZW4gYXNzZW1ibHkuDQo+IA0KPiBXZWxsLi4uIG5vdCBhcyBjbG9zZSBhdCBsZWFzdCBvbiBB
Uk0uICBNYXliZSAyeCB0byAzeCBtb3JlIGNvc3RseSB0aGFuIA0KPiB0aGUgb25lIHdpdGggYXNz
ZW1ibHkuICBTdGlsbCBiZXR0ZXIgdGhhbiAxMDB4IG9yIHNvIHdpdGhvdXQgdGhpcyANCj4gb3B0
aW1pemF0aW9uLg0KDQpJbmRlZWQgZXZlbiBoYXZpbmcgdGhhdCBmdW5jdGlvbiAyNSB0aW1lcyBm
YXN0ZXIgaW5zdGVhZCBvZiAxMDAgdGltZXMgaXMNCmFscmVhZHkgcXVpdGUgYW4gYWNoaWV2ZW1l
bnQuIEZvciBleGFtcGxlIHRoYXQgd2lsbCBhbHJlYWR5IGN1cmUgbXkgaXBlcmYNCnBlcmZvcm1h
bmNlIGRlZ3JhZGF0aW9uOiBJJ2xsIHNlZSBkb19kaXYoKSB0YWtpbmcgPCAxJSBpbnN0ZWFkIG9m
ID4gMTAlIG5vdy4NCg0KTXkgdGVzdCBzb3VyY2Ugd2FzOg0KLS0tLS0tLS0tLS0tLS0tLS0tLS0t
PjgtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0NCmludCBteWZ1bmModTY0IGRhdGEpDQp7DQoJcmV0
dXJuIGRvX2RpdihkYXRhLCAxMDAwKTsNCn0NCi0tLS0tLS0tLS0tLS0tLS0tLS0tLT44LS0tLS0t
LS0tLS0tLS0tLS0tLS0tLS0tDQoNCk5vdyB0YWtlIGEgbG9vayBhdCBkaXNhc3NlbWJseSB0aGF0
IEknbSBnZXR0aW5nOg0KLS0tLS0tLS0tLS0tLS0tLS0tLS0tPjgtLS0tLS0tLS0tLS0tLS0tLS0t
LS0tLS0NCjAwMDAwNjJjIDxteWZ1bmM+Og0KIDYyYzoJMTkgMjggODYgMGYgNGYgOGQgM2IgZGYg
CW1weWR1ICAgICAgcjYscjAsMHg4ZDRmZGYzYg0KIDYzNDoJMDAgMjYgODYgOGYgNGYgOGQgM2Ig
ZGYgCWFkZC5mICAgICAgcjYscjYsMHg4ZDRmZGYzYg0KIDYzYzoJMDIgMjcgODcgMGYgZWQgN2Mg
NjkgOTEgCXN1YiAgICAgICAgcjcscjcsMHg3Y2VkOTE2OQ0KIDY0NDoJYzAgMjcgNjUgMDAgICAg
ICAgICAgICAgCWFkZC5jICAgICAgcjcscjcsMQ0KIDY0ODoJODUgMGUgYzQgNzEgMTIgODMgOTcg
NmUgCWJybG8gICAgICAgMHg4MzEyNmU5NyxyNyw2Y2MgPG15ZnVuYysweGEwPg0KDQogNjUwOgk3
NSAwZiA4MCAwZiAxMiA4MyA5NyA2ZSAJYnJlcSAgICAgICByNywweDgzMTI2ZTk3LDZjNCA8bXlm
dW5jKzB4OTg+DQoNCiA2NTg6CTBkIDcwICAgICAgICAgICAgICAgICAgIAltb3ZfcyAgICAgIHI4
LDANCiA2NWE6CTJkIDcxICAgICAgICAgICAgICAgICAgIAltb3ZfcyAgICAgIHI5LDENCiA2NWM6
CTE5IDI5IDhhIDBmIDRmIDhkIDNiIGRmIAltcHlkdSAgICAgIHIxMCxyMSwweDhkNGZkZjNiDQog
NjY0OgkwMCAyNyA4NCA4MiAgICAgICAgICAgICAJYWRkLmYgICAgICByNCxyNyxyMTANCiA2Njg6
CWFjIDcwICAgICAgICAgICAgICAgICAgIAltb3ZfcyAgICAgIHI1LDANCiA2NmE6CTE5IDI4IDg2
IDBmIDEyIDgzIDk3IDZlIAltcHlkdSAgICAgIHI2LHIwLDB4ODMxMjZlOTcNCiA2NzI6CTAxIDI1
IGM1IDAyICAgICAgICAgICAgIAlhZGMgICAgICAgIHI1LHI1LHIxMQ0KIDY3NjoJMDAgMjQgMDQg
ODIgICAgICAgICAgICAgCWFkZC5mICAgICAgcjQscjQscjgNCiA2N2E6CTAwIDI1IDQ1IDAyICAg
ICAgICAgICAgIAlhZGQgICAgICAgIHI1LHI1LHI5DQogNjdlOgljMCAyNSA2NSAwMCAgICAgICAg
ICAgICAJYWRkLmMgICAgICByNSxyNSwxDQogNjgyOgkwMCAyNiAwNiA4MSAgICAgICAgICAgICAJ
YWRkLmYgICAgICByNixyNixyNA0KIDY4NjoJMDEgMjcgNDcgMDEgICAgICAgICAgICAgCWFkYyAg
ICAgICAgcjcscjcscjUNCiA2OGE6CTUxIDBmIDQ0IDAxICAgICAgICAgICAgIAlicmxvICAgICAg
IHI3LHI1LDZkOCA8bXlmdW5jKzB4YWM+DQoNCiA2OGU6CTQ5IDBkIGMwIDAxICAgICAgICAgICAg
IAlicmVxICAgICAgIHI1LHI3LDZkNCA8bXlmdW5jKzB4YTg+DQoNCiA2OTI6CThjIDcwICAgICAg
ICAgICAgICAgICAgIAltb3ZfcyAgICAgIHI0LDANCiA2OTQ6CWFjIDcwICAgICAgICAgICAgICAg
ICAgIAltb3ZfcyAgICAgIHI1LDANCiA2OTY6CWUwIDQyICAgICAgICAgICAgICAgICAgIAltb3Zf
cyAgICAgIHIyLHI3DQogNjk4OgkxOSAyOSA4NiAwZiAxMiA4MyA5NyA2ZSAJbXB5ZHUgICAgICBy
NixyMSwweDgzMTI2ZTk3DQogNmEwOgkwMCAyMiA4MiA4MSAgICAgICAgICAgICAJYWRkLmYgICAg
ICByMixyMixyNg0KIDZhNDoJNmMgNzAgICAgICAgICAgICAgICAgICAgCW1vdl9zICAgICAgcjMs
MA0KIDZhNjoJMDEgMjMgYzMgMDEgICAgICAgICAgICAgCWFkYyAgICAgICAgcjMscjMscjcNCiA2
YWE6CTAwIDIyIDAyIDgxICAgICAgICAgICAgIAlhZGQuZiAgICAgIHIyLHIyLHI0DQogNmFlOglh
MCA3MyAgICAgICAgICAgICAgICAgICAJYWRkX3MgICAgICByMyxyMyxyNQ0KIDZiMDoJYzAgMjMg
NjUgMDAgICAgICAgICAgICAgCWFkZC5jICAgICAgcjMscjMsMQ0KIDZiNDoJMjkgYmEgICAgICAg
ICAgICAgICAgICAgCWxzcl9zICAgICAgcjIscjIsOQ0KIDZiNjoJMTcgYmIgICAgICAgICAgICAg
ICAgICAgCWFzbF9zICAgICAgcjMscjMsMjMNCiA2Yjg6CTY1IDdhICAgICAgICAgICAgICAgICAg
IAlvcl9zICAgICAgIHIyLHIyLHIzDQogNmJhOgk5YSAyMiAwZiAwYSAgICAgICAgICAgICAJbXB5
ICAgICAgICByMixyMiwweDNlOA0KIDZiZToJZTAgN2YgICAgICAgICAgICAgICAgICAgCWpfcy5k
ICAgICAgW2JsaW5rXQ0KIDZjMDoJNDIgNzggICAgICAgICAgICAgICAgICAgCXN1Yl9zICAgICAg
cjAscjAscjINCiA2YzI6CWUwIDc4ICAgICAgICAgICAgICAgICAgIAlub3BfcyAgICAgIA0KIDZj
NDoJOTUgMGUgODUgZjEgNGYgOGQgM2EgZGYgCWJyaHMubnQgICAgMHg4ZDRmZGYzYSxyNiw2NTgg
PG15ZnVuYysweDJjPg0KDQogNmNjOgkwZCA3MCAgICAgICAgICAgICAgICAgICAJbW92X3MgICAg
ICByOCwwDQogNmNlOgk5MSAwNyBlZiBmZiAgICAgICAgICAgICAJYi5kICAgICAgICA2NWMgPG15
ZnVuYysweDMwPg0KDQogNmQyOgkyZCA3MCAgICAgICAgICAgICAgICAgICAJbW92X3MgICAgICBy
OSwwDQogNmQ0OgliZiAwZSAwNSA4MSAgICAgICAgICAgICAJYnJocy5udCAgICByNixyNCw2OTIg
PG15ZnVuYysweDY2Pg0KDQogNmQ4Ogk4YyA3MCAgICAgICAgICAgICAgICAgICAJbW92X3MgICAg
ICByNCwwDQogNmRhOgliZiAwNyBlZiBmZiAgICAgICAgICAgICAJYi5kICAgICAgICA2OTYgPG15
ZnVuYysweDZhPg0KDQogNmRlOglhYyA3MSAgICAgICAgICAgICAgICAgICAJbW92X3MgICAgICBy
NSwxDQotLS0tLS0tLS0tLS0tLS0tLS0tLS0+OC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQ0KDQpX
aGF0IHlvdSBzZWUgaGVyZSBpcyBwcmV0dHkgc3RyYWlnaHQtZm9yd2FyZCBjb252ZXJzaW9uIHRv
IGFzc2VtYmx5IG9mICJydW4tdGltZSBjYWxjdWxhdGlvbnMiLg0KVGhpbmdzIHRvIG5vdGU6DQog
WzFdIE9ubHkgNSBtdWx0aXBsaWNhdGlvbnMgYXJlIHVzZWQuIFRoYXQncyBiZWNhdXNlIHdlIGhh
dmUgMzJ4MzIgbXVsdGlwbGljYXRpb24gdW5pdA0KICAgICB0aGF0IHJldHVybnMgNjQtYml0IHJl
c3VsdCBpbiByZWdpc3RlciBwYWlyLg0KDQogWzJdIEluZGVlZCBsb3RzIG9mIG1vdmVzIGFuZCBh
ZGRpdGlvbnMgaGFwcGVuIGhlcmUuDQoNClNvIG15IGNvbmNsdXNpb24gd291bGQgYmU6DQogWzFd
IFByb3Bvc2VkIGltcGxlbWVudGF0aW9uIG1ha2VzIHBlcmZlY3Qgc2Vuc2UgYmVjYXVzZSBhbHJl
YWR5IHNwZWVkcy11cCBkb19kaXYoKQ0KICAgICBzaWduaWZpY2FudGx5Lg0KDQogWzJdIEFiaWxp
dHkgdG8gc3Vic3RpdHV0ZSAicnVuLXRpbWUgY2FsY3VsYXRpb25zIiBvbiBwZXItYXJjaCBiYXNp
cyB3b3VsZCBiZSBhd3NvbWUNCiAgICAgYmVjYXVzZSB3aXRoIGZldyBsaW5lcyBvZiBhc3NlbWJs
eSBhbm90aGVyIDItNCB0aW1lcyBvZiBpbXByb3ZlbWVudCBjb3VsZCBiZQ0KICAgICBhY2hpZXZl
ZC4NCg0KLUFsZXhleQ==
--
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/

[toc] | [prev] | [next] | [standalone]

#1258503 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

[Multipart message — attachments visible in raw view] — view raw

Hi Alexey,

[auto build test ERROR on v4.3-rc7 -- if it's inappropriate base, please suggest rules for selecting the more suitable base]

url:    https://github.com/0day-ci/linux/commits/Alexey-Brodkin/__div64_32-implement-division-by-multiplication-for-32-bit-arches/20151029-065010
config: arm-mini2440_defconfig (attached as .config)
reproduce:
        wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=arm 

All error/warnings (new ones prefixed by >>):

   In file included from include/linux/kernel.h:136:0,
                    from lib/div64.c:20:
>> arch/arm/include/asm/div64.h:215:2: error: expected identifier or '(' before '{' token
    ({         \
     ^
>> lib/div64.c:27:12: note: in expansion of macro '__div64_fls'
    inline int __div64_fls(int bits)
               ^

vim +/__div64_fls +27 lib/div64.c

    14	 * Code generated for this function might be very inefficient
    15	 * for some CPUs. __div64_32() can be overridden by linking arch-specific
    16	 * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S.
    17	 */
    18	
    19	#include <linux/export.h>
  > 20	#include <linux/kernel.h>
    21	#include <linux/math64.h>
    22	
    23	/* Not needed on 64bit architectures */
    24	#if BITS_PER_LONG == 32
    25	
    26	/* our own fls implementation to make sure constant propagation is fine */
  > 27	inline int __div64_fls(int bits)
    28	{
    29		unsigned int __left = bits, __nr = 0;
    30	

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[toc] | [prev] | [next] | [standalone]

#1258770

Alexey Brodkin <Alexey.Brodkin@synopsys.com> writes:

> Existing default implementation of __div64_32() for 32-bit arches unfolds
> into huge routine with tons of arithmetics like +, -, * and all of them
> in loops. That leads to obvious performance degradation if do_div() is
> frequently used.
>
> Good example is extensive TCP/IP traffic.
> That's what I'm getting with perf out of iperf3:
>  -------------->8--------------
>     30.05%  iperf3   [kernel.kallsyms]        [k] copy_from_iter
>     11.77%  iperf3   [kernel.kallsyms]        [k] __div64_32
>      5.44%  iperf3   [kernel.kallsyms]        [k] memset
>      5.32%  iperf3   [kernel.kallsyms]        [k] stmmac_xmit
>      2.70%  iperf3   [kernel.kallsyms]        [k] skb_segment
>      2.56%  iperf3   [kernel.kallsyms]        [k] tcp_ack
>  -------------->8--------------
>
> do_div() here is mostly used in skb_mstamp_get() to convert nanoseconds
> received from local_clock() to microseconds used in timestamp.
> BTW conversion itself is as simple as "/=1000".
>
> Fortunately we already have much better __div64_32() for 32-bit ARM.
> There in case of division by constant preprocessor calculates so-called
> "magic number" which is later used in multiplications instead of divisions.
> It's really nice and very optimal but obviously works only for ARM
> because ARM assembly is involved.
>
> Now why don't we extend the same approach to all other 32-bit arches
> with multiplication part implemented in pure C. With good compiler
> resulting assembly will be quite close to manually written assembly.
>
> And that change implements that.
>
> But there's at least 1 problem which I don't know how to solve.
> Preprocessor magic only happens if __div64_32() is inlined (that's
> obvious - preprocessor has to know if divider is constant or not).
>
> But __div64_32() is already marked as weak function (which in its turn
> is required to allow some architectures to provide its own optimal
> implementations). I.e. addition of "inline" for __div64_32() is not an
> option.
>
> So I do want to hear opinions on how to proceed with that patch.
> Indeed there's the simplest solution - use this implementation only in
> my architecture of preference (read ARC) but IMHO this change may
> benefit other architectures as well.

I tried something similar for MIPS a while ago after noticing a similar
perf report.  Adapting Nico's ARM code gave some nice speedups, but only
when I used MIPS assembly for the long multiplies.  Apparently gcc is
still too stupid to do the sane thing.

-- 
Måns Rullgård
mans@mansr.com
--
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/

[toc] | [prev] | [next] | [standalone]

#1258775 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

SGkgbWFucywNCg0KT24gVGh1LCAyMDE1LTEwLTI5IGF0IDEyOjUyICswMDAwLCBNw6VucyBSdWxs
Z8OlcmQgd3JvdGU6DQo+IEFsZXhleSBCcm9ka2luIDxBbGV4ZXkuQnJvZGtpbkBzeW5vcHN5cy5j
b20+IHdyaXRlczoNCj4gDQo+ID4gRXhpc3RpbmcgZGVmYXVsdCBpbXBsZW1lbnRhdGlvbiBvZiBf
X2RpdjY0XzMyKCkgZm9yIDMyLWJpdCBhcmNoZXMgdW5mb2xkcw0KPiA+IGludG8gaHVnZSByb3V0
aW5lIHdpdGggdG9ucyBvZiBhcml0aG1ldGljcyBsaWtlICssIC0sICogYW5kIGFsbCBvZiB0aGVt
DQo+ID4gaW4gbG9vcHMuIFRoYXQgbGVhZHMgdG8gb2J2aW91cyBwZXJmb3JtYW5jZSBkZWdyYWRh
dGlvbiBpZiBkb19kaXYoKSBpcw0KPiA+IGZyZXF1ZW50bHkgdXNlZC4NCj4gPiANCj4gPiBHb29k
IGV4YW1wbGUgaXMgZXh0ZW5zaXZlIFRDUC9JUCB0cmFmZmljLg0KPiA+IFRoYXQncyB3aGF0IEkn
bSBnZXR0aW5nIHdpdGggcGVyZiBvdXQgb2YgaXBlcmYzOg0KPiA+ICAtLS0tLS0tLS0tLS0tLT44
LS0tLS0tLS0tLS0tLS0NCj4gPiAgICAgMzAuMDUlICBpcGVyZjMgICBba2VybmVsLmthbGxzeW1z
XSAgICAgICAgW2tdIGNvcHlfZnJvbV9pdGVyDQo+ID4gICAgIDExLjc3JSAgaXBlcmYzICAgW2tl
cm5lbC5rYWxsc3ltc10gICAgICAgIFtrXSBfX2RpdjY0XzMyDQo+ID4gICAgICA1LjQ0JSAgaXBl
cmYzICAgW2tlcm5lbC5rYWxsc3ltc10gICAgICAgIFtrXSBtZW1zZXQNCj4gPiAgICAgIDUuMzIl
ICBpcGVyZjMgICBba2VybmVsLmthbGxzeW1zXSAgICAgICAgW2tdIHN0bW1hY194bWl0DQo+ID4g
ICAgICAyLjcwJSAgaXBlcmYzICAgW2tlcm5lbC5rYWxsc3ltc10gICAgICAgIFtrXSBza2Jfc2Vn
bWVudA0KPiA+ICAgICAgMi41NiUgIGlwZXJmMyAgIFtrZXJuZWwua2FsbHN5bXNdICAgICAgICBb
a10gdGNwX2Fjaw0KPiA+ICAtLS0tLS0tLS0tLS0tLT44LS0tLS0tLS0tLS0tLS0NCj4gPiANCj4g
PiBkb19kaXYoKSBoZXJlIGlzIG1vc3RseSB1c2VkIGluIHNrYl9tc3RhbXBfZ2V0KCkgdG8gY29u
dmVydCBuYW5vc2Vjb25kcw0KPiA+IHJlY2VpdmVkIGZyb20gbG9jYWxfY2xvY2soKSB0byBtaWNy
b3NlY29uZHMgdXNlZCBpbiB0aW1lc3RhbXAuDQo+ID4gQlRXIGNvbnZlcnNpb24gaXRzZWxmIGlz
IGFzIHNpbXBsZSBhcyAiLz0xMDAwIi4NCj4gPiANCj4gPiBGb3J0dW5hdGVseSB3ZSBhbHJlYWR5
IGhhdmUgbXVjaCBiZXR0ZXIgX19kaXY2NF8zMigpIGZvciAzMi1iaXQgQVJNLg0KPiA+IFRoZXJl
IGluIGNhc2Ugb2YgZGl2aXNpb24gYnkgY29uc3RhbnQgcHJlcHJvY2Vzc29yIGNhbGN1bGF0ZXMg
c28tY2FsbGVkDQo+ID4gIm1hZ2ljIG51bWJlciIgd2hpY2ggaXMgbGF0ZXIgdXNlZCBpbiBtdWx0
aXBsaWNhdGlvbnMgaW5zdGVhZCBvZiBkaXZpc2lvbnMuDQo+ID4gSXQncyByZWFsbHkgbmljZSBh
bmQgdmVyeSBvcHRpbWFsIGJ1dCBvYnZpb3VzbHkgd29ya3Mgb25seSBmb3IgQVJNDQo+ID4gYmVj
YXVzZSBBUk0gYXNzZW1ibHkgaXMgaW52b2x2ZWQuDQo+ID4gDQo+ID4gTm93IHdoeSBkb24ndCB3
ZSBleHRlbmQgdGhlIHNhbWUgYXBwcm9hY2ggdG8gYWxsIG90aGVyIDMyLWJpdCBhcmNoZXMNCj4g
PiB3aXRoIG11bHRpcGxpY2F0aW9uIHBhcnQgaW1wbGVtZW50ZWQgaW4gcHVyZSBDLiBXaXRoIGdv
b2QgY29tcGlsZXINCj4gPiByZXN1bHRpbmcgYXNzZW1ibHkgd2lsbCBiZSBxdWl0ZSBjbG9zZSB0
byBtYW51YWxseSB3cml0dGVuIGFzc2VtYmx5Lg0KPiA+IA0KPiA+IEFuZCB0aGF0IGNoYW5nZSBp
bXBsZW1lbnRzIHRoYXQuDQo+ID4gDQo+ID4gQnV0IHRoZXJlJ3MgYXQgbGVhc3QgMSBwcm9ibGVt
IHdoaWNoIEkgZG9uJ3Qga25vdyBob3cgdG8gc29sdmUuDQo+ID4gUHJlcHJvY2Vzc29yIG1hZ2lj
IG9ubHkgaGFwcGVucyBpZiBfX2RpdjY0XzMyKCkgaXMgaW5saW5lZCAodGhhdCdzDQo+ID4gb2J2
aW91cyAtIHByZXByb2Nlc3NvciBoYXMgdG8ga25vdyBpZiBkaXZpZGVyIGlzIGNvbnN0YW50IG9y
IG5vdCkuDQo+ID4gDQo+ID4gQnV0IF9fZGl2NjRfMzIoKSBpcyBhbHJlYWR5IG1hcmtlZCBhcyB3
ZWFrIGZ1bmN0aW9uICh3aGljaCBpbiBpdHMgdHVybg0KPiA+IGlzIHJlcXVpcmVkIHRvIGFsbG93
IHNvbWUgYXJjaGl0ZWN0dXJlcyB0byBwcm92aWRlIGl0cyBvd24gb3B0aW1hbA0KPiA+IGltcGxl
bWVudGF0aW9ucykuIEkuZS4gYWRkaXRpb24gb2YgImlubGluZSIgZm9yIF9fZGl2NjRfMzIoKSBp
cyBub3QgYW4NCj4gPiBvcHRpb24uDQo+ID4gDQo+ID4gU28gSSBkbyB3YW50IHRvIGhlYXIgb3Bp
bmlvbnMgb24gaG93IHRvIHByb2NlZWQgd2l0aCB0aGF0IHBhdGNoLg0KPiA+IEluZGVlZCB0aGVy
ZSdzIHRoZSBzaW1wbGVzdCBzb2x1dGlvbiAtIHVzZSB0aGlzIGltcGxlbWVudGF0aW9uIG9ubHkg
aW4NCj4gPiBteSBhcmNoaXRlY3R1cmUgb2YgcHJlZmVyZW5jZSAocmVhZCBBUkMpIGJ1dCBJTUhP
IHRoaXMgY2hhbmdlIG1heQ0KPiA+IGJlbmVmaXQgb3RoZXIgYXJjaGl0ZWN0dXJlcyBhcyB3ZWxs
Lg0KPiANCj4gSSB0cmllZCBzb21ldGhpbmcgc2ltaWxhciBmb3IgTUlQUyBhIHdoaWxlIGFnbyBh
ZnRlciBub3RpY2luZyBhIHNpbWlsYXINCj4gcGVyZiByZXBvcnQuICBBZGFwdGluZyBOaWNvJ3Mg
QVJNIGNvZGUgZ2F2ZSBzb21lIG5pY2Ugc3BlZWR1cHMsIGJ1dCBvbmx5DQo+IHdoZW4gSSB1c2Vk
IE1JUFMgYXNzZW1ibHkgZm9yIHRoZSBsb25nIG11bHRpcGxpZXMuICBBcHBhcmVudGx5IGdjYyBp
cw0KPiBzdGlsbCB0b28gc3R1cGlkIHRvIGRvIHRoZSBzYW5lIHRoaW5nLg0KDQpDb3VsZCB5b3Ug
cGxlYXNlIGVsYWJvcmF0ZSBhIGxpdHRsZSBiaXQgb24gd2hhdCB3YXMgYSBwcm9ibGVtIHdpdGgg
Z2NjDQpjb21wYXJlZCB0byBoYW5kLXdyaXR0ZW4gYXNtPw0KDQpUaGUgcG9pbnQgaXMgaWYgcHJl
cHJvY2Vzc29yIGRvZXMgcHJvcGVyIGNvbnN0YW50IHByb3BhZ2F0aW9uIHRoZW4gY29tcGlsZXIN
CndpbGwgbmVlZCB0byBpbXBsZW1lbnQgb25seSBjYWxjdWxhdGlvbnMgbWFya2VkICJydW4tdGlt
ZSBjYWxjdWxhdGlvbnMiLg0KQW5kIGluIGl0cyB0dXJuIHRob3NlIGFyZSBwcmV0dHkgc3RyYWln
aHQtZm9yd2FyZCAzMi1iaXQgKyBhbmQgKi4NCg0KQW5kIGF0IGxlYXN0IG9uIEFSQyBJIHNhdyB3
aXRoIHRoYXQgY2hhbmdlIHBlcmYgbm8gbG9uZ2VyIGNhcHR1cmVzDQpfX2RpdjY0XzMyKCkgZHVy
aW5nIGlwZXJmIGFuZCBpcGVyZiByZXN1bHRzIGl0c2VsZiBpbXByb3ZlZCBmb3IgYWJvdXQgMTAl
Lg0KU28gSSdkIHNheSBhZHZhbnRhZ2UgaXMgcXVpdGUgbm90aWNlYWJsZS4NCg0KLUFsZXhleQ0K
--
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/

[toc] | [prev] | [next] | [standalone]

#1258793

Alexey Brodkin <Alexey.Brodkin@synopsys.com> writes:

> Hi mans,
>
> On Thu, 2015-10-29 at 12:52 +0000, Måns Rullgård wrote:
>> Alexey Brodkin <Alexey.Brodkin@synopsys.com> writes:
>> 
>> > Existing default implementation of __div64_32() for 32-bit arches unfolds
>> > into huge routine with tons of arithmetics like +, -, * and all of them
>> > in loops. That leads to obvious performance degradation if do_div() is
>> > frequently used.
>> > 
>> > Good example is extensive TCP/IP traffic.
>> > That's what I'm getting with perf out of iperf3:
>> >  -------------->8--------------
>> >     30.05%  iperf3   [kernel.kallsyms]        [k] copy_from_iter
>> >     11.77%  iperf3   [kernel.kallsyms]        [k] __div64_32
>> >      5.44%  iperf3   [kernel.kallsyms]        [k] memset
>> >      5.32%  iperf3   [kernel.kallsyms]        [k] stmmac_xmit
>> >      2.70%  iperf3   [kernel.kallsyms]        [k] skb_segment
>> >      2.56%  iperf3   [kernel.kallsyms]        [k] tcp_ack
>> >  -------------->8--------------
>> > 
>> > do_div() here is mostly used in skb_mstamp_get() to convert nanoseconds
>> > received from local_clock() to microseconds used in timestamp.
>> > BTW conversion itself is as simple as "/=1000".
>> > 
>> > Fortunately we already have much better __div64_32() for 32-bit ARM.
>> > There in case of division by constant preprocessor calculates so-called
>> > "magic number" which is later used in multiplications instead of divisions.
>> > It's really nice and very optimal but obviously works only for ARM
>> > because ARM assembly is involved.
>> > 
>> > Now why don't we extend the same approach to all other 32-bit arches
>> > with multiplication part implemented in pure C. With good compiler
>> > resulting assembly will be quite close to manually written assembly.
>> > 
>> > And that change implements that.
>> > 
>> > But there's at least 1 problem which I don't know how to solve.
>> > Preprocessor magic only happens if __div64_32() is inlined (that's
>> > obvious - preprocessor has to know if divider is constant or not).
>> > 
>> > But __div64_32() is already marked as weak function (which in its turn
>> > is required to allow some architectures to provide its own optimal
>> > implementations). I.e. addition of "inline" for __div64_32() is not an
>> > option.
>> > 
>> > So I do want to hear opinions on how to proceed with that patch.
>> > Indeed there's the simplest solution - use this implementation only in
>> > my architecture of preference (read ARC) but IMHO this change may
>> > benefit other architectures as well.
>> 
>> I tried something similar for MIPS a while ago after noticing a similar
>> perf report.  Adapting Nico's ARM code gave some nice speedups, but only
>> when I used MIPS assembly for the long multiplies.  Apparently gcc is
>> still too stupid to do the sane thing.
>
> Could you please elaborate a little bit on what was a problem with gcc
> compared to hand-written asm?

In the final multiplications (the ones using ARM assembly), gcc has a
tendency to multiply things by zero and add the (zero) result to
something.  This generally happens when multiplying a 64-bit value by a
32-bit one.  The 32-bit value is simply converted to 64-bit by the usual
promotion rules, and gcc forgets that the upper half is know to be zero.

> The point is if preprocessor does proper constant propagation then compiler
> will need to implement only calculations marked "run-time calculations".
> And in its turn those are pretty straight-forward 32-bit + and *.

The constant calculation is fine.  It's the final multiplication that's
the problem.

> And at least on ARC I saw with that change perf no longer captures
> __div64_32() during iperf and iperf results itself improved for about 10%.
> So I'd say advantage is quite noticeable.

There was an improvement without assembly as well, but with the MIPS
equivalent of the ARM assembly, it got much better.

-- 
Måns Rullgård
mans@mansr.com
--
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/

[toc] | [prev] | [next] | [standalone]

#1258790 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

On Thu, Oct 29, 2015 at 01:47:35AM +0300, Alexey Brodkin wrote:
> diff --git a/lib/div64.c b/lib/div64.c
> index 62a698a..3055328 100644
> --- a/lib/div64.c
> +++ b/lib/div64.c
> +/*
> + * If the divisor happens to be constant, we determine the appropriate
> + * inverse at compile time to turn the division into a few inline
> + * multiplications instead which is much faster.
> + */
>  uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)
>  {
> -	uint64_t rem = *n;
> -	uint64_t b = base;
> -	uint64_t res, d = 1;
> -	uint32_t high = rem >> 32;
> -
> -	/* Reduce the thing a bit first */
> -	res = 0;
> -	if (high >= base) {
> -		high /= base;
> -		res = (uint64_t) high << 32;
> -		rem -= (uint64_t) (high*base) << 32;
> -	}
> +	unsigned int __r, __b = base;
>  
> -	while ((int64_t)b > 0 && b < rem) {
> -		b = b+b;
> -		d = d+d;
> -	}
> +	if (!__builtin_constant_p(__b) || __b == 0) {

Can you explain who __builtin_constant_p(__b) can be anything but false
here?  I can't see that this will ever be true.

This is a function in its own .c file - the compiler will have no
knowledge about the callers of this function scattered throughout the
kernel, and it has to assume that the 'base' argument to this function
is variable.  So, __builtin_constant_p(__b) will always be false, which
means this if () statement will always be true and the else clause will
never be used.

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.
--
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/

[toc] | [prev] | [next] | [standalone]

#1258831 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

SGkgUnVzc2VsLA0KDQpPbiBUaHUsIDIwMTUtMTAtMjkgYXQgMTM6MzEgKzAwMDAsIFJ1c3NlbGwg
S2luZyAtIEFSTSBMaW51eCB3cm90ZToNCj4gT24gVGh1LCBPY3QgMjksIDIwMTUgYXQgMDE6NDc6
MzVBTSArMDMwMCwgQWxleGV5IEJyb2RraW4gd3JvdGU6DQo+ID4gZGlmZiAtLWdpdCBhL2xpYi9k
aXY2NC5jIGIvbGliL2RpdjY0LmMNCj4gPiBpbmRleCA2MmE2OThhLi4zMDU1MzI4IDEwMDY0NA0K
PiA+IC0tLSBhL2xpYi9kaXY2NC5jDQo+ID4gKysrIGIvbGliL2RpdjY0LmMNCj4gPiArLyoNCj4g
PiArICogSWYgdGhlIGRpdmlzb3IgaGFwcGVucyB0byBiZSBjb25zdGFudCwgd2UgZGV0ZXJtaW5l
IHRoZSBhcHByb3ByaWF0ZQ0KPiA+ICsgKiBpbnZlcnNlIGF0IGNvbXBpbGUgdGltZSB0byB0dXJu
IHRoZSBkaXZpc2lvbiBpbnRvIGEgZmV3IGlubGluZQ0KPiA+ICsgKiBtdWx0aXBsaWNhdGlvbnMg
aW5zdGVhZCB3aGljaCBpcyBtdWNoIGZhc3Rlci4NCj4gPiArICovDQo+ID4gIHVpbnQzMl90IF9f
YXR0cmlidXRlX18oKHdlYWspKSBfX2RpdjY0XzMyKHVpbnQ2NF90ICpuLCB1aW50MzJfdCBiYXNl
KQ0KPiA+ICB7DQo+ID4gLQl1aW50NjRfdCByZW0gPSAqbjsNCj4gPiAtCXVpbnQ2NF90IGIgPSBi
YXNlOw0KPiA+IC0JdWludDY0X3QgcmVzLCBkID0gMTsNCj4gPiAtCXVpbnQzMl90IGhpZ2ggPSBy
ZW0gPj4gMzI7DQo+ID4gLQ0KPiA+IC0JLyogUmVkdWNlIHRoZSB0aGluZyBhIGJpdCBmaXJzdCAq
Lw0KPiA+IC0JcmVzID0gMDsNCj4gPiAtCWlmIChoaWdoID49IGJhc2UpIHsNCj4gPiAtCQloaWdo
IC89IGJhc2U7DQo+ID4gLQkJcmVzID0gKHVpbnQ2NF90KSBoaWdoIDw8IDMyOw0KPiA+IC0JCXJl
bSAtPSAodWludDY0X3QpIChoaWdoKmJhc2UpIDw8IDMyOw0KPiA+IC0JfQ0KPiA+ICsJdW5zaWdu
ZWQgaW50IF9fciwgX19iID0gYmFzZTsNCj4gPiAgDQo+ID4gLQl3aGlsZSAoKGludDY0X3QpYiA+
IDAgJiYgYiA8IHJlbSkgew0KPiA+IC0JCWIgPSBiK2I7DQo+ID4gLQkJZCA9IGQrZDsNCj4gPiAt
CX0NCj4gPiArCWlmICghX19idWlsdGluX2NvbnN0YW50X3AoX19iKSB8fCBfX2IgPT0gMCkgew0K
PiANCj4gQ2FuIHlvdSBleHBsYWluIHdobyBfX2J1aWx0aW5fY29uc3RhbnRfcChfX2IpIGNhbiBi
ZSBhbnl0aGluZyBidXQgZmFsc2UNCj4gaGVyZT8gIEkgY2FuJ3Qgc2VlIHRoYXQgdGhpcyB3aWxs
IGV2ZXIgYmUgdHJ1ZS4NCj4gDQo+IFRoaXMgaXMgYSBmdW5jdGlvbiBpbiBpdHMgb3duIC5jIGZp
bGUgLSB0aGUgY29tcGlsZXIgd2lsbCBoYXZlIG5vDQo+IGtub3dsZWRnZSBhYm91dCB0aGUgY2Fs
bGVycyBvZiB0aGlzIGZ1bmN0aW9uIHNjYXR0ZXJlZCB0aHJvdWdob3V0IHRoZQ0KPiBrZXJuZWws
IGFuZCBpdCBoYXMgdG8gYXNzdW1lIHRoYXQgdGhlICdiYXNlJyBhcmd1bWVudCB0byB0aGlzIGZ1
bmN0aW9uDQo+IGlzIHZhcmlhYmxlLiAgU28sIF9fYnVpbHRpbl9jb25zdGFudF9wKF9fYikgd2ls
bCBhbHdheXMgYmUgZmFsc2UsIHdoaWNoDQo+IG1lYW5zIHRoaXMgaWYgKCkgc3RhdGVtZW50IHdp
bGwgYWx3YXlzIGJlIHRydWUgYW5kIHRoZSBlbHNlIGNsYXVzZSB3aWxsDQo+IG5ldmVyIGJlIHVz
ZWQuDQoNCkVzc2VudGlhbGx5IGNvbnN0YW50IHByb3BhZ2F0aW9uIHdpbGwgb25seSBoYXBwZW4g
aWYgX19kaXY2NF8zMigpIGlzIGlubGluZWQuDQpGb3IgdGhhdCB3ZSBuZWVkIHRvIGFkZCAiaW5s
aW5lIiBzcGVjaWZpZXIgdG8gX19kaXY2NF8zMigpLCBidXQgdGhhdCBpbiBpdHMNCnR1cm4gd2ls
bCBwcmV2ZW50IHVzZSBvZiBhcmNoLXNwZWNpZmljIG1vcmUgb3B0aW1hbCBfX2RpdjY0XzMyKCkg
aW1wbGVtZW50YXRpb24uDQoNCkFuZCB0aGF0IHdhcyBteSBtYWluIHF1ZXN0aW9uIGhvdyB0byBp
bXBsZW1lbnQgdGhpcyBwcm9wZXJseTogaGF2ZSBiZXR0ZXIgZ2VuZXJpYw0KZG9fZGl2KCkgb3Ig
X19kaXY2NF8zMigpIGFzIGl0cyBoZWF2eSBsaWZ0aW5nIHBhcnQgYW5kIHN0aWxsIGtlZXAgYW4g
YWJpbGl0eSBmb3INCnNvbWUgYXJjaGl0ZWN0dXJlcyB0byB1c2UgdGhlaXIgb3duIGltcGxlbWVu
dGF0aW9ucy4NCg0KLUFsZXhleQ0K
--
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/

[toc] | [prev] | [next] | [standalone]

#1258925 — Re: [PATCH] __div64_32: implement division by multiplication for 32-bit arches

typos (spellos):

On 10/28/15 15:47, Alexey Brodkin wrote:
> ---
>  lib/div64.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++----------
>  1 file changed, 128 insertions(+), 25 deletions(-)
> 
> diff --git a/lib/div64.c b/lib/div64.c
> index 62a698a..3055328 100644
> --- a/lib/div64.c
> +++ b/lib/div64.c
> @@ -23,37 +23,140 @@
>  /* Not needed on 64bit architectures */
>  #if BITS_PER_LONG == 32
>  
> +
> +/*
> + * If the divisor happens to be constant, we determine the appropriate
> + * inverse at compile time to turn the division into a few inline
> + * multiplications instead which is much faster.
> + */
>  uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)
>  {
> -	uint64_t rem = *n;
> -	uint64_t b = base;
> -	uint64_t res, d = 1;
> -	uint32_t high = rem >> 32;
> -
> -	/* Reduce the thing a bit first */
> -	res = 0;
> -	if (high >= base) {
> -		high /= base;
> -		res = (uint64_t) high << 32;
> -		rem -= (uint64_t) (high*base) << 32;
> -	}
> +	unsigned int __r, __b = base;
>  
> -	while ((int64_t)b > 0 && b < rem) {
> -		b = b+b;
> -		d = d+d;
> -	}
> +	if (!__builtin_constant_p(__b) || __b == 0) {
> +		/* non-constant divisor (or zero): slow path */
> +		uint64_t rem = *n;
> +		uint64_t b = base;
> +		uint64_t res, d = 1;
> +		uint32_t high = rem >> 32;
> +
> +		/* Reduce the thing a bit first */
> +		res = 0;
> +		if (high >= base) {
> +			high /= base;
> +			res = (uint64_t) high << 32;
> +			rem -= (uint64_t) (high*base) << 32;
> +		}
> +
> +		while ((int64_t)b > 0 && b < rem) {
> +			b = b+b;
> +			d = d+d;
> +		}
> +
> +		do {
> +			if (rem >= b) {
> +				rem -= b;
> +				res += d;
> +			}
> +			b >>= 1;
> +			d >>= 1;
> +		} while (d);
>  
> -	do {
> -		if (rem >= b) {
> -			rem -= b;
> -			res += d;
> +		*n = res;
> +		__r = rem;
> +	} else if ((__b & (__b - 1)) == 0) {
> +		/*
> +		 * Trivial: __b is constant and a power of 2
> +		 * gcc does the right thing with this code.
> +		 * Even though code is the same as above but
> +		 * we make it visually as a separate path.
> +		 * Still only one of these branches will survive
> +		 * pre-processor stage, so let's leave it here.
> +		 */
> +		__r = *n;
> +		__r &= (__b - 1);
> +		*n /= __b;
> +	} else {
> +		/* Start of preprocessor calculations */
> +
> +		/*
> +		 * Multiply by inverse of __b: *n/b = *n*(p/b)/p
> +		 * We rely on the fact that most of this code gets
> +		 * optimized away at compile time due to constant
> +		 * propagation and only a couple inline assembly
> +		 * instructions should remain. Better avoid any
> +		 * code construct that might prevent that.
> +		 */
> +		unsigned long long __res, __x, __t, __m, __n = *n;
> +		unsigned int __p;
> +		/* preserve low part of *n for reminder computation */

		                               remainder

> +		__r = __n;
> +		/* determine number of bits to represent __b */
> +		__p = 1 << __div64_fls(__b);
> +		/* compute __m = ((__p << 64) + __b - 1) / __b */
> +		__m = (~0ULL / __b) * __p;
> +		__m += (((~0ULL % __b + 1) * __p) + __b - 1) / __b;
> +		/* compute __res = __m*(~0ULL/__b*__b-1)/(__p << 64) */
> +		__x = ~0ULL / __b * __b - 1;
> +		__res = (__m & 0xffffffff) * (__x & 0xffffffff);
> +		__res >>= 32;
> +		__res += (__m & 0xffffffff) * (__x >> 32);
> +		__t = __res;
> +		__res += (__x & 0xffffffff) * (__m >> 32);
> +		__t = (__res < __t) ? (1ULL << 32) : 0;
> +		__res = (__res >> 32) + __t;
> +		__res += (__m >> 32) * (__x >> 32);
> +		__res /= __p;
> +		/* End of preprocessor calculations */
> +
> +		/* Start of run-time calculations */
> +		__res = (unsigned int)__m * (unsigned int)__n;
> +		__res >>= 32;
> +		__res += (unsigned int)__m * (__n >> 32);
> +		__t = __res;
> +		__res += (unsigned int)__n * (__m >> 32);
> +		__t = (__res < __t) ? (1ULL << 32) : 0;
> +		__res = (__res >> 32) + __t;
> +		__res += (__m >> 32) * (__n >> 32);
> +		__res /= __p;
> +
> +		/*
> +		 * The reminder can be computed with 32-bit regs

		       remainder

> +		 * only, and gcc is good at that.
> +		 */
> +		{
> +			unsigned int __res0 = __res;
> +			unsigned int __b0 = __b;
> +
> +			__r -= __res0 * __b0;
>  		}
> -		b >>= 1;
> -		d >>= 1;
> -	} while (d);
> +		/* End of run-time calculations */
>  
> -	*n = res;
> -	return rem;
> +		*n = __res;
> +	}
> +	return __r;
>  }
>  
>  EXPORT_SYMBOL(__div64_32);



-- 
~Randy
--
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/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web