Stack Space, My Attempt to Make Sense of it.
Duane Degn
Posts: 10,588
Note: Parallax has an appnote on the subject of stack space. I encourage interested parties to read it. I don't have a link right now since it appears the Parallax Semiconductor site is down right now. I personally like my technique better than described in the appnote.
Table of Contents
Post #2 Why this thread.
Post #3 My attempt.
Post #4 Other techniques
Post #5 & 6 Other stuff.
Sorry about reserving so many posts. I often find I wish I had a bit of room at the beginning of a thread to kind of sort out the contents of a threads to make any useful posts within the thread easier to find.
Table of Contents
Post #2 Why this thread.
Post #3 My attempt.
Post #4 Other techniques
Post #5 & 6 Other stuff.
Sorry about reserving so many posts. I often find I wish I had a bit of room at the beginning of a thread to kind of sort out the contents of a threads to make any useful posts within the thread easier to find.
Comments
I'm hoping to use this thread to show how to figure out how much stack space will be required when launching a cog to run some Spin code.
I'll use the first few posts to collect any demo programs I find and to use post #1 as a sort of "Table of Contents" to the rest of the thread.
I know there are several versions of code to find how much stack space is used but I recently wrote my own version of a method for finding stack space. Now that I think I can figure out how to do this on my own, I'll take a look at the other objects/methods to do it and share my opinions on the various techniques. As is often the case when I look around to see how others are doing something, I'll probably find much better ways of find stack space than the way I came up with (even there I didn't come up with it, I just implemented what I've read others write about the topic).
This thread is the result of a little back and forth I had with Dave James. I mentioned my recent experiments with finding stack requirements and he expressed a desire I post what I've learned.
Here's my method for finding stack space used.
PRI DebugLoop | measuredStack measuredStack := 0 repeat Pst.Home Pst.ClearEnd Pst.NewLine [COLOR=#ff0000] measuredStack := CheckStack(@ledStack, LED_STACK_SIZE, measuredStack)[/COLOR] Pst.Str(string(" The LED cog has so far use ")) Pst.Dec(measuredStack) Pst.Str(string(" of the ")) Pst.Dec(LED_STACK_SIZE) Pst.Str(string(" longs originally set aside for it.")) Pst.ClearEnd Pst.NewLine Pst.Str(string(" ledLoopCount = ")) Pst.Dec(ledLoopCount) Pst.ClearEnd Pst.NewLine Pst.ClearEnd Pst.ClearBelow [COLOR=#ff0000]PRI CheckStack(localPtr, localSize, previousSize)[/COLOR] '' Find the highest none zero long in the section '' of RAM "localSize" longs in size and starting '' at "localPtr". The return value will be at '' least the size of "previousSize" and will only '' be larger if a non-zero long is found at a higher '' memory location than in previous calls to '' the method. [COLOR=#ff0000] localSize--[/COLOR] [COLOR=#ff0000] previousSize--[/COLOR] [COLOR=#ff0000] repeat result from 0 to localSize[/COLOR] [COLOR=#ff0000] if long[localPtr][result][/COLOR] [COLOR=#ff0000] if result > previousSize[/COLOR] [COLOR=#ff0000] previousSize := result[/COLOR] [COLOR=#ff0000] result := ++previousSize[/COLOR]A cog to display a binary count on the QuickStart's LEDs (or other board with LEDs). The method which sets the LED states also calls some other objects.
You can watch the size of the stack used by the code change as more complex parts of the program are started.
Here's the output after the program has been running a while.
The number of longs used starts out at 8 and then jumps to 21. There also a jump to 32 longs before reaching the final value of 44 longs used by the stack.
I have some questions as comments within the code. I think it's interesting to see what sorts of changes affect the stack size.
So this is what I've come up with. As time permits, I'll investigate the other techniques for determining stack size.
I just remembered. Parallax has a AppNote on this topic. I'll make sure and add a link to the appnote from this thread. It's also a pretty good idea for me to read the appnote so I can pass along any glaring omissions to what I've posted (I should have done this before starting the thread).
Edit: I've reread the appnote. It had been a while since I had read it and I was able to completely understand it this time. I personally like my technique of finding the stack space better. I generally have a debug loop running in my code anyway so adding a line to display the results of the call to "CheckStack" is a pretty simple way to check on the stack space used.
One thing the appnote did make me wonder is if my checking to see if a long is a zero or not is such a good idea. I suppose it may be possible for the stack to have zeros in the last longs of the stack in use but I kind of doubt it. The local variables which are likely to remain zero are not found at the end of the stack in use. I'm not positive, but I don't think a stack can end in zeros. If anyone knows otherwise please let me know.
If one is worried about zeros in the stack causing an error in the stack length result, the code could be modified to fill the stack with some other number before calling the "CheckStack" method and the method itself could be changed to check for this "other number". My gut (which is frequently wrong) is telling me the used portion of the stack isn't going to consistently end with zeros.
I also like my technique better since it can be used while your program is being used in its normal way. Since it's not really in the way, you can fully "exercise" your code and the "CheckStack" method keep watching to see if the stack of the cog in question gets any bigger with use.
Edit(3/11/15): Warning, the code attached is an old version. There are likely better options available.
I plan to upload this program or an improved version to my GitHub account
If there isn't code similar to what is attached here on my on GitHub, send me a message and I'll make and check for any improved versions of the code.
Thanks.
-- you need at least 8 longs
-- you need a long for every parameter and local variable
-- you need 2 longs if the Spin cog makes a call, and a long for each parameter and local used by the called routine
* this stacks up, as it were, if that routine calls another
There are a couple tools out in the world the help one evaluate stack usage; one by Phil, another by Jeff Martin (Parallax). For complex systems they can be useful.
I just recently noticed the 8 long thing myself. Thanks for pointing out the other items which use space.
A good resource for seeing what sorts of things require how much stack space are the objects by Kye. He lists how many longs each method of an object require.
I've seen the tool by Jeff Martin (it's in the Propeller Library), I'm not surprised to learn Phil has a tool. I'll try to find it and add a link somewhere in the first few posts of the thread. I recall Cluso99 saying something about writing his own tool to check stack space. I'll try to find out if he has posted it or not.
I know stack space has been discussed many times on the forum. I just wasn't ready to really pay much attention to what was being said. Hopefully I can round up enough links on the subject to make it easier for other Propeller users to find the information they may need on the subject.
Is it safe to assume* the last long used in the stack won't be zero?
The method (double meaning) I posted checks for the highest non-zero memory location in the stack array. The array should start out initialized to zero (assuming it hasn't be used for other purposes) and I don't see a way for the last stack long to remain zero after it's in use.
I'm very interested to know if there are any examples of zero terminated stacks.
I noticed it doesn't matter if the local variables are left zeros or not, they don't appear to be located at the end of the stack.
*Don't give me the old "when you assume. . ." lecture. We all have to assume stuff all the time to function. I don't go running outside right now because I assume my roof isn't going to fall on me.
The more I think about this the more the zero thing bothers me. You're of course right about zero being a common value (probably the most common).
It would just really simplify the process of determining stack size if the array could be left in its initialized state. Though a "longfill" isn't hard to add.
I think I'll experiment a bit to see where zeros turn up in a stack initialized to some other value.
I filled the array with $AA55_55AA before launching the cog. I had the method check for this value to determine to determine stack size.
I also added a method to dump the stack array to the terminal window (I've attached the code I used). Below is an example of the output.
The final long of the used stack was always either $00000002 or $0000000A.
I'm curious to know how many different end of stack values there are.
I'm interested in hearing suggestions on ways to get different values for the last long of the stack.
So far, I'm still inclined to think the code posted in post #3 can be used to consistently find the amount of stack space a cog running Spin will require.
Edit(3/11/15): Warning, the code attached is an old version. There are likely better options available.
I plan to upload this program or an improved version to my GitHub account
If there isn't code similar to what is attached here on my on GitHub, send me a message and I'll make and check for any improved versions of the code.
The stack can end with zero.
I'll post the code to generate the above output in a while.
Darn. I would have made things simpler not to need to fill the array first.
Edit: I attached the code to generate the output displayed above. There's really not much different between this "d" version and the "c" version I posted earlier. I added some delays so I'd have a better chance of seeing the values of the array. I also added a couple of test methods in an attempt to find a combination of method calls that would produce a zero as the last long of the stack. I was successful in doing so. The last zero does not stay zero but the fact that it can be zero is enough of a reason to want to fill the stack with some non-zero value when checking the stack size.
Edit(3/11/15): Warning, the code attached is an old version. There are likely better options available.
I plan to upload this program or an improved version to my GitHub account
If there isn't code similar to what is attached here on my on GitHub, send me a message and I'll make and check for any improved versions of the code.
You're right about it not being a big deal to myself but a big part of my desire to keep it simple was to make it less intimidating to new users of the Propeller. So the instructions to use this method now require an additional step. "Add a longfill prior to launching cog." It's just not as nice and simple as I had hoped it would be.
I acknowledge my aversion to adding a longfill or prefilled array in not entirely rational.
Wouldn't you need to run the same test twice to be very sure? Once with one value and once with another. Maybe $AA5555AA for the first test and $BB6666BB for the second.
Sandy
That crossed my mind but after watching the stack numbers transition for a while, I'm pretty convinced the stack will always end with relatively low numbers. I'm pretty sure the last long holds data used by the Spin interpreter and not computational data.
I still hold out some hope that the final zero I saw will always be transitory. The final zero was transitory in the example I posted. I haven't found a combination of methods that will leave a terminating zero on the stack but I admit I haven't been looking very hard lately.
I'm pretty sure (not completely sure), the final long on the stack is not generated based on calculations within the program. I think it's used by the Spin interpreter for some sort of bookkeeping. It has been (my relatively limited) experience, the final long of the stack is not going to be some arbitrary random number but it will be one of a relatively limited pool of possible numbers.