BxDism question Re: stack

Started by arhodes19044 August 7, 2005
I used BxDism, and confirmed that I was running out of stack space in
a major way. I deleted wasted space/variables and fised it up and
have just enough by 5 bytes, according to BxDism. This is tight
enough that I am worried. None of my functions are very odd, so all
the required stack should be pretty obvious in static analysis. With
only 5 to spare, I will soon find out.

One question, the total stack required that BxDism lists, Does this
equal the worse case of the stack required for the entire function
tree (Functions called by functions which are called by yet another
function, and so on)? I would presume it is. I have a few stack
hungry functions. Of course, they are string processing functions. -Tony


--- In basicx@basi..., "arhodes19044" <spamiam@c...> wrote:
> One question, the total stack required that BxDism lists, Does this
> equal the worse case of the stack required for the entire function
> tree (Functions called by functions which are called by yet another
> function, and so on)? I would presume it is.

I believe that the estimate is "worst case".

One thing that you can do to reduce the stack requirement is
to "flatten out" the call tree. Normally, we try to factor out common
code into subroutines/functions in order to simplify the code and
reduce the need to maintain multiple identical sequences of code.
However, when faced with limited resources you sometimes need to
compromise on this ideal.

A call to a subroutine requires 9 bytes of stack space plus the space
for each of the parameters, if any. Placing the code for the called
subroutine in-line eliminates all of that overhead.

You may also be able to reduce the RAM requirement for your
application by reducing the default maximum string length (use the
Environment item on the Options menu). If you have a few cases where
you need longer strings you can used the BoundedString type for those.

Don

>
>
> -Tony


I succeeded in reducing my stack requirement from 223 to 140 bytes
by eliminating unused variables that were hanging on from various
iterations of the code.

I then used a BoundedString for a sub-string that is deciphered off
the main GPS data string. In that case I could make it a length of
3. I also got rid of all the "buffer" string declarations in each
function/subroutine, and used a single global buffer string. Of
course I can't use it in all cases, but essentially the program runs
top-down, so each use of the buffer will never interfere with some
other use.

Interestingly, the NetMedia BasicX documents are incorrect regarding
the declaration of a BoundedString. It needs to be declared as a
NEW BoundedString. The manual does not show it that way.

In the BxDism output regarding stack usage, there are double
asterisks next to the "stack usage", and the explanation is: "Lines
with ** indicate routines with string instructions that may affect
the stack size at runtime". The Basicx documents indicate that the
maximum length of a string is allocated when the string is declared,
so does the stack usage number indicate stack usage NOT INCLUDING
string usage, or does it include some/all string declarations?

-Tony --- In basicx@basi..., "Don Kinzer" <dkinzer@e...> wrote:
> --- In basicx@basi..., "arhodes19044" <spamiam@c...> wrote:
> > One question, the total stack required that BxDism lists, Does
this
> > equal the worse case of the stack required for the entire
function
> > tree (Functions called by functions which are called by yet
another
> > function, and so on)? I would presume it is.
>
> I believe that the estimate is "worst case".
>
> One thing that you can do to reduce the stack requirement is
> to "flatten out" the call tree. Normally, we try to factor out
common
> code into subroutines/functions in order to simplify the code and
> reduce the need to maintain multiple identical sequences of code.
> However, when faced with limited resources you sometimes need to
> compromise on this ideal.
>
> A call to a subroutine requires 9 bytes of stack space plus the
space
> for each of the parameters, if any. Placing the code for the
called
> subroutine in-line eliminates all of that overhead.
>
> You may also be able to reduce the RAM requirement for your
> application by reducing the default maximum string length (use the
> Environment item on the Options menu). If you have a few cases
where
> you need longer strings you can used the BoundedString type for
those.
>
> Don
>
> >
> >
> > -Tony



arhodes19044 wrote:

> I succeeded in reducing my stack requirement from 223 to 140 bytes
> by eliminating unused variables that were hanging on from various
> iterations of the code.

bxDism indicates unused variables so I'm sure that it how you found
them. You got a significant saving there !!

>
> I then used a BoundedString for a sub-string that is deciphered off
> the main GPS data string. In that case I could make it a length of
> 3. I also got rid of all the "buffer" string declarations in each
> function/subroutine, and used a single global buffer string. Of
> course I can't use it in all cases, but essentially the program runs
> top-down, so each use of the buffer will never interfere with some
> other use.

Yes that is a good practice to save space by reusing one global variable
instead of repeating it many times. The trade off is not always so good
but worth watching for.

