Re: Memory management strategy

On 30 May 2005 16:25:43 GMT, roberson@xxxxxxxxxxxxxxxxxx (Walter
Roberson) wrote:

>In article <23am91lnhhu5afenncqo7lq166vma7tn0l@xxxxxxx>,
>Paul Mesken <usurper@xxxxxxxxxx> wrote:
>>On 30 May 2005 07:09:41 -0700, ira2402@xxxxxxxxx wrote:
>
>>>We are developing sw for a small embedded OS and we have limited
>>>memory.
>>>We are looking for algorithms, links, and articles about this.
>
>>Well, as far as C goes, I could think of a couple of tips :
>
>Generally good recommendations, but a few of them do not always work.
>
>>- Don't use speed optimizations of your compiler. These might involve
>>trading memory for speed (loop unrolling, for example).
>
>Inlining of short routines can -sometimes- take less memory than
>calling the routine, as the registers can sometimes be used directly
>"as-is", without having to save important values and generate the
>call and have the return stack.

The use of registers instead of the stack doesn't need inlining. There
are often calling conventions that can control this behaviour (of
course, such things are depending on the capabilities of the compiler
and linker).

"Inline functions" are more liable to use more memory since the whole
function is put in place of the code that calls such a function. If
some inline function is called at 20 different places in the program
then the code of that function is placed 20 times in the code. If the
function is big then this might give a quite substantial code size
penalty. The fact that the function takes a little bit less code
because it doesn't need to do stack manipulations (or less stack
manipulations) doesn't amount to a lot when the code of that function
is copied 20 times in the program.

>Some compilers allow control over when unrolling is done -- e.g.,
>may allow you to place an upper limit on the complexity of the code
>to be unrolled.
>
>Thus I would not say "don't use" the optimizations: I would say
>"investigate the available options and their effects" -- and be
>prepared for the possibility that the next compiler update down the
>road, the tradeoffs might change.

You are right that my statement was too coarse. A compiler like gcc
(which is probably used for embedded systems) gives very fine control
over optimizations.

>>- Use the minimum sized datatype you need. All too often, int's are
>>used automatically by the programmer where short's and char's could
>>have been used. You might even be able to pack some values with
>>bitfields.
>
>That can depend upon how often the data is used and how much
>of one type there is, and upon the architecture. Some systems need
>longer instructions to access smaller data than they were optimized for.
>Particularily for bitfields.

It is very true indeed that using the values of bitfields requires
more instructions (shifts, and's, or's, etc.).

Yes, it's only sensible to use packed values when the extra amount of
code necessary to manipulate such values is less than the amount of
memory that was saved by having such packed values.

>>- Avoid recursive functions, if you can. Although recursive functions
>>often reduce code size, they might turn out to be very memory hungry.
>
>Rewriting a recursive function into its iterative form (which always
>possible) can require more memory and lower efficiency than leaving
>it recursive -- in the iterative form, you have to do dynamic memory
>management, linked lists or growing arrays in place, with all the code
>and memory overhead that represents.

Although the non-recursive function typically takes more code than its
recursive version, it's not always unavoidable that some stack has to
be used.

Two weeks ago I finished a floodfill algorithm (which are often
recursive or use some kind of stack). It was lengthier than the usual
"point" or "line" floodfills (it utilizes an expanding and shrinking
square) but it didn't need recursion or some kind of stack.

In short : it is often possible to write a function that is not
recursive nor uses some kind of stack and that achieves the same goals
as a recursive function.

You're right for pointing out that replacing a recursive function with
a function that uses some kind of stack hardly gives some code size
gains (although such a function would still be safer than a recursive
function).

>>- Using global variables might reduce memory usage (in passing less
>>parameters) in some cases but this is considered a bit ugly and is a
>>bit of a micro optimization :-)
>
>Using global variables can also increase code size, depending on the
>architecture. Sometimes there are shorter instructions for referring
>to objects "near" a base register (e.g., within 16 bits offset)
>whereas a full address may be required for a global. On the other
>hand, some architectures have short instructions for referring to
>objects in "low memory" (e.g., first 64 Kb), and on those architectures
>a global that can be located within that "low memory" block might have
>the smallest instruction. You really need to know your architecture
>to get this kind of thing right.

You're right in that (and it was an ugly optimization anyway :-)

.

Relevant Pages

  • Re: Stack, Heap, Mfc
    ... >> is put on the heap. ... >> decendant does this not mean that all memory will be on the heap because ... > stack or the heap. ... You first try to limit the recursion to an acceptable ...
    (microsoft.public.vc.mfc)
  • Re: Doubt on Stack variables.
    ... As other posters have pointed out, the notion of a "stack" does not appear ... compilers have memory models where they don't use a stack. ... A conforming implementation must support recursion; ... A compiler can allocate local variables statically *if* ...
    (comp.lang.c)
  • Re: Suggestions on improving program on binary tree postorder traversal
    ... more one of stack than of the compiler. ... lot less memory than using recursion would. ... since any iteration can be replaced with recusion do you really ...
    (comp.lang.c)
  • Re: Iteration over recursion?
    ... time-efficient than recursion. ... in most languages it's a memory thing. ... This (depending on the stack size and implementation etc...) ...
    (comp.lang.python)
  • Re: the stack
    ... Charles Crayne writes: ... fixed to top of memory (which I'm assuming from his statement since I ... The 8080, like the 8086, had a 16-bit stack pointer, which allowed the ... instructions to directly manipulate it. ...
    (alt.lang.asm)