Thread: reallocation of heap memory

There is no direct equivalent of realloc() in C++ (unless you are using malloc() or calloc() to allocate memory, which is often not a good idea in C++) because the approach used by realloc() does not play well (in fact, it gives undefined behaviour) if the allocated memory contains objects with constructors and destructors.

You can simulate a rough equivalent: use operator new[] to allocate a new block of required size. Use a loop to copy objects from old block to new block as required. delete [] old block. This approach DOES play well with objects that have constructors and destructors.

Better yet, employ a standard container (for example, std::vector) and resize as needed. The implementation of the standard containers takes care of the details for you.

Rather than wondering about realoc for C++, I'd be wondering about removing realloc from C.

I've practically never seen a new poster use it correctly in the initial post of their code, and I seriously don't think it has any real benefits. If the memory had to be moved then it's no faster than a separate allocation, and if it didn't then it was no different than preallocating a larger buffer to begin with.

Welcome to C++; Kindly forget that realloc ever existed.

Originally Posted by iMalc

I've practically never seen a new poster use it correctly in the initial post of their code, and I seriously don't think it has any real benefits. If the memory had to be moved then it's no faster than a separate allocation, and if it didn't then it was no different than preallocating a larger buffer to begin with.

It is a bit hard to preallocate a buffer without knowing its size in advance. realloc() is for those cases where an initial guess might be made, but later proven insufficient.

The more important - albeit one that few people know how to do well - use case is where the buffer must go repeatedly through cycles of growing and shrinking. Depending on the allocation and release strategy used by malloc()/calloc()/realloc()/free() - realloc() has some advantages in such a situation.

I am inclined to agree with grumpy here.
Consider, for example, a database. Its size is always unknown and will typically grow. But is it acceptable to use 1 GB of memory when you have only a few MB worth of data? In most cases, I'd say no.
So that leaves us with the option to have to dynamically resize buffers such as caches to meet demand. But as our demands grow, out buffers needs to get larger, and we can never predict how large they are going to be in advance, nor should we, since it will hurt scalability, since it will mean we have a fixed upper limit.

So why don't we just allocate a bigger buffer and move all the data over, then? Because it's slow and because it's slow, it's silly to do it all the time. With virtual memory, it's all typically a contiguous address space, meaning we can usually steal the page virtual page to our previously allocated ones when we need more. And how can we do this without realloc, since this function knows the internal structures used by malloc? In worst case scenario, we have to copy over all the data; but otherwise we'll gain a huge benefit.

And just to add... it's a damn shame C++ does not have an equivalent realloc. Standard containers are relatively slow because of the lack of this. I can easily write (and have written) a data structure that is much faster than the standard library data structures due to their inefficient memory management. I simply took advantage of realloc features (using Windows API, of course).

Originally Posted by phantomotap

...The `realloc' function doesn't do anything magical; it literally only potentially over-allocates to a predefined, possibly system specific size and because of that may be able to use that extra space on successive calls...

It doesn't have to. A smart realloc can easily snag adjacent virtual memory, if free or unallocated, instead of having to reallocate and move data.
That is the biggest benefit of realloc.

The fact is that realloc can only avoid the copy if the memory addresses following the allocation are not in use. When a user calls malloc, the system has no way of knowing if you're ever going to use realloc with that allocation. So what can it do? At best it can allow most things room to grow just in case, until such time as memory starts getting tight at which point it probably digs into those reserves for new allocations. That's an advantage it could have over a vector since the vector reserves that extra space explicitly for that container.
But if it typically reserves more space for each allocation then it's really not much different to a vector, which as we know doesn't use realloc. If it doesn't then it can be worse than a vector, because it will more often need to copy even if just enlarging the allocation slightly.

It makes little difference whether the "allowing for room to grow" is done by the STL container or by the CRT. This is why it does not exist in C++.


Elysia: Standard library containers are not "slow", and most certainly not due to lack of realloc. That's preposterous. Anything you wrote doesn't compare unless it has all the exact same features and iterator invalidation rules etc.

Well, there are two things:
- There can be adjacent "free" memory. That is, memory that has been allocated once, but later freed using free.
- There can be adjacent free virtual pages.

In both of the cases, we can eat up that memory instead of copying all data over to a new region.
If we carefully optimize our application, we could reserve a region for growing for our containers or data. But allocating it would be bad since that would eat physical memory. This is definitely something realloc could easily provide, though it may or may not be as good as reserving those virtual pages.

The standard containers are slow under certain circumstances. This can easily be proven, and a solution using realloc could easily fix this. How quick or slow they are in practice with lots and lots of allocations in the background is difficult to predict.
What might such a situation be? Just push new values into a vector over and over again without preallocating.

The standard containers are slow under certain circumstances. This can easily be proven, and a solution using realloc could easily fix this. How quick or slow they are in practice with lots and lots of allocations in the background is difficult to predict.
What might such a situation be? Just push new values into a vector over and over again without preallocating.

O_o

Well iMalc, it looks like we've lost this argument.

[Edit]
Elysia, it is possible to add a `renew' operator to C++ by capturing type information with templates, generating the necessary expansion functions, and storing pointers to those functions along with the other per allocation data. If you really think it would be such a boon you have no reason not to explore it further.
[/Edit]

[Edit]
Protip: My source is probably still archived at the Dev-C++ forums if not at this forum. (Yeah, I've done it.)
[/Edit]

[Edit]
And before this argument goes further into the great city of "I don't understand the design of the standard library." I invite you to look at the container parameters allowing for other allocators than the default, the `hint' parameter to the allocators allocate function, and the published C++ allocator based on Google's `TCMalloc' for reference.
[/Edit]

Soma

Even if you were to attempt such a thing, not having access to the data structures used by new (which are also highly implementation dependent), I assume it would only be possible via OS specific APIs, though?
I wouldn't really call that a portable solution, and seeing as new probably won't play nice with any OS API functions (due to we now knowing the implementation), the only real solution if you need such a thing would probably be to implement some memory pool using OS APIs anyway.

Okay, it might have some benefit although it's a bit of a gamble as to whether it'll help at all each time.

In my opinion (and clearly that of the authors of C++) the added complexity and chance of using it incorrectly, for such a small performance gain, doesn't warrant it's existence.

Originally Posted by iMalc

In my opinion (and clearly that of the authors of C++) the added complexity and chance of using it incorrectly, for such a small performance gain, doesn't warrant it's existence.

That is not it at all.

malloc(), calloc(), realloc(), and free() works with raw memory that is not necessarily initialised (although it can be, optionally, by using calloc()). operators new and delete work with more than raw memory - they actually construct and destroy objects. It is a completely different level of abstraction.

Practically, operator new has two steps. The first is allocating raw memory - the equivalent of malloc(). The second is constructing objects from that raw memory - something which is left up to the user of malloc(). That second step requires embedded knowledge of the type of object(s) being reallocated - information that is not needed at all for C's realloc().

With C++ struct/class types, that means invoking constructors and destructors (and possibly also assignment operators) which may be user-defined. And each one of those needs to be properly invoked for each object.

I don't know that renew is a good idea, but it'd be nice if standard allocators had a realloc function.