>
> In the BxDism output regarding stack usage, there are double
> asterisks next to the "stack usage", and the explanation is: "Lines
> with ** indicate routines with string instructions that may affect
> the stack size at runtime". The Basicx documents indicate that the
> maximum length of a string is allocated when the string is declared,
> so does the stack usage number indicate stack usage NOT INCLUDING
> string usage, or does it include some/all string declarations?
>
Variables are used in 4 places: global, local, parameter or in
expressions. For strings it is possible to determine how stack space is
used for the first 3 cases. That means BasicX correctly calculates stack
usage for declared strings and takes into account the string size.
However as I said before, it is for the dynamic case in expressions
which is much harder to calculate. Two of the dynamic things that throw
off the calculation is the creation of a string directly on the stack
for the statement s = "A" and that the BasicX VM stack pointer is saved
and restored for some more complex operations. Run bxDism on some of
your string operations and read the VM codes to see what I mean.

Mike



Oh, I didn't understand your meaning of dynamic. I thought you
meant variable length declared strings, but I think I see what you
mean by dynamic like this:
'___________________________________________
dim buffer as string 'this is able to be calculated in BxDism
dim length as integer

length = SomeVariableValue

debug.print mid(buffer,1,length) 'this will push some unknown # of
bytes on the stack dynamically
'______________________________________________________________

If the debug.print has a dynamically allocated string, then I see
what you mean. I would still have thought it could never be longer
than 66 bytes, and could be less. Couldn't you still use a worst
case of 66 bytes on the stack?

In this function:
public sub garmin_get_comma_field(byref Tbuffer as string)
dim character as byte

Tbuffer = ""
do
character = garmin_get_char()
if (character = 44) then '44 = ","
exit do
end if
Tbuffer = Tbuffer & chr(character)
loop

end sub

I think there is one dynamic character function (chr()) and that can
only be 1 character long, therefore uses 3 bytes. Should I add 3
bytes to the total stack usage of 26 it reports?

-Tony
--- In basicx@basi..., Mike Perks <basicx@a...> wrote:
> Variables are used in 4 places: global, local, parameter or in
> expressions. For strings it is possible to determine how stack
space is
> used for the first 3 cases. That means BasicX correctly calculates
stack
> usage for declared strings and takes into account the string size.
> However as I said before, it is for the dynamic case in
expressions
> which is much harder to calculate. Two of the dynamic things that
throw
> off the calculation is the creation of a string directly on the
stack
> for the statement s = "A" and that the BasicX VM stack pointer is
saved
> and restored for some more complex operations. Run bxDism on some
of
> your string operations and read the VM codes to see what I mean.
>
> Mike


arhodes19044 wrote:

> Oh, I didn't understand your meaning of dynamic. I thought you
> meant variable length declared strings, but I think I see what you
> mean by dynamic like this:
> '___________________________________________
> dim buffer as string 'this is able to be calculated in BxDism
> dim length as integer
>
> length = SomeVariableValue
>
> debug.print mid(buffer,1,length) 'this will push some unknown # of
> bytes on the stack dynamically
> '______________________________________________________________
>
> If the debug.print has a dynamically allocated string, then I see
> what you mean. I would still have thought it could never be longer
> than 66 bytes, and could be less. Couldn't you still use a worst
> case of 66 bytes on the stack?

The problem with using this is that the result is even less precise and
if you do it for every place a string is used then the stack estimate
will be totally off. If you are interested, look at the BasicX
instructions generated by the compiler and you will see what I mean
about saving the SP, doing some string work and then restoring it thus
making it very to determine actual stack usage.

>
> In this function:
> public sub garmin_get_comma_field(byref Tbuffer as string)
> dim character as byte
>
> Tbuffer = ""
> do
> character = garmin_get_char()
> if (character = 44) then '44 = ","
> exit do
> end if
> Tbuffer = Tbuffer & chr(character)
> loop
>
> end sub
>
> I think there is one dynamic character function (chr()) and that can
> only be 1 character long, therefore uses 3 bytes. Should I add 3
> bytes to the total stack usage of 26 it reports?

The 26 you report includes the nested function garmin_get_char. This
subroutine by itself reports only using 11 bytes including the
subroutine call.. In this case you should add 1 extra byte for the chr()
function.

At this point I think I should tell you about the undocumented option
-D1 which for bxDism debugging purposes shows the actual bytes used for
every instruction in a routine. At the end of each routine this stack
usage should be zero. The maximum is the reported stack usage. If the
stack usage at the end of the routine is non-zero then I call this
"residual" and I optimistically subtract it from the stack usage for the
routine because it can sometimes clearly get out of hand. In the case of
your routine above you will see that bxDism reports a residual of 1. If
you look at the instructions in detail you can see where this extra byte
comes from or rather where it was subtracted when it shouldn't have been.

