realloc but not copy

[ivan.leben]

Let's say I have a piece of allocated memory which I want to expand and
reuse if possible or allocate in a different part of RAM if resizing is
not possible, however, in the latter case I don't care about the old
data and I don't need to copy it to the new location. Is there a
standard function that could do that? As far as I understand the
description of the realloc() function, it _always_ copies the data to
the new location, even if that is not desired. Can I somehow just
_check_ if the expansion is possible and invoke a new malloc() myself
in case it is not? I'd like this operation to be as fast as possible
because the size of the memory I need is very large.

greets,
Ivan Leben

 

[Richard Heathfield]

(e-mail address removed) said:

Let's say I have a piece of allocated memory which I want to expand and
reuse if possible or allocate in a different part of RAM if resizing is
not possible, however, in the latter case I don't care about the old
data and I don't need to copy it to the new location. Is there a
standard function that could do that?

No. I guess ISO missed a trick there. It would have been easy enough to
support, obviously, but... no.

 

[Al Balmer]

Let's say I have a piece of allocated memory which I want to expand and
reuse if possible or allocate in a different part of RAM if resizing is
not possible, however, in the latter case I don't care about the old
data and I don't need to copy it to the new location. Is there a
standard function that could do that? As far as I understand the
description of the realloc() function, it _always_ copies the data to
the new location, even if that is not desired. Can I somehow just
_check_ if the expansion is possible and invoke a new malloc() myself
in case it is not? I'd like this operation to be as fast as possible
because the size of the memory I need is very large.

Since you don't care about the old data, you can always free it and
allocate the new area.

 

[websnarf]

Let's say I have a piece of allocated memory which I want to expand and
reuse if possible or allocate in a different part of RAM if resizing is
not possible, however, in the latter case I don't care about the old
data and I don't need to copy it to the new location. Is there a
standard function that could do that?

Short answer: no.

[...] As far as I understand the
description of the realloc() function, it _always_ copies the data to
the new location, even if that is not desired. Can I somehow just
_check_ if the expansion is possible and invoke a new malloc() myself
in case it is not? I'd like this operation to be as fast as possible
because the size of the memory I need is very large.

Well, if a realloc fails, then a malloc then copy, then free should
probably fail too (ignoring multitasking and weird heap
implementations.)

I had a similar issue in implementing the Better String Library. For
reasonably large allocations, the performance is usually going to be
limited by the copy. Now, if your data is anything like Bstrlib's the
problem is that the allocated buffer is usually larger than the amount
of valid data that its holding. But realloc doesn't know this, and so
will copy the entire buffer on realloc if a data move is required.

There is a possible approach here that will work on some heap designs.
You can first reallocate the allocation to the *smallest* possible
containing buffer (removing any unnecessary tail data) *then*
reallocate it to your intended final buffer size. As you can see, this
should avoid the unnecessarily large copies. One problem is that it
calls realloc() twice, and realloc is not guaranteed to keep the buffer
in the same spot even if you are making the size smaller. Another
problem is that realloc may not actually shrink the buffer when you
reallocate it with the smaller size. But if, instead, the heap behaves
in the ideal way that we all hope, then this will perform the
equivalent of a minimal copy on realloc so long as your valid data is
packed toward the beginning of your allocation.

In the Better String Library, I decided that I could not rely on good
heap design, and instead went with a probabilistic model. I basically
guessed that realloc()'s cause a shift 7 out of 8 times (which I
estimated by doing a random malloc/free/realloc test on a couple of
heap implementations) and so I just do the calculation of what the
expected cost of a straight realloc() versus a malloc() shortcopy and
free(), and I choose whichever strategy is like to be faster.

 

[Miquel van Smoorenburg]

Let's say I have a piece of allocated memory which I want to expand and
reuse if possible or allocate in a different part of RAM if resizing is
not possible, however, in the latter case I don't care about the old
data and I don't need to copy it to the new location. Is there a
standard function that could do that? As far as I understand the
description of the realloc() function, it _always_ copies the data to
the new location, even if that is not desired. Can I somehow just
_check_ if the expansion is possible and invoke a new malloc() myself
in case it is not? I'd like this operation to be as fast as possible
because the size of the memory I need is very large.

It depends on your OS if this is a problem or not.

Linux has mremap(), and glibc's realloc() uses this. It means that
in almost all cases, realloc() doesn't have to copy memory even if
it moves the data around: the kernel does it by remapping memory.
Because of this Linux's realloc is magnitudes faster than, say, BSD's.

You can also use mmap(MAP_ANONYMOUS) and mremap() directly if
you want, giving you some more control.

Mike.

 

[CBFalconer]

.... snip ...

I had a similar issue in implementing the Better String Library.
For reasonably large allocations, the performance is usually going
to be limited by the copy. Now, if your data is anything like
Bstrlib's the problem is that the allocated buffer is usually
larger than the amount of valid data that its holding. But
realloc doesn't know this, and so will copy the entire buffer on
realloc if a data move is required.

That is a problem better handled in the realloc function proper.
nmalloc goes to lengths to avoid any copying during realloc. It
can do this because it maintains quickly accessible knowledge of
the size and availability of adjacent memory chunks.

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

 

