FORTH Kernel Design -- Parameter Stack Size? 
Author Message
 FORTH Kernel Design -- Parameter Stack Size?

_
  When designing a Forth kernel, what is a good maximum size
  for the Parameter Stack under each of these conditions:
_
  1.   small program, simple control application
_
  2.   larger program with many nested calls
_
  3.   extensive program which employs interrupts and recursion
_

 -- Douglas Beattie Jr.

_



Mon, 15 Jun 1998 03:00:00 GMT  
 FORTH Kernel Design -- Parameter Stack Size?

Quote:
>_
>  When designing a Forth kernel, what is a good maximum size
>  for the Parameter Stack under each of these conditions:

Here are some "rules of thumb" we've used.  By the way, modern
terminoligy (i.e., ANS Forth) calls it the "data stack".

Quote:
>  1.   small program, simple control application

32-64 cells

Quote:
>  2.   larger program with many nested calls

256 cells (default in polyFORTH)

Quote:
>  3.   extensive program which employs interrupts and recursion

You really should measure or look at the specific requirement.  The #2
figure allows for interrupts, but recursion can create massive
requirements.  I've seen a graphics area fill routine programmed
recursively that could use several K of return stack, but not that much
data stack.

A good way to measure is to pre-initialize your stack area with some
recognizable pattern and run your program using worst-case scenarios,
then examine the memory.  

Elizabeth D. Rather
FORTH, Inc.                 Products and services for
111 N. Sepulveda Blvd.      professional Forth programmers
Manhattan Beach, CA  90266  since 1973.  See us at:
310-372-8493/fax 318-7130   http://www.earthlink.net/~forth/



Mon, 15 Jun 1998 03:00:00 GMT  
 FORTH Kernel Design -- Parameter Stack Size?


Quote:
>_
>  When designing a Forth kernel, what is a good maximum size
>  for the Parameter Stack under each of these conditions:
>_

For the MISC point of view I might offer some food for thought:

Quote:
>  1.   small program, simple control application

6 cells

Quote:
>  2.   larger program with many nested calls

16 cells

Quote:
>  3.   extensive program which employs interrupts and recursion

18 cells

This is based on current MISC hardware designs and programs
running native Forth on those machines.  Those numbers may seem
way too small but are based on MuP21, F21, i21, V21, etc.
One advantage to this type of minimal Forth is that it can
compile to run out of registers most of the time on most
hardware.

These numbers seem plenty deep to Chuck.  But he has also said he cannot
imagine a program larger than 64K.  (of course OK and OKAD
are still only about 7K of code after more than six years. :-)

Version 3 of the draft ANS standard included a minimal depth
of 32 on the data stack to validate ANS compliance as I recall.
However this requirement was removed.  So I guess you can just
declare an environmental dependency that you only support a 6 deep
data stack and still declare an ANS compliant system.

Jeff Fox



Mon, 15 Jun 1998 03:00:00 GMT  
 FORTH Kernel Design -- Parameter Stack Size?

: _
:   When designing a Forth kernel, what is a good maximum size
:   for the Parameter Stack under each of these conditions:
: _
:   1.   small program, simple control application
: _
:   2.   larger program with many nested calls
: _
:   3.   extensive program which employs interrupts and recursion
: _

I've sometimes wondered this myself.  A 8051-based system I just finished
needed about 50 bytes for both the data and return stacks.  This probably
falls between (1) and (2).  My 8051 Forth is subroutine threaded and the
stacks grow together.  Interrupts tend to eat up stack space and require
you to leave enough extra for whatever the interrupts might need.  
One way to find out how much stack space your application _really_ needs
is to fill the unused stack space with a known bit pattern, run the app,
and view the stack spaces to see how big the stacks got.

-- Brad
------------------------------------------------------------------

  "Never underestimate the power of the Forth." -- Darth Vader
------------------------------------------------------------------



Tue, 16 Jun 1998 03:00:00 GMT  
 FORTH Kernel Design -- Parameter Stack Size?

Quote:
>_
>  When designing a Forth kernel, what is a good maximum size
>  for the Parameter Stack under each of these conditions:
>_
>  1.   small program, simple control application
>_
>  2.   larger program with many nested calls
>_
>  3.   extensive program which employs interrupts and recursion

-<sig deleted>-

I'll takle them in reverse order:
3.  If you use recursion, your limiting resource is not parameter stack
space, but return stack space on most systems.  This is where the return
addresses are stored.  If this stack overflows, you might lose the FORTH
system to hyperspace.  If you are handling interrupts from within the
FORTH system, and you expect the interrupt handlers to make heavy use of
the stacks, you could include code to create custom stacks for each handler,
and each handler could switch to its own stack on entry.  Of course, this
isn't re-entrant, but if you have a fixed size stack, it may be the only
way to go.

2.  Again, if you have deeply nested and/or recursive functions, your limiting
factor is the return stack.  Try to find the most deeply nested function
called by your program, and use its level of nesting as a guide.  You will
probably want a 20%-100% safety margin, just to be on the safe side.

1.  A "simple" program could take up a tremendous amout of stack space, or
it could require no space at all.  It really depends on the application.
If your simple control program makes heavy use of variables, your stack can
probably be very small.

To compute the amount of stack space you may need, you could try this:
(be warned -- this could take a long time)
For each definition in your application that just uses primatives, compute the
"stack usage" quotient of each by:
1) start with 0.
2) going down the definition one word at a time:
        add one for every instance of DUP, OVER, PICK, any number, variable
name, or constant.
        subtract one for every DROP, two for every !, etc.
        If you come to an expression like "7 PICK", and your current quotient
is less than the argument, discard the current quotient in favor of the
argument.
The idea is to keep track of the number of cells that can be affected on the
stack by a word.  If your word has more than one flow of execution, follow
all paths, and the quotient you keep is the highest one computed for the word.
The quotient can be negative (for example, the quotient for 2DROP is -2)

After you have computed the quotient for each word in your application that
only uses words not defined in your application, you can start using these
results to compute the stack usage quotient for words that depend on words
defined in your program.

For example, if this were your application:

: FOO 2SWAP 2DROP ;
VARIABLE AVAR
1623 CONSTANT BCON
: BAR AVAR BCON FOO ;

the stack usage quotients would be:
FOO: 2 (4 for 2SWAP, -2 for 2DROP)
AVAR: 1
BCON: 1
BAR: 4 (1 each for AVAR and BCON, 2 for FOO)

Thus, you would need a four cell deep stack to successfully run BAR.
The biggest drawback to this method is that it is time-consuming and error
prone.  It could be automated (any volunteers?).



Tue, 16 Jun 1998 03:00:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Fwd(2): 3-stack Forth in the Linux kernel

2. stack size parameter?

3. Forth Core and Kernel Design

4. Forth Core and Kernel Design

5. Regex, stack overflow, and adjusting stack size

6. Stack overflow problem but increasing stack size does not solve the problem

7. Kernel::load wrap parameter

8. ANS Forth: Cell Size vs. Address Size

9. Kernel Calls, Best Design

10. Linux Kernel Design and Why Python is Rad

11. kernel forth

12. An Almost-Z180 FORTH Kernel

 

 
Powered by phpBB® Forum Software