Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #45012 > unrolled thread

Stack space size

Back to article view | Back to comp.lang.forth

Contents

  Stack space size Brad Eckert <hwfwguy@gmail.com> - 2016-01-21 21:50 -0800
    Re: Stack space size hughaguilar96@gmail.com - 2016-01-21 22:00 -0800
    Re: Stack space size Raimond Dragomir <raimond.dragomir@gmail.com> - 2016-01-21 22:30 -0800
      Small strings as ints Ron Aaron <rambamist@gmail.com> - 2016-01-22 08:41 +0200
        Re: Small strings as ints Raimond Dragomir <raimond.dragomir@gmail.com> - 2016-01-21 23:41 -0800
          Re: Small strings as ints Ron Aaron <rambamist@gmail.com> - 2016-01-22 09:50 +0200
        Re: Small strings as ints Ron Aaron <rambamist@gmail.com> - 2016-01-24 07:15 +0200
    Re: Stack space size anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-22 15:31 +0000
    Re: Stack space size Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-22 17:10 -0500
      Re: Stack space size Coos Haak <chforth@hccnet.nl> - 2016-01-22 23:21 +0100
        Re: Stack space size "Elizabeth D. Rather" <erather@forth.com> - 2016-01-22 13:28 -1000
          Re: Stack space size hughaguilar96@gmail.com - 2016-01-25 21:23 -0800
      Re: Stack space size "HAA" <someone@microsoft.com> - 2016-01-24 00:08 +1100
      Re: Stack space size anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-26 16:23 +0000

#45012 — Stack space size

Hi All,

What's the typical stack space you find you need in embedded application and what things cause that to grow. As for me, 64 cells per task (32 cells each for data and return) is fine. I just fill them with $55 at init and dump at run time to see how tight things are.

I suppose CATCH is something that eats stack space, but I tend to not use it much in embedded code. Maybe decent separation of tasks tends to limit the weirdness that CATCH was invented to resolve.

Metrics in Phil Koopman's Stack Machines book indicate that 32-cell data and return stacks handle whatever you throw at them, in general. Of course, modern OS calls change the game but in OS-less embedded land I think that still prevails. Opinions?

-Brad

[toc] | [next] | [standalone]

#45013

On Thursday, January 21, 2016 at 10:50:44 PM UTC-7, Brad Eckert wrote:
> Hi All,
> 
> What's the typical stack space you find you need in embedded application and what things cause that to grow. As for me, 64 cells per task (32 cells each for data and return) is fine. I just fill them with $55 at init and dump at run time to see how tight things are.
> 
> I suppose CATCH is something that eats stack space, but I tend to not use it much in embedded code. Maybe decent separation of tasks tends to limit the weirdness that CATCH was invented to resolve.
> 
> Metrics in Phil Koopman's Stack Machines book indicate that 32-cell data and return stacks handle whatever you throw at them, in general. Of course, modern OS calls change the game but in OS-less embedded land I think that still prevails. Opinions?
> 
> -Brad

32 for data and return should be fine.

[toc] | [prev] | [next] | [standalone]

#45015

vineri, 22 ianuarie 2016, 07:50:44 UTC+2, Brad Eckert a scris:
> Hi All,
> 
> What's the typical stack space you find you need in embedded application and what things cause that to grow. As for me, 64 cells per task (32 cells each for data and return) is fine. I just fill them with $55 at init and dump at run time to see how tight things are.
> 
> I suppose CATCH is something that eats stack space, but I tend to not use it much in embedded code. Maybe decent separation of tasks tends to limit the weirdness that CATCH was invented to resolve.
> 
> Metrics in Phil Koopman's Stack Machines book indicate that 32-cell data and return stacks handle whatever you throw at them, in general. Of course, modern OS calls change the game but in OS-less embedded land I think that still prevails. Opinions?
> 
> -Brad

I also use 64 cells for my stacks (mines are facing each other so I wouldn't
call them 32+32) usually.
That's only the forth stacks, and it's a very crude estimation.
My task total stacks are at least 128 cells for the cortex-m CPUs
because of the interrupt handling. I usually have multiple levels,
and on cortex-m any level eats at least 8 cells... (8 registers pushed).