[robertwessel2]

Let's say I have a piece of allocated memory which I want to expand and
reuse if possible or allocate in a different part of RAM if resizing is
not possible, however, in the latter case I don't care about the old
data and I don't need to copy it to the new location. Is there a
standard function that could do that? As far as I understand the
description of the realloc() function, it _always_ copies the data to
the new location, even if that is not desired. Can I somehow just
_check_ if the expansion is possible and invoke a new malloc() myself
in case it is not? I'd like this operation to be as fast as possible
because the size of the memory I need is very large.

There's no way to do this in standard C.

(OT)

Your implementation may provide a _expand() or _bexpand() (or similar)
function which would enable this (typically these would fail if the
existing area could not be expanded as requested, at which point you
could do a free/malloc yourself).

 

[Eric Sosman]

Let's say I have a piece of allocated memory which I want to expand and
reuse if possible or allocate in a different part of RAM if resizing is
not possible, however, in the latter case I don't care about the old
data and I don't need to copy it to the new location. Is there a
standard function that could do that? As far as I understand the
description of the realloc() function, it _always_ copies the data to
the new location, even if that is not desired. Can I somehow just
_check_ if the expansion is possible and invoke a new malloc() myself
in case it is not? I'd like this operation to be as fast as possible
because the size of the memory I need is very large.

free(ptr);
ptr = malloc(newsize);
if (ptr == NULL) ...

Or to look at it another way: Why do you prefer to re-use
the memory already allocated, as opposed to some other piece of
memory? Since the former contents are of no importance, what
difference does it make if you get "old" or "new" space?

 

[robertwessel2]

free(ptr);
ptr = malloc(newsize);
if (ptr == NULL) ...

Or to look at it another way: Why do you prefer to re-use
the memory already allocated, as opposed to some other piece of
memory? Since the former contents are of no importance, what
difference does it make if you get "old" or "new" space?

One can easily envision a data structure that needs to be (relatively
expensively) rebuilt if moved, but that can extended in a
straight-forward fashion. The OP would like to avoid the pointless
copying of the existing data if he's only going to have to rebuild it
anyway, but be able to avoid the rebuild if an "extend" is possible.

An object large enough to have significant pieces paged out may also be
easier/faster to recreate than copy.

A better solution may be to break down what's likely a large and
complex data structure into smaller pieces most of which could avoid
needing to be extended as things grow thus eliminating the need to ever
move them).

 

[Eric Sosman]

One can easily envision a data structure that needs to be (relatively
expensively) rebuilt if moved, but that can extended in a
straight-forward fashion. The OP would like to avoid the pointless
copying of the existing data if he's only going to have to rebuild it
anyway, but be able to avoid the rebuild if an "extend" is possible.

The only such data structures I can think of off-hand are
contiguous and have embedded absolute pointers. That's a rather
odd combination! If you've got pointers, where's the need for
contiguity? And if you've got contiguity, links (all known to
be within the contiguous region, remember) can be relative offsets
rather than pointers.

Note that I'm only saying such a data structure is "odd," not
that it's impossible. I myself ran across such an arrangement,
just (let's see ...) nineteen years ago. IMHO, that particular
data structure could and should have been arranged differently,
but I didn't have the freedom to make the rules.

Anyhow, it may be easy to envision a must-be-contiguous data
structure that uses embedded absolute self-links, but for any such
I bet it's equally easy to envision an alternative that removes the
requirement for contiguity or for absolute pointers. (Maybe both!)

An object large enough to have significant pieces paged out may also be
easier/faster to recreate than copy.

Note that the O.P. specifically said he *doesn't* want to copy
the data; a copy would be (for reasons not divulged) useless to him.
That's what's behind the question I posed to him: Why does he care
whether the new object does or doesn't overlap the addresses of
the old?

A better solution may be to break down what's likely a large and
complex data structure into smaller pieces most of which could avoid
needing to be extended as things grow thus eliminating the need to ever
move them).

Right: The easily-envisioned superior alternative (until and
unless we learn more about the requirements, anyhow).

 

[James Antill]

That is a problem better handled in the realloc function proper.
nmalloc goes to lengths to avoid any copying during realloc. It
can do this because it maintains quickly accessible knowledge of
the size and availability of adjacent memory chunks.

realloc() can't know, that's the problem. You have:

X = size program is using
Y = size allocated from malloc/realloc
Z = new desired size

ptr = realloc(Y_ptr, Z); /* realloc can't know X */

....at the extreme X could be 1, and Y could be "big" with Z being only
slightly "bigger". For network IO it's not even that weird a case, but
then that's one reason why Vstr is designed the way it is (it doesn't need
continuous blocks of memory).

 

[CBFalconer]

realloc() can't know, that's the problem. You have:

X = size program is using
Y = size allocated from malloc/realloc
Z = new desired size

ptr = realloc(Y_ptr, Z); /* realloc can't know X */

