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

Groups > comp.lang.forth > #46294 > unrolled thread

The problem with implementation defined behaviour.

Back to article view | Back to comp.lang.forth

Contents

  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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

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

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/

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

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

Am Wed, 06 Apr 2016 10:03:04 +0000 schrieb Anton Ertl:
> 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.

The branch checks the remainder for 0, so it can't fully decide before 
the division is done - it can check for the sign before, but that alone 
is equal to the "branch not taken, anyways" case.  Try dividing with a 
pseudo-random pattern of +-2 (with both even and odd dividends), and look 
at the results; that's the worst case for branch prediction.

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

The wrapping algorithm decided that u/mod can be put into two lines ;-)

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

Yes, that's possible fine-tuning.  If you want to compute the modulus, 
too, it's not necessary.  The possible off-by-one error in Goldschmidt 
can be corrected quickly, by looking at the sign of the modulus.

> 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

If we pack that up, yes.

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

Yes, the main problem is the division by 1 and -1.  If you exclude that, 
it's just one cell, e.g. try this:

: prepare/ ( n1 -- n2 )  0 1 rot fm/mod nip ;
: uprepare ( u1 -- u2 )  0 1 rot um/mod nip ;
: p/ ( n1 something -- n2 )  m* nip ;
: up/ ( u1 something -- u2 ) um* nip ;

IIRC, you can solve the +-1 case by decrementing the something by 1, so 
that it fits in one cell, that makes p/ and up/ a bit more complicated, 
though (need to add the input with m+).

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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

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

Bernd Paysan <bernd.paysan@gmx.de> writes:
>Am Wed, 06 Apr 2016 10:03:04 +0000 schrieb Anton Ertl:
>> 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.
>
>The branch checks the remainder for 0, so it can't fully decide before 
>the division is done

Good point.  Ok, so we have to consider how often the branch os
mispredicted.  Given that there were no complaints about switching
from symmetric to floored, it seems that the correction is never used,
so the branch is very predictable.  The reason for this predictability
may be that only +/+-divisions occur, or that -/+-divisions, when they
occur, give remainder 0; or maybe that people don't care about the
exact result in these cases:-).

> - it can check for the sign before, but that alone 
>is equal to the "branch not taken, anyways" case.

Not sure what you mean here.

>> 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.
>
>Yes, the main problem is the division by 1 and -1.  If you exclude that, 
>it's just one cell, e.g. try this:
>
>: prepare/ ( n1 -- n2 )  0 1 rot fm/mod nip ;
>: uprepare ( u1 -- u2 )  0 1 rot um/mod nip ;
>: p/ ( n1 something -- n2 )  m* nip ;
>: up/ ( u1 something -- u2 ) um* nip ;

6 3 prepare/ p/ . \ outputs 1

It's not that simple:-).

I need to study the paper again:

Robert Alverson: Integer Division using Reciprocals.

Or maybe there is a more appropriate one.

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

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

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

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>Yes, the main problem is the division by 1 and -1.  If you exclude that, 
>>it's just one cell, e.g. try this:
>>
>>: prepare/ ( n1 -- n2 )  0 1 rot fm/mod nip ;
>>: uprepare ( u1 -- u2 )  0 1 rot um/mod nip ;
>>: p/ ( n1 something -- n2 )  m* nip ;
>>: up/ ( u1 something -- u2 ) um* nip ;
>
>6 3 prepare/ p/ . \ outputs 1
>
>It's not that simple:-).

Unfortunately, it's quite a bit more complicated, as discussed by
several sources.

Let's consider the unsigned case and only divisor 3.  Your PREPARE/
gives $5555555555555555 as reciprocal.  As we can see, this is too
small, so let's try $5555555555555556 instead:

6 $5555555555555556 up/ . \ outputs 2

So that's ok in this case.  Let's see if it's always right.  The error
will be largest with the largest dividend that gives a rest of 2 (or
generally, divisor-1).  For the divisor 3 and 64 bits, that number
happens to be $fffffffffffffffe.

$fffffffffffffffe $5555555555555556 up/ hex. \ gives $5555555555555555
\ let's check the result:
$5555555555555555 3 * hex. \ gives $FFFFFFFFFFFFFFFF

So this simple UP/ is not good enough in general.  The two approaches
for fixing it are to use extra precision (a longer reciprocal, and
more right-shifting), or computing the remainder of the approximate
quotient, and correcting the error based on that.

