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

Groups > linux.kernel > #1259478

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

Show all headers | View raw

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/

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[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

csiph-web