Is realloc good form ?

[Guillaume Dargaud]

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 ?

 

[christian.bau]

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.

 

[vipvipvipvip.ru]

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.

 

[Spiros Bousbouras]

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.

 

[Mark Bluemel]

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.

 

[Richard Heathfield]

Mark Bluemel said:

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.

 

[CBFalconer]

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

 

[Kenneth Brody]

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:[email protected]>

 

[Keith Thompson]

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.

 

[christian.bau]

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.

 

[Kenneth Brody]

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:[email protected]>

 

[Kenneth Brody]

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:[email protected]>

 

[CBFalconer]

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

 

[Charlie Gordon]

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?