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

The problem with implementation defined behaviour.

Started by	Albert van der Horst <albert@spenarnc.xs4all.nl>
First post	2016-03-29 14:39 +0000
Last post	2016-03-30 12:49 +0000
Articles	20 on this page of 46 — 9 participants

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

  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 1 of 3 [1] 2 3 Next page →

#46294 — The problem with implementation defined behaviour.

From	Albert van der Horst <albert@spenarnc.xs4all.nl>
Date	2016-03-29 14:39 +0000
Subject	The problem with implementation defined behaviour.
Message-ID	<56fa93aa$0$5868$e4fe514c@news.xs4all.nl>

I have this package that calculates modulo a VARIABLE _m.
: +m   + _m @ MOD ;
*m -m /m
etc.

The result of those operations result on a number 0<=n<=_m.
It makes no sense to have _m negative, and we would
have to fantasize about what number we want back anyway
( -|floor(_m/2)| < n <= |floor(_m/2)| anybody? )
It also would require duplicating all the code with
checks for _m<0 and that in a package where speed is
of the essence (euler problems).

So the doc's say
**********************************************
* _m must be positive, if not you're screwed *
**********************************************

It is certain that with negative _m answers will be wrong,
and it is even more work to specify how wrong than implementing
something reasonable for negative _m.

I could use a setter and thow an exception 73 "invalid
modulo". That doesn't change it into implementation
defined behaviour, as one still can do
    -3 _m !
We have a defined behaviour for set-m, not for the
package. (Now if we were able to hide _m behind
an iron curtain, that would solve it of course, and
some languages do it that way, but not Forth.)

The bottomline:
The behaviour of the mod package for negative _m is
undefined. I find this acceptable.

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] | [next] | [standalone]

#46297

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-03-29 16:20 +0000
Message-ID	<2016Mar29.182032@mips.complang.tuwien.ac.at>
In reply to	#46294

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.
>
>The result of those operations result on a number 0<=n<=_m.

[long discussion of protecting against negative _m]

I don't know what you are getting at, but the implementation-defined
behaviour that I thought of first when seeing this code is that

-2 3 mod

produces -2 on some Forth systems and 1 on others.  A way to fix that
is to use FM/MOD, which produces positive numbers for a positive
dividend.

But if, as you write, performance is important, and if _M does not
change often, I would go for implementing floored MOD through division
by multiplication with the inverse, which is quite a bit faster.  And
then your SET-M helps by allowing this implementation without changing
the interface.

>The bottomline:
>The behaviour of the mod package for negative _m is
>undefined. I find this acceptable.

And the GCC and LLVM people find undefined behaviour in C acceptable,
if that's what inspired this posting.  Does not mean that it's ok for
the rest of us.

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

#46308

From	"Elizabeth D. Rather" <erather@forth.com>
Date	2016-03-29 09:16 -1000
Message-ID	<n9-dnSdCKI4ASWfLnZ2dnUU7-InNnZ2d@supernews.com>
In reply to	#46297

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.
>>
>> The result of those operations result on a number 0<=n<=_m.
>
> [long discussion of protecting against negative _m]
>
> I don't know what you are getting at, but the implementation-defined
> behaviour that I thought of first when seeing this code is that
>
> -2 3 mod
>
> produces -2 on some Forth systems and 1 on others.  A way to fix that
> is to use FM/MOD, which produces positive numbers for a positive
> dividend.
>
> But if, as you write, performance is important, and if _M does not
> change often, I would go for implementing floored MOD through division
> by multiplication with the inverse, which is quite a bit faster.  And
> then your SET-M helps by allowing this implementation without changing
> the interface.
>
>> The bottomline:
>> The behaviour of the mod package for negative _m is
>> undefined. I find this acceptable.
>
> And the GCC and LLVM people find undefined behaviour in C acceptable,
> if that's what inspired this posting.  Does not mean that it's ok for
> the rest of us.

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.

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]

#46311

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2016-03-30 00:06 +0000
Message-ID	<ndf59p$kap$1@dont-email.me>
In reply to	#46308

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

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
"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]

#46313

From	mhx@iae.nl
Date	2016-03-29 22:09 -0700
Message-ID	<4b57b1ee-841e-4007-8812-0c0810620dec@googlegroups.com>
In reply to	#46311

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.

> 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

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

#46315

From	"Elizabeth D. Rather" <erather@forth.com>
Date	2016-03-29 21:37 -1000
Message-ID	<376dnVdN3IqCH2bLnZ2dnUU7-a3NnZ2d@supernews.com>
In reply to	#46313

