execution time becomes unpredictable?!

[vashwath]

Might be off topic but I don't know where to post this question.Hope
some body clears my doubt.

The coding standard of the project which I am working on say's not to
use malloc.When I asked my lead(I have just started working) he said we
should not use dynamic allocation in real time systems, the code will
not run in predictable time period.Can anybody tell what does he
mean?Why the execution time becomes unpredictable?

Thanks

 

[Neil Kurzman]

Might be off topic but I don't know where to post this question.Hope
some body clears my doubt.

The coding standard of the project which I am working on say's not to
use malloc.When I asked my lead(I have just started working) he said we
should not use dynamic allocation in real time systems, the code will
not run in predictable time period.Can anybody tell what does he
mean?Why the execution time becomes unpredictable?

Thanks

Because the time to find a block of memory the correct size will vary. Of
course since the system runs "forever", what will your system do if a
malloc fails due to fragmentation.

 

[Walter Roberson]

Might be off topic but I don't know where to post this question.Hope
some body clears my doubt.

The coding standard of the project which I am working on say's not to
use malloc.When I asked my lead(I have just started working) he said we
should not use dynamic allocation in real time systems, the code will
not run in predictable time period.Can anybody tell what does he
mean?Why the execution time becomes unpredictable?

In the general case, the lead is correct, but not -inevitably- so.

The problem with malloc() is that usually it is implimented by
searching through a free list looking for a chunk of a large enough
size (after alignment constraints). If memory is badly fragmented,
there could be a lot of available memory but it might take a long time
to find a chunk known to be long enough.

Similarily, depending on how smart the free() operation is, the
procedure for returning a chunk of memory might involve merging together
adjacent regions; that could in turn trigger more merging, for an
indefinite amount of time spent in reclamation.

The more work that free() does to merge adjacent areas of memory, the
less deterministic the time it will take is -- but if it does not do
merging, then malloc() and kin could end up taking quite a bit of time
to search and could plausibly decide that there is no available memory
even though there are plenty of mergable spaces left.

Some free() implimentations hold off merging until malloc() request
comes in that could be satisfied by merging but not by itself alone.
In that case, free() might be fast, but every once in a while malloc() could
take quite a bit of time.


There are, I believe, versions of malloc() and free() around that have
upper bounds on time. For example, malloc() could divide memory into
a series of pools of fixed size, and always return the smallest
pool that fits. If the pools are sized as powers of 2, then simple
bitmaps can be used to discover whether a pool member is available
or not, and returning a pool member can come out as simply or'ing in
a bit to say the element is free. This pool strategy has to be tuned
to allow for enough of the right size of pool members, which might be
done once at initialization time. There are some varients that will
crack apart larger pools if necessary to provide more small entries:
this makes the timing less deterministic, but the algorithm can
be initialized to place a maximum limit on the depth it will do this
to, thus placing a maximum limit on the malloc()/free() time.

When you are working with real-time systems, there may be some
areas where sheer speed is important, but -generally-
"real-time systems" are more concerned with -predictability- of
response times than with sheer speed. An interrupt must be handled
within so many milliseconds -- so you can't be held up for several
seconds on garbage collection for something low priority. The
handling of the interrupt will not necessarily take very long
(it might involve very little computation as such), but for
"real-time systems" that not-very-long-time usually has to happen
within a relatively short time from the event trigger.

 

[Peter Nilsson]

Might be off topic but I don't know where to post this question.

comp.programming perhaps.

Hope some body clears my doubt.

The coding standard of the project which I am working on say's
not to use malloc.When I asked my lead(I have just started
working) he said we should not use dynamic allocation in real
time systems, the code will not run in predictable time period.

You have responses already explaining why, but your lead's
concerns are surprising given that real time systems are
implemented in Java and other languages that use garbage
collection.

In critical systems, the main concern is what to do if a
dynamic allocation fails.

 

[Ravi Uday]

In the general case, the lead is correct, but not -inevitably- so.

