Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #52339
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: Stack Operator Symbols |
| Date | 2016-10-31 14:49 +0000 |
| Organization | Institut fuer Computersprachen, Technische Universitaet Wien |
| Message-ID | <2016Oct31.154903@mips.complang.tuwien.ac.at> (permalink) |
| References | (7 earlier) <87k2cpl42w.fsf@nightsong.com> <nlxRz.173904$EN.36366@fx30.am4> <87fundl0i7.fsf@nightsong.com> <tMednQ-_iuzahIrFnZ2dnUU7-XednZ2d@supernews.com> <2016Oct31.131235@mips.complang.tuwien.ac.at> |
anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Paul Rubin <no.email@nospam.invalid> wrote:
>>> Spiros Bousbouras <spibou@gmail.com> writes:
>>>> "you wouldn't write code like this in Forth for any other purpose than
>>>> a benchmark".
>>>
>>> Would you code that function differently if it were for some purpose
>>> other than benchmarking?
>>
>>Perhaps. To start with, the outermost recursive call could be turned
>>into a while loop and the args reordered to (z y x) to simplify stack
>>handling.
>
>Given that the arguments are rotated all the way, I don't see how z y
>x would help. Please enlighten me with code.
>
>>Also, the stack depth might be prohibitively large on some
>>systems, so maybe further action would be required.
>
>Not a problem on the systems I tried, but a stack effect of
>
>( a b c -- a b c r )
>
>might not just reduce stack depth, but also have other benefits.
I took all these ideas, and did two new versions:
\ variation for reducing data stack depth
: tak1 ( z y x -- z y x r )
2dup < if
1- recurse >r 1+ -rot ( x z y )
1- recurse >r 1+ -rot ( y x z )
1- recurse >r 1+ -rot ( z y x )
r> r> r> recurse nip nip nip
else
2 pick
then ;
\ variation that stack-juggles directly and eliminates the tail call of tak
: tak2 ( z y x -- r )
2dup < if
begin
2dup 4 pick 1- recurse >r \ z'
dup 2over 1- recurse >r \ y'
1- recurse
2r> rot
2dup >= until
then
2drop ;
Don't forget to reverse the parameters when calling them.
TAK1 is cute, but not tail-recursive (but, judging from the results,
this does not really hurt). For TAK2, it's interesting how 2DUP and
2OVER enable us to use only one PICK; there might be other ways to
arrange the parameters and the recursive calls that allow using even
fewer words, but I guess one would need an exhaustive search to find
them.
Here are the results (Core i7-6700K):
3dup-builtin 3dup-2pick 3dup-locals locals tak1 tak2
gforth 1160859139 1239191117 1023792580 816129237 816266680
sf 472184708 533401690 1753487060 4529954652 356164897 356006772
vfxlin 490283220 401685949 721040449 700320112 352936074 352709005
The new versions are the fastest versions on all three systems, and
there is no significant speed difference between them on any of the
systems, which is surprising given that they are not that similar.
Strangely, the locals version is even slower on sf than yesterday; if
I repeat the measurements, I get a lot of variation, from 3.2G cycles
to 6.2G cycles; none of the runs was as fast as yesterday (3.0G
cycles). There is something strange going on there.
One variation that I also thought about keeps X Y Z in variables A B
C, and there are 6 variations of TAK, one for each possible assignment
of X Y Z to the variables; instead of rotating the values, you call
the appropriate version of TAK; you decrease and increase the
variables for the first three recursions as in TAK1. E.g., one
version might look like:
: tak-abc ( -- r )
\ a=x, b=y, c=z
y @ x @ < if
-1 a +! tak-abc 1 a +!
-1 b +! tak-cab 1 b +!
-1 c +! tak-bca 1 c +1
a @ b @ c @ 2>r >r c ! b ! a ! tak-abc r> 2r> c ! b ! a !
else
c @
then ;
Not clearer than the existing solutions, longer, and probably slower,
and certainly unidiomatic (at least for me), I'll spare myself the
effort to do the other versions.
- 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 2016: http://www.euroforth.org/ef16/
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Stack Operator Symbols trans <transfire@gmail.com> - 2016-10-24 20:42 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-25 01:58 -0700
Re: Stack Operator Symbols november.nihal@gmail.com - 2016-10-25 10:52 -0700
Re: Stack Operator Symbols Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2016-10-27 19:13 -0400
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-27 17:08 -1000
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-10-28 21:53 +1000
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-28 20:42 -0700
Re: Stack Operator Symbols Walter Banks <walter@bytecraft.com> - 2016-10-29 17:15 -0400
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-29 17:27 -0700
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-28 20:56 -1000
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-29 00:46 -0700
Re: Stack Operator Symbols Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-10-29 04:30 -0500
Re: Stack Operator Symbols rickman <gnuarm@gmail.com> - 2016-10-29 16:58 -0400
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-29 14:21 -0700
Re: Stack Operator Symbols Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-10-30 04:03 -0500
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-30 18:06 -0700
Re: Stack Operator Symbols Spiros Bousbouras <spibou@gmail.com> - 2016-10-31 01:43 +0000
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-30 19:23 -0700
Re: Stack Operator Symbols Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-10-31 05:13 -0500
Re: Stack Operator Symbols albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-10-31 12:42 +0100
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-31 12:12 +0000
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-31 14:49 +0000
Re: Stack Operator Symbols mhx@iae.nl - 2016-10-31 13:17 -0700
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-11-03 16:38 +0000
Re: Stack Operator Symbols Spiros Bousbouras <spibou@gmail.com> - 2016-11-20 14:33 +0000
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-31 08:35 +0000
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-30 11:01 +0000
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-30 10:01 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-11-03 14:46 -0700
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-11-04 23:04 +0000
Re: Stack Operator Symbols Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2016-11-05 03:16 -0400
Re: Stack Operator Symbols peter.m.falth@gmail.com - 2016-10-29 09:13 -0700
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-10-30 08:47 +1100
Re: Stack Operator Symbols trans <transfire@gmail.com> - 2016-10-29 14:57 -0700
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-10-30 09:20 +1100
Re: Stack Operator Symbols Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2016-10-29 18:46 -0400
Re: Stack Operator Symbols Paul Rubin <no.email@nospam.invalid> - 2016-10-29 19:45 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-29 20:29 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-29 20:47 -0700
Re: Stack Operator Symbols Cecil Bayona <cbayona@cbayona.com> - 2016-10-29 23:15 -0500
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-29 21:37 -1000
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-30 10:07 -0700
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-29 21:35 -1000
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-10-31 13:11 +1100
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-30 20:02 -0700
Re: Stack Operator Symbols "Elizabeth D. Rather" <erather@forth.com> - 2016-10-30 22:08 -1000
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-10-31 09:02 +0000
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-11-03 20:49 +1100
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-11-03 15:33 +0000
Re: Stack Operator Symbols Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2016-11-03 16:55 -0400
Re: Stack Operator Symbols anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-11-03 22:21 +0000
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-27 20:31 -0700
Re: Stack Operator Symbols november.nihal@gmail.com - 2016-10-28 09:52 -0700
Re: Stack Operator Symbols hughaguilar96@gmail.com - 2016-10-28 20:32 -0700
Re: Stack Operator Symbols Mark Wills <markwills1970@gmail.com> - 2016-10-30 04:49 -0700
Re: Stack Operator Symbols Coos Haak <htrofhc@gmail.com> - 2016-10-30 14:49 +0100
Re: Stack Operator Symbols Matthias Koch <matthias.koch@hot.uni-hannover.de> - 2016-10-31 13:31 +0100
Re: Stack Operator Symbols Coos Haak <htrofhc@gmail.com> - 2016-10-31 14:12 +0100
Re: Stack Operator Symbols Matthias Koch <matthias.koch@hot.uni-hannover.de> - 2016-10-31 15:03 +0100
Re: Stack Operator Symbols Mark Wills <markwills1970@gmail.com> - 2016-11-03 14:22 -0700
Re: Stack Operator Symbols Coos Haak <htrofhc@gmail.com> - 2016-11-04 00:46 +0100
Re: Stack Operator Symbols "HAA" <someone@microsoft.com> - 2016-11-05 13:14 +1100
Re: Stack Operator Symbols trans <transfire@gmail.com> - 2016-10-30 06:50 -0700
Re: Stack Operator Symbols trans <transfire@gmail.com> - 2016-10-30 08:56 -0700
Re: Stack Operator Symbols albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-10-30 18:19 +0100
csiph-web