On 3/29/16 7:09 PM, mhx@iae.nl wrote:
> 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.

Not to mention the "real world" qualifier.

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]

#46316

From	Paul Rubin <no.email@nospam.invalid>
Date	2016-03-30 00:48 -0700
Message-ID	<8760w49zjy.fsf@nightsong.com>
In reply to	#46313

mhx@iae.nl writes:
>> on UM/MOD, which is faster, too.  But unfortunately, that's
>> completely non-standard...
> So, it *does* matter in a measureable way: for speed....  This tells
> you why Python uses floored division

The real issue here is that division on integers isn't really a thing,
the integers don't have multiplicative integers.  The reason for signed
mod is if you write a division sign you expect the obvious identity
to work:  (-a)/b = -(a/b).  With floored division you have 7/3=2 
but (-7)/3 = -3.  If you take the view that division is ordinary
arithmetic that everyone knows about, while mod is a math or computer
thing that's more abstruse, you want (-7)/3 = -2 if you're throwing
away the fraction part.  So that means the remainder is -1.

Lisp supplies both versions, though I don't remember how to use them.

In Haskell, dividing two integers with / is a compile time type error.
The operators "div" and "mod" give floored division (so the modulus is
positive if the divisor is positive, like Python), while "quot" and
"rem" give truncated division (like C99 and later).

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

#46317

From	Paul Rubin <no.email@nospam.invalid>
Date	2016-03-30 00:48 -0700
Message-ID	<871t6s9zis.fsf@nightsong.com>
In reply to	#46316

Paul Rubin <no.email@nospam.invalid> writes:
> the integers don't have multiplicative integers. 

Oops, multiplicative inverses.

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

#46319

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-03-30 07:59 +0000
Message-ID	<2016Mar30.095908@mips.complang.tuwien.ac.at>
In reply to	#46313

mhx@iae.nl writes:
>It isn't that simple. Even in FP the "round to zero" mode exists.

As well as round to positive infinity and round to negative infinity.
But all these modes are rarely used (so rarely that we don't have a
way to set them in standard Forth), and the usual way is
round-to-nearest-or-even.

>So, it *does* matter in a measureable way: for speed.

For constant divisors, floored division is faster.  That's very easy
to see for the power-of-2 case where the right shift gives you floored
division, but the same also applies to multiplying with the inverse
for non-power-of-2 divisors.

For non-constant divisors, here are the timings we did (on a Pentium
4) when we switched to floored division
<2007Jan26.165751@mips.complang.tuwien.ac.at>:

           development     0.6.2
        floored symmetric symmetric
/        194 ms   181 ms    175 ms
mod      197 ms   181 ms    175 ms
/mod     193 ms   183 ms    175 ms
*/       252 ms   250 ms    908 ms
*/mod    258 ms   259 ms    885 ms
fm/mod   278 ms   277 ms   1283 ms
sm/rem   196 ms   196 ms   1215 ms
um/mod   235 ms   235 ms    693 ms
m*/     2018 ms  1764 ms   2373 ms

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

#46339

From	mhx@iae.nl
Date	2016-03-30 10:16 -0700
Message-ID	<5d973aa6-707b-4e4b-b510-2f62acf80c5d@googlegroups.com>
In reply to	#46319

On Wednesday, March 30, 2016 at 10:11:05 AM UTC+2, Anton Ertl wrote:
> mhx@iae.nl writes:
> >It isn't that simple. Even in FP the "round to zero" mode exists.
> 
> As well as round to positive infinity and round to negative infinity.
> But all these modes are rarely used (so rarely that we don't have a
> way to set them in standard Forth), and the usual way is
> round-to-nearest-or-even.
> 
> >So, it *does* matter in a measureable way: for speed.
> 
> For constant divisors, floored division is faster.  That's very easy
> to see for the power-of-2 case where the right shift gives you floored
> division, but the same also applies to multiplying with the inverse
> for non-power-of-2 divisors.
> 
> For non-constant divisors, here are the timings we did (on a Pentium
> 4) when we switched to floored division
> <2007Jan26.165751@mips.complang.tuwien.ac.at>:
> 
>            development     0.6.2
>         floored symmetric symmetric
> /        194 ms   181 ms    175 ms
> mod      197 ms   181 ms    175 ms
> /mod     193 ms   183 ms    175 ms
> */       252 ms   250 ms    908 ms
> */mod    258 ms   259 ms    885 ms
> fm/mod   278 ms   277 ms   1283 ms
> sm/rem   196 ms   196 ms   1215 ms
> um/mod   235 ms   235 ms    693 ms
> m*/     2018 ms  1764 ms   2373 ms

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 )