In my experiments bxDism is fairly accurate unless you are doing a lot
of string manipulation. It reports stack usage on a per task basis so
you can fine tune your task stacks as well. It tends to under read
slightly so I would always add 5 to 10 bytes to its results when
allocating stack space and then experiment. Again bxDism does a static
analysis only which cannot substitute for an actual run on the BasicX
hardware.

Regards,
Mike



Thanls for following thru this with me. I think I finally
understand the basics of what the string sllocations are doing and
how BxDism reports.

While you say that it may under report, and it probably does
slightly, I did an initial test where BxDism reported only 5 bytes
of stack to spare, and the program seemed to work fine.

I really like BxDism. Right now it gives me a reality check on what
is happening in RAM esp with regard to the stack and free RAM. It
helps me find unused variables. And it will help me tune my code to
give the shortest possible overall code.

I already wrote some custom variable-to-text functions that will
output precisely the format I need, and use much less stack and
moderately less program space than the general built-in ones.
Unfortunately, even one use of the built-in ones eliminates all the
benefits of shorter code (overall), and if it occurs in the same
function, then the stack consumed by the function does not
diminish. Anyway, more efficiency is OK. I may write some some
other slightly more general functions to eliminate my use of the
built-ins entirely. (E.G. no bounds and character checking. Unless
there is a major SNAFU, the variable was created from GPS text, so
it must be the expected magnitude and it must be a real number with
no other alphanumerics insetad.)

-Tony

--- In basicx@basi..., Mike Perks <basicx@a...> wrote:
> arhodes19044 wrote:
>
> > Oh, I didn't understand your meaning of dynamic. I thought you
> > meant variable length declared strings, but I think I see what
you
> > mean by dynamic like this:
> > '___________________________________________
> > dim buffer as string 'this is able to be calculated in BxDism
> > dim length as integer
> >
> > length = SomeVariableValue
> >
> > debug.print mid(buffer,1,length) 'this will push some unknown
# of
> > bytes on the stack dynamically
> > '______________________________________________________________
> >
> > If the debug.print has a dynamically allocated string, then I see
> > what you mean. I would still have thought it could never be
longer
> > than 66 bytes, and could be less. Couldn't you still use a worst
> > case of 66 bytes on the stack?
>
> The problem with using this is that the result is even less
precise and
> if you do it for every place a string is used then the stack
estimate
> will be totally off. If you are interested, look at the BasicX
> instructions generated by the compiler and you will see what I
mean
> about saving the SP, doing some string work and then restoring it
thus
> making it very to determine actual stack usage.
>
> >
> > In this function:
> > public sub garmin_get_comma_field(byref Tbuffer as string)
> > dim character as byte
> >
> > Tbuffer = ""
> > do
> > character = garmin_get_char()
> > if (character = 44) then '44 = ","
> > exit do
> > end if
> > Tbuffer = Tbuffer & chr(character)
> > loop
> >
> > end sub
> >
> > I think there is one dynamic character function (chr()) and that
can
> > only be 1 character long, therefore uses 3 bytes. Should I add 3
> > bytes to the total stack usage of 26 it reports?
>
> The 26 you report includes the nested function garmin_get_char.
This
> subroutine by itself reports only using 11 bytes including the
> subroutine call.. In this case you should add 1 extra byte for the
chr()
> function.
>
> At this point I think I should tell you about the undocumented
option
> -D1 which for bxDism debugging purposes shows the actual bytes
used for
> every instruction in a routine. At the end of each routine this
stack
> usage should be zero. The maximum is the reported stack usage. If
the
> stack usage at the end of the routine is non-zero then I call this
> "residual" and I optimistically subtract it from the stack usage
for the
> routine because it can sometimes clearly get out of hand. In the
case of
> your routine above you will see that bxDism reports a residual of
1. If
> you look at the instructions in detail you can see where this
extra byte
> comes from or rather where it was subtracted when it shouldn't
have been.
>
> In my experiments bxDism is fairly accurate unless you are doing a
lot
> of string manipulation. It reports stack usage on a per task basis
so
> you can fine tune your task stacks as well. It tends to under read
> slightly so I would always add 5 to 10 bytes to its results when
> allocating stack space and then experiment. Again bxDism does a
static
> analysis only which cannot substitute for an actual run on the
BasicX
> hardware.
>
> Regards,
> Mike


