Thread: renew

What is realloc() equivalent of new?

There is none (not as directly, anyway). You could read Why doesn't C++ have an equivalent to realloc()?

Can you give an example case where "renew" can be used?

Exactly where realloc can be used.

If new is the replacement of malloc() it should has a replacement for realloc(). Example:

Code:

int *intArr = new int [200];
//We need a bigger array;
intArr = renew (intArr) [400];

Good link laserlight!

Originally Posted by matsp

Since "new" doesn't quite do the same thing as "malloc"[1], what do you expect "renew" to do?

If you consider something like this:

Code:

class blah {
    blah() {
        a = new int[20];
        ....
    }

private:
    int *a;
};

...
   class blah *p = new blah[100];
....
   p = renew blah[200];
....

Should we call the constructor for blah 100 times or 200 times in the second instance? What do we do with the content of the first 100 instances of *a - allocate new ones, copy the existing ones or something else?

This is exactly why renew would be useful. Renew would only reconstruct the objects that it needs to. This would be like vector, except that resizing the vector beyond capacity does not necessarily require the vector to copy elements if the operating system can spare the extra space after the internal dynamic array. It leaves the task of whether to copy the element in the bigging over or not up to the operating system, which knows more about the available memory than the program.

If you have a need to "resize" your datablocks, why not allocate them in "chunks" so that you get some spare size left over, and then fill that out until you get to the "size" and then do your own "renew" by using allocating a new array (or whatever it is you're dealing with) and then copying the old content into the new one.

Becomes sometimes you need sequential memory. Vectors are sometimes preferred over deques. Vector and vector like objects would benefit from renew.

As for how to pick a "slightly larger size", perhaps picking the next (1 << n) that is bigger than the reuqested size.

Using a fixed addition works well if you often only add a little bit, but if you don't know what size you're going to grow the block of memory to, then you may find that a "double it each time" is a better way [2].

That's the problem. Increasing the capacity of the vector by a little bit should not require copying every element over most of the time.

This is exactly why renew would be useful. Renew would only reconstruct the objects that it needs to. This would be like vector, except that resizing the vector beyond capacity does not necessarily require the vector to copy elements if the operating system can spare the extra space after the internal dynamic array. It leaves the task of whether to copy the element in the bigging over or not up to the operating system, which knows more about the available memory than the program.

What I am curious about is whether it is possible to write an allocator for vector that tries to grow the vector without copying existing elements to a newly allocated block unless absolutely necessary, keeping in mind that the vector's elements are expected to be contiguous. It does not sound possible to me, but then I am a beginner at allocators and sophisticated memory management in general.

I'm pretty sure it doesn't specifically say that you couldn't allocate "spare area" whenever it needs to grow, and thus only actually grow it when it runs out of spare area - selecting increasingly larger spare area when it's growing larger.

That is precisely what vector is expected to do, hence the member functions capacity(), reserve(), resize() and size(). I believe some existing implementations do double the capacity when it is maxed out.

Originally Posted by matsp

Most operating systems don't do realloc natively - it's done in the C-library, and it's done by looking at the internal data in the heap, to see if there's enough space to expand it [e.g. we asked for a block of 4K, but the heap contained one that is bigger, so the "rest" of that block is free - realloc can just change the size of the block. If it's unable to expand "in situ", it does a fresh malloc and copies the data anyways].

Right, that's what realloc does. A renew function/operation would do the same thing but with constructors.

The OS may allocate 4K to the program. But the c++ code cannot directly access that 4K; it relies on calls to malloc, calloc, new, ext. Thus if you have a size 100 dynamic array, which uses objects with nontrivial constructors, and you want to increase the size by 1, there is currently no way to do it without copying the entire array over and deleting the old array. This is inefficient.

It's just a case of "where do you solve the problem" as well as "how do you know what needs to be done". I'm not clued up enough about how vector is implemented, but I'm pretty sure it doesn't specifically say that you couldn't allocate "spare area" whenever it needs to grow, and thus only actually grow it when it runs out of spare area - selecting increasingly larger spare area when it's growing larger. Not saying this is how vector is implemented at the moment, but that it COULD BE done. And it certainly can be done without using "renew".

Vector itself can be implemented to work like realloc because there is no requirement that vector is written in c++ (as long as it behaves like it's written in c++). More to the point is how to write an more specialized version vector that uses realloc like functionality in c++ for our own purposes.

Originally Posted by laserlight

What I am curious about is whether it is possible to write an allocator for vector that tries to grow the vector without copying existing elements to a newly allocated block unless absolutely necessary, keeping in mind that the vector's elements are expected to be contiguous. It does not sound possible to me, but then I am a beginner at allocators and sophisticated memory management in general.

It's not possible. There were proposals to make it possible, but I don't know about their status.

That is precisely what vector is expected to do, hence the member functions capacity(), reserve(), resize() and size(). I believe some existing implementations do double the capacity when it is maxed out.

In fact, doubling the capacity is required behaviour for push_back if the vector is full, and no implementation I know does anything different for other insertion functions.

I don't repeat King Mir.

In that case I would use a std::vector

Don't you ever thought how vector grows?

Using a fixed addition works well if you often only add a little bit, but if you don't know what size you're going to grow the block of memory to, then you may find that a "double it each time" is a better way [2].

It is not good. Example:

You need to get some numbers from input. Initially ou make space for 100 items. But there are 122 items! If you double the allocation, you will have room for 200 items. 200 - 122 = 78
78 unit of memory is wasted.

...then do your own "renew" by using allocating a new array (or whatever it is you're dealing with) and then copying the old content into the new one.

Of course I can do my own renew if I could write the realloc function by myself!

renew should first look at the memory allocated by the last new. If it has more room at its tail then that space will be allocated. In this case the pointer does not change. Else it should find a continous free space at the size we want and copy the contents of our array to this new location, delete the old array, return the address of this new location.

Originally Posted by CornedBee

In fact, doubling the capacity is required behaviour for push_back if the vector is full, and no implementation I know does anything different for other insertion functions.

I assume you mean that multiplying the size by some constant > 1, as resizing to 1.5x the size is also acceptable afaik.