I'm sure the difference is even greater in VFX (we don't
do 32bits anymore).

-marcel

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

#46345

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2016-03-30 23:43 +0000
Message-ID	<ndhob4$eer$3@dont-email.me>
In reply to	#46339

Am Wed, 30 Mar 2016 10:16:19 -0700 schrieb mhx:
> I'm sure the difference is even greater in VFX (we don't do 32bits
> anymore).

I've tested with the current git branchless variants of floored division 
(which now bases on unsigned division):

: utest $1234.5678.9abc.def0 $40000000 $300 DO
     2dup i um/mod 2drop  $12 +LOOP  2drop ;
: ftest $1234.5678.9abc.def0 $40000000 $300 DO
     2dup i fm/mod 2drop  $12 +LOOP  2drop ;
: stest $1234.5678.9abc.def0 $40000000 $300 DO
     2dup i sm/rem 2drop  $12 +LOOP  2drop ;
: mtest $1234.5678.9abc.def0 $40000000 $300 DO
     2dup i du/mod 2drop  $12 +LOOP  2drop ;

du/mod is a branchless version of PolyForth's m/mod, i.e. divide d by u.

After letting the CPU warm up a bit:

utest 874.929920ms 
mtest 878.108114ms 
ftest 920.383290ms 
stest 983.614423ms 

stest uses idiv, all the other's use div, mobile Core i7 3GHz, 64 bit 
Gforth.

I suppose ftest will be slower than stest when the sign of the divider 
changes unpredictable, but that situation seems to be rare, that's why I 
chose not to have a branchless implementation for that case.

That way, floored is simply faster than symmetric.

Forth reference implementation of fm/mod based on Polyforth's m/mod:

: fm/mod ( d1 n1 -- n2 n3 )
  dup >r dup 0< IF  negate >r dnegate r>  THEN
  >r dup 0< r@ and + r> um/mod
  r> 0< IF  swap negate swap  THEN ;

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

#46360

From	mhx@iae.nl
Date	2016-03-31 06:01 -0700
Message-ID	<35ca30c9-dbd9-49e0-804b-da26b0b7dbe6@googlegroups.com>
In reply to	#46345

On Thursday, March 31, 2016 at 1:46:47 AM UTC+2, Bernd Paysan wrote:
> Am Wed, 30 Mar 2016 10:16:19 -0700 schrieb mhx:
> > I'm sure the difference is even greater in VFX (we don't do 32bits
> > anymore).
> 
> I've tested with the current git branchless variants of floored division 
> (which now bases on unsigned division):
> 
> : utest $1234.5678.9abc.def0 $40000000 $300 DO
>      2dup i um/mod 2drop  $12 +LOOP  2drop ;
> : ftest $1234.5678.9abc.def0 $40000000 $300 DO
>      2dup i fm/mod 2drop  $12 +LOOP  2drop ;
> : stest $1234.5678.9abc.def0 $40000000 $300 DO
>      2dup i sm/rem 2drop  $12 +LOOP  2drop ;
> : mtest $1234.5678.9abc.def0 $40000000 $300 DO
>      2dup i du/mod 2drop  $12 +LOOP  2drop ;
> 
> du/mod is a branchless version of PolyForth's m/mod, i.e. divide d by u.
> 
> After letting the CPU warm up a bit:
> 
> utest 874.929920ms 
> mtest 878.108114ms 
> ftest 920.383290ms 
> stest 983.614423ms 
> 
> stest uses idiv, all the other's use div, mobile Core i7 3GHz, 64 bit 
> Gforth.
> 
> I suppose ftest will be slower than stest when the sign of the divider 
> changes unpredictable, but that situation seems to be rare, that's why I 
> chose not to have a branchless implementation for that case.
> 
> That way, floored is simply faster than symmetric.
> 
> Forth reference implementation of fm/mod based on Polyforth's m/mod:
> 
> : fm/mod ( d1 n1 -- n2 n3 )
>   dup >r dup 0< IF  negate >r dnegate r>  THEN
>   >r dup 0< r@ and + r> um/mod
>   r> 0< IF  swap negate swap  THEN ;

Please add the qualifier: "on gForth" :-)

This is on a 3.4GHz i7-4930K:
 