The problem with malloc() is that usually it is implimented by
searching through a free list looking for a chunk of a large enough
size (after alignment constraints). If memory is badly fragmented,
there could be a lot of available memory but it might take a long time
to find a chunk known to be long enough.

Similarily, depending on how smart the free() operation is, the
procedure for returning a chunk of memory might involve merging together
adjacent regions; that could in turn trigger more merging, for an
indefinite amount of time spent in reclamation.

The more work that free() does to merge adjacent areas of memory, the
less deterministic the time it will take is -- but if it does not do
merging, then malloc() and kin could end up taking quite a bit of time
to search and could plausibly decide that there is no available memory
even though there are plenty of mergable spaces left.

Some free() implimentations hold off merging until malloc() request
comes in that could be satisfied by merging but not by itself alone.
In that case, free() might be fast, but every once in a while malloc() could
take quite a bit of time.


There are, I believe, versions of malloc() and free() around that have
upper bounds on time. For example, malloc() could divide memory into
a series of pools of fixed size, and always return the smallest
pool that fits. If the pools are sized as powers of 2, then simple
bitmaps can be used to discover whether a pool member is available
or not, and returning a pool member can come out as simply or'ing in
a bit to say the element is free. This pool strategy has to be tuned
to allow for enough of the right size of pool members, which might be
done once at initialization time. There are some varients that will
crack apart larger pools if necessary to provide more small entries:
this makes the timing less deterministic, but the algorithm can
be initialized to place a maximum limit on the depth it will do this
to, thus placing a maximum limit on the malloc()/free() time.

When you are working with real-time systems, there may be some
areas where sheer speed is important, but -generally-
"real-time systems" are more concerned with -predictability- of
response times than with sheer speed. An interrupt must be handled
within so many milliseconds -- so you can't be held up for several
seconds on garbage collection for something low priority. The
handling of the interrupt will not necessarily take very long
(it might involve very little computation as such), but for
"real-time systems" that not-very-long-time usually has to happen
within a relatively short time from the event trigger.

.. and generally interrupt routines wont have malloc/free call,
it just comes up as higher priority does its routine and exits

 

[CBFalconer]

Might be off topic but I don't know where to post this question.
Hope some body clears my doubt.

The coding standard of the project which I am working on say's not
to use malloc.When I asked my lead(I have just started working) he
said we should not use dynamic allocation in real time systems, the
code will not run in predictable time period.Can anybody tell what
does he mean?Why the execution time becomes unpredictable?

That depends entirely on the system and the actual malloc package.
In general the C language does not specify any timing. Where this
discussion belongs is really a problem, because it may well be
beyond the knowledge of the system specific group users for the
rarer systems. Tell your lead to take a look at:

<http://cbfalconer.home.att.net/download/nmalloc.zip>

for some possibilities. It is especially designed to control
execution time.

 

[websnarf]

Might be off topic but I don't know where to post this question.Hope
some body clears my doubt.

The coding standard of the project which I am working on say's not to
use malloc.When I asked my lead(I have just started working) he said
we should not use dynamic allocation in real time systems, the code
will not run in predictable time period.Can anybody tell what does he
mean?Why the execution time becomes unpredictable?

The implementation of malloc used for System V Unix (which was used by
compilers beyond System V Unix) gets slower and slower after repeated
usage. In fact I have seen it actually eventually lose memory
allocations. Some implementations of malloc/free are just really poor.

Basically the C language standard does not mandate anything about
performance and real implementations of memory heaps *really do*
execute in unpredictable amounts of time. That said, there certainly
do exist O(1) implementations of malloc/free (and realloc, if we ignore
the memcpy overhead.) So malloc() is only slow on *some* systems --
but it may be hard to know which such systems. As far as I know, gcc,
because its open source and "Lea" malloc implementation is reasonably
documented, we know that its memory allocation scheme is fairly
reasonable. OTOH, I've measured MSVC's memory allocation speed, and
its *MUCH* faster than gcc, but since its closed source, I can't sit
here and tell you that its even O(1) in all cases.

 

[Keith Thompson]

comp.programming perhaps.


