Stack length problem

Enrique · 2008-09-24 14:58

I just finished writing an object and decided to estimate its stack size using the Stack Length object.
·
During development I gave the stack size a value of 100 figuring it should be more than enough. I ran the Stack Length as indicated in the instructions and it came back with a Stack Usage of 11. I gave the program’s stack 15 longs, just in case, and ran again the exerciser. This time I got a message stating that the Stack Usage is 31. Gave the stack 35, ran the exerciser but the Propeller froze.
·
Went back to a stack of 100 and got back the same result: Stack Usage 11. I repeated this tests several times and always got the same results. When I give the stack 200 longs I also get back a Stack Length of 11.
·
Can someone explain what’s going on?
·
·
Thanks,
·
Enrique

Mike Green · 2008-09-24 15:23

The Stack Length object fills the stack space with a known bit pattern, then watches how many of those 32-bit words are left as the program uses them for something else. It's not a very accurate technique because it doesn't tell you what the program might use under various circumstances, just what the program actually used in one circumstance. It's possible to do a worst case estimate of the amount of stack used by a program by looking at the compiled code and adding up all the local variables, the depth of calls, the amount of temporary storage used to evaluate statements.

rjo_ · 2008-09-24 18:50

Mike always answers questions like this... and I would like to hear from someone else.

I thought I understood the stack size problem... and I can certainly follow Mikes guidelines, but somehow I think I need to see a "stack for dummies" conversation[noparse]:)[/noparse]

Timmoore · 2008-09-24 19:13

I tend to develop using a larger number for the stack size. 200 longs is common, if I have a random problem/memory overwrite problem I increase it. Once done developing I use the stacksize from obex - which is slightly difference from the one on the forum posting - it uses a pseudorandom sequence in the stack. What I do do is look at the cog code and work out how to drive the code though all the major paths - I dont bother with every if but branchs that call different routines or a very different in code I make sure to try - then I set the stack size to the largest value + some extra (depends on how much testing/risk I feel but tends to be 20-50 longs).

BradC · 2008-09-25 04:39

rjo_ said...
Mike always answers questions like this... and I would like to hear from someone else.

Ok then.. from "someone else".

[noparse][[/noparse] Outrageous french accent ]
Listen very carefully, I shall say this only once..
[noparse][[/noparse]/ ]

Mike is absolutely spot on the money.

You _can_ estimate stack usage if you are careful.
Every method call requires 1 long for
a) the return parameter
b) each parameter
c) each local variable
+ the call itself (which is 4 longs)

Then, all your arithmetic evaluations require some stack depending on their complexity.
X1 := 1 + 2 + X3 + 4 would require 2 longs.
X1 := 1 * 4 / X3 +4 would require 4 longs.

It can be done.. it's not easy from the source, it's easier from a disassembly.

mmm.. that might be something fun to add to a compiler, a stack usage estimator.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Pull my finger!

Mike Green · 2008-09-25 05:00

BradC,
It looks simple for a single method. Once you get any kind of complexity in your program with methods calling other methods that maybe call off to a method in another object, then a couple of calls there before anything returns ... hopefully you get the picture. You can write a utility program that looks at the compiled Spin bytecodes for a program and does a worst case rough simulation of the program assuming that, if a call to another method appears somewhere in a method, that it will always be called at least once. The utility can make a worst case stack requirement estimate based on that call graph unless there's recursion. In that case, it can't tell because the stack requirement is data dependent (depends on the data processed by the program).

BradC · 2008-09-25 05:38

Mike Green said...
BradC,
It looks simple for a single method. Once you get any kind of complexity in your program with methods calling other methods that maybe call off to a method in another object, then a couple of calls there before anything returns ...

Oh, I agree completely, I was just pointing out that if you had an understanding as to how your algorithms worked you could do a rough tot up by hand.
It's not _easy_ but it's certainly doable.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Pull my finger!

Enrique · 2008-09-25 07:21

No one has addresses the basic problem of why do I get different results for the stack usage when I set the object’s stack to the suggested value plus a couple of additional longs.

You must keep in mind that in all cases I run the object through the same paces, so this difference cannot be attributed to the fact that the program is going through different paths in each run. It should also be stated that the method that runs in the cog does not call other methods.

So, why am I getting these strange results?

Enrique

Timmoore · 2008-09-25 07:32

Are you displaying the stack size once and are you doing it on the cog you are measuring?
If yes and yes, then the display code is the thing that takes the largest stack and the 31/35 were because the display code overran the stack after they tried to measure it.
Also 4 long spare I found is too small unless you have no variation in the code path - no ifs, repeats, etc that are data dependent.
I suggest you post you object with the stacksize code in it so we can take a look, there could be other memory corruption issues that are not showing up in the running of your code but cause problems

Enrique · 2008-09-25 07:55

The answer to both questions is indeed yes and yes.

The code that runs in that cog is made up of many repeat blocks with if statements in them.

I cannot publish the code as it is for a commercial venture.

Timmoore does make an interesting point in that he states tht the Stack Length object itself may be corrupting the stack.

Mike Green · 2008-09-25 13:23

We can't answer your question in any more detail without looking at your code. The Stack Length object, once it initializes the stack array, doesn't modify it again. Timmoore was implying that there may be other problems with your code that result in memory corruption, not that Stack Length was causing it.

REPEAT blocks with IF statements in them certainly use a few levels for the temporaries needed. Just how many depend on the complexity of the statements and how they're nested.