FORTH> : fm/modpF ( d1 n1 -- n2 n3 )
<3>[FORTH>]   dup >r dup 0< IF  negate >r dnegate r>  THEN
<3>[FORTH>]   >r dup 0< r@ and + r> um/mod
<3>[FORTH>]   r> 0< IF  swap negate swap  THEN
<3>[FORTH>] ;  ok
FORTH>   ok
FORTH> : tests
<3>[FORTH>]      cr ." \ utest    : " timer-reset $1234.5678.9abc.def0 $40000000 $300 DO
[3]<3>[FORTH>]      2dup i um/mod 2drop  $12 +LOOP  2drop  .elapsed
<3>[FORTH>]      cr ." \ ftest    : " timer-reset $1234.5678.9abc.def0 $40000000 $300 DO
[3]<3>[FORTH>]      2dup i fm/mod 2drop  $12 +LOOP  2drop .elapsed
<3>[FORTH>]      cr ." \ stest    : " timer-reset $1234.5678.9abc.def0 $40000000 $300 DO
[3]<3>[FORTH>]      2dup i sm/rem 2drop  $12 +LOOP  2drop .elapsed
<3>[FORTH>]      cr ." \ fm/modpF : " timer-reset $1234.5678.9abc.def0 $40000000 $300 DO
[3]<3>[FORTH>]      2dup i fm/modpF 2drop  $12 +LOOP  2drop .elapsed ;  ok
FORTH>   ok
FORTH> tests
\ utest    : 0.435 seconds elapsed.
\ ftest    : 0.555 seconds elapsed.
\ stest    : 0.458 seconds elapsed.
\ fm/modpF : 0.578 seconds elapsed. ok

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

#46398

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2016-04-01 21:36 +0000
Message-ID	<ndmpkg$ek8$2@dont-email.me>
In reply to	#46360

Am Thu, 31 Mar 2016 06:01:12 -0700 schrieb mhx:

> Please add the qualifier: "on gForth"

I didn't implement the new fm/mod in Gforth, seems to be that GCC is 
considerably better than iForth in translating the code... it also 
managed to convert the last IF into a conditional move.

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

#46400

From	mhx@iae.nl
Date	2016-04-01 14:57 -0700
Message-ID	<5e546e35-2d1e-431f-b5ab-612939509531@googlegroups.com>
In reply to	#46398

On Friday, April 1, 2016 at 11:39:32 PM UTC+2, Bernd Paysan wrote:
> Am Thu, 31 Mar 2016 06:01:12 -0700 schrieb mhx:
> 
> > Please add the qualifier: "on gForth"
> 
> I didn't implement the new fm/mod in Gforth, seems to be that GCC is 
> considerably better than iForth in translating the code... it also 
> managed to convert the last IF into a conditional move.

"considerably better?" Are we still talking about [ufsm]test?
That code seems to be at least two times slower on a 25% faster 
cpu.

-marcel

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

#46401

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2016-04-01 21:59 +0000
Message-ID	<ndmr0u$ek8$4@dont-email.me>
In reply to	#46400

Am Fri, 01 Apr 2016 14:57:40 -0700 schrieb mhx:

> On Friday, April 1, 2016 at 11:39:32 PM UTC+2, Bernd Paysan wrote:
>> Am Thu, 31 Mar 2016 06:01:12 -0700 schrieb mhx:
>> 
>> > Please add the qualifier: "on gForth"
>> 
>> I didn't implement the new fm/mod in Gforth, seems to be that GCC is
>> considerably better than iForth in translating the code... it also
>> managed to convert the last IF into a conditional move.
> 
> "considerably better?" Are we still talking about [ufsm]test? That code
> seems to be at least two times slower on a 25% faster cpu.

Yes, I'm talking about the code GCC made, using div and fixing up the 
upper half of d.  It's faster than the code GCC has for sm/rem, which is 
just wrapping up idiv.  It's way slower for negative numbers, but that's 
not what I had been testing...

I suppose when I say >R in iForth, it's pushing to the real return stack, 
and not keeping the value in a register?

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

#46409

From	mhx@iae.nl
Date	2016-04-02 00:51 -0700
Message-ID	<ea16f6c1-58ff-4e6d-abb3-85eab7a9e68d@googlegroups.com>
In reply to	#46401

On Saturday, April 2, 2016 at 12:03:14 AM UTC+2, Bernd Paysan wrote:
> Am Fri, 01 Apr 2016 14:57:40 -0700 schrieb mhx:
> 
> > On Friday, April 1, 2016 at 11:39:32 PM UTC+2, Bernd Paysan wrote:
> >> Am Thu, 31 Mar 2016 06:01:12 -0700 schrieb mhx:
 