You have responses already explaining why, but your lead's
concerns are surprising given that real time systems are
implemented in Java and other languages that use garbage
collection.

In critical systems, the main concern is what to do if a
dynamic allocation fails.

I think the distinction between "real time" and "*hard* real time"
might be relevant here. comp.realtime would be a good place to
discuss the details.

 

[Thomas Matthews]

comp.programming perhaps.




You have responses already explaining why, but your lead's
concerns are surprising given that real time systems are
implemented in Java and other languages that use garbage
collection.

In critical systems, the main concern is what to do if a
dynamic allocation fails.

Actually, many real-time systems are implemented in C
and C++ as well as other languages that don't have
garbage collection.

As others have stated, garbage collection and memory
fragmentation are a nightmare for real-time and
critical systems. Even stack allocation causes
trembles in experienced programmers; they are
worried about overruning a limited stack area.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library

 

[Richard Bos]

The problem with malloc() is that usually it is implimented by
searching through a free list looking for a chunk of a large enough
size (after alignment constraints). If memory is badly fragmented,
there could be a lot of available memory but it might take a long time
to find a chunk known to be long enough.

Similarily, depending on how smart the free() operation is, the
procedure for returning a chunk of memory might involve merging together
adjacent regions; that could in turn trigger more merging, for an
indefinite amount of time spent in reclamation.

Surely only a very unsmart implementation would ever need more than two
merges for a single free()? Once with the block before it; once with the
block after it. You only need more if you save up merges, which seems to
me to be a decidedly suboptimal solution for more reasons than this.

Richard

 

[Eric Sosman]

Surely only a very unsmart implementation would ever need more than two
merges for a single free()? Once with the block before it; once with the
block after it. You only need more if you save up merges, which seems to
me to be a decidedly suboptimal solution for more reasons than this.

Two words: "Buddy system."

 

[Chris Croughton]

comp.programming perhaps.


You have responses already explaining why, but your lead's
concerns are surprising given that real time systems are
implemented in Java and other languages that use garbage
collection.

/Some/ real time systems are implemented in Java and other languages
with GC. Those will be ones where deterministic behaviour in the time
domain is not important to the application (or at least to that part of
it using dynamic memory -- a user interface, for instance, probably
doesn't care within a few hundred milliseconds, but the underlying
control application does care a lot). Not all applications can afford
to ignore the time, however.

In critical systems, the main concern is what to do if a
dynamic allocation fails.

That's certainly a major concern, and one for which there is often no
good answer except "don't do it".

Chris C

 

[CBFalconer]

Surely only a very unsmart implementation would ever need more
than two merges for a single free()? Once with the block before
it; once with the block after it. You only need more if you save
up merges, which seems to me to be a decidedly suboptimal solution
for more reasons than this.

They only need two merges max, but the problem is finding those
candidates. Some systems search lists for adjacencies, in fact I
find most do this. [1] This makes the free operation O(n).
nmalloc keeps, for each block, links to physically adjacent blocks,
which makes the free operation O(1). The significant delays only
show up (in the O(N) systems) after many thousands of allocations
have been made.

The cost of those links appears in 'wasted' memory when mallocing.
In nmalloc they account for an extra 8 bytes per allocation (since
the links need to be bidirectional to avoid any searches).
Similarly the search for a free block is limited to a few block
sizes, expanding in size by two. This makes that operation O(1)
also, but increases the possibility of needless failure. For
details see:

<http://cbfalconer.home.att.net/download/nmalloc.zip>

[1] 'most' here is a sampling of DJGPP 2.03, CRTDLL.DLL in W98,
MSVCRT.DLL from VC 6, and whatever was in CYGWIN a few years ago.
IIRC all exhibited the O(N*N) behaviour in freeing long lists of
allocations. This was the principal reason for creating nmalloc.
It also added healthy debugging capabilities due to the extensive
linking. A quick check can show up inconsistencies, and catch
errant memory usage fairly early.

 

[CBFalconer]

Two words: "Buddy system."

Which I have not looked at for many years, but I believe it has the
potential of leaving up to 50% of memory unavailable. Am I wrong?
My Knuths are hidden away somewhere.

 