Cluso99 · 2008-09-25 15:03

I am not sure if this is possible or not (not enough work with spin bytecodes). The bytecodes usage increase as the code/stack/variables move up in hub ram because the compiler optimises the storage of addresses into bytes (if the address is <100 the one byte is used, <10000 2 bytes, etc). This also affects the number of native pasm instructions executed. Since the stack is 32 bits, I would not have thought this would have any bearing, but maybe Brad could answer this.

Certainly, just running the code under test does not always (I should more often than not) exercise code fully and therefore the stack use may not be fully used. There is probably no real way to absolutely to know what the stack usage will really be, so whatever you find, make sure you add plenty more unless you are short of space in hub. The results of stack overflow cause all sorts of funny things and are very hard to find - so if something happens, increase your stack to some enormous number first.

I published a debugger (spin and pasm) which will display the stack space used per spin instruction. Use the mode -2 version, not the mode -3 as the stack use cannot be calculated propery since this version interrupts the rom interpreter and by that time the original stack start pointer has been destroyed. (Look in the last few days threads).

hippy · 2008-09-25 15:06

On corruption which could be revealed when stack space is reduced you could overcoming that by balancing what's lost with another array -

VAR
long stack[noparse][[/noparse] 100 ]

becomes

VAR
long stack[noparse][[/noparse] 50 ]
long dummy[noparse][[/noparse] 50 ]

and seeing how that affects what the Stack length object returns.

It could be there is some flaw or limitation in that object or the way you are using it causes the problem, or any number of things. Without some source code to demonstrate the problem there's not a lot anyone else can really do but make educated guesses.

You can write your own equivalent of the Stack Length object and see how that compares. It's as simple as seeding the stack array with some unlikely to be put on stack constant and then checking how much of the stack remains seeded during / after execution. You can also check that a long variable / array after stack isn't being corrupted by stack overflow ...

PUB Main | i
  repeat i from 0 to STACK_SIZE-1
    stack[noparse][[/noparse] i ] := SEED_VALUE
  CogNew( Whatever, @stack )
  repeat
    i := STACK_SIZE-1
    repeat while stack[noparse][[/noparse] i ] == SEED_VALUE
      i--
    ReportStackUsedAs( i )

Post Edited (hippy) : 9/25/2008 3:11:54 PM GMT

hippy · 2008-09-25 15:25

@ cluso99 : I don't think the Spin interpreter itself pushes anything to the stack beyond what a user program's bytecode does, so that should no't be an issue. The only exception may be CogNew/CogInit using that "run" code in ROM, and easy enough to factor in to the count.

It is possible to walk the bytecode and build a graph of method calls and determine the worse case stack depth used from any point in a program including inter-object calls. And that should work in all cases except for recursion.

It's something I've been planning to add to my PropList but I need to get a round tuit.

Timmoore · 2008-09-25 16:41

I had 2 comments, 1 the comment Mike picked up - there maybe other problems
The other is that the times that I display the stack length from the cog that I am getting the stack size of. Its always been the display code that used the most stack and if the display code wasn't in a loop I wouldn't see that and get teh stack size too small

Mike Green said...
We can't answer your question in any more detail without looking at your code. The Stack Length object, once it initializes the stack array, doesn't modify it again. Timmoore was implying that there may be other problems with your code that result in memory corruption, not that Stack Length was causing it.

REPEAT blocks with IF statements in them certainly use a few levels for the temporaries needed. Just how many depend on the complexity of the statements and how they're nested.

Enrique · 2008-09-25 17:07

Sorry folks,

********** MY FAULT *********

(Can you hear how I’m banging my head against the wall?)

As always the, the tougher the problem the more stupid the cause.

I went again through the code and realized that when I changed the stack size to the suggested value I didn’t change the second parameter, Longs, in the “Stack Length” Init method. After correcting this I’m getting consistent results.

How could I make such a stupid mistake.

Thank you all,

Enrique

Enrique · 2008-09-25 17:23

How much do you usually add to the value returned by the Stack Length?

In my case I’m getting a usage of 11, how much should I add to it?

Enrique

hippy · 2008-09-25 17:39

How much to add ... if that's a good estimate of what stack is used regardless of how the code may otherwise execute in different circumstances you'll need to add very little.

Cluso99 · 2008-09-26 02:40

@Hippy - I like your concept of the dummy following the stack - at the program end you could then determine the stack length used for that execution

I spent ages trying to find an obscure bug in my debugger only to find out I had exceeded the stack, which of course, I had defined early in my coding before I thought about all the other bits I could add.

hippy · 2008-09-26 03:19

Here's an idea, given that it's easy to identify which methods are launched in their own Cog and it is possible to determine the stack depth required automatically ... allow the user not to specify an @stack, calculate what is needed, automatically allocate that as the stack array behind the scenes and insert the address where it would have been in CogNew/CogInit. A compiler should have no problems in identifying if that optional parameter is there or not.

Anyone who wanted to specify a stack ( an @var or a function which returns an address ) could do so as they do now so entirely 100% backwards compatible, if through recursion it's not possible to auto-allocate a stack that can be reported as a compilation error.

How many "how big does the stack need to be ?" questions, how many stack too small problems and how much wasted memory from over-size stack guesses would that get rid of ? Nearly all of them I'd imagine.

Aren't we all sick of or hate trying to guess the size of stack required ? Don't we all ultimately just take a stab in the dark, make it 'large' or keep our fingers crossed ?

Stack length problem

Comments