Experimental Physics and
Industrial Control System

Benjamin Franksen <[email protected]> · Tue, 01 Mar 2005 00:20:12 +0100

On Friday 25 February 2005 00:54, Jeff Hill wrote:
> >> The executive summary is that, with the C RTL, continuously
> >> allocating random sized blocks has a very bad impact on memory
> >> fragmentation, and therefore CPU overhead.
> >
> > Just curious.  What's the basis for the above statement?
> > Is this problem present everywhere or only on vxWorks?
>
> In my experience malloc and free are very high overhead calls
> compared to free list based memory management. It is well known
> that the overhead associated with calls to malloc and free goes
> up when the number of fragments in pool increases. When designing
> the C RTL it is important to avoid fragmenting memory in the
> first place. There are many different approaches {best fit, first
> fit etc} and considerable research has gone into finding an
> optimal approach. Nevertheless, it is still possible to fragment
> memory. Naturally, fragmentation will be worse with certain usage
> patterns. For example it will be worse when you allocate in
> between every block that you keep a small block that you will
> free. The particular choice of {best fit, first fit etc} isn't
> going to eliminate the problem. However, if you are willing to
> add some additional latency and overhead to malloc and free, you
> can decrease the probability of noticeable pool fragmentation.

http://citeseer.ist.psu.edu/johnstone97memory.html throws a considerable 
amount of quantitative light on the problem in general. Maybe epics should 
re-implement malloc and free (using e.g. address ordered first fit) for 
systems where the default implementation is bad with regard to fragmentation 
(and maybe slow, too).

However, the test programs used in the above paper are not of the run-forever 
(server) kind. I find it hard to judge if this invalidates the results for 
our purposes.

All this doesn't mean I want to argue against "free-lists" in cases where the 
requested allocation sizes are typically of a fixed size. I also don't argue 
against supporting string or array implementations that use fixed size 
non-contiguous blocks. To the contrary: I would think that any interface that 
precludes such implemetations is a broken design to begin with.

Jeff, could you please explain why the interface of std::string is not 
compatible with such implementations?

BTW, "free-list" is a strange term for allocation in fixed-sized blocks. 
AFAIK, many different memory allocation schemes keep a list of free memory 
blocks.

> We did experience memory fragmentation issues on vxWorks in the
> 90's. I vaguely recall that at the time, after someone had a
> quick look at the WRS source code, it was stated that the WRS
> memory allocation algorithms wasn't main stream.

I've been told things were even worse with the original VxWorks semaphore 
implementation ;-)

Ben

Experimental Physics and Industrial Control System

Experimental Physics and
Industrial Control System