> I suppose when I say >R in iForth, it's pushing to the real return stack, 
> and not keeping the value in a register?

That depends on context. When register pressure is low, an equivalent register sequence is used. However, the CPU return stack 
is used as iForth's parameter stack.

FORTH> : t1 swap >R swap R> swap ;  ok
FORTH> see t1
Flags: TOKENIZE, ANSI
: t1  SWAP >R SWAP R> SWAP ;  ok
FORTH> ' t1 idis
$013211C0  : t1
$013211CA  pop           rbx
$013211CB  pop           rdi
$013211CC  pop           rax
$013211CD  push          rbx
$013211CE  push          rdi
$013211CF  push          rax
$013211D0  ;
FORTH> : t2 1 2 3 t1 ; ' t2 idis
$01321240  : t2
$0132124A  push          3 b#
$0132124C  push          2 b#
$0132124E  push          1 b#
$01321250  ;

etc.

-marcel

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

#46386

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-04-01 08:25 +0000
Message-ID	<2016Apr1.102503@mips.complang.tuwien.ac.at>
In reply to	#46345

Bernd Paysan <bernd.paysan@gmx.de> writes:
>I've tested with the current git branchless variants of floored division 
>(which now bases on unsigned division):
>
>: utest $1234.5678.9abc.def0 $40000000 $300 DO
>     2dup i um/mod 2drop  $12 +LOOP  2drop ;
>: ftest $1234.5678.9abc.def0 $40000000 $300 DO
>     2dup i fm/mod 2drop  $12 +LOOP  2drop ;
>: stest $1234.5678.9abc.def0 $40000000 $300 DO
>     2dup i sm/rem 2drop  $12 +LOOP  2drop ;
>: mtest $1234.5678.9abc.def0 $40000000 $300 DO
>     2dup i du/mod 2drop  $12 +LOOP  2drop ;

I wanted to compare with the old implementation (commit
58411a3ad8335ee6d7d5d54c40b520ba71f5f169), but the timing code is
missing, so I used contrib/divspeed.fs (100M iterations); timings from
a 4GHz Core i7-6700K:

implementation    old         old        new
       default symmetric   floored     floored
        /        832 ms     820 ms      784 ms
        mod      776 ms     864 ms      868 ms
        /mod     780 ms     816 ms      936 ms
        */       792 ms     836 ms      852 ms
        */mod    828 ms     844 ms      896 ms
        fm/mod   856 ms     876 ms     2448 ms
        sm/rem   844 ms     860 ms      812 ms
        um/mod   820 ms     820 ms      756 ms
        m*/     3304 ms    3344 ms     3280 ms

I find the results puzzling: The new / is faster (even than the
symmetric variant), but /MOD */ and */MOD is slower than the old
variant (divspeed.fs makes the branches easy to predict, so the new
variant might have advantages on other code).

FM/MOD is very slow in the new variant; it's code is longer, but not
that much longer (see below). Strange.  SM/REM and UM/MOD are a bit
faster in the new implementation, although their source code did not
change, and the binary code for um/mod is the same.

I get similar timings on repeating these runs, so these are not
one-time flukes.  Inserting code before the benchmarked code to vary
code alignment seems to cause differences by up to 60ms for this test,
so code alignment may be responsible for the smaller differences
(which means we need a better way to benchmark this stuff).  The
big slowdown for FM/MOD remains unexplained.

Here are some code fragments:

/
old symmetric        old floored            new floored
mov  0x8(%r15),%rax  mov    0x8(%r15),%rcx  mov    0x8(%r15),%rcx 
add  $0x8,%rbx       mov    %r14,%rsi       add    $0x8,%r15      
add  $0x8,%r15       add    $0x8,%r15       test   %r14,%r14      
cqto                 mov    %rcx,%rax       jns    (to lea)       
idiv %r14            cqto                   mov    %r14,%rax      
mov  %rax,%r14       idiv   %r14            test   %rcx,%rcx      
mov  -0x8(%rbx),%rdx mov    %rax,%rdi       mov    $0x0,%edx      
mov  %rdx,%rax       mov    %rax,%r14       not    %rax           
jmpq *%rax           mov    %rcx,%rax       cmovns %rax,%rdx      
                     xor    %rsi,%rax       mov    %rcx,%rax      
                     jns (after cmovne)     neg    %r14           
                     mov    %rcx,%rax       neg    %rax           
                     sub    $0x1,%rdi       jmp    (to div)       
                     cqto                   lea    -0x1(%r14),%rax
                     idiv   %rsi            test   %rcx,%rcx      
                     test   %rdx,%rdx       mov    $0x0,%edx      
                     cmovne %rdi,%r14       cmovs  %rax,%rdx      
                     add    $0x8,%rbx       mov    %rcx,%rax      
                     mov    -0x8(%rbx),%rdx div    %r14           
                     mov    %rdx,%rax       add    $0x8,%rbx      
                     jmpq   *%rax           mov    %rax,%r14      
                                            mov    -0x8(%rbx),%rdx
                                            mov    %rdx,%rax      
                                            jmpq   *%rax          

