Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #46608
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: division performance (was: The problem with implementation defined ...) |
| Date | 2016-04-09 10:14 +0000 |
| Organization | Institut fuer Computersprachen, Technische Universitaet Wien |
| Message-ID | <2016Apr9.121431@mips.complang.tuwien.ac.at> (permalink) |
| References | (7 earlier) <ndmpdi$ek8$1@dont-email.me> <2016Apr5.131223@mips.complang.tuwien.ac.at> <ne1864$c9u$1@dont-email.me> <2016Apr6.120304@mips.complang.tuwien.ac.at> <ne9cp7$2gt$2@dont-email.me> |
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/
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-29 14:39 +0000
Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-29 16:20 +0000
Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-29 09:16 -1000
Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 00:06 +0000
Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-29 22:09 -0700
Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-29 21:37 -1000
Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-30 00:48 -0700
Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-30 00:48 -0700
Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 07:59 +0000
Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-30 10:16 -0700
Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 23:43 +0000
Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-31 06:01 -0700
Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:36 +0000
Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-01 14:57 -0700
Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:59 +0000
Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-02 00:51 -0700
Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-01 08:25 +0000
Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:32 +0000
division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-05 11:12 +0000
Re: division performance (was: The problem with implementation defined ...) Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-05 20:45 +0000
Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-06 10:03 +0000
Re: division performance (was: The problem with implementation defined ...) Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-08 22:53 +0000
Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-09 10:14 +0000
Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-09 13:43 +0000
Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-31 10:55 +0000
Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-31 06:38 -0700
Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-31 16:21 +0000
Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-31 11:49 -0700
Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-31 10:11 -1000
Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-01 03:53 -0700
Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-01 11:44 +0000
Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:53 +0000
Re: The problem with implementation defined behaviour. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-02 11:46 -0500
Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-02 21:43 +0000
Re: The problem with implementation defined behaviour. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-03 03:17 -0500
Re: The problem with implementation defined behaviour. hughaguilar96@gmail.com - 2016-04-01 23:54 -0700
Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:58 +0000
Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 22:22 +0000
Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:55 +0000
Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 07:44 +0000
Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 13:08 +0000
Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 13:43 +0000
Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 22:06 +0000
Re: The problem with implementation defined behaviour. trevor <tgritchie@blueyonder.co.uk> - 2016-03-30 13:13 +0100
Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 13:56 +0000
Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:49 +0000
csiph-web