...at the extreme X could be 1, and Y could be "big" with Z being
only slightly "bigger". For network IO it's not even that weird a
case, but then that's one reason why Vstr is designed the way it
is (it doesn't need continuous blocks of memory).

Actually assuming X < Y < Z, with nmalloc you can handle that
without unneeded copying:

if (tmp = realloc(Yptr, X)) Yptr = tmp;
if (tmp = realloc(Yptr, Z)) Yptr = tmp;
else {
/* handle allocation failure */
}

Actually the reduction in size need not check for realloc failure,
since it will always succeed barring damage to the memory arena. I
am referring to nmalloc here, not the general case.

However the case X < Y should normally not arise with
semi-intelligent programming, making the problem moot.

 

[Scott Fluhrer]

One can easily envision a data structure that needs to be (relatively
expensively) rebuilt if moved, but that can extended in a
straight-forward fashion. The OP would like to avoid the pointless
copying of the existing data if he's only going to have to rebuild it
anyway, but be able to avoid the rebuild if an "extend" is possible.

Another possiblity is that he knows that he just accessed the old buffer
(and so a good portion is likely to be sitting in the cache) -- if he
switches to a new buffer, he'll take a bunch of cache hits.

An object large enough to have significant pieces paged out may also be
easier/faster to recreate than copy.

A better solution may be to break down what's likely a large and
complex data structure into smaller pieces most of which could avoid
needing to be extended as things grow thus eliminating the need to ever
move them).

Agreed; if the problem can be restructured in this way, this would be a
better solution
[/QUOTE]

 

[Frederick Gotham]

Ivan posted:

Let's say I have a piece of allocated memory which I want to expand and
reuse if possible or allocate in a different part of RAM if resizing is
not possible, however, in the latter case I don't care about the old
data and I don't need to copy it to the new location. Is there a
standard function that could do that? As far as I understand the
description of the realloc() function, it _always_ copies the data to
the new location, even if that is not desired. Can I somehow just
_check_ if the expansion is possible and invoke a new malloc() myself
in case it is not? I'd like this operation to be as fast as possible
because the size of the memory I need is very large.

I'd just like to take this opportunity to point out how utterly stupid I
found the replies which contained solutions akin to:


free(p);
p = malloc(new_size);

 

[Al Balmer]

One can easily envision a data structure that needs to be (relatively
expensively) rebuilt if moved, but that can extended in a
straight-forward fashion. The OP would like to avoid the pointless
copying of the existing data if he's only going to have to rebuild it
anyway, but be able to avoid the rebuild if an "extend" is possible.

If that is the case, I strongly suspect that a different data
structure should be used, one that's extensible without moving data.

 

[Scott Fluhrer]

Ivan posted:



I'd just like to take this opportunity to point out how utterly stupid I
found the replies which contained solutions akin to:


free(p);
p = malloc(new_size);

Why is that suggestion stupid? It certainly meets the requirements as
stated (given that, with the standard malloc API, expanding without copying
is not possible), and should be fairly efficient (assuming a decent
library).

 

[Frederick Gotham]

Scott Fluhrer posted:

Why is that suggestion stupid? It certainly meets the requirements as
stated (given that, with the standard malloc API, expanding without
copying is not possible), and should be fairly efficient (assuming a
decent library).

Obviously the OP already knew that the option was open to them.

There problem was as follows:

(1) Determine if "realloc" will have to relocate the data.
(2) If so, it'd be nice if we had of way of preventing it from copying the
original data over.

 

[Robert Latest]

On Tue, 24 Oct 2006 15:29:20 GMT,

Obviously the OP already knew that the option was open to them.

There problem was as follows:

(1) Determine if "realloc" will have to relocate the data.
(2) If so, it'd be nice if we had of way of preventing it from copying the
original data over.

Hey, you understood the question. Not bad. Thanks for sharing.

robert

 

[Frederick Gotham]

posted:

Let's say I have a piece of allocated memory which I want to expand and
reuse if possible or allocate in a different part of RAM if resizing is
not possible, however, in the latter case I don't care about the old
data and I don't need to copy it to the new location. Is there a
standard function that could do that? As far as I understand the
description of the realloc() function, it _always_ copies the data to
the new location, even if that is not desired. Can I somehow just
_check_ if the expansion is possible and invoke a new malloc() myself
in case it is not? I'd like this operation to be as fast as possible
because the size of the memory I need is very large.

You might like to know that the C++ Standards Committee were discussing this
just yesterday:

http://groups.google.ie/group/comp.std.c++/browse_frm/thread/6019d395338be357
/b0df539b6b7fa47a?lnk=st&q=&rnum=4&hl=en#b0df539b6b7fa47a

I believe Howard posted a link in that thread.

 

[websnarf]

posted:

You might like to know that the C++ Standards Committee were discussing this
just yesterday:

http://groups.google.ie/group/comp.std.c++/browse_frm/thread/6019d395338be357
/b0df539b6b7fa47a?lnk=st&q=&rnum=4&hl=en#b0df539b6b7fa47a

I believe Howard posted a link in that thread.

Looks very promising (i.e., that they are addressing the problem). I
called for this years ago, and _msize() and _expand() calls have been
sitting in the WATCOM C/C++ compiler for over nearly two decades.
Hopefully this makes it into the next C++ standard so that it has some
hope of making it into mainstream compilers.