fm/mod
old (both engines)      new
mov  0x8(%r15),%r8      mov    %r14,%rcx      
mov  %r14,%rsi          mov    %r15,%rsi      
mov  0x10(%r15),%rax    mov    0x10(%r15),%r10
mov  %r15,%rcx          shr    $0x3f,%rcx     
lea  0x8(%r15),%r15     mov    0x8(%r15),%r11 
mov  %r8,%rdx           lea    0x8(%r15),%r15 
idiv %r14               test   %cl,%cl        
xor  %rsi,%r8           je     (to next mov)  
mov  %rax,%r14          neg    %r14           
jns  (to add)           neg    %r10           
test %rdx,%rdx          adc    $0x0,%r11      
je   (to add)           neg    %r11           
lea  -0x1(%rax),%r14    mov    %r11,%rdi      
lea  (%rdx,%rsi,1),%rdx movzbl %cl,%ecx       
add  $0x8,%rbx          mov    %r11,%rdx      
mov  %rdx,0x10(%rcx)    sar    $0x3f,%rdi     
mov  -0x8(%rbx),%rdx    mov    %r10,%rax      
mov  %rdx,%rax          add    $0x8,%rbx      
jmpq *%rax              and    %r14,%rdi      
                        add    %rdi,%rdx      
                        div    %r14           
                        mov    %rax,%r14      
                        mov    %rcx,%rax      
                        neg    %rax           
                        xor    %rdx,%rax      
                        add    %rcx,%rax      
                        mov    %rax,0x10(%rsi)
                        mov    -0x8(%rbx),%rdx
                        mov    %rdx,%rax      
                        jmpq   *%rax          








































































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

#46397

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2016-04-01 21:32 +0000
Message-ID	<ndmpdi$ek8$1@dont-email.me>
In reply to	#46386

Am Fri, 01 Apr 2016 08:25:03 +0000 schrieb Anton Ertl:

> Bernd Paysan <bernd.paysan@gmx.de> writes:
>>I've tested with the current git branchless variants of floored division
>>(which now bases on unsigned division):
>>
>>: utest $1234.5678.9abc.def0 $40000000 $300 DO
>>     2dup i um/mod 2drop  $12 +LOOP  2drop ;
>>: ftest $1234.5678.9abc.def0 $40000000 $300 DO
>>     2dup i fm/mod 2drop  $12 +LOOP  2drop ;
>>: stest $1234.5678.9abc.def0 $40000000 $300 DO
>>     2dup i sm/rem 2drop  $12 +LOOP  2drop ;
>>: mtest $1234.5678.9abc.def0 $40000000 $300 DO
>>     2dup i du/mod 2drop  $12 +LOOP  2drop ;
> 
> I wanted to compare with the old implementation (commit
> 58411a3ad8335ee6d7d5d54c40b520ba71f5f169), but the timing code is
> missing,

Oh, timing is easy, just !time <word> .time

> so I used contrib/divspeed.fs (100M iterations); timings from a
> 4GHz Core i7-6700K:
> 
> implementation    old         old        new
>        default symmetric   floored     floored
>         /        832 ms     820 ms      784 ms mod      776 ms     864
>         ms      868 ms /mod     780 ms     816 ms      936 ms */      
>         792 ms     836 ms      852 ms */mod    828 ms     844 ms     
>         896 ms fm/mod   856 ms     876 ms     2448 ms sm/rem   844 ms   
>          860 ms      812 ms um/mod   820 ms     820 ms      756 ms m*/  
>           3304 ms    3344 ms     3280 ms
> 
> I find the results puzzling: The new / is faster (even than the
> symmetric variant),

Yes, that's expected.

> but /MOD */ and */MOD is slower than the old variant
> (divspeed.fs makes the branches easy to predict, so the new variant
> might have advantages on other code).

Funny, because I haven't changed anything on */ and */MOD yet ;-).

Using cputime as divspeed.fs does is not very accurate.

