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

Groups > comp.lang.forth > #46552

Re: division performance (was: The problem with implementation defined ...)

From anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups comp.lang.forth
Subject Re: division performance (was: The problem with implementation defined ...)
Date 2016-04-06 10:03 +0000
Organization Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID <2016Apr6.120304@mips.complang.tuwien.ac.at> (permalink)
References (6 earlier) <ndhob4$eer$3@dont-email.me> <2016Apr1.102503@mips.complang.tuwien.ac.at> <ndmpdi$ek8$1@dont-email.me> <2016Apr5.131223@mips.complang.tuwien.ac.at> <ne1864$c9u$1@dont-email.me>

Show all headers | View raw

Bernd Paysan <bernd.paysan@gmx.de> writes:
>Am Tue, 05 Apr 2016 11:12:23 +0000 schrieb Anton Ertl:
>
>> Alternatively, we could also use something "mid"-like for positive
>> dividends, and something "old"-like for negative dividends, but the code
>> would grow, and it introduces a branch that might cause a misprediction.
>
>The old code had a branch in it, the new code based on symmetric division 
>is branch-free.  That's additional cost for the default case (all 
>operands are positive).

I thought about that, too.  The branchless code always increases the
latency.  The old (branchy) code may have a branch misprediction, but
that misprediction is in parallel with the division; the division
takes 20-26 cycles, which is about the cost of the branch
misprediction, so even if we have a branch misprediction, it will not
incur additional cost.  So I think the old, branchy code is preferable
here.

Concerning the idea of using the mid code for the +/any case (or just
unsigned division for the +/+) case: There the branch is before the
division, so unfortunately a branch misprediction would be in addition
to the division latency.  So if we expect mispredictions to occur more
frequently than in exceptional cases, we should not go there.

>My current conclusion is that we are programming in Forth, and if all 
>operands are positive is the default case, we should give the users a 
>source code optimization, which is unsigned division, i.e. u/, umod and u/
>mod for the fast path.

Yes.  (I assume you mean u/mod).

>Since Intel's 128/64 bit division is ridiculously slow, there is the 
>option to implement the table+Goldschmidt division algorithm, it should 
>be much faster, especially for M*/, where the division by the same 
>quotient needs to be done twice.

Maybe.  See also recent discussions in comp.arch where Mitch Alsup
mentioned using Goldschmidt for the first iterations, and
Newton-Raphson for the final iteration, because of Goldschmidts better
latency, and Newton-Raphson's correction of errors.

One other thing I have thought about is to provide support for
division by constants, and divisions of many dividends by the same
divisor, both implemented through reciprocal multiplication.  E.g.,
division by constants could have a syntax like

[ n ]/
[ n ]mod
[ n ]/mod
[ u ]u/
[ u ]umod
[ u ]u/mod

(do we need all of those?)

Computing the muliplicative inverse and using it could be along these
lines:

( n ) prepare/ ( something ) \ or uprepare/
( n something ) p/ \ or pmod or p/mod; up/ upmod up/mod

"something" needs 1 cell + 1 bit if I understood a paper on that
topic correctly. 

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-29 14:39 +0000
  Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-29 16:20 +0000
    Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-29 09:16 -1000
      Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 00:06 +0000
        Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-29 22:09 -0700
          Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-29 21:37 -1000
          Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-30 00:48 -0700
            Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-30 00:48 -0700
          Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 07:59 +0000
            Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-30 10:16 -0700
              Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 23:43 +0000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-31 06:01 -0700
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:36 +0000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-01 14:57 -0700
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:59 +0000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-02 00:51 -0700
                Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-01 08:25 +0000
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:32 +0000
                division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-05 11:12 +0000
                Re: division performance (was: The problem with implementation defined ...) Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-05 20:45 +0000
                Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-06 10:03 +0000
                Re: division performance (was: The problem with implementation defined ...) Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-08 22:53 +0000
                Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-09 10:14 +0000
                Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-09 13:43 +0000
              Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-31 10:55 +0000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-31 06:38 -0700
                Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-31 16:21 +0000
                Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-31 11:49 -0700
                Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-31 10:11 -1000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-01 03:53 -0700
                Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-01 11:44 +0000
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:53 +0000
                Re: The problem with implementation defined behaviour. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-02 11:46 -0500
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-02 21:43 +0000
                Re: The problem with implementation defined behaviour. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-03 03:17 -0500
                Re: The problem with implementation defined behaviour. hughaguilar96@gmail.com - 2016-04-01 23:54 -0700
          Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:58 +0000
          Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 22:22 +0000
        Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:55 +0000
      Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 07:44 +0000
        Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 13:08 +0000
          Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 13:43 +0000
        Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 22:06 +0000
      Re: The problem with implementation defined behaviour. trevor <tgritchie@blueyonder.co.uk> - 2016-03-30 13:13 +0100
        Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 13:56 +0000
      Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:49 +0000

csiph-web