I fill my stack space with 0xdeadc0de :)

Probably I'm not a typical forther, my stacks grows especially because
of local variables usage. I even use small strings (let's say up to 32 chars)
as local variables.

[toc] | [prev] | [next] | [standalone]

#45016 — Small strings as ints

On 22/01/2016 08:30, Raimond Dragomir wrote:

> Probably I'm not a typical forther, my stacks grows especially because
> of local variables usage. I even use small strings (let's say up to 32 chars)
> as local variables.

Hey!  Sticking a small string inside an 'int'... that sounds like a
possibly interesting optimization!  Only problem is it would add some
overhead to decide whether the string was allocated on the heap or
sitting inside an int...

Has anyone tried this?

[toc] | [prev] | [next] | [standalone]

#45018 — Re: Small strings as ints

vineri, 22 ianuarie 2016, 08:41:14 UTC+2, Ron Aaron a scris:
> On 22/01/2016 08:30, Raimond Dragomir wrote:
> 
> > Probably I'm not a typical forther, my stacks grows especially because
> > of local variables usage. I even use small strings (let's say up to 32 chars)
> > as local variables.
> 
> Hey!  Sticking a small string inside an 'int'... that sounds like a
> possibly interesting optimization!  Only problem is it would add some
> overhead to decide whether the string was allocated on the heap or
> sitting inside an int...
> 
> Has anyone tried this?

As long as I can get the local variable address, there is no overhead and
no optimization needed. And the stack strings are very nice, completely
reentrant and no heap/dynamic allocation hassle.

[toc] | [prev] | [next] | [standalone]

#45019 — Re: Small strings as ints

On 22/01/2016 09:41, Raimond Dragomir wrote:

> As long as I can get the local variable address, there is no overhead and
> no optimization needed. And the stack strings are very nice, completely
> reentrant and no heap/dynamic allocation hassle.

Right, that's why I'm thinking it could be very good (in 8th) for small
items.  Just "allocate" in an int instead of in the heap.  It would
probably make things faster as well because the item being accessed
would more likely be in the CPU cache...

Still, needs to be tested and measured before getting excited.

[toc] | [prev] | [next] | [standalone]

#45054 — Re: Small strings as ints

On 22/01/2016 08:41, Ron Aaron wrote:
> 
> 
> On 22/01/2016 08:30, Raimond Dragomir wrote:
> 
>> Probably I'm not a typical forther, my stacks grows especially because
>> of local variables usage. I even use small strings (let's say up to 32 chars)
>> as local variables.
> 
> Hey!  Sticking a small string inside an 'int'... that sounds like a
> possibly interesting optimization!  Only problem is it would add some
> overhead to decide whether the string was allocated on the heap or
> sitting inside an int...

Well, I didn't stick the string in an int, but just used a char array in
the string structure, for small strings.  I was curious if the benefit
of not allocating small strings would outweigh the cost of managing it all.

Turns out to be a big win!

On OS X, one of my string benchmarks was about 50% faster, and on Linux
it was about 25% faster.  Definitely worthwhile for 8th.

The downside is that the amount of memory statically allocated is
larger, but "you can't win 'em all"...

[toc] | [prev] | [next] | [standalone]

#45029

Brad Eckert <hwfwguy@gmail.com> writes:
>Metrics in Phil Koopman's Stack Machines book indicate that 32-cell data an=
>d return stacks handle whatever you throw at them, in general.

The data for my first stack caching paper
<https://www.complang.tuwien.ac.at/misc/stack-caching-data/> show that
for these non-embedded programs 32 registers are almost, but not quite
enough.

compile: 32 cells: 6 loads, 3 stores, 93 moves, 9 updates
cross:   31 cells: 3 loads, 0 stores, 0 moves, 3 updates
gray:    32 cells: 42 loads, 39 stores, 1187 moves, 81 updates
prims2x: 32 cells: 12 loads, 9 stores, 278 moves, 21 updates

These are data for stack caches: if we have an n-cell stack cache, how
many loads from main memory, stores to main memory, moves between
stack cache elements, and stack pointer updates remain.

I.e., for cross 31 registers are sufficient, for compile 32 are almost
sufficient, prims2x probably needs a few more, and gray probably yet
more (or maybe they all need just a few more, and gray yo-yos much
more than the others).

- 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 2015: http://www.rigwit.co.uk/EuroForth2015/

[toc] | [prev] | [next] | [standalone]

#45032

On Thu, 21 Jan 2016 21:50:40 -0800 (PST)
Brad Eckert <hwfwguy@gmail.com> wrote:

> What's the typical stack space you find you need in embedded
> application

...

> and what things cause that to grow.

From this group, my understanding is that user defined words
shouldn't leave items on the data or return stacks.  This means
a net stack change of zero for both stacks.  So, that would
mean that system words are the primary source of stack bloat
or growth.  Most usage of stack "producers" is immediately
followed by stack "consumers".  You're probably interested in
functionality which is "split" or wraps around other words,
e.g., >R ... R> or DO ... LOOP or BEGIN ... AGAIN, etc.
I.e., look for control flow and "do" and "undo" operations.
The stack image for the words in your dictionary could be
a useful starting point.  Which words leave stuff on the
stacks?

> As for me, 64 cells
> per task (32 cells each for data and return) is fine. I just fill
> them with $55 at init and dump at run time to see how tight things
> are.

When you run the standard Forth test programs, like sieve, bubble,
matrix, fib, quick sort, 8-queens, life, hanoi, etc, how much stack
pressure do you see?  Test apps should provide a good baseline
reference as to whether you're about to overflow the stack.

> Metrics in Phil Koopman's Stack Machines book indicate that 32-cell
> data and return stacks handle whatever you throw at them, in general.

Section 6.4.1.  See also 6.5.3.1., which indicates slightly larger.

Anton Ertl has a paper titled "Ways to Reduce the Stack Depth"
which reviews various techniques.  The paper basically concludes
that locals are the best solution, but that other combinations
of other solutions work as well.  I've only skimmed one section
and the summary, so you'll need to read it yourself.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#45033

Op Fri, 22 Jan 2016 17:10:39 -0500 schreef Rod Pemberton:

> On Thu, 21 Jan 2016 21:50:40 -0800 (PST)
> Brad Eckert <hwfwguy@gmail.com> wrote:
> 
>> What's the typical stack space you find you need in embedded
>> application
> 
> ...
> 
>> and what things cause that to grow.
> 
> From this group, my understanding is that user defined words
> shouldn't leave items on the data or return stacks.
I would agree if you wrote that the return stack must be balenced
within a definition. But I've never read or heard that that
one may not change the depth of stack in user defined words.
System defined words like ! DUP PARSE do it all the time.
Perhaps it is meant that a whole program is expected to have
balanced stacks. But that would be work of a bad programmer.

groet Coos

[toc] | [prev] | [next] | [standalone]

#45035

On 1/22/16 12:21 PM, Coos Haak wrote:
> Op Fri, 22 Jan 2016 17:10:39 -0500 schreef Rod Pemberton:
>
>> On Thu, 21 Jan 2016 21:50:40 -0800 (PST)
>> Brad Eckert <hwfwguy@gmail.com> wrote:
>>
>>> What's the typical stack space you find you need in embedded
>>> application
>>
>> ...
>>
>>> and what things cause that to grow.
>>
>>  From this group, my understanding is that user defined words
>> shouldn't leave items on the data or return stacks.
> I would agree if you wrote that the return stack must be balenced
> within a definition. But I've never read or heard that that
> one may not change the depth of stack in user defined words.
> System defined words like ! DUP PARSE do it all the time.
> Perhaps it is meant that a whole program is expected to have
> balanced stacks. But that would be work of a bad programmer.

Words should expect their arguments on the data stack, remove them, and 
leave results there. There's no requirement that stacks be balanced from 
one word to the next, that would defeat its purpose. But it is important 
for words to remove their input parameters unless it's an explicit 
requirement in a sequence of words that something be carried along. 
Normally this just happens: + takes two integers and adds them, leaving 
the sum, for instance. Every once in a while I see newbies start a 
definition with a bunch of DUPs or 2DUPs and then leave stray stuff, and 
when I point this out they say, "Oh, I just thought I'd make some extra 
copies in case I needed one." Wrong. *Use* your input parameters and 
leave explicit results, if any.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#45080

On Friday, January 22, 2016 at 4:28:26 PM UTC-7, Elizabeth D. Rather wrote:
> > Op Fri, 22 Jan 2016 17:10:39 -0500 schreef Rod Pemberton:
> >>  From this group, my understanding is that user defined words
> >> shouldn't leave items on the data or return stacks.
 
> Words should expect their arguments on the data stack, remove them, and 
> leave results there. There's no requirement that stacks be balanced from 
> one word to the next, that would defeat its purpose. But it is important 
> for words to remove their input parameters unless it's an explicit 
> requirement in a sequence of words that something be carried along. 
> Normally this just happens: + takes two integers and adds them, leaving 
> the sum, for instance. Every once in a while I see newbies start a 
> definition with a bunch of DUPs or 2DUPs and then leave stray stuff, and 
> when I point this out they say, "Oh, I just thought I'd make some extra 
> copies in case I needed one." Wrong. *Use* your input parameters and 
> leave explicit results, if any.

Elizabeth Rather (who claims to be the "leading expert" on Forth) is teaching Forth to Rod Pemberton (who claims that C is the "god language")  --- this is exciting! --- if ANS-Forth is considered to be Special-Ed, then Forth Inc. may qualify for government grants.

Note for Elizabeth Rather: shut up, stupid!

BTW:, in this thread:
https://groups.google.com/forum/#!searchin/comp.lang.forth/elizabeth$20exciting%7Csort:date/comp.lang.forth/UtGNNAuCU_o/2oNwlthVQREJ
I responded to Mentifex (Arthur Murray) and Elizabeth Rather interjected, resulting in a discussion of the Forth Inc. Mission Statement:

On Friday, October 22, 2010 at 2:20:34 PM UTC-7, Hugh Aguilar wrote:
> What I said was:
> 
> On Oct 21, 5:22 pm, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> > I just don't understand what you are doing. What does "think"
> > mean? I still don't have any inkling of what the purpose of the
> > program is.
> 
> And what Elizabeth Rather says is:
> 
> On Oct 21, 6:12 pm, Elizabeth D Rather <erat...@forth.com> wrote:
> > This is exciting.  Hugh and Arthur could make a great team.
> 
> How are we going to make a "great team" if I don't have any inkling of
> what he is doing?
> 
> I think Elizabeth Rather hates Arthur, and she hates me, so she is
> hoping to lump us together somehow --- kill two birds with one stone.
> 
> The reason why E.R. hates Arthur, is because Arthur is an unabashed
> hobbyist. He describes programming in Forth as "great fun" (I have to
> agree with him on that). He clearly states that he expects people to
> be interested in his MindForth because: "People are interested in
> finding out how the human mind works." Such an educational goal pretty
> much precludes the development of a product that performs some useful
> function and which the general public would be willing to pay money
> for. This hobbyist emphasis is in complete contradiction to the
> (ahem!) *professional* image that Forth Inc. is striving for. The
> irony here is that Forth Inc. has been in business for over 30 years
> and they still don't have a product to sell. Their "product" is
> SwiftForth/SwiftX, but that is only a development system that gives
> the customer the *potential* to someday develop a product. Forth Inc.
> is representing computer programming as a service industry. Forth Inc.
> is willing to help its customers develop a product, but they want to
> get paid up front, or at least get a legal obligation for payment,
> before they begin the long and arduous (and expensive!) task of
> developing a product (which may or may not come to fruition). It is
> all just "blue sky" and "unlimited potential" --- but Forth Inc.
> doesn't have (in the present tense) an actual product that does
> something useful and which somebody somewhere would be willing to pay
> money for.
> 
> The reason why E.R. hates me, is because I wrote my novice package
> (for free!) which provides code that can be used for writing
> applications --- which is in direct competition with SwiftForth which
> is supposedly useful for writing applications. My novice package
> provides a lot of useful building blocks (records, arrays, lists,
> associative arrays, etc.), which are painfully absent in SwiftForth,
> and which are present in pretty much *every* other development system
> in the programming world. When you pay $500 for SwiftForth, you get a
> very bare-bones system. You may get unlimited potential (woo hoo!),
> but you still have quite a lot work ahead of you. Before you can even
> begin writing your application, you have to spend time implementing
> basic data-structures and basic support code. SwiftForth really
> doesn't put you any closer to developing a product than you were
> before, but it does lighten your wallet by $500. A much better use for
> that $500 would be to pay somebody a week's salary to implement
> whatever data-structure your application needs. E.R. is hoping that
> you'll pay Forth Inc. yet another $500 (beyond the $500 that
> SwiftForth cost) as a consulting fee, so the geniuses at Forth Inc.
> can implement your linked lists or associative arrays or what-not for
> you. The problem, of course, is that if they knew how to implement
> data structures such as these, they would have done so a long time ago
> --- the fact that SwiftForth lacks these basic features implies that
> nobody at Forth Inc. knows how to implement them. Giving Forth Inc. an
> extra $500 is not going to improve their knowledge of basic
> programming. For the most part, if you want basic features such as
> these, you have to either write them yourself or download my novice
> package.
> 
> This is Forth Inc.'s mission statement (you will notice that there is
> no mention of them having any product to sell, or having any knowledge
> of any particular application-domain):
> 
> PUBLIC MISSION
> 
> * To provide innovative, cost-efficient and resource-mindful solutions
> to our consulting clients.
> 
> * To accept challenging assignments to which we can apply our special
> expertise in intelligent system design and our intimate understanding
> of hardware-software interfaces.
> 
> * To offer powerful alternatives to the programming community, the
> same interactive development systems we create for in-house use.
> 
> To summarize: "Give us a suitcase full of cash today, and maybe we
> will give you something substantial at some indeterminate date in the
> future --- unless we don't."

[toc] | [prev] | [next] | [standalone]

#45043

Rod Pemberton wrote:
> On Thu, 21 Jan 2016 21:50:40 -0800 (PST)
> Brad Eckert <hwfwguy@gmail.com> wrote:
>
> > What's the typical stack space you find you need in embedded
> > application
>
> ...
>
> > and what things cause that to grow.
>
> From this group, my understanding is that user defined words
> shouldn't leave items on the data or return stacks.  This means
> a net stack change of zero for both stacks.  So, that would
> mean that system words are the primary source of stack bloat
> or growth.  Most usage of stack "producers" is immediately
> followed by stack "consumers".  You're probably interested in
> functionality which is "split" or wraps around other words,
> e.g., >R ... R> or DO ... LOOP or BEGIN ... AGAIN, etc.
> I.e., look for control flow and "do" and "undo" operations.
> The stack image for the words in your dictionary could be
> a useful starting point.  Which words leave stuff on the
> stacks?
>
> > As for me, 64 cells
> > per task (32 cells each for data and return) is fine. I just fill
> > them with $55 at init and dump at run time to see how tight things
> > are.
>
> When you run the standard Forth test programs, like sieve, bubble,
> matrix, fib, quick sort, 8-queens, life, hanoi, etc, how much stack
> pressure do you see?  Test apps should provide a good baseline
> reference as to whether you're about to overflow the stack.
>
> > Metrics in Phil Koopman's Stack Machines book indicate that 32-cell
> > data and return stacks handle whatever you throw at them, in general.
>
> Section 6.4.1.  See also 6.5.3.1., which indicates slightly larger.
>
> Anton Ertl has a paper titled "Ways to Reduce the Stack Depth"
> which reviews various techniques.  The paper basically concludes
> that locals are the best solution, but that other combinations
> of other solutions work as well.  I've only skimmed one section
> and the summary, so you'll need to read it yourself.
>
>
> Rod Pemberton

Locals chew up return stack and unlike data stack the space won't
be released until the definition ends.  Nest several definitions each
containing locals and work out the return stack requirements.  Add
to this the data stack that locals will use anyway.  Locals provide
convenience - not memory efficiency.

[toc] | [prev] | [next] | [standalone]

#45090

Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> writes:
>Anton Ertl has a paper titled "Ways to Reduce the Stack Depth"
>which reviews various techniques.

This paper is about managing the data stack within words; some of the
techniques discussed there may increase the return stack usage.

- 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 2015: http://www.rigwit.co.uk/EuroForth2015/

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web