The Core i7 idiv and div take a shortcut when the input is actually 64 
bit and not 128 bit, so using idiv is faster for small negative numbers 
(which is what divtest.fs does).

That's divtest.fs on my 3.4GHz non-mobile Core i7, with fm/mod for 
negative double numbers first, and positive second:

/       1068 ms  2712 ms
mod      980 ms  2588 ms
/mod     988 ms  2604 ms
*/      1080 ms
*/mod   1164 ms
fm/mod  2712 ms  1028 ms
sm/rem  1132 ms  1144 ms
um/mod   940 ms
m*/     3832 ms

Second column is "negated input"

That is an awful lot worse, just because it's now a "big" number and not 
a small number.

Old method:

/       1212 ms
mod     1168 ms
/mod    1144 ms
*/      1108 ms
*/mod   1100 ms
fm/mod  1144 ms
sm/rem  1128 ms
um/mod   940 ms
m*/     3524 ms

Testing the new code with negative numbers shows that the slowdown is 
quite big:  So the new code is good for the common case (all numbers are 
positive), but bad for the uncommon case.

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

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

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Date	2016-04-05 11:12 +0000
Subject	division performance (was: The problem with implementation defined ...)
Message-ID	<2016Apr5.131223@mips.complang.tuwien.ac.at>
In reply to	#46397

Bernd Paysan <bernd.paysan@gmx.de> writes:
>> I find the results puzzling: The new / is faster (even than the
>> symmetric variant),
>
>Yes, that's expected.
>
>> but /MOD */ and */MOD is slower than the old variant
>> (divspeed.fs makes the branches easy to predict, so the new variant
>> might have advantages on other code).
>
>Funny, because I haven't changed anything on */ and */MOD yet ;-).

Yes, that shows the problem of the benchmark.

>Using cputime as divspeed.fs does is not very accurate.

In the measurements below I only included the user times (instead of
adding the system time as the original divspeed.fs does), but I don't
think that was the problem.

Experiments with different code alignments produced different results,
consistent for each alignment (even with the old divspeed time
measurements), so my guess is that this was the problem.  I have now
rewritten divspeed to use 64 different code alignments for all tests
(result in contrib/divspeed2.fs), and that seems to have cured the
problem.  Basic benchmarks where the code should not change across
versions (for SM/REM and UM/MOD) actually produce results that differ
by at most a tick (4ms).

>The Core i7 idiv and div take a shortcut when the input is actually 64 
>bit and not 128 bit, so using idiv is faster for small negative numbers 
>(which is what divtest.fs does).

Yes, the Intel Optimization manual gives latency/inverse throughput of
20-26 for 32-bit DIV/IDIV and 80-95 for DIV with RDX!=0, and 85-100
for IDIV with RDX!=0 (probably they meant that RDX is not a sign
extension of RAX).

and says this (section C.3.2):

| 9. The throughput of "DIV/IDIV r64" varies with the number of
|    significant digits in the input RDX:RAX.  The throughput is
|    significantly higher if RDX input is 0, similar to those of
|    "DIV/IDIV r32". If RDX is not zero, the throughput is
|    significantly lower, as shown in the range. The throughput
|    decreases (increasing numerical value in cycles) with increasing
|    number of significant bits in the input RDX:RAX (relative to the
|    number of significant bits of the divisor) or the output
|    quotient. The latency of "DIV/IDIV r64" also varies with the
|    significant bits of input values. For a given set of input values,
|    the latency is about the same as the throughput in cycles.
|
|10. The throughput of "DIV/IDIV r32" varies with the number of
|    significant digits in the input EDX:EAX and/or of the quotient of
|    the division for a given size of significant bits in the divisor
|    r32. The throughput decreases (increasing numerical value in
|    cycles) with increasing number of significant bits in the input
|    EDX:EAX or the output quotient. The latency of "DIV/IDIV r32" also
|    varies with the significant bits of the input values. For a given
|    set of input values, the latency is about the same as the
|    throughput in cycles.

3.4GHz non-mobile Core i7

The actual model number (/proc/cpuinfo) may be more useful than
mobile/non-mobile for these kinds of measurements.  There is a
difference between your i7 being a Nehalem or a Skylake, and for
single-thread measurements, that difference is more important than the
difference between i3 and i7.

>Testing the new code with negative numbers shows that the slowdown is 
>quite big:  So the new code is good for the common case (all numbers are 
>positive), but bad for the uncommon case.

