Message-ID: <233@iham1.UUCP>
Date: Wed, 10-Oct-84 19:23:27 EDT
Article-I.D.: iham1.233
Posted: Wed Oct 10 19:23:27 1984
Date-Received: Fri, 12-Oct-84 08:04:01 EDT
Organization: AT&T Bell Labs, Naperville, IL
Lines: 35



   An article appeared in a recent issue of BYTE presenting a case for changing
 the way FORTH handles its threading.  Ordinarily, FORTH's resident words are
 written in assembler and the user defined words are threaded using these
 resident words and other user defined words.  At the end of any particular
 word, a return pointer to the preceding word is stored.  The article said that
 this technique was used to keep FORTH small.

   A faster way to handle returns from any particular word would be to use the
 return procedure built into the microprocessor.  Rather than going through the
 bother of storing the pointers, the author argued that treating every word as
 a subroutine would provide faster execution.  He then gave some comparisons
 between the usual pointer returns and the subroutine/macro routines that he
 advocated.

   I have the opportunity to obtain the assembly source code for the FORTH that
 has been implemented by Texas Instruments on their TI 99/4A.  If there is
 indeed a significant performance improvement to be realized, a nice project
 for me might involve modifying the returns according to this guy's proposal.
 My question concerns the value of the article's argument.

   Is there a significant performance improvement to be had by treating FORTH
 words as subroutines?  Has anyone in netland considered this possibility?  Are
 there presently some implementations of FORTH that already treat its words as
 subroutines (and uses the subroutine return native to the micro)?  Replies
 will be read if either posted to this newsgroup or sent to me directly.
 Thank you.

-- 

                                    Patrick Wyant
                                    AT&T Bell Laboratories (Naperville, IL)
                                    *!iham1!gjphw

Message-ID: <1741@sun.uucp>
Date: Fri, 12-Oct-84 12:21:38 EDT
Article-I.D.: sun.1741
Posted: Fri Oct 12 12:21:38 1984
Date-Received: Tue, 16-Oct-84 05:37:20 EDT
References: <233@iham1.UUCP>
Organization: Sun Microsystems, Inc.
Lines: 77
Xref: sun net.lang.forth:132 net.micro.ti:43

 >  ...
 > A faster way to handle returns from any particular word would be to use the
 > return procedure built into the microprocessor.  Rather than going through
 > the bother of storing the pointers, the author argued that treating every
 > word as a subroutine would provide faster execution.  He then gave some
 > comparisons between the usual pointer returns and the subroutine/macro
 > routines that he advocated.
 >  ...
 > Is there a significant performance improvement to be had by treating FORTH
 > words as subroutines?  Has anyone in netland considered this possibility?
 > Are there presently some implementations of FORTH that already treat its
 > words as subroutines (and uses the subroutine return native to the micro)?

This opens up a whole can of worms.  There is no simple answer, so here's
the complicated one:

There are at least 5 different ways of "threading" that I know of.  Every one
of these schemes has been used before.
1) Indirect threading (ITC) - compile a pointer to a pointer to the code to
   execute.  This is the common FIG-Forth way.  It os compact an makes
   it easy to implement DOES> words.
2) Direct Threaded Code (DTC) - compile a pointer to the code to execute.
   This is frequently faster than (ITC), but DOES> words are not quite as
   easy as with ITC.
3) Token Threaded Code (TTC) - Compile an index into a jump table of pointers
   to the code to execute.  This has the potential for being very compact,
   and is also very easy to dynamically relocate.  Usually a little slower
   than either ITC or DTC, but not by much.
4) JSR Threaded Code (JTC) - compile a JSR instruction to the code to execute.
   May be somewhat faster than 1,2, or 3, but see discussion below.
5) Native Code (NC) - attempt to compile machine code sequences for Forth
   words.  A good compromise is to compile the sequences for short CODE words
   in-line, and to use JSR threading for references to longer words.  This
   is the way the Princeton VAX Forth works.  This is the fastest scheme of
   all, but depending on the processor, it may take up a lot of space.
   In the case of the VAX, there is hardly any space penalty at all!
   The 68000 has only a moderate space penalty; for most 8-bit micros
   (with the possible exception of the 6809), the space penalty is severe.

The only way to decide which scheme is faster for a particular processor
it to write down the code to implement the inner interpreter for each
scheme, then count cycles.  You MUST include the DOCOLON and EXIT routines
as part of the inner interpreter in order to make a fair comparison.
Ditto for an JMP instructions used to get to NEXT, if applicable.
It is usually okay to neglect to time the run-time code for VARIABLE,
CONSTANT, and DOES>, unless that code is horribly long.

Dynamic word frequencies I have measured for an ITC forth:
(Program was the outer interpreter compiling Forth code)

Relative frequencies of execution:

CODE words: 90%
COLON definitions: 8%
Other (VARIABLE, CONSTANT, DOES>): 2%

What this means is that saving one cycle on the execution time of
CODE words is worth about 10 cycles saved on COLON definitions.

It turns out that for the 68000, DTC is faster than JTC.  The reason
is that DTC NEXT for the 68000 does  MOVE (IP)+,A0   JMP (A0)
exactly once per CODE word, whereas JTC does  JSR  ... RTS
which involves pushing and popping a long word on the stack.

The bottom line is that you have to do a lot of work to get the
right answer for an particular processor.

Another thing to consider is the ease of implementing desireable
utilities like a decompiler.  Some threading schemes are easier to
decompile than others.  I personally find a decompiler to be a very
valuable tool.  Other people get along quite well by having convenient
access to the source code.  Since I frequently use Forth for debugging
peripheral hardware, in which case I don't have any mass storage on line,
I really use the decompiler a lot.

Good Luck,
Mitch Bradley

Message-ID: <3077@utah-cs.UUCP>
Date: Tue, 16-Oct-84 12:58:39 EDT
Article-I.D.: utah-cs.3077
Posted: Tue Oct 16 12:58:39 1984
Date-Received: Wed, 17-Oct-84 09:56:33 EDT
References: <233@iham1.UUCP>, <1741@sun.uucp>
Organization: Univ of Utah CS Dept
Lines: 6
Xref: utah-cs net.lang.forth:147 net.micro.ti:42

Is there an implementation of FORTH for 8080/z80s or VAX that
uses the Token Threaded Code mentioned by Mitch Bradley?  From what
I read, this sounds equivalent to Lisp's function cell - is that
correct?  In Lisp, the ability to dynamically redefine functions
gives alot of power, especially for debugging.

Harold Carr    Arpa: CARR@UTAH-20   uucp: harpo!utah-cs!carr