Memory allocation strategies

Discussion in 'C Programming' started by jacob navia, Apr 28, 2010.

  1. jacob navia

    jacob navia Guest

    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
    jacob navia, Apr 28, 2010
    #1
    1. Advertising

  2. 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
    Ersek, Laszlo, Apr 28, 2010
    #2
    1. Advertising

  3. jacob navia

    jacob navia Guest

    Richard Harter a écrit :
    > though.
    >> The reduced interface proposes
    >>
    >> newPool (create a pool)
    >> PoolAlloc (allocate)
    >> PoolDestroy (release memory)

    >
    > 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.
    jacob navia, Apr 28, 2010
    #3
  4. jacob navia

    spinoza1111 Guest

    On Apr 28, 5:56 pm, jacob navia <> wrote:
    > 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.
    spinoza1111, May 4, 2010
    #4
  5. jacob navia

    jacob navia Guest

    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.
    jacob navia, May 4, 2010
    #5
  6. jacob navia

    spinoza1111 Guest

    On May 4, 9:13 pm, jacob navia <> wrote:
    > 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.


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


    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.

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


    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.
    spinoza1111, May 4, 2010
    #6
  7. On May 4, 10:13 am, jacob navia <> wrote:
    > spinoza1111 a écrit :

    <snip>
    >
    > > Stroustrup made mistakes: we all do. But the "new" keyword is a thing
    > > of beauty.


    <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
    William Hughes, May 4, 2010
    #7
  8. jacob navia

    Moi Guest

    On Tue, 04 May 2010 04:21:58 -0700, spinoza1111 wrote:

    > On Apr 28, 5:56 pm, jacob navia <> wrote:
    >> 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
    Moi, May 5, 2010
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jacob navia

    Memory management strategies in C. (long)

    jacob navia, Aug 20, 2003, in forum: C Programming
    Replies:
    7
    Views:
    864
    Chris Torek
    Aug 23, 2003
  2. s.subbarayan

    Dynamic memory allocation and memory leak...

    s.subbarayan, Mar 18, 2005, in forum: C Programming
    Replies:
    10
    Views:
    698
    Eric Sosman
    Mar 22, 2005
  3. Ken
    Replies:
    24
    Views:
    3,860
    Ben Bacarisse
    Nov 30, 2006
  4. chris
    Replies:
    6
    Views:
    988
    chris
    Oct 28, 2005
  5. Bjarke Hammersholt Roune
    Replies:
    14
    Views:
    1,184
    Bjarke Hammersholt Roune
    Mar 6, 2011
Loading...

Share This Page