Given that we had no complaints about the switch to floored, the
uncommon case seems to be really uncommon.  But given that we
implement floored division exactly for that case, it should also be
fast in that case, so going back to basing floored on symmetric is a
good idea.

Here are the results with contrib/divspeed2.fs.  The columns are four
different gforth-fast binaries:

sym is version 58411a3ad8335... configured for default symmetric division
old is the same version with default floored division
mid is the version (f9935b520f2b9e80...), floored uses unsigned division
new is the current version (5251de747f5cc7f...), floored based on symmetric

The benchmarks are divided into three sets:

"classic" is a reimplementation of divspeed (same inputs, same loop kernels)
"influcence" varies inputs to show their influence
"dependent" measures the latency instead of the throughput.
         it also varies the inputs and uses all operation that classic uses.

Numbers are times in ms.

 1       classic divspeed reloaded
 2   sym  old  mid  new kernel
 3   768  788  760  824 dup i / drop
 4   760  796  828  832 dup i mod drop
 5   752  832  876  840 dup i /mod 2drop
 6   768  812  820  824 2dup i */ drop
 7   784  800  852  856 2dup i */mod 2drop
 8   828  824 2336  860 2dup i fm/mod 2drop
 9   780  780  780  784 2dup i sm/rem 2drop
10   768  772  772  772 2dup i um/mod 2drop
11  
12       influence of dividend
13   sym  old  mid  new kernel
14   780  804  772  840 1 i / drop
15   780  808  772  836 $7fffffffffffffff i / drop
16   776 1472 2296  836 -1 i / drop
17   792  792  792  792 $ffffffffffffffff. i 1+ um/mod 2drop
18  2264 2264 2264 2268 $10000000000000000. i 1+ um/mod 2drop
19  
20       dependent divides for latency
21   sym  old  mid  new kernel
22  1084 1084  960 1168 100000000 swap /
23  1108 1500 2356 1192 -100000000 swap / negate
24  1028 1032  920 1176 10 mod
25  1060 1128 2300 1212 10 mod -10 +
26  1128 1156 1016 1288 10 /mod +
27  1152 1208 2404 1316 10 /mod + -9 +
28  1092 1132 1172 1168 20000 5000 rot */
29  1116 1112 1192 1192 -20000 5000 rot */ negate
30  1200 1200 1380 1364 1 10 */mod +
31  1220 1248 1408 1388 1 10 */mod + -9 +
32  1060 1056  936 1172 10 fm/mod
33  1192 1192 2432 1296 10 fm/mod -10 0 d+
34  1036 1036 1036 1036 10 sm/rem
35  1052 1052 1056 1052 10 sm/rem -1 +
36   852  852  848  848 10 um/mod

First, you see very little variation between the Forth systems for
SM/REM (9 34 35) and UM/MOD (10 17 18 36), unlike the original
divspeed.fs, so my alignment problem theory seems to be correct and
the workaround works.

There's a big jump from 2^64-1 to 2^64 as dividend for UM/MOD (17 18);
that's what makes the mid variant slow for FM/MOD with negative
dividends.

Looking at the "dependent" benchmarks, floored division in "mid" where
implemented based on unsigned division (for / MOD /MOD FM/MOD) is
faster than sym for positive operands (22 24 26 32), and much slower
(23 25 27 33) for negative operands.

/ is slow for negative dividends in "old" (16 23), because the
correction code performs a second IDIV in this case (the compiler does
not combine the / and the % (necessary for the correction) in this
case, contrary to my expectations; the compiler apparently worked
better for the other operations).  The "new" variant does not have
that problem.

Looking at the "dependent" code (but also "classic"), if we ignore the
"/" with negative dividend anomaly, the "old" floored code is pretty
close to the symmetric code, between -4ms (29) and 68ms (25) slower
than "sym".  Ignoring the anomaly, the "new" code is slower than "old"
by 36ms(28)-164ms(30).  It seems to me that we should return to the
"old" code, except for fixing the anomaly.

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.

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

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

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2016-04-05 20:45 +0000
Subject	Re: division performance (was: The problem with implementation defined ...)
Message-ID	<ne1864$c9u$1@dont-email.me>
In reply to	#46523

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

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.

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. Up to 100 cycles for a 128/64 division 
is really slow.

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

Page 1 of 3 [1] 2 3 Next page →

csiph-web

The problem with implementation defined behaviour.

Contents

#46294 — The problem with implementation defined behaviour.

#46297

#46308

#46311

#46313

#46315

#46316

#46317

#46319

#46339

#46345

#46360

#46398

#46400

#46401

#46409

#46386

#46397

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

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