Index of /forth/programs/map-array
Article: 127742 of comp.lang.forth
Path: tunews.univie.ac.at!aconews-feed.univie.ac.at!aconews.univie.ac.at!not-for-mail
X-newsreader: xrn 9.03-beta-14
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.lang.forth,comp.lang.postscript
Subject: Factor, Postscript, and Forth: A case study
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Keywords:
Date: Thu, 03 May 2007 20:01:19 GMT
Message-ID: <2007May3.220119@mips.complang.tuwien.ac.at>
Lines: 96
NNTP-Posting-Host: a4.complang.tuwien.ac.at
X-Trace: 1178231720 tunews.univie.ac.at 28520 128.130.173.65
X-Complaints-To: abuse@tuwien.ac.at
Xref: tunews.univie.ac.at comp.lang.postscript:92934 comp.lang.forth:127742
At the recent Forth-Tagung, Ulrich Hoffman gave a talk about Factor, a
language that's somewhere between Forth (mainly in syntax) and
Postscript (mainly in semantics, in particular the dynamic type
checking).
Eventually we decided to write and benchmark a small example in all
three languages: Generate an array of 1000 integers, then sum all the
elements 100000 times.
Here's the Forth version:
: map-array ( ... addr u xt -- ... )
\ executes xt ( ... x -- ... ) for every element of the array starting
\ at addr and containing u elements
{ xt }
cells over + swap ?do
i @ xt execute
1 cells +loop ;
create array 1000 cells allot
: init 1000 0 DO I array I cells + ! LOOP ;
init
: step 0 array 1000 ['] + map-array drop ;
: bench 100000 0 DO step LOOP ;
bench
Forth does not have the built-in word reduce (Factor) or forall (PS),
so this has to be written explicitly; however, a definition can be
found in the Gforth tutorial
<http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Execution-Tokens-Tutorial.html>.
Here's the Factor version:
USING: syntax vectors namespaces math kernel sequences tools ;
SYMBOL: v
1000 <vector> v set
0 1000 [ 1+ dup v get push ] times drop
: step v get 0 [ + ] reduce drop ;
: bench 100000 [ step ] times ;
bench
It is probably possible to write this in a simpler way (none of us is
a Factor expert). E.g., I have found that "0 [ + ] reduce" is already
factored out as "sum".
One thing I notice here is that reduce requires the quotation to have
the stack effect ( prev elt -- next ), whereas MAP-ARRAY above and
Postscript's forall support additional stack effects, e.g. ( elt -- )
or ( prev1 prev2 elt -- next1 next2 ). That's due to the more
flexible stack effect of MAP-ARRAY and forall.
More generally, my impression is that Factor provides more words for
processing sequences than Postscript and Forth, but in many cases
several of these words can be subsumed by Postscript's forall (e.g.,
not just reuce, but also map).
Finally, here's the Postscript version:
/v [ 0 1 999 {} for ] def
/step {0 v { add } forall} def
100000 {step pop} repeat
The definition of v demonstrates the way that arrays are constructed
in Postscript: by pushing the elements on the stack and then
constructing the array from there. This is unidiomatic in Forth, but
seems entirely appropriate for a dynamically type-checked language.
Using this method, Postscript can also implement Factor's map using
forall.
You can find all these programs on
<http://www.complang.tuwien.ac.at/forth/programs/map-array/>.
Finally, here are the benchmark results, on a 3000MHz Xeon 5160:
user time lang invocation
2.528s Factor time factor map-array.factor -shell=none
2.122s PS time gs -dBATCH map-array.ps
1.990s PS time gs -dBATCH map-array.ps #with bind inserted in step
0.942s Forth time gforth-fast map-array.fs -e bye #badly compiled
0.484s Forth time $IFORTH/iflinux/bin/iforth 'include ../../anslocal.fs include map-array.fs bye'
I am quite surprised by the relatively good performance of Postscript,
despite having to look up the name on each execution step. I guess
quite a bit of optimization went into Ghostscript.
OTOH, I would have expected Factor and it's native-code compiler to
run faster.
Crossposted to c.l.forth, c.l.postscript
- 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 2007: http://www.complang.tuwien.ac.at/anton/euroforth2007/
Article: 127769 of comp.lang.forth
Path: tunews.univie.ac.at!aconews-feed.univie.ac.at!aconews.univie.ac.at!not-for-mail
X-newsreader: xrn 9.03-beta-14
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Subject: Re: Factor, Postscript, and Forth: A case study
Newsgroups: comp.lang.forth
References: <2007May3.220119@mips.complang.tuwien.ac.at> <133m9nohdhdje47@news.supernews.com>
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Keywords:
Date: Fri, 04 May 2007 19:48:26 GMT
Message-ID: <2007May4.214826@mips.complang.tuwien.ac.at>
Lines: 60
NNTP-Posting-Host: a4.complang.tuwien.ac.at
X-Trace: 1178308761 tunews.univie.ac.at 28520 128.130.173.65
X-Complaints-To: abuse@tuwien.ac.at
Xref: tunews.univie.ac.at comp.lang.forth:127769
Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>In comp.lang.forth Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> Here's the Forth version:
>
>> : map-array ( ... addr u xt -- ... )
>> \ executes xt ( ... x -- ... ) for every element of the array starting
>> \ at addr and containing u elements
>> { xt }
>> cells over + swap ?do
>> i @ xt execute
>> 1 cells +loop ;
>
>The classic Forth way to do this would be with compiling words, not by
>passing an xt:
>
>: (map) ( a n - a a') cells over + swap ;
>: map[ postpone (map) postpone ?do ; immediate
>: ]map postpone cell postpone +loop ; immediate
>
>: step 0 array 1000 map[ + ]map drop ;
This does not pass the current element to +. I guess the idiomatic
way to deal with this is:
: step 0 array 1000 map[ i @ + ]map drop ;
so I used that.
>I'm not saying that there's anything wrong with your map-array, but I
>don't think you'd write it that way unless trying to translate the
>idiom from another languyage into Forth.
I have map-array in the Gforth tutorial, and I have used words like
this several times, but maybe I was influenced by Lisp or Postscript.
In the work on the Sudoku solver a few months ago I eventually decided
on an approach like the one you suggest, though
<2006Nov12.224000@mips.complang.tuwien.ac.at>.
Anyway, I have put all the suggestions in separate programs, and here
are the results of the original and the new programs (sorted by
execution time):
0.23 iforth-noprf include ../../anslocal.fs include haley.fs bye
0.48 iforth-noprf include ../../anslocal.fs include map-array.fs bye
0.73 gforth-fast haley.fs -e bye
0.94 gforth-fast map-array.fs -e bye
0.96 factor slava.factor -shell=none
1.99 gs -dBATCH bind.ps
2.11 gs -dBATCH map-array.ps
2.56 factor map-array.factor -shell=none
The programs and the benchmark script can be found at
http://www.complang.tuwien.ac.at/forth/programs/map-array/
- 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 2007: http://www.complang.tuwien.ac.at/anton/euroforth2007/
![[ICO]](/icons/blank.gif){kind=icon}
![[DIR]](/icons/back.gif){kind=icon}
![[ ]](/icons/unknown.gif){kind=icon}
![[ ]](/icons/a.gif){kind=icon}