Alverson's extra-precision way is to have a w+1-bit (w is the cell
width) reciprocal (representable in w bits, because the first bit is
always 1), with the shift being w+(number of bits in the divisor).
Instead, we could also use a 2w-bit reciprocal and a w*2w->3w
multiplication (of which we use the top word).  The latter seems
simpler to implement in software (and not slower on a machine with a
pipelined w*w->2w multiplier).

Terje Mathisen devised an algorithm (presented by Agner Fog), that
works with just a w-bit reciprocal, but requires different UP/ actions
for different divisors.  We could represent "something" as cell-wide
reciprocal, plus shift amount, plus the xt of the required action, and
UP/ would then just be EXECUTE.  This can also be made to work with
divisor 1.

I have also seen a reference to Hacker's Delight, and an addendum
<http://www.hackersdelight.org/divcMore.pdf> covers the case when the
high word of multiplication is not available, but the original part
apparently is only in the book, so I'll look at it on Monday, if I
remember to do so.

Sources: 

<http://homepage.cs.uiowa.edu/~jones/bcd/divide.html>
Fog: <http://www.agner.org/optimize/optimizing_assembly.pdf> (page 143 ff.)
Alverson: <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1710>

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

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

#46358

mhx@iae.nl writes:
>In answer of which I posted, at that time,
>
>FORTH> DIVTEST
>CELL-BITS = 64
>Divisions tested 10,000,000 times (#times).
>     /    : 0.033 seconds elapsed.
>[s]  /    : 0.110 seconds elapsed.
>[f]  /    : 0.155 seconds elapsed.
>      mod : 0.020 seconds elapsed.
>[s]   mod : 0.112 seconds elapsed.
>[f]   mod : 0.152 seconds elapsed.
>     /mod : 0.021 seconds elapsed.
>[s]  /mod : 0.110 seconds elapsed.
>[f]  /mod : 0.150 seconds elapsed.
>    */mod : 0.115 seconds elapsed.
>[s] */mod : 0.111 seconds elapsed.
>[f] */mod : 0.171 seconds elapsed.
>    */    : 0.113 seconds elapsed.
>[s] */    : 0.113 seconds elapsed.
>[f] */    : 0.182 seconds elapsed.
>   um/mod : 0.099 seconds elapsed.
>   fm/mod : 0.133 seconds elapsed.
>   sm/rem : 0.110 seconds elapsed.
>   m*/    : 0.236 seconds elapsed. ok
>
>( nothing == default in iForth, [s] symmetrical, [f] == floored )

The difference between SM/REM and FM/MOD is not that big (actually
smaller than in the Gforth/Pentium 4 numbers I posted).  But these
data leave some questions open:

Why are the default / MOD and /MOD so much faster than the [S]
variants?  Did some optimization kick in that did not work for the [S]
variants?

Why is the [F] variant of / MOD /MOD */MOD and */ slower than FM/MOD,
while the [S] variants have the same speed as SM/REM?  Did you perform
some inlining or other optimization for the [S] variants that you did
not do for the [F] variants?

The M*/ speed is great.  You obviously found a much better
implementation than we did.

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

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

#46361

On Thursday, March 31, 2016 at 1:24:24 PM UTC+2, Anton Ertl wrote:
> mhx@iae.nl writes:
> >In answer of which I posted, at that time,
> >
> >FORTH> DIVTEST
> >CELL-BITS = 64
> >Divisions tested 10,000,000 times (#times).
> >     /    : 0.033 seconds elapsed.
> >[s]  /    : 0.110 seconds elapsed.
> >[f]  /    : 0.155 seconds elapsed.
> >      mod : 0.020 seconds elapsed.
> >[s]   mod : 0.112 seconds elapsed.
> >[f]   mod : 0.152 seconds elapsed.
> >     /mod : 0.021 seconds elapsed.
> >[s]  /mod : 0.110 seconds elapsed.
> >[f]  /mod : 0.150 seconds elapsed.
> >    */mod : 0.115 seconds elapsed.
> >[s] */mod : 0.111 seconds elapsed.
> >[f] */mod : 0.171 seconds elapsed.
> >    */    : 0.113 seconds elapsed.
> >[s] */    : 0.113 seconds elapsed.
> >[f] */    : 0.182 seconds elapsed.
> >   um/mod : 0.099 seconds elapsed.
> >   fm/mod : 0.133 seconds elapsed.
> >   sm/rem : 0.110 seconds elapsed.
> >   m*/    : 0.236 seconds elapsed. ok
> >
> >( nothing == default in iForth, [s] symmetrical, [f] == floored )
> 
> The difference between SM/REM and FM/MOD is not that big (actually
> smaller than in the Gforth/Pentium 4 numbers I posted).  But these
> data leave some questions open:
> 
> Why are the default / MOD and /MOD so much faster than the [S]
> variants?  Did some optimization kick in that did not work for the [S]
> variants?

That is indeed because "/" is optimized in the metacompiler (by me),
while iForth "itself" works on SM/REM and must break it down first.
I didn't put much effort in optimizing SM/REM and FM/MOD.

 
> Why is the [F] variant of / MOD /MOD */MOD and */ slower than FM/MOD,
> while the [S] variants have the same speed as SM/REM?  Did you perform
> some inlining or other optimization for the [S] variants that you did
> not do for the [F] variants?

The answer is more or less the same as for the first question.
It would cost me years to really optimize every case in iForth 
(at least, in the way it is done now).
 
> The M*/ speed is great.  You obviously found a much better
> implementation than we did.

There is some triple-length stuff inside which is apparently 
quite efficient / easy for the CPU.

-marcel

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

#46362

mhx@iae.nl writes:
>On Thursday, March 31, 2016 at 1:24:24 PM UTC+2, Anton Ertl wrote:
>> mhx@iae.nl writes:
>> >In answer of which I posted, at that time,
>> >
>> >FORTH> DIVTEST
>> >CELL-BITS = 64
>> >Divisions tested 10,000,000 times (#times).
>> >     /    : 0.033 seconds elapsed.
>> >[s]  /    : 0.110 seconds elapsed.
>> >[f]  /    : 0.155 seconds elapsed.
>> >      mod : 0.020 seconds elapsed.
>> >[s]   mod : 0.112 seconds elapsed.
>> >[f]   mod : 0.152 seconds elapsed.
>> >     /mod : 0.021 seconds elapsed.
>> >[s]  /mod : 0.110 seconds elapsed.
>> >[f]  /mod : 0.150 seconds elapsed.
>> >    */mod : 0.115 seconds elapsed.
>> >[s] */mod : 0.111 seconds elapsed.
>> >[f] */mod : 0.171 seconds elapsed.
>> >    */    : 0.113 seconds elapsed.
>> >[s] */    : 0.113 seconds elapsed.
>> >[f] */    : 0.182 seconds elapsed.
>> >   um/mod : 0.099 seconds elapsed.
>> >   fm/mod : 0.133 seconds elapsed.
>> >   sm/rem : 0.110 seconds elapsed.
>> >   m*/    : 0.236 seconds elapsed. ok
>> >
>> >( nothing == default in iForth, [s] symmetrical, [f] == floored )
>> 
>> The difference between SM/REM and FM/MOD is not that big (actually
>> smaller than in the Gforth/Pentium 4 numbers I posted).  But these
>> data leave some questions open:
>> 
>> Why are the default / MOD and /MOD so much faster than the [S]
>> variants?  Did some optimization kick in that did not work for the [S]
>> variants?
>
>That is indeed because "/" is optimized in the metacompiler (by me),
>while iForth "itself" works on SM/REM and must break it down first.
>I didn't put much effort in optimizing SM/REM and FM/MOD.
>
> 
>> Why is the [F] variant of / MOD /MOD */MOD and */ slower than FM/MOD,
>> while the [S] variants have the same speed as SM/REM?  Did you perform
>> some inlining or other optimization for the [S] variants that you did
>> not do for the [F] variants?
>
>The answer is more or less the same as for the first question.
>It would cost me years to really optimize every case in iForth 
>(at least, in the way it is done now).

That's not necessary, but it means that the results of these
microbenchmarks may say more about your optimizations than about
floored vs. symmetric division on your hardware.

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

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

#46364

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> That's not necessary, but it means that the results of these
> microbenchmarks may say more about your optimizations than about
> floored vs. symmetric division on your hardware.

I know div, mod, and divMod in Haskell (like /, mod, and /mod in Forth)
give floored division, and if your program uses them a lot and doesn't
actually need floored division, you can often get a worthwhile speedup
by using quot, rem, and quotRem (symmetric division) instead.

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

#46366

On 3/31/16 3:38 AM, mhx@iae.nl wrote:
>> The M*/ speed is great.  You obviously found a much better
>> >implementation than we did.
> There is some triple-length stuff inside which is apparently
> quite efficient / easy for the CPU.

The native multiply on virtually all CPUs leaves a double product in 
registers. Likewise, virtually all native divisions divides a single 
into a double in those registers. Therefore, it's a piece of cake in 
assembler. This is actually why M*/ exists: Chuck discovered that long, 
long ago and took advantage of it.

Similarly, virtually all native divisions leave both a quotient and a 
remainder, which is why Chuck introduced the /MOD operator.

Each of those primitives is only a very few instructions on any processor.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

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

#46387

On Thursday, March 31, 2016 at 10:12:03 PM UTC+2, Elizabeth D. Rather wrote:
> On 3/31/16 3:38 AM, mhx@iae.nl wrote:
> >> The M*/ speed is great.  You obviously found a much better
> >> >implementation than we did.
> > There is some triple-length stuff inside which is apparently
> > quite efficient / easy for the CPU.
> 
> The native multiply on virtually all CPUs leaves a double product in 
> registers. Likewise, virtually all native divisions divides a single 
> into a double in those registers. Therefore, it's a piece of cake in 
> assembler. 

I assumed that m*/ has the stack picture ( d1 n1 n2 -- d1*n1/n2 ).
Therefore, d1*n1 might overflow into a triple length number
(unsupported by the CPU), and d1/n2 could result in a severe
decrease of precision (say d1 = 1., n1 = 200 and n2 = 100).

-marcel

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

#46389

mhx@iae.nl writes:
>On Thursday, March 31, 2016 at 10:12:03 PM UTC+2, Elizabeth D. Rather wrote:
>> On 3/31/16 3:38 AM, mhx@iae.nl wrote:
>> >> The M*/ speed is great.  You obviously found a much better
>> >> >implementation than we did.
>> > There is some triple-length stuff inside which is apparently
>> > quite efficient / easy for the CPU.
>> 
>> The native multiply on virtually all CPUs leaves a double product in 
>> registers. Likewise, virtually all native divisions divides a single 
>> into a double in those registers. Therefore, it's a piece of cake in 
>> assembler. 
>
>I assumed that m*/ has the stack picture ( d1 n1 n2 -- d1*n1/n2 ).
>Therefore, d1*n1 might overflow into a triple length number
>(unsupported by the CPU),

Correct.  The specification of M*/ starts with 

|Multiply d1 by n1 producing the triple-cell intermediate result t.
|Divide t by +n2 giving the double-cell quotient d2.

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

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

#46399

Am Fri, 01 Apr 2016 11:44:04 +0000 schrieb Anton Ertl:
> Correct.  The specification of M*/ starts with
> 
> |Multiply d1 by n1 producing the triple-cell intermediate result t.
> |Divide t by +n2 giving the double-cell quotient d2.

For benchmarking, and for code that expects to run on a 32 bit system, 
but actually runs on a 64 bit system, it's wise to tune M*/ by checking 
first if the double number actually needs the precision, and if not, 
using the ordinary */ code instead.  That's for sure much faster.

Given the timing results of div on Core i7, that approach is even done by 
Intel: use a fast path for divisions where the top half of the number is 
just sign extended.

On the 4stack processor, I decided against implementing a divider unit, 
and for Goldschmidt division: first find-first-one in the divider, then 
shift it so that it is between 0.5 and 0.9999 (decimal point left of the 
actual number), compute the inverse (which is now between 1 and 1.9999, 
top bit actually not represented), multiply, and then shift right.  For 
32 bits, that's 3 multiplications, for 64 bits would be 4 multiplications 
(just one more); supposed there's an 8 bit index table for the starting 
value.  Computing the remainder requires another multiplication.  
Multiplications are way faster than division, so that's going to pay off, 
especially in the 64 bit case, and even more with the M*/ case... because 
here, the inverse computed once is good enough for both divisions.

If you don't have find-first-one as instruction, forget it, but ff1 is 
far easier to implement than SRT division.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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

#46418

Bernd Paysan <bernd.paysan@gmx.de> wrote:
> On the 4stack processor, I decided against implementing a divider unit, 
> and for Goldschmidt division: first find-first-one in the divider, then 
> shift it so that it is between 0.5 and 0.9999 (decimal point left of the 
> actual number), compute the inverse (which is now between 1 and 1.9999, 
> top bit actually not represented), multiply, and then shift right.

Interesting.  How do you compute the inverse?  A lookup table, perhaps?

Andrew.

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

#46422

Am Sat, 02 Apr 2016 11:46:09 -0500 schrieb Andrew Haley:

> Bernd Paysan <bernd.paysan@gmx.de> wrote:
>> On the 4stack processor, I decided against implementing a divider unit,
>> and for Goldschmidt division: first find-first-one in the divider, then
>> shift it so that it is between 0.5 and 0.9999 (decimal point left of
>> the actual number), compute the inverse (which is now between 1 and
>> 1.9999, top bit actually not represented), multiply, and then shift
>> right.
> 
> Interesting.  How do you compute the inverse?  A lookup table, perhaps?

After normalizing the number and excluding division by zero, you use the 
top n bits (e.g. top 8 bits) to get an approximate inverse.  And then you 
continue either with Goldschmidt or Newton-Raphson (both are quite 
similar algorithms) to double the precision of that approximation per 
round.  Both use the same number of multiplications (two per iteration), 
but Goldschmidt can use the multiplications in parallel, which means the 
cost is much closer to one multiplication on pipelined architectures; so 
the latency is one multiplication per iteration.

Rounding can be tricky to get exactly what you want, so I compute the 
remainder, too, and adjust off-by-one results if necessary.  If you are 
careful with your initial approximation table, most results are rounded 
good enough.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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

#46436

Bernd Paysan <bernd.paysan@gmx.de> wrote:
> Am Sat, 02 Apr 2016 11:46:09 -0500 schrieb Andrew Haley:
> 
>> Bernd Paysan <bernd.paysan@gmx.de> wrote:
>>> On the 4stack processor, I decided against implementing a divider unit,
>>> and for Goldschmidt division: first find-first-one in the divider, then
>>> shift it so that it is between 0.5 and 0.9999 (decimal point left of
>>> the actual number), compute the inverse (which is now between 1 and
>>> 1.9999, top bit actually not represented), multiply, and then shift
>>> right.
>> 
>> Interesting.  How do you compute the inverse?  A lookup table,
>> perhaps?
> 
> After normalizing the number and excluding division by zero, you use the 
> top n bits (e.g. top 8 bits) to get an approximate inverse.

So I'm guessing that answer was "yes".  :-)

> And then you continue either with Goldschmidt or Newton-Raphson
> (both are quite similar algorithms) to double the precision of that
> approximation per round.  Both use the same number of
> multiplications (two per iteration), but Goldschmidt can use the
> multiplications in parallel, which means the cost is much closer to
> one multiplication on pipelined architectures; so the latency is one
> multiplication per iteration.

OK, I get that now.

> Rounding can be tricky to get exactly what you want, so I compute
> the remainder, too, and adjust off-by-one results if necessary.  If
> you are careful with your initial approximation table, most results
> are rounded good enough.

Thanks,

Andrew.

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

#46407

On Thursday, March 31, 2016 at 1:12:03 PM UTC-7, Elizabeth D. Rather wrote:
> On 3/31/16 3:38 AM, mhx@iae.nl wrote:
> >> The M*/ speed is great.  You obviously found a much better
> >> >implementation than we did.
> > There is some triple-length stuff inside which is apparently
> > quite efficient / easy for the CPU.
> 
> The native multiply on virtually all CPUs leaves a double product in 
> registers. Likewise, virtually all native divisions divides a single 
> into a double in those registers. Therefore, it's a piece of cake in 
> assembler. This is actually why M*/ exists: Chuck discovered that long, 
> long ago and took advantage of it.

This isn't the first time that Elizabeth Rather has praised M*/ --- when I needed a D/ for my continued-fraction program she said this:

On Nov 20, 12:07 am, Elizabeth D Rather <erat...@forth.com> wrote:
> There are D+, D-, M*, M/, and M*/ (and the unsigned operators).  These
> were adequate in a very wide variety of projects over a 30 year period,
> many of which were extremely computation-intensive and running on slow
> 16-bit processors.
>
> Forth's design is pragmatic: it has functions that have been needed and
> that have proven their usefulness *in Forth*, not necessarily those that
> have been required in other languages.  Generally speaking, Forth has
> the most flexible set of *integer* arithmetic operators of any language.
>   In particular, M*/ was one of Chuck's most brilliant innovations.  I'm
> sure if Chuck were trying to do your continued fractions that is what he
> would rely on.  Yes, that sometimes requires thinking differently, like
> many other things in Forth.

*/ and M*/ are only useful when you have rational approximations to irrational numbers. The book "Starting Forth" provided a few rational approximations, such as the well-known 355/113 for pi. To obtain better-precision rational approximations and/or to obtain rational approximations of numbers other than pi, you need to have a continued-fraction program (and it needs to have D/ available). I have CF.4TH in the novice-package that was written by Nathaniel Grossman (Sept/Oct 1984 "Forth Dimensions") and he provides a D/ written in high-level Forth.

Most likely, Charles Moore knew how to write a continued-fraction program. He wouldn't have provided Forth with */ and M*/ if he didn't know how to obtain rational approximations, because rational approximations are the only thing that */ and M*/ are good for. So why didn't he provide us with this continued-fraction program? The answer is that Elizabeth Rather kicked him out of Forth Inc. in 1982 and so he just abandoned the Forth community and moved onto other pursuits (mostly weird processor designs). This is why in 1984 Nathaniel Grossman had to provide us with a continued-fraction program, and over half of his program is the D/ function (realistically, the typical Forth programmer is not going to figure out how to write a program like this). Now, 30 years later Elizabeth Rather is praising M*/ as being one of Charles Moore's "most brilliant innovations." She doesn't know what it is for though, because she doesn't know how to write a continued-fraction program, and she doesn't provide a D/ because she thinks that M*/ could be used instead of D/ in a continued-fraction program (it can't). Adding insult to injury, she then tells me that I need to "think differently" --- differently from what? --- I'm apparently the only Forth programmer who knows how to obtain rational approximations, because my novice-package is the only Forth package available that provides a continued-fraction program.

The Forth community needs a lot less of Elizabeth Rather's hot air about "thinking differently" --- math is math no matter what programming language is being used --- we need to get a lot more solid on the math if we expect the world to take us seriously.

Apparently "thinking differently" means that the Forth programmer pulls rational approximations out of his ass, rather that use his brain to write a continued-fraction program to generate them.

BTW: I'll bet that the reason Charles Moore didn't provide us with his continued-fraction program is that he wrote it in Fortran or some other such language that has a D/ available (you aren't allowed to publish Fortran code in "Forth Dimensions," even if you are the inventor of Forth). Elizabeth Rather was totally unaware of this (she doesn't even know what a continued-fraction program is), which is why she refused to allow ANS-Forth to have a D/ function when she wrote the ANS-Forth standard. 

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

#46326

mhx@iae.nl writes:

>On Wednesday, March 30, 2016 at 2:09:32 AM UTC+2, Bernd Paysan wrote:
>> Am Tue, 29 Mar 2016 09:16:44 -1000 schrieb Elizabeth D. Rather:
>> > FORTH, Inc. argued for many years that the MOD operators should be
>> > unsigned; they were unsigned in our systems from the 1970's till
>> > SwiftForth (which conformed to Forth94). None of our users ever found a
>> > problem with this usage. A signed MOD makes no real-world sense. No one
>> > has ever presented a mathematical argument for having a signed MOD that
>> > I know of.

>Elizabeth probably means *convincing* mathematical argument.
>I remember Robert Berkey / Zafar Essak published quite an extended
>mathematical analysis in FORML 1986.
>
>> And while the CPU designers and C programmers seem to think it doesn't
>> matter, even scripting languages like Python now get it right. MOD has a
>> clear and obvious mathematical definition, and that is that the result of
>> n MOD is between 0 and n-1 (or between n+1 and 0 if n<0).

>It isn't that simple. Even in FP the "round to zero" mode exists.

That is a different matter. I'm working on a floating point extension
and is the most practical mode when working on input and output.
All rounding modes are needed at one time or another.

>
>> When we made the switch to floored division in Gforth, I did some
>> benchmarks, and the result was that it doesn't really matter.  The only
>> remarkable result was that PolyForth's division with an unsigned quotient
>> was faster than the competition, which is no surprise, because it bases
>> on UM/MOD, which is faster, too.  But unfortunately, that's completely
>> non-standard...

>So, it *does* matter in a measureable way: for speed. And when
>one is aware of the problem, one gets the speed advantage in 99%
>of the cases, while 1% need a little thought for that pathological
>motor controller.  This tells you why Python uses floored division
>(assume the user doesn not know much and isn't interested in
>efficiency) while most Forths don't.

>-marcel

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#46342

Am Tue, 29 Mar 2016 22:09:07 -0700 schrieb mhx:

>> When we made the switch to floored division in Gforth, I did some
>> benchmarks, and the result was that it doesn't really matter.  The only
>> remarkable result was that PolyForth's division with an unsigned
>> quotient was faster than the competition, which is no surprise, because
>> it bases on UM/MOD, which is faster, too.  But unfortunately, that's
>> completely non-standard...
> 
> So, it *does* matter in a measureable way: for speed. And when one is
> aware of the problem, one gets the speed advantage in 99%
> of the cases, while 1% need a little thought for that pathological motor
> controller.  This tells you why Python uses floored division (assume the
> user doesn not know much and isn't interested in efficiency) while most
> Forths don't.

For speed, unsigned is fastest, followed by the branchless implementation 
of Forth Inc. mixed sign division (which is floored with two quadrants), 
followed by symmetric, and standard floored (four quadrants) is last, 
slightly slower than symmetric.  If you only divide by positive numbers, 
we could implement standard floored in terms of Forth Inc's version if 
the divider is positive, and since that's then an always taken branch, it 
is faster than symmetric.

Floating point round to zero is there, because the same people who think 
that symmetric division is a good idea also want conversion of floating 
point to integer also symmetric.  This causes a discontinuation around 
zero, and usually that shows up as a hickup when your arguments actually 
cross zero.

The rounding mode you actually want for serious scientific computing and 
signal processing, round by noise, is not available.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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

#46325

Bernd Paysan <bernd.paysan@gmx.de> writes:

>Am Tue, 29 Mar 2016 09:16:44 -1000 schrieb Elizabeth D. Rather:
>> FORTH, Inc. argued for many years that the MOD operators should be
>> unsigned; they were unsigned in our systems from the 1970's till
>> SwiftForth (which conformed to Forth94). None of our users ever found a
>> problem with this usage. A signed MOD makes no real-world sense. No one
>> has ever presented a mathematical argument for having a signed MOD that
>> I know of.

>And while the CPU designers and C programmers seem to think it doesn't
>matter, even scripting languages like Python now get it right. MOD has a
>clear and obvious mathematical definition, and that is that the result of
>n MOD is between 0 and n-1 (or between n+1 and 0 if n<0).

No. MOD has no mathematical definition, it is a programming concept.
MOD or doesn't return a modulo class: an infinite set of numbers
that suffer an equivalence relation.

Instead it returns a somewhat arbitrary member of that set of functions.
Mathematically DROP would be acceptable. Because the result is a valid
member that is in the modulo class. Because there is freedom which
member to choose, the hassle results.

This has nothing to do with what I presented. I don't want to implement
the modulo package for negative _m.

>When we made the switch to floored division in Gforth, I did some
>benchmarks, and the result was that it doesn't really matter.  The only
>remarkable result was that PolyForth's division with an unsigned quotient
>was faster than the competition, which is no surprise, because it bases
>on UM/MOD, which is faster, too.  But unfortunately, that's completely
>non-standard...

>--
>Bernd Paysan
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#46318

"Elizabeth D. Rather" <erather@forth.com> writes:
>On 3/29/16 6:20 AM, Anton Ertl wrote:
>> Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>> I have this package that calculates modulo a VARIABLE _m.
>>> : +m   + _m @ MOD ;
>>> *m -m /m
>>> etc.
...
>A signed MOD makes no real-world sense. No one 
>has ever presented a mathematical argument for having a signed MOD that 
>I know of.

I thought about recommending to use UM/MOD for the problem outlined
above, but then found a case where negative dividends occur:

: -m - _m @ MOD ;

E.g., if you do 1 2 -M, the dividend is negative, so unsigned MOD
won't cut it here.

However, most people seem to only divide positive numbers by positive
numbers, as evidenced by the complete lack of complaints from users
when Gforth switched from symmetric to floored.

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

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.forth

csiph-web