arhodes19044 wrote:

> Thanls for following thru this with me. I think I finally
> understand the basics of what the string sllocations are doing and
> how BxDism reports.
>
> While you say that it may under report, and it probably does
> slightly, I did an initial test where BxDism reported only 5 bytes
> of stack to spare, and the program seemed to work fine.

Good I'm glad you found it useful. It only under reports in the case
where you are manipulating strings.

bxDism is jointly authored by Don Kinzer and myself. We do not work for
or have any relationship with NetMedia, Inc.

Mike



Mike, I think you just provided a 'BasicX Revelation' here...

For example, given a Main program with several Modules and typically
using "I" as a loop variable, would it be best to declare it as
Global vs Local Module/Subroutine/Function levels? While the local
variable would come and go, would the stack space be reduced? Thanks,

- Tom

--- In basicx@basi..., Mike Perks <basicx@a...> wrote:
> arhodes19044 wrote:
>
> > I succeeded in reducing my stack requirement from 223 to 140 bytes
> > by eliminating unused variables that were hanging on from various
> > iterations of the code.
>
> bxDism indicates unused variables so I'm sure that it how you found
> them. You got a significant saving there !!
>
> >
> > I then used a BoundedString for a sub-string that is deciphered
off
> > the main GPS data string. In that case I could make it a length
of
> > 3. I also got rid of all the "buffer" string declarations in each
> > function/subroutine, and used a single global buffer string. Of
> > course I can't use it in all cases, but essentially the program
runs
> > top-down, so each use of the buffer will never interfere with some
> > other use.
>
> Yes that is a good practice to save space by reusing one global
variable
> instead of repeating it many times. The trade off is not always so
good
> but worth watching for.
>
> >
> > In the BxDism output regarding stack usage, there are double
> > asterisks next to the "stack usage", and the explanation
is: "Lines
> > with ** indicate routines with string instructions that may affect
> > the stack size at runtime". The Basicx documents indicate that
the
> > maximum length of a string is allocated when the string is
declared,
> > so does the stack usage number indicate stack usage NOT INCLUDING
> > string usage, or does it include some/all string declarations?
> >
> Variables are used in 4 places: global, local, parameter or in
> expressions. For strings it is possible to determine how stack
space is
> used for the first 3 cases. That means BasicX correctly calculates
stack
> usage for declared strings and takes into account the string size.
> However as I said before, it is for the dynamic case in expressions
> which is much harder to calculate. Two of the dynamic things that
throw
> off the calculation is the creation of a string directly on the
stack
> for the statement s = "A" and that the BasicX VM stack pointer is
saved
> and restored for some more complex operations. Run bxDism on some
of
> your string operations and read the VM codes to see what I mean.
>
> Mike


tombhandley wrote:

> Mike, I think you just provided a 'BasicX Revelation' here...
>
> For example, given a Main program with several Modules and typically
> using "I" as a loop variable, would it be best to declare it as
> Global vs Local Module/Subroutine/Function levels? While the local
> variable would come and go, would the stack space be reduced? Thanks,
>
> - Tom

I can't take credit for this idea. It does save overall RAM usage which
may help in a tight situation. If you only use your loop variable in two
places, it may not be worthwhile and you should look for other changes.
Too deep nesting of function calls is usually more of a problem. The
output from the bxDism tool can help understand the static nesting of calls.

As with any change to improve performance, here are the 4 questions to
ask yourself (in order):

1. Do I need to do this change now? For example if you are not running
out of RAM yet then why bother making changes now that may not be needed
in the end. This is not an excuse for poor choices in data structures
and algorithms - see 2.

2. Is there other change in data structure, algorithm or function that
would provide a much better fix both in terms of performance and code
maintainability?. Sometimes a change here has dramatic effects.

3. Did the performance fix actually improve anything? You need to
compare (and measure) the before and after.

4. Is the trade-off of improved performance really worth the worse or
much worse code maintainability or loss of encapsulation? For example
global variables are a poor programming practice but sometimes we have
to do it.

Mike

> --- In basicx@basi..., Mike Perks <basicx@a...> wrote:
> > arhodes19044 wrote:
> >
> > > 3. I also got rid of all the "buffer" string declarations in each
> > > function/subroutine, and used a single global buffer string. Of
> > > course I can't use it in all cases, but essentially the program
> runs
> > > top-down, so each use of the buffer will never interfere with some
> > > other use.
> >
> > Yes that is a good practice to save space by reusing one global
> variable
> > instead of repeating it many times. The trade off is not always so
> good
> > but worth watching for.
> >