From csn!magnus.acs.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!usc!nic-nac.CSU.net!charnel.ecst.csuchico.edu!psgrain!news.tek.com!news.bv.tek.com!wu.labs.tek.com!not-for-mail Tue Aug 02 15:59:24 1994
Path: csn!magnus.acs.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!usc!nic-nac.CSU.net!charnel.ecst.csuchico.edu!psgrain!news.tek.com!news.bv.tek.com!wu.labs.tek.com!not-for-mail
From: toma@wu.labs.tek.com (Tom Almy)
Newsgroups: comp.lang.forth
Subject: Re: locals
Date: 2 Aug 1994 10:36:55 -0700
Organization: Tektronix Laboratories, Tektronix, Inc., Beaverton, OR
Lines: 175
Message-ID: <31m07n$1qg@wu.labs.tek.com>
References: <wilbadenCtv3EL.D6B@netcom.com> <31j7pt$d5@wu.labs.tek.com> <wilbadenCtvsuG.Cot@netcom.com>
NNTP-Posting-Host: wu.labs.tek.com

In article <wilbadenCtvsuG.Cot@netcom.com> wilbaden@netcom.com (W. Baden) writes:
>Tom Almy (toma@wu.labs.tek.com) wrote:

>: Local definitions (of variables) don't work for recursive words or 
>: in some cases re-entrant words. Local variables have the advantage that
>: each invocation of the word create a new set of variables.

>True.  Local variables are for programs where the programmer has too much
>trouble managing the stack or factoring his definition.

>Forth programs that you think need local variables are programs that you
>shouldn't be writing in Forth.
>
>Forth with local variables is just Small C with Postfix Operators.

I did some benchmarking of the Tower of Hanoi puzzle using local variables.
Being recursive, local definitions won't work, but you are probably right
about programs which seem to need local variables are not suitable for Forth.

The local variable implementation is basically the best I can do, but it cannot
beat traditional Forth coding in either generated code size or in execution
time. In addition, C came out on top, for reasons that are obvious when
examining the code. I'd say that Forth with local variables is *worse* than
Small C with Postfix Operators, at least in this problem!

The compilers tested were ForthCMP 2.1S, now being tested, and Borland
C++ 3.1. The system has a 80486DX2/66 processor. The move printing routine
was put into a separate function so that it could be dummied out for 
performance checking. The main function calls the recursive function 1000
times, with a "ring count" of 10.

The first function represents traditional Forth coding, using stack 
manipulation only so the parameter stack doesn't grow in size. No functions
consume their arguments.

: HANOI1 ( SOURCE DEST EXTRA n -- SOURCE DEST EXTRA n )
    DUP IF
       >R  SWAP R@ 1-  RECURSE  \ SOURCE EXTRA DEST n-1
       DROP 
       SWAP R@  MOVERING1       \ SOURCE DEST EXTRA n
       DROP
       -ROT SWAP R@ 1- RECURSE  \ EXTRA DEST SOURCE n-1
       DROP
       -ROT SWAP R>
    THEN
;

This function took 83 bytes, and executed in 2.39 seconds. It looks ugly
because of the stack manipulation.

The second version pushes new arguments on the stack. All functions consume
their arguments. This design is capable of being tail-recursive.

: HANOI2 ( SOURCE DEST EXTRA n -- )
    DUP IF
       3 PICK 2 PICK 4 PICK 3 PICK 1- RECURSE  \ SOURCE EXTRA DEST n-1
       3 PICK 3 PICK 2 PICK  MOVERING2         \ SOURCE DEST n
       >R -ROT SWAP R> 1- RECURSE              \ EXTRA DEST SOURCE n-1
    THEN
    2DROP 2DROP
;


The use of PICK makes the function look cleaner, but it still is not
easily understood without the comments. It was 98 bytes long (102 with tail
recursion enabled), and ran in 2.25 seconds.

The third version uses local variables:

: HANOI3 ( SOURCE DEST EXTRA n -- ) LOCALS| N EXTRA DEST SOURCE |
    N IF 
      SOURCE EXTRA DEST N 1- RECURSE
      SOURCE DEST N MOVERING2
      EXTRA DEST SOURCE N 1- RECURSE
    THEN
;

Very clean! Also very slow. 101 bytes, 111 with tail recursion, and takes 2.80
seconds to run. Note that tail recursion does not help performance in either
of these cases.

Now lets look at the C version:

void hanoi(char src, char dst, char extra, int n) {
	if (n) {
		hanoi(src, extra, dst, n-1);
		movering(src, dst, n);
		hanoi(extra, dst, src, n-1);
	}
}

Very close in appearance to HANOI3. However the C version takes just 73
bytes and executes in 2.2 seconds.


The reason that C outperforms ForthCMP is the linkage conventions.
These become particularly horrendous for the local variable version.
The 80x86 only efficiently implements one stack, which is also used
for call/return. Standard procedural languages build a stack frame
upon entry, using the BP registers as the frame pointer, and
referencing locations relative to BP for local variables or function
parameters, depending on sign of the offset. So you get the following
code at function entry:

	push	bp	; save old stack frame pointer
	mov	bp,sp	; new stack frame
	sub	sp,n	; space for local variables

and at exit:

	add	sp,n	; get rid of local variables
	pop	bp	; restore old stack frame
	ret

Forth, however, needs *two* stacks. Either the parameter stack or the
return stack can be shared with the processor stack. I decided to
share the parameter stack with the processor stack trading off
potentially inferior linkage for better parameter stack access. The
return stack uses the BP register, and is not very efficient.

Normal code at function entry is:
	pop	ax	; get return address
	dec	bp	; (sub bp,2 would be faster with recent processors)
	dec	bp
	mov	[bp],ax	; push return address on return stack

and at exit:
	mov	ax,[bp]	; pop return address
	inc	bp
	inc	bp
	jmp	ax	; return to calling function

To speed things up, if the number of arguments and result values are
known and are both constant and less than or equal to two, registers
are used for the values, and the return address is kept on the
parameter stack. This eliminates all function entry code and all exit
code but the return. This is very efficient! As an intermediate
position, functions that have only primitive operations can save the
return address in one of the registers, which is almost as efficient.

However in the Hanoi puzzle case, the number of arguments are four,
requiring the worst case linkage.

For HANOI3, the local variables are held on the return stack. This
means the values must be popped off the parameter stack and pushed on
the return stack:
	pop	ax
	dec	bp
	dec	bp
	mov	[bp], ax

These 16 instructions (4 per argument) are not needed in C since
parameters can be accessed in the same manner as local variables.

ForthCMP accesses the local variables in the same manner as C (BP
relative instructions). PICK, used in HANOI2, is somewhat more
involved. Only the high end processors have SP relative memory
referencing, and then it requires awkwardly long instructions. The
implementation of n PICK is basically:
	mov	di, sp
	mov	ax, n*2[di]
taking an extra instruction over using a local variable.

Anyway, the bottom line doesn't look good for local variables, from
the implementation point of view. There are a few optimizations I can
put in (replacing the multiple INCs and DECs with single ADDs) which
might make it a bit faster. I'll have to try and see. There is no
question in my mind that they *can* enhance readability.


-- 
Tom Almy
tom.almy@tek.com
Standard Disclaimers Apply


