Memory allocation strategies

[jacob navia]

Hi
I am not an IUT student, and I do not have a question, but I have some
answers.

The standard memory allocation strategy of C is to keep track of each
and every piece of RAM. This is an incredibly error prone activity, as
proved by the countless memory allocation bugs that appear in code built
using that strategy.

Another strategy, and the one that I have been proposing here since some
years, is to use the garbage collector and get rid of most problems.

There is an intermediate strategy however, based on pools of memory.

Normally you have a set of related allocations, that can be done from a
memory pool, that is released in a single call when the module that uses
the pool is finished or when the activity associated with the pool is
finished.

A pool, for instance, is handy for a hash table with variable length
keys and variable lengths objects. When the hash table is destroyed, all
the memory that it required can be freed with a single call to pool destroy.


Many other applications are possible. Normally, all big applications are
built with modules that are more or less independent and could benefit
from pooled allocation. In a database application all memory used by one
query can be pooled and released when the query is done.

An example of pool management is in the Apache Runtime (APR) library.
There, the module apr_pools.c proposes a sophisticated interface for
pooled memory management. That library can be downloaded at no cost,
and its license is quite liberal. I adapted some of the code for the
container library, reducing the size of the module to just 1K (1076
bytes when compiled with lcc-win) from around 40K of the original.

The reduced interface proposes

newPool (create a pool)
PoolAlloc (allocate)
PoolDestroy (release memory)

I think all other stuff is not essential. No need for parent pools,
pools sub-allocation, sibling management, process shared pools, printf
versions that use a pool, and many other features like compatibility
with older versions... No need for that.

Obviously you may have different requirements, in that case use tha APR
library, a fine piece of software


jacob

 

[Ersek, Laszlo]

On Wed, 28 Apr 2010, jacob navia wrote:

[snip]

Normally you have a set of related allocations, that can be done from a
memory pool, that is released in a single call when the module that uses
the pool is finished or when the activity associated with the pool is
finished.
[snip]

An example of pool management is in the Apache Runtime (APR) library.

[snip]


Another example is GNU obstacks.

http://www.gnu.org/s/libc/manual/html_node/Obstacks.html

(Sorry for being tangential.)

Cheers,
lacos

 

[jacob navia]

Richard Harter a écrit :

though.

I find it useful to add two other functions to the interface.

PoolRealloc (resizes a block)
PoolClear (restores a pool to its initial state)

The desirability of a realloc should be obvious.

The effect of a PoolClear is a destroy followed by an create. In
my experience there are situations where using it simplifies
code. It also can be more efficient than the destroy/create
sequence.

The potential performance improvement of a PoolClear depends on
your implementation. In the implementation I use the pool
actually consists of a linked list of allocated blocks of
increasing size. (Allocation coming from a malloc like
allocator) PoolClear frees all allocated blocks in the pool
except the first, which it makes available for reuse.

For realloc, it is quite complicated, since the pool is implemented with
an array that implicitely stores the size of the allocated node
Now, resizing could involve eliminating a node and storing it elsewhere,
what is doable of course but not so evident. Maybe the best solution
would be to allocate new and release the old block.

Thanks for your contribution.

 

[spinoza1111]

Hi
I am not an IUT student, and I do not have a question, but I have some
answers.

The standard memory allocation strategy of C is to keep track of each
and every piece of RAM. This is an incredibly error prone activity, as
proved by the countless memory allocation bugs that appear in code built
using that strategy.

Another strategy, and the one that I have been proposing here since some
years, is to use the garbage collector and get rid of most problems.

There is an intermediate strategy however, based on pools of memory.

Normally you have a set of related allocations, that can be done from a
memory pool, that is released in a single call when the module that uses
the pool is finished or when the activity associated with the pool is
finished.

A pool, for instance, is handy for a hash table with variable length
keys and variable lengths objects. When the hash table is destroyed, all
the memory that it required can be freed with a single call to pool destroy.

Many other applications are possible. Normally, all big applications are
built with modules that are more or less independent and could benefit
from pooled allocation. In a database application all memory used by one
query can be pooled and released when the query is done.

An example of pool management is in the Apache Runtime (APR) library.
There, the module apr_pools.c proposes a sophisticated interface for
pooled memory management. That library can be downloaded at no cost,
and its license is quite liberal. I adapted some of the code for the
container library, reducing the size of the module to just 1K (1076
bytes when compiled with lcc-win) from around 40K of the original.

