Memory management strategy

[ira2402]

Hi All,
We are developing sw for a small embedded OS and we have limited
memory.
We are looking for algorithms, links, and articles about this.
The goal is efficient utilization of small amount of memory - means -
allocation for fixed length blocks / variable length blocks.
Thanks.

[Lawrence Kirby]

On Mon, 30 May 2005 07:09:41 -0700, ira2402 wrote:

Hi All,
We are developing sw for a small embedded OS and we have limited
memory.
We are looking for algorithms, links, and articles about this.
The goal is efficient utilization of small amount of memory - means -
allocation for fixed length blocks / variable length blocks.
Thanks.

You could try comp.programmin g for datastructures and algorithms and
comp.arch.embed ded for embedded systems. comp.lang.c is for discussing the
standard C programming language which is not really what your question is
about.

Lawrence

[Paul Mesken]

On 30 May 2005 07:09:41 -0700, ir*****@yahoo.c om wrote:

Hi All,
We are developing sw for a small embedded OS and we have limited
memory.
We are looking for algorithms, links, and articles about this.
The goal is efficient utilization of small amount of memory - means -
allocation for fixed length blocks / variable length blocks.
Thanks.

Well, as far as C goes, I could think of a couple of tips :

- Instead of allocating memory for each small object, allocate a big
piece of memory and manage it yourself. Each individual allocation
comes with some overhead and functions like malloc and calloc might
have a minimum size they allocate (for example, if you allocate memory
for 2 bytes, it might turn out that 16 bytes were allocated because
allocation works with such a granularity). Also, allocating one big
block also reduces the ever present danger of memory leaks.

- Don't use speed optimizations of your compiler. These might involve
trading memory for speed (loop unrolling, for example).

- 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. As far as struct's go : note that you might lose some extra
memory due to padding.

- Avoid recursive functions, if you can. Although recursive functions
often reduce code size, they might turn out to be very memory hungry.

- Don't pass big objects (like struct's) by value but by reference, if
you can.

- 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 :-)

- Use const where appropriate (especially for arrays).

Furthermore : you could think of compression of data and writing data
to some mass storage device (if your embedded system has one) if the
data isn't used for a long time.

Now (I just can't help myself ;-) if all else fails then you might
want to resort to Assembly which often allows for all kinds of
trickery that can even further reduce code size (one of the most
notorious methods was self modifying code, but your system must be
able to allow such a thing).

[Walter Roberson]

In article <23************ *************** *****@4ax.com>,
Paul Mesken <us*****@eurone t.nl> wrote:

On 30 May 2005 07:09:41 -0700, ir*****@yahoo.c om 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.

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
"investigat e the available options and their effects" -- and be
prepared for the possibility that the next compiler update down the
road, the tradeoffs might change.

- 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.

- 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.

- 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.
--
Oh, to be a Blobel!

[Paul Mesken]

On 30 May 2005 16:25:43 GMT, ro******@ibd.nr c-cnrc.gc.ca (Walter
Roberson) wrote:

In article <23************ *************** *****@4ax.com>,
Paul Mesken <us*****@eurone t.nl> wrote:

On 30 May 2005 07:09:41 -0700, ir*****@yahoo.c om 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
"investigat e 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.
Particularil y 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 :-)

[Paul Mesken]

On Mon, 30 May 2005 19:12:45 +0200, Paul Mesken <us*****@eurone t.nl>
wrote:

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).

Errr... I meant, of course :

....uses some kind of stack hardly gives some code/data size gains.

Or just "size", for short :-)

[Malcolm]

<ir*****@yahoo. com> wrote

The goal is efficient utilization of small amount of memory - means -
allocation for fixed length blocks / variable length blocks.

Here are a couple of handy hints.

Declare a stack and allocate on that. This differs from the regular stack in
that it is designed to hold larger amounts of memory, and can hold amounts
calculated at complile time.

If you need many chunks of a fixed size, allocate a block large enough to
hold the number you need. Then keep a linked list, storing the pointers in
the fist bytes. To allocate, take the first block in the list nad update the
"head" pointer. To free, simply place the freed block at the head of the
list.

[Keith Thompson]

Paul Mesken <us*****@eurone t.nl> writes:

On 30 May 2005 16:25:43 GMT, ro******@ibd.nr c-cnrc.gc.ca (Walter
Roberson) wrote: [...]

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).

A function call, depending on the calling conventions, might require
the use of some registers; inlining the call might make those
registers available for other purposes (like caching local variables).
This is, of course, extremely system-specific.
"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.
On the other hand, inlining a function can provide more opportunities
for optimization. For example:

void foo(int x)
{
if (x < 0) {
/* some stuff */
}
else if (x == 0) {
/* some other stuff */
}
else {
/* yet other stuff */
}
}

If a call to foo() is inlined in a context where the compiler knows
that x is positive, the "some stuff" and "some other stuff", along
with the tests, can be eliminated. Add to that the savings from
eliminating the entry and exit code, and you just might get less code
with 20 inlined copies than with 20 calls to a single function. Or
you might not.

[...]
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.

For single variables, it rarely makes sense to use a smaller type.
For arrays, you can often save space by using an array of char or
short rather than int or long, or an array of float rather than double
-- but of course you need to make sure that the values will actually
fit in the smaller type.

One more possible tip: In embedded systems, my understanding is that
code and constant data are typically in ROM, while variable data is
typically in RAM, and that ROM is often much more plentiful than RAM.
It might make sense to write a large amount of code, or declare a
large constant array, to save a little bit of run-time data.

And of course *all* this stuff is extremely system-specific. None of
this advice should be followed blindly. Understand the system you're
using, and *measure*.

I'm sure the folks in comp.arch.embed ded know more about this stuff
than I do.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[pete]

ir*****@yahoo.c om wrote:

Hi All,
We are developing sw for a small embedded OS and we have limited
memory.
We are looking for algorithms, links, and articles about this.
The goal is efficient utilization of small amount of memory - means -
allocation for fixed length blocks / variable length blocks.
Thanks.

K&R2
Section 8.7
8.7 Example-A Storage Allocator
page 185.

http://cm.bell-labs.com/cm/cs/cbook/

--
pete

[Malcolm]

"Paul Mesken" <us*****@eurone t.nl> wrote

"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.

Unless the instructions go in ROM and the stack goes in RAM, and RAM is
twenty times more precious.