Is realloc good form ?

Discussion in 'C Programming' started by Guillaume Dargaud, Oct 18, 2007.

  1. Hello all,
    I have a 'good practice' question.
    Lately I've been using a lot of functions such as this:

    void Func(int Size, double *Array) {
    static double *Transformed=NULL;
    Transformed=realloc(Transformed, Size*sizeof(double));
    // Do something from Array to Transformed
    }

    Now if the value of Size changes a lot between calls, the resulting prog is
    poorly optimized (it reallocates each time). I'm ok with that.
    Ignoring the fact that the memory is never freed, if the value of Size
    changes seldom, does the call to realloc wastes time then ?
    --
    Guillaume Dargaud
    http://www.gdargaud.net/
     
    Guillaume Dargaud, Oct 18, 2007
    #1
    1. Advertising

  2. On Oct 18, 10:02 am, "Guillaume Dargaud"
    <> wrote:
    > Hello all,
    > I have a 'good practice' question.
    > Lately I've been using a lot of functions such as this:
    >
    > void Func(int Size, double *Array) {
    > static double *Transformed=NULL;
    > Transformed=realloc(Transformed, Size*sizeof(double));
    > // Do something from Array to Transformed
    >
    > }
    >
    > Now if the value of Size changes a lot between calls, the resulting prog is
    > poorly optimized (it reallocates each time). I'm ok with that.
    > Ignoring the fact that the memory is never freed, if the value of Size
    > changes seldom, does the call to realloc wastes time then ?


    It depends. realloc will often be clever enough to realise that it can
    just use the previous block of data without any change. So if you pass
    in the same Size or similar Size values (like 10000, 10001, 9999) it
    will be fast. However, if a new block is allocated, all the data will
    be copied from the previous block to the new block, because that is
    what realloc does. That might be quite wasteful.

    You might just add another variable "static int allocatedSize = 0",
    compare new and old size and only realloc when it gets bigger.
     
    christian.bau, Oct 18, 2007
    #2
    1. Advertising

  3. Guillaume Dargaud

    Guest

    On Oct 18, 1:28 pm, "christian.bau" <>
    wrote:
    > It depends. realloc will often be clever enough to realise that it can
    > just use the previous block of data without any change. So if you pass
    > in the same Size or similar Size values (like 10000, 10001, 9999) it
    > will be fast. However, if a new block is allocated, all the data will
    > be copied from the previous block to the new block, because that is
    > what realloc does. That might be quite wasteful.


    realloc tries not to copy the data, just resize the available block of
    memory.
    > Note that realloc() *may* move the memory allocation resulting in a different return value than ptr.
     
    , Oct 18, 2007
    #3
  4. On Oct 18, 11:28 am, "christian.bau"
    <> wrote:
    > On Oct 18, 10:02 am, "Guillaume Dargaud"
    >
    > <> wrote:
    > > Hello all,
    > > I have a 'good practice' question.
    > > Lately I've been using a lot of functions such as this:

    >
    > > void Func(int Size, double *Array) {
    > > static double *Transformed=NULL;
    > > Transformed=realloc(Transformed, Size*sizeof(double));
    > > // Do something from Array to Transformed

    >
    > > }

    >
    > > Now if the value of Size changes a lot between calls, the resulting prog is
    > > poorly optimized (it reallocates each time). I'm ok with that.
    > > Ignoring the fact that the memory is never freed, if the value of Size
    > > changes seldom, does the call to realloc wastes time then ?


    If you're ok with the fact that the function calls realloc each time,
    then which waste of time are you worried about ?

    Leaving your question aside there are a couple of problems with the
    function. It would be better to make Size of type size_t. You need to
    make sure that the expression Size*sizeof(double) does not overflow
    before you pass it to realloc.

    > You might just add another variable "static int allocatedSize = 0",
    > compare new and old size and only realloc when it gets bigger.


    I second that apart from the fact that allocatedSize also needs to be
    size_t.
     
    Spiros Bousbouras, Oct 18, 2007
    #4
  5. Guillaume Dargaud

    Mark Bluemel Guest

    wrote:

    > realloc tries not to copy the data, just resize the available block of
    > memory.


    Does the standard enforce this? Otherwise you are simply discussing what
    some (possibly all, but I doubt you could prove that) implementations do.
     
    Mark Bluemel, Oct 18, 2007
    #5
  6. Mark Bluemel said:

    > wrote:
    >
    >> realloc tries not to copy the data, just resize the available block of
    >> memory.

    >
    > Does the standard enforce this?


    No.

    > Otherwise you are simply discussing what
    > some (possibly all, but I doubt you could prove that) implementations do.


    Right.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Oct 18, 2007
    #6
  7. Guillaume Dargaud

    CBFalconer Guest

    wrote:
    > "christian.bau" <> wrote:
    >
    >> It depends. realloc will often be clever enough to realise that
    >> it can just use the previous block of data without any change.
    >> So if you pass in the same Size or similar Size values (like
    >> 10000, 10001, 9999) it will be fast. However, if a new block is
    >> allocated, all the data will be copied from the previous block
    >> to the new block, because that is what realloc does. That might
    >> be quite wasteful.

    >
    > realloc tries not to copy the data, just resize the available
    > block of memory.


    That depends on the malloc/free/realloc package, and is not
    guaranteed. One package that goes to lengths to avoid copying is
    nmalloc for DJGPP and similar, available at:

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

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Oct 18, 2007
    #7
  8. Guillaume Dargaud wrote:
    >
    > Hello all,
    > I have a 'good practice' question.
    > Lately I've been using a lot of functions such as this:
    >
    > void Func(int Size, double *Array) {
    > static double *Transformed=NULL;
    > Transformed=realloc(Transformed, Size*sizeof(double));
    > // Do something from Array to Transformed
    > }
    >
    > Now if the value of Size changes a lot between calls, the resulting prog is
    > poorly optimized (it reallocates each time). I'm ok with that.
    > Ignoring the fact that the memory is never freed, if the value of Size
    > changes seldom, does the call to realloc wastes time then ?


    I would suspect that any decent realloc() would, once it sees that
    the old size and new size are identical, simply return the current
    pointer. (It must determine the old size at some point, in order
    to perform its duties. Even a suboptimal "call malloc, memcpy the
    buffer, and then free the original" routine needs to know the old
    size.)

    If you're that concerned, you can always keep track of the old size,
    and skip the realloc() if it didn't change:

    void Func(int Size, double *Array)
    {
    static double *Transformed = NULL;
    static int OldSize = 0;

    ASSERT( Size != 0 ); /* What do we want to do about zero size? */

    if ( Size != OldSize )
    {
    Transformed = realloc(Transformed, Size*sizeof(*Transformed));
    OldSize = Size;
    }

    /* Do something from Array to Transformed */

    }

    If you're not concerned about "wasted memory", you could even
    change the realloc-condition to:

    if ( Size > OldSize )

    Then, it will only realloc if the buffer needs to grow.

    Finally, if you don't need the current contents of Transformed,
    it may be more efficient to call free/malloc instead, as this
    skips the copy.

    --
    +-------------------------+--------------------+-----------------------+
    | Kenneth J. Brody | www.hvcomputer.com | #include |
    | kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
    +-------------------------+--------------------+-----------------------+
    Don't e-mail me at: <mailto:>
     
    Kenneth Brody, Oct 19, 2007
    #8
  9. Kenneth Brody <> writes:
    [...]
    > I would suspect that any decent realloc() would, once it sees that
    > the old size and new size are identical, simply return the current
    > pointer. (It must determine the old size at some point, in order
    > to perform its duties. Even a suboptimal "call malloc, memcpy the
    > buffer, and then free the original" routine needs to know the old
    > size.)

    [...]

    Very likely, but it's not guaranteed and code shouldn't depend on it.

    The system needn't keep track of the requested size of an allocated
    chunk of memory; the size is typically rounded up somehow, and the
    system need only remember the rounded-up size. (If you requested,
    say, 900 bytes, allocating 1024 bytes in malloc() and copying 1024
    bytes in realloc() shouldn't cause any problems.)

    Also, even if you try to reallocate the same size, I can imagine
    realloc() noticing that the chunk is in the middle of a region of
    mostly free space, and that it can help future allocations by
    relocating it so it's adjacent to other allocated space. I don't know
    whether any actual allocators do this.

    --
    Keith Thompson (The_Other_Keith) <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."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Oct 19, 2007
    #9
  10. On Oct 19, 8:32 pm, Keith Thompson <> wrote:

    > Also, even if you try to reallocate the same size, I can imagine
    > realloc() noticing that the chunk is in the middle of a region of
    > mostly free space, and that it can help future allocations by
    > relocating it so it's adjacent to other allocated space. I don't know
    > whether any actual allocators do this.


    I have used implementations used for debugging that would _always_
    allocate a new block on purpose. That makes bugs where someone didn't
    expect a changed pointer more obvious.
     
    christian.bau, Oct 20, 2007
    #10
  11. Keith Thompson wrote:
    >
    > Kenneth Brody <> writes:
    > [...]
    > > I would suspect that any decent realloc() would, once it sees that
    > > the old size and new size are identical, simply return the current
    > > pointer. (It must determine the old size at some point, in order
    > > to perform its duties. Even a suboptimal "call malloc, memcpy the
    > > buffer, and then free the original" routine needs to know the old
    > > size.)

    > [...]
    >
    > Very likely, but it's not guaranteed and code shouldn't depend on it.


    True. It sounded like the OP was concerned as to the impact on
    calling realloc() over and over with the same size. (Of course,
    if he's that concerned, he should probably change the logic to
    one where he has control over such things, such as my example of
    keeping track of the previously-requested size.)

    > The system needn't keep track of the requested size of an allocated
    > chunk of memory; the size is typically rounded up somehow, and the
    > system need only remember the rounded-up size. (If you requested,
    > say, 900 bytes, allocating 1024 bytes in malloc() and copying 1024
    > bytes in realloc() shouldn't cause any problems.)


    True. But it doesn't really change what I said, as you could simply
    take the calculated buffer size, rather than the actual requested
    size, and compare those.

    > Also, even if you try to reallocate the same size, I can imagine
    > realloc() noticing that the chunk is in the middle of a region of
    > mostly free space, and that it can help future allocations by
    > relocating it so it's adjacent to other allocated space. I don't know
    > whether any actual allocators do this.


    I don't believe I've seen such an implementation, either. The
    question there becomes how much overhead is involved in making such
    a determination, and is it worth it? (Only the implementor could
    answer that question.)

    I have seen implementations take a shrinking realloc(), and merge
    the released space with an adjoining free chunk, creating a single,
    larger chunk. (I would suspect that this is relatively common.)

    --
    +-------------------------+--------------------+-----------------------+
    | Kenneth J. Brody | www.hvcomputer.com | #include |
    | kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
    +-------------------------+--------------------+-----------------------+
    Don't e-mail me at: <mailto:>
     
    Kenneth Brody, Oct 20, 2007
    #11
  12. "christian.bau" wrote:
    >
    > On Oct 19, 8:32 pm, Keith Thompson <> wrote:
    >
    > > Also, even if you try to reallocate the same size, I can imagine
    > > realloc() noticing that the chunk is in the middle of a region of
    > > mostly free space, and that it can help future allocations by
    > > relocating it so it's adjacent to other allocated space. I don't know
    > > whether any actual allocators do this.

    >
    > I have used implementations used for debugging that would _always_
    > allocate a new block on purpose. That makes bugs where someone didn't
    > expect a changed pointer more obvious.


    Sounds reasonable, especially if the old block's contents are trashed
    at the same time.

    --
    +-------------------------+--------------------+-----------------------+
    | Kenneth J. Brody | www.hvcomputer.com | #include |
    | kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
    +-------------------------+--------------------+-----------------------+
    Don't e-mail me at: <mailto:>
     
    Kenneth Brody, Oct 20, 2007
    #12
  13. Guillaume Dargaud

    CBFalconer Guest

    Kenneth Brody wrote:
    >

    .... snip ...
    >
    > I have seen implementations take a shrinking realloc(), and merge
    > the released space with an adjoining free chunk, creating a single,
    > larger chunk. (I would suspect that this is relatively common.)


    Here is an extraction from nmalloc.c, with most code removed,
    showing the cases handled to avoid any unnecessary memory copying.

    /* if decreasing simply reduce size and move excess to free */
    else if (szneed > ((ulong)(INT_MAX - 65536))) {
    /* reject excessive size request */
    p = NULL; goto exeunt;
    }
    else if (ISFREE(m->next) &&
    (szneed <= (m->sz + m->next->sz)) ) {
    /* the 'next' block is free and adequate so use it */
    /* else m is the oversized return block */
    }
    else if ((lastsbrk == m->next) &&
    ((szneed + MINSAVE) <= (m->sz + lastsbrk->sz)) ) {
    /* lastsbrk is adequate and adjacent so use it */
    }
    else if (ISFREE(m->prev) &&
    (szneed <= (m->sz + m->prev->sz)) ) {
    /* the 'prev' block is free and adequate so use it */
    }
    else if ((b = searchfree(szneed))) {
    /* An adequate free block exists, copy over, free old */
    }
    else if (lastsbrk &&
    ((szneed + MINSAVE) <= lastsbrk->sz) ) {
    DBGPRTR(EOL " Realloc is copying into lastsbrk");
    }
    /* else malloc new size, copy data, and free old */
    else if ((m1 = extendsbrk(szneed))) {
    if (lastsbrk == m->next) {
    DBGPRTR(EOL " Realloc is now using lastsbrk extended");
    }
    else {
    /* At this point lastsbrk is adequate size */
    /* split off, copy over, and free old */
    }
    }
    else m = NULL; /* failure */

    You can find the complete code on my site (URL in sig).

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>


    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Oct 20, 2007
    #13
  14. "Kenneth Brody" <> a écrit dans le message de news:
    ...
    > Guillaume Dargaud wrote:
    >>
    >> Hello all,
    >> I have a 'good practice' question.
    >> Lately I've been using a lot of functions such as this:
    >>
    >> void Func(int Size, double *Array) {
    >> static double *Transformed=NULL;
    >> Transformed=realloc(Transformed, Size*sizeof(double));
    >> // Do something from Array to Transformed
    >> }
    >>
    >> Now if the value of Size changes a lot between calls, the resulting prog
    >> is
    >> poorly optimized (it reallocates each time). I'm ok with that.
    >> Ignoring the fact that the memory is never freed, if the value of Size
    >> changes seldom, does the call to realloc wastes time then ?

    >
    > I would suspect that any decent realloc() would, once it sees that
    > the old size and new size are identical, simply return the current
    > pointer. (It must determine the old size at some point, in order
    > to perform its duties. Even a suboptimal "call malloc, memcpy the
    > buffer, and then free the original" routine needs to know the old
    > size.)
    >
    > If you're that concerned, you can always keep track of the old size,
    > and skip the realloc() if it didn't change:
    >
    > void Func(int Size, double *Array)
    > {
    > static double *Transformed = NULL;
    > static int OldSize = 0;
    >
    > ASSERT( Size != 0 ); /* What do we want to do about zero size? */
    >
    > if ( Size != OldSize )
    > {
    > Transformed = realloc(Transformed, Size*sizeof(*Transformed));
    > OldSize = Size;
    > }
    >
    > /* Do something from Array to Transformed */
    >
    > }
    >
    > If you're not concerned about "wasted memory", you could even
    > change the realloc-condition to:
    >
    > if ( Size > OldSize )
    >
    > Then, it will only realloc if the buffer needs to grow.
    >
    > Finally, if you don't need the current contents of Transformed,
    > it may be more efficient to call free/malloc instead, as this
    > skips the copy.


    In order to minimize the number of calls to realloc and if memory wastage of
    up to a factor of 2 is not an issue, you can round Size up to the next power
    of 2 before comparing to Oldsize:

    int Newsize = Size - 1;
    Newsize |= (Newsize >> 1);
    Newsize |= (Newsize >> 2);
    Newsize |= (Newsize >> 4);
    Newsize |= (Newsize >> 8);
    Newsize |= (Newsize >> 16);
    Newsize += 1;

    if (Newsize > Oldsize) {
    Transformed = realloc(Transformed, Newsize * sizeof(*Transformed));
    OldSize = Newsize;
    }

    As a sizenote, you naming convention is very unusual and quite confusing.
    How do you name local loop counters? I, J, K?

    --
    Chqrlie.
     
    Charlie Gordon, Oct 22, 2007
    #14
    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. Mr T
    Replies:
    0
    Views:
    600
  2. Eitan Michaelson

    Impossible Leak realloc

    Eitan Michaelson, Jun 27, 2003, in forum: C++
    Replies:
    11
    Views:
    1,222
  3. Jonathan.Bailleul

    g++ 3.2.2 realloc bug?

    Jonathan.Bailleul, Aug 8, 2003, in forum: C++
    Replies:
    3
    Views:
    641
    John Harrison
    Aug 8, 2003
  4. Bren
    Replies:
    8
    Views:
    2,045
    Stephen Howe
    Sep 4, 2003
  5. Henrik J

    Realloc a struct **

    Henrik J, Nov 10, 2003, in forum: C++
    Replies:
    1
    Views:
    415
    David White
    Nov 10, 2003
Loading...

Share This Page