The reduced interface proposes

newPool (create a pool)
PoolAlloc (allocate)
PoolDestroy (release memory)

I think all other stuff is not essential. No need for parent pools,
pools sub-allocation, sibling management, process shared pools, printf
versions that use a pool, and many other features like compatibility
with older versions... No need for that.

Obviously you may have different requirements, in that case use tha APR
library, a fine piece of software

jacob

Nice wheel. Did you invent that?

Seriously: the goal should be to allow programmers to solve new
problems by supporting the right level of abstraction, and by
providing "pools of memory" you allow the applications programmer to
distract herself with "clever code".

Stroustrup made mistakes: we all do. But the "new" keyword is a thing
of beauty. Because his mentors (Nygaard and Dahl) were forced by
Denmark's socialist law to treat PEOPLE, "mere workers", as more
important than computers, Stroustrup created something useful.

Seebach's uninformed ramblings about the Bad Things that Might Happen
if we don't use int main(...) are an example of the transformation,
predicted by Adorno, of "science and reason" under administrative
pressure BACK to superstition. This transformation back to barbarism
is alleviated by the realization that all or most functions are
expressible by a "tuple" of facts, in which we are free of concern
about a resource that is no longer scarce.

We don't have to think like misers, foolish misers, whose main concern
is protecting a tool of production they don't own in hopes that some
capitalist will reward them for this solicitude, when in fact the
capitalist could really care less. If the union's demands mean we have
to add RAM, we add RAM, and to plead the expense is just foolish these
days as it was in the seventies relative to requirements.

My first (8K 1401) job was in a unionized computer center in which the
operators had been abused by nonunion programmers who thought it was
cute to crash on invalid punched card data, causing "jobs" to take
hours. Because I liked my minority coworkers and they, me, I
developed, within 8K, a method for recording errors as numbers on a
work card deck and a separate program to translate the errors into a
printed report. We then collectively decided on a four day, ten hour
work week because they had families and we were getting the work done
faster.

Dijkstra said somewhere that the Puritan falls in love with his pain,
his self-sacrifice to the groaning clock-god and a created scarcity,
for Dijkstra, like most Dutchmen, was an Arminian and not a Puritan in
outlook. Even if storage is genuinely scarce, as it was on my first
machines (an 8K IBM 1401 and then a 32K IBM 360/30), you first solve
the problem as if resources were unlimited, and then you sharply
separate concerns. On the 1401, I discovered that all six bits of a
"word" could be used for numbers. Pre-virtual storage, Cobol provided
manual overlays on the 360. Sir Clive Sinclair packed a Basic
interpreter in 2K and I squozed a Mouse compiler and runtime into 1K.

In each case, you did so by separating concerns and working at the
state of the art, not by reinventing the wheel.

You are on what I think is a fool's errand, because it arrives if
successful at the Palace of Objects, and other men have trod this path
before you. These efforts, it appears to me, stunt your personality.

 

[jacob navia]

spinoza1111 a écrit :

Nice wheel. Did you invent that?

As I stated in my article the code comes from the Apache Runtime.

Seriously: the goal should be to allow programmers to solve new
problems by supporting the right level of abstraction, and by
providing "pools of memory" you allow the applications programmer to
distract herself with "clever code".

Your point of view is that the programmer should have no control of anything, not even how memory us
allocated and used. This is the extreme opposite of the current C allocation schema where the
programmer must take care of each piece of RAM. What you consider "distractions", I consider
important issues that cazn be fine tuned by the programmer to avoid slowing down the application
with a general schema that will never fit perfectly to all applications.

As I said in my article, lcc-win provides a garbage collector, for people taht do not want to care
about memory allocation at all. And even with a GC you can't completely ignore the issue. Tyhe pools
solution provides with a more abstract interface than the C implementation without the problems of
the GC.

Stroustrup made mistakes: we all do. But the "new" keyword is a thing
of beauty. Because his mentors (Nygaard and Dahl) were forced by
Denmark's socialist law to treat PEOPLE, "mere workers", as more
important than computers, Stroustrup created something useful.

The "new" solution isn't possible in C since there are no automatic destructors that call the
"delete" for you. Please remember that C is NOT C++.

Seebach's uninformed ramblings about the Bad Things that Might Happen

