Increase memory buffer with realloc or malloc?

[Jef Driesen]

Hi,

Is there any difference in increasing the size of a dynamically
allocated buffer with realloc() or malloc()'ing a new buffer and
memcpy() the old data?

I can imagine realloc() can be more efficient than a malloc+memcpy
solution in some cases. For instance when there is enough free space
available immediately after the existing memory block, there is probably
no need to malloc() a new buffer and copy the data over. I am aware that
this is likely implementation dependent, but is there an advantage over
using realloc for typical implementations/platforms?

One of the reasons I'm asking this, is that sometimes I need to increase
the buffer at its start. If implemented with realloc(), I would need to
do an additional memmove() to move the existing data to the end. Thus in
that case the data needs to be moved anyway, and I'm not sure what is
more efficient in this situation.

Jef

 

[Morris Keesan]

Hi,

Is there any difference in increasing the size of a dynamically
allocated buffer with realloc() or malloc()'ing a new buffer and
memcpy() the old data?

I can imagine realloc() can be more efficient than a malloc+memcpy
solution in some cases. For instance when there is enough free space
available immediately after the existing memory block, there is probably
no need to malloc() a new buffer and copy the data over. I am aware that
this is likely implementation dependent, but is there an advantage over
using realloc for typical implementations/platforms?

For typical implementations, there's a big advantage to using realloc(),
because the implementation can tell when the the buffer can be resized,
and knows when copying is necessary.

One of the reasons I'm asking this, is that sometimes I need to increase
the buffer at its start. If implemented with realloc(), I would need to
do an additional memmove() to move the existing data to the end. Thus in
that case the data needs to be moved anyway, and I'm not sure what is
more efficient in this situation.

If you're going to move the data to the end of the buffer, it seems to me
that there's no reason to use realloc, and it's likely to be less efficient
than just calling malloc() and memcpy(), because in many cases realloc()
will be doing an extra unnecessary copy.

But perhaps you should examine your algorithm, and see if there's a way you
can eliminate, or reduce, the need to resize your allocated buffers.

 

[Eric Sosman]

Hi,

Is there any difference in increasing the size of a dynamically
allocated buffer with realloc() or malloc()'ing a new buffer and
memcpy() the old data?

I can imagine realloc() can be more efficient than a malloc+memcpy
solution in some cases. For instance when there is enough free space
available immediately after the existing memory block, there is probably
no need to malloc() a new buffer and copy the data over. I am aware that
this is likely implementation dependent, but is there an advantage over
using realloc for typical implementations/platforms?

Yes, that's it: realloc() may be able to avoid the copy, at
least some of the time.

One of the reasons I'm asking this, is that sometimes I need to increase
the buffer at its start. If implemented with realloc(), I would need to
do an additional memmove() to move the existing data to the end. Thus in
that case the data needs to be moved anyway, and I'm not sure what is
more efficient in this situation.

There's no "Would realloc(ptr,newsiz) be forced to copy if
I were to call it right now?" query you can make.

If you used some data structure other than "One big blob,"
it's possible you could handle insert-at-front or -in-middle
without all that copying. But I don't know what your program
looks like.

 

[Jef Driesen]

If you're going to move the data to the end of the buffer, it seems to me
that there's no reason to use realloc, and it's likely to be less efficient
than just calling malloc() and memcpy(), because in many cases realloc()
will be doing an extra unnecessary copy.

That confirms my assumption.

But perhaps you should examine your algorithm, and see if there's a way you
can eliminate, or reduce, the need to resize your allocated buffers.

In most cases I know the final size in advance and I do pre-allocate the
entire buffer once. Thus appending or prepending data only requires a
memcpy() to the right location, which is efficient. But the final amount
of data is not always known in advance, and in those cases the buffer
needs to be enlarged. I know I can use certain strategies (like doubling
the size each time) to reduce the number of malloc() calls, but that is
independent of the realloc vs malloc question.

 

[Jef Driesen]

There's no "Would realloc(ptr,newsiz) be forced to copy if
I were to call it right now?" query you can make.

