Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #46523
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | division performance (was: The problem with implementation defined ...) |
| Date | 2016-04-05 11:12 +0000 |
| Organization | Institut fuer Computersprachen, Technische Universitaet Wien |
| Message-ID | <2016Apr5.131223@mips.complang.tuwien.ac.at> (permalink) |
| References | (5 earlier) <2016Mar30.095908@mips.complang.tuwien.ac.at> <5d973aa6-707b-4e4b-b510-2f62acf80c5d@googlegroups.com> <ndhob4$eer$3@dont-email.me> <2016Apr1.102503@mips.complang.tuwien.ac.at> <ndmpdi$ek8$1@dont-email.me> |
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/
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