[Rob Thorpe]

The implementation of malloc used for System V Unix (which was used by
compilers beyond System V Unix) gets slower and slower after repeated
usage. In fact I have seen it actually eventually lose memory
allocations. Some implementations of malloc/free are just really poor.

I hope they don't still use SysV malloc.

Basically the C language standard does not mandate anything about
performance and real implementations of memory heaps *really do*
execute in unpredictable amounts of time. That said, there certainly
do exist O(1) implementations of malloc/free (and realloc, if we ignore
the memcpy overhead.) So malloc() is only slow on *some* systems --
but it may be hard to know which such systems. As far as I know, gcc,
because its open source and "Lea" malloc implementation is reasonably
documented, we know that its memory allocation scheme is fairly
reasonable.

(The following isn't really that relevant to the O/P question, but
interesting

Ben Zorn at the university of Colorado used to have a nice webpage
with the source of many malloc's on it including his. Unfortunately
it looks like the university have taken his personal webpage down
since he moved to Microsoft.

Real implementations of malloc at use bining at least, and many other
tricks. For fast machines like modern desktops no-one seems to care
that much to make malloc run very fast. They do try to make it
stable, and stop it from wasting loads of memory which many simple
mallocs do. Very slow algorithms can't be used, but saving some
memory by spending a little more time is OK.

On a very small embedded system it might not be possible to use an
elaborate malloc algorithm because of code space. (Which is obvious,
why did I type it? )

OTOH, I've measured MSVC's memory allocation speed, and
its *MUCH* faster than gcc, but since its closed source, I can't sit
here and tell you that its even O(1) in all cases.

The time spent can be split up between malloc and free in different
ways. For example you could split it up so it works like this:-

malloc 1
------
m1 Look at size asked for, find the nearest bin
m2 Get a pointer to that bin from the free list
m3 attach it to the used list (? maybe if there is a used list)
m4 store some data just before the pointer location
m5 give it to the program

free 1
----
f1 Go to the ptr location look at the data you put in just before
f2 Add it back onto the relevant free list
f3 Do some merging (? maybe)
f4 Update the used list (? maybe)

Here, if there is no used list everything malloc does is fast, but
free must traverse the free list. It may also have to merge.

But the algorithm can be done the other way around, so in step 1
malloc traverses one of the free lists and takes an element from the
end. Some of the other data structures you could use would have the
same problem (but I'm sure there'd be one that would be reasonably
fast at both ends at the expense of space).

It could be that GNU malloc splits the time up differently to MS
malloc. Also, it could be that it has an interface into the operating
system that allows it to work faster from knowledge gleaned from
inside the OS. I don't think GNU malloc does that, even on Linux.

Anyway, a "large machine" malloc would probably want to use some
devious way to avoid fragmentation, which would probably make it
unlikely to be O(1). A malloc for a small machine might not need to
so thoroughly though.

(I'm aware I'm telling somes to Paul Hsieh about speed, which is
rather like talking to Gengis Khan about conquering Asia. Don't flame
me too much for any of the above that is wrong.)

 

[Eric Sosman]

Which I have not looked at for many years, but I believe it has the
potential of leaving up to 50% of memory unavailable. Am I wrong?
My Knuths are hidden away somewhere.

For a binary buddy system, the worst case occurs when
all request sizes are of the form (1<<n)+1: the size must be
rounded up to 1<<(n+1), thus wasting just a smidgen less than
half the memory.

Because programmers are superstitious and like to use
powers of two even when there's no reason to, cases close to
the worst are distressingly common. Programmer habitually
requests memory in power-of-two sizes, the memory manager
tacks on a few bytes of metadata, and lo! the block size is
power-of-two plus a small amount ...

Buddy systems don't necessarily have to be binary,
where a large block splits into two equally-sized buddies.
I've seen mention of a Fibonacci system, where a large
block of size F[n] splits into buddies of F[n-1] and F[n-2];
such a scheme might cope better with programmers' fondness
for magic numbers. Can't say I've ever seen such a system
in production, though.

<Drags out Knuth>: "J.M. Robson has shown [...] that
dynamic storage allocation strategies which never relocate
reserved blocks cannot possibly be guaranteed to use memory
efficiently [...] Even when blocks are restricted to be
of sizes 1 and 2, overflow might occur with the memory only
about 2/3 full, no matter what allocation algorithm is used!"

 

[REH]

Might be off topic but I don't know where to post this question.Hope
some body clears my doubt.

The coding standard of the project which I am working on say's not to
use malloc.When I asked my lead(I have just started working) he said we
should not use dynamic allocation in real time systems, the code will
not run in predictable time period.Can anybody tell what does he
mean?Why the execution time becomes unpredictable?

Thanks

What that means is the time to execute the call to malloc is
non-deterministic. That is, you cannot know exactly how long it will take.
The reason it is important in real-time systems, is you have hard
dead-lines. You have X amount of time to handle an event. You cannot prove
that the software can meet its deal-lines if you call functions with
non-deterministic execution times.

REH

 

[E. Robert Tisdale]

The coding standard [for] the project which I am working on
say's not to use malloc.
When I asked my lead (I have just started working), he said that,
"We should not use dynamic allocation in real time systems
[because] the code will not run in predictable time period."
Can anybody tell what he means?
Why [does] the execution time becomes unpredictable?

It is practically impossible to predict how long
it will take malloc to find a free memory fragment
that is at least as large as you requested.

Dynamic memory allocation may still be used in real-time programs
in the initialization phase
before it is expected to service real-time events.

Modern implementations of malloc
on high performance computer architectures are so fast
that you would almost never miss a real-time deadline
but that's not the problem. The problem is that,
if your program begins to miss real-time deadlines intermittently,
you would have no practical way to eliminate malloc
as the source of the problem.

This still wouldn't be a problem except that
real-time applications are so often also *critcal* applications --
you just can't afford to miss deadlines.
For this reason, real-time programmers like your lead
prefer to avoid dynamic memory allocation altogether.

 

[Stephen Sprunk]

What that means is the time to execute the call to malloc is
non-deterministic. That is, you cannot know exactly how long it
will take. The reason it is important in real-time systems, is you
have hard dead-lines. You have X amount of time to handle an
event. You cannot prove that the software can meet its deal-lines
if you call functions with non-deterministic execution times.

Non-determinism isn't necessarily bad as long as you can prove the _maximum_
time required for all the functions you call (plus your own function)
doesn't exceed the deadline. The problem with malloc() and free() is that
there is usually no way to prove the maximum time required for one or the
other (or sometimes both). I'm not even sure it's possible in theory for
both.

In some environments, though, this is not enough and the system needs the
exact same cycle count for _every_ execution. Few systems can provide this
even at the hardware level, but they exist.

S

 

[Walter Roberson]

Surely only a very unsmart implementation would ever need more than two
merges for a single free()? Once with the block before it; once with the
block after it. You only need more if you save up merges, which seems to
me to be a decidedly suboptimal solution for more reasons than this.

I don't know if there is a formal name like "Buddy System"
for what I was thinking of. Consider, though, a system which
is written to only merge together blocks to produce larger
superblocks with magic size and alignment properties.

To put it more concretely, free() might only merge together
blocks to the extent that the resulting block size was 2^N
aligned on a "natural" binary boundary.

In such a case, if the block size being returned was the
minimum size handled by the allocator (e.g, 4 bytes) then
the return could trigger a merge with the 4 bytes beside it,
and the resulting 8 byte block could then be merged with the
8 byte block beside that, and so on up through the powers of
2 to the maximum allocation size.

This sort of merging is trivial if handled by a bitmap, but
if for some reason this kind of merging was being done -and-
there was the traditional "each free block points to the
next free block" chain, then a number of pointer fixups could
end up being done.


This issue only arises in situations where certain block sizes or
alignments are magic and those magic properties are to be preserved; as
you point out, it does not come into play if free() just merges
together adjacent blocks of whatever size and alignment happen to be
there.