A realloc() that fails if the memory buffer cannot be enlarged without
copying would have been even better. That way you could implement the
fallback with malloc() and memcpy() manually. But that one doesn't exist
either

If you used some data structure other than "One big blob,"
it's possible you could handle insert-at-front or -in-middle
without all that copying. But I don't know what your program
looks like.

I'm implementing a bytebuffer object, thus the "one big blob"
representation makes sense here. The bytebuffer objects are typically
filled by appending or prepending data packets. This could be
implemented with another datastructure like a linked list, but that
would make the processing of the final buffer much more complicated
without a continuous buffer.

I do pre-allocate the entire buffer whenever its final size is known in
advance. Knowing the final size in advance is the typical case in my
code, but not always.

 

[Eric Sosman]

A realloc() that fails if the memory buffer cannot be enlarged without
copying would have been even better. That way you could implement the
fallback with malloc() and memcpy() manually. But that one doesn't exist
either

Long ago I worked on a memory-management package that had
such a query, in the form "How much free space immediately
follows the allocation pointed to by `ptr'?" That turned out
to be a most unfortunate design choice, as we discovered when
we first ported the code to a 64-bit platform, and the query
was made of the "last" allocated block ... I changed the API
so the query was "Is the block at `ptr' followed by at least
`N' free bytes?" and all was well again.

But, as you say, no query of this type exists for the
malloc()/calloc()/realloc()/free() suite.

I'm implementing a bytebuffer object, thus the "one big blob"
representation makes sense here. The bytebuffer objects are typically
filled by appending or prepending data packets. This could be
implemented with another datastructure like a linked list, but that
would make the processing of the final buffer much more complicated
without a continuous buffer.

A classic trade-off: You simplify the accesses at the cost
of the extra copying, or you avoid the copying at the cost of
complicating the accesses. Sometimes you get the bear; sometimes
the bear gets you.

I do pre-allocate the entire buffer whenever its final size is known in
advance. Knowing the final size in advance is the typical case in my
code, but not always.

Some idea of the original estimate's success rate should
probably enter into the decision about what to do when it's
wrong.

 

[karthikbalaguru]

Hi,

Is there any difference in increasing the size of a dynamically
allocated buffer with realloc() or malloc()'ing a new buffer and
memcpy() the old data?

I can imagine realloc() can be more efficient than a malloc+memcpy
solution in some cases. For instance when there is enough free space
available immediately after the existing memory block, there is probably
no need to malloc() a new buffer and copy the data over. I am aware that
this is likely implementation dependent, but is there an advantage over
using realloc for typical implementations/platforms?

One of the reasons I'm asking this, is that sometimes I need to increase
the buffer at its start. If implemented with realloc(), I would need to
do an additional memmove() to move the existing data to the end. Thus in
that case the data needs to be moved anyway, and I'm not sure what is
more efficient in this situation.

Obviously it is malloc & memcpy compared to realloc in this scenario
as you
are sometimes required to increase the buffer at the start & existing
data at the end.

Karthik Balaguru

 

[Jef Driesen]

I'll disagree. There's a substantial chance that if realloc() fails
when it has to copy because of some philosophy like "death before
inefficiency", that the fallback with malloc() and memcpy() will
fail also. This is especially true if the memory chunk is over
half of available memory and you try to enlarge it. There isn't
enough memory to hold the old and the new chunks. If you freed the
old chunk, there might be enough contiguous memory to allocate the
new chunk, but some of the new chunk is *before* the old one, so
realloc() would have to do an overlapping copy (with, say, memmove()).

I assumed that realloc() implementations can only grow the memory block
towards the end of the block, but not the start. If that's true, it
would never have to memmove/memcpy() the original data. Except when it
had to allocate a new block of course. But I have no idea if that
assumption is valid.

Anyway, in my application this wouldn't be a real problem, because the
memory blocks are much smaller than the available memory

The realloc "query" that was mentioned above has the problem that
between the query and the actual allocation, the situation might have
changed. For instance another thread could have allocated the block that
was reported as free. That's why I brought up my realloc with failure
approach.