[snip Seebach's problems]

My first (8K 1401) job was in a unionized computer center in which the

[snip personal remembrances ]

Dijkstra said somewhere that the Puritan falls in love with his pain,

[snip things that have nothing to do with memory pools]

You are on what I think is a fool's errand, because it arrives if
successful at the Palace of Objects, and other men have trod this path
before you. These efforts, it appears to me, stunt your personality.

I think that your "Palace of Objects" is just another paradigm of programming, like event oriented
programming, actors, constraint based programming, rule based programming, etc.

It is just another house in the block. No palace please.

 

[spinoza1111]

spinoza1111 a écrit :




As I stated in my article the code comes from the Apache Runtime.


Your point of view is that the programmer should have no control of anything, not even how memory us
allocated and used. This is the extreme opposite of the current C allocation schema where the
programmer must take care of each piece of RAM. What you consider "distractions", I consider
important issues that cazn be fine tuned by the programmer to avoid slowing down the application
with a general schema that will never fit perfectly to all applications.

Quite a broad assertion. I would say that for the same reason we
cannot "know" that a book is "bad", mere programmers can never have
enough applications knowledge to "know" how to optimize perfectly.

As I said in my article, lcc-win provides a garbage collector, for people taht do not want to care
about memory allocation at all. And even with a GC you can't completely ignore the issue. Tyhe pools
solution provides with a more abstract interface than the C implementation without the problems of
the GC.


The "new" solution isn't possible in C since there are no automatic destructors that call the
"delete" for you. Please remember that C is NOT C++.

Yes, but if you find a good solution to your problems, it will
converge on C++, and you will have reinvented the wheel, it seems to
me.

Seebach's uninformed ramblings about the Bad Things that Might Happen

[snip Seebach's problems]

My first (8K 1401) job was in a unionized computer center in which the

[snip personal remembrances ]

Their importance is that like Nygaard's experiences, they demonstrate
how free-market ideology leads to unsafe software and a failure to
separate concerns.

Dijkstra said somewhere that the Puritan falls in love with his pain,

[snip things that have nothing to do with memory pools]

Everything has something to do with something: the question is how
much. Here, I'm saying you are in love with the "pain" of trying to
make C what it is not. I'd prefer you focused on optimizing your
compiler's output code.

I think that your "Palace of Objects" is just another paradigm of programming, like event oriented
programming, actors, constraint based programming, rule based programming, etc.

It is just another house in the block. No palace please.

Sure, le Palais d'Objets is just another Odeon, just another Madeline.
But we must live somewhere, even in Paris. I would prefer something
that is already built. Or, as I put it in original verse:

There is a French girl who lives at the Ritz
Who does not shave under her armpits
I live at the Crillon
And I don't shave me own
So confusion to all foes of the girl at the Ritz.

Let me see if I can translate, you are welcome to improve it:

C'etait une jeune fille Francais qui vivre en grande Hotels
Qui ne rase pas sous les aisselles
Je vivre au la Crillon
Et je ne rasez pas le mien
Donc, l'honte à tous les ennemis de la jeune fille à l'hôtels

Monsieur, please be advised: unless you descend into the gutter with
that turd blossom Rosenau, all is meant in fun, but I defend myself.
If it floats your boat to invent a novel form of memory management, I
am not one to stop you.

 

[William Hughes]

spinoza1111 a écrit :

<snip>

"new" is of course wonderful. You can say "new fiddlestick"
and even if making a fiddlestick requires megabytes of code
and gigabytes of memory you don't have to worry about anything.

"new" is of course terrible. You say "new fiddlestick" but
making a fiddlestick may require megabytes of code
and gigabytes of memory and there is no way to know.

The "new" solution isn't possible in C since there are no automatic destructors that call the
"delete" for you.

No but surely adding destructors to C does not get
you to C++ any more than adding operator overloading
does. It seems to me that destructors work
quite well with your concept that garbage collection
is a good thing,


- William Hughes

 

[Moi]

Hi
I am not an IUT student, and I do not have a question, but I have some
answers.

[snipped]


Dijkstra said somewhere that the Puritan falls in love with his pain,
his self-sacrifice to the groaning clock-god and a created scarcity, for
Dijkstra, like most Dutchmen, was an Arminian and not a Puritan in

If you meant ewd224
( http://userweb.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD224.html )
, then you probably misunderstood it.
It is not about pain. It is about research and education, and how to combine them
in a joyful way.

HTH,
AvK