Comments on: Implementing a True realloc() in C++ I'll agree, the C library <code>realloc()</code> function is not without it's issues when used in this context, but the implementation presented here allows for an in-place reallocation regardless of the memory manager in use. I only selected <code>realloc()</code> because it is available on just about every platform, and it saved me from having to first describe how to write a custom memory allocation system. :) However, paired with a better allocator (such as the Win32 Heap() functions), it becomes possible to eliminate the remaining issues of the copy operator not being called on a relocation, and to also guarantee that a block can be expanded in-place. There have been various tests done by others that show that reallocating in-place is indeed more beneficial than <code>std::vector</code>, especially if the elements are added to the array directly after creation. One such test result can be found <a href="http://stackoverflow.com/questions/4089200/using-realloc-in-c" rel="nofollow">on StackOverflow</a>. I've been using this reallocation implementation in my own code for a few years now, and have been able to avoid useless memory copies and enjoy less memory fragmentation because of it. Perhaps in a future post I can do an in-depth comparison between <code>std::vector</code>'s allocation and the method presented here. I’ll agree, the C library realloc() function is not without it’s issues when used in this context, but the implementation presented here allows for an in-place reallocation regardless of the memory manager in use. I only selected realloc() because it is available on just about every platform, and it saved me from having to first describe how to write a custom memory allocation system. :) However, paired with a better allocator (such as the Win32 Heap() functions), it becomes possible to eliminate the remaining issues of the copy operator not being called on a relocation, and to also guarantee that a block can be expanded in-place.

There have been various tests done by others that show that reallocating in-place is indeed more beneficial than std::vector, especially if the elements are added to the array directly after creation. One such test result can be found on StackOverflow.

I’ve been using this reallocation implementation in my own code for a few years now, and have been able to avoid useless memory copies and enjoy less memory fragmentation because of it. Perhaps in a future post I can do an in-depth comparison between std::vector‘s allocation and the method presented here.

]]>
By: Tom Seddon/2011/05/28/implementing-a-true-realloc-in-cpp/#comment-5151 Tom Seddon Sun, 05 Jun 2011 13:05:27 +0000 * <code>vector::reserve</code> only works once, before any elements are inserted, and it requires you to estimate the potential size of your array. If you estimate too small, pushing more elements past the capacity will incur a new allocation and data relocation. If you estimate too large, you end up wasting memory. In game development, where there are numerous outside factors affecting the environment (such as physics and networking), it is simply not possible to estimate the sizes of certain arrays, and they must be able to expand at runtime. The implementation presented here at least attempts to expand the block in-place first, potentially avoiding the complete reallocation and costly data move. * <code>std::deque</code> is indeed an option to keep elements in a fixed location if the container needs to resize, but it doesn't attempt to expand existing blocks in-place, and so contributes to memory fragmentation (albeit less than <code>std::list</code>). * Quoting from the source of <code>vector::_Insert_n()</code> itself: <code>_Capacity = max_size() - _Capacity / 2 < _Capacity ? 0 : _Capacity + _Capacity / 2; // try to grow by 50%</code> A <code>vector</code> which is 512KB in size would become: 512 + 512 / 2 = 512 + 256 = 768KB. In order to copy the existing elements from the old <code>vector</code> into the new one, this would temporarily require both <code>vector</code>s to coexist in memory, requiring a total of 512 + 768 = 1.25MB, which I explain at the beginning of this article. * Custom allocators cannot be used to implement a <code>realloc()</code>-like functionality. The <code>std::vector</code> implementation simply requests new memory from the allocator and moves all existing elements into the new memory. The allocator has no control over how the memory is utilized. * As long as optimizations are enabled, most compilers will likely remove non-existent constructor and destructor calling for any type, whether it is a POD or not. This can be easily confirmed by looking at the compiled assembly code from gcc-4.5, for example. But this has nothing to do with the article. * So C++0x has extra move operators to avoid a possibly expensive copy constructor -- that's nice. But does the container attempt to resize in-place? No, it doesn't. The point of this article is to completely avoid the costly move in the first place. My complaint is not with <code>std::vector</code>, but with the C++ language lacking an <code>operator realloc[]</code> to allow a block to be expanded in-place. If such an operator had existed at the beginning, <code>std::vector</code> could be utilizing it now, and the compiler-generated code could completely avoid this mess where constructors and destructors need to be called manually. * vector::reserve only works once, before any elements are inserted, and it requires you to estimate the potential size of your array. If you estimate too small, pushing more elements past the capacity will incur a new allocation and data relocation. If you estimate too large, you end up wasting memory. In game development, where there are numerous outside factors affecting the environment (such as physics and networking), it is simply not possible to estimate the sizes of certain arrays, and they must be able to expand at runtime. The implementation presented here at least attempts to expand the block in-place first, potentially avoiding the complete reallocation and costly data move.

* std::deque is indeed an option to keep elements in a fixed location if the container needs to resize, but it doesn’t attempt to expand existing blocks in-place, and so contributes to memory fragmentation (albeit less than std::list).

* Quoting from the source of vector::_Insert_n() itself:
_Capacity = max_size() - _Capacity / 2 < _Capacity ? 0 : _Capacity + _Capacity / 2; // try to grow by 50%

A vector which is 512KB in size would become: 512 + 512 / 2 = 512 + 256 = 768KB. In order to copy the existing elements from the old vector into the new one, this would temporarily require both vectors to coexist in memory, requiring a total of 512 + 768 = 1.25MB, which I explain at the beginning of this article.

* Custom allocators cannot be used to implement a realloc()-like functionality. The std::vector implementation simply requests new memory from the allocator and moves all existing elements into the new memory. The allocator has no control over how the memory is utilized.

* As long as optimizations are enabled, most compilers will likely remove non-existent constructor and destructor calling for any type, whether it is a POD or not. This can be easily confirmed by looking at the compiled assembly code from gcc-4.5, for example. But this has nothing to do with the article.

* So C++0x has extra move operators to avoid a possibly expensive copy constructor — that’s nice. But does the container attempt to resize in-place? No, it doesn’t. The point of this article is to completely avoid the costly move in the first place.

My complaint is not with std::vector, but with the C++ language lacking an operator realloc[] to allow a block to be expanded in-place. If such an operator had existed at the beginning, std::vector could be utilizing it now, and the compiler-generated code could completely avoid this mess where constructors and destructors need to be called manually.

]]>
By: snk_kid/2011/05/28/implementing-a-true-realloc-in-cpp/#comment-5040 snk_kid Tue, 31 May 2011 23:39:12 +0000 If your intention is just to build <code>realloc()</code> into a simple array wrapper, then the code you have provided will work just fine for that -- although you might want to make sure you at least call the destructors in reverse order! My intention was to go more low-level and implement an <code>operator realloc[]</code>, which I personally feel is missing from the C++ language. The benefit of this is that it can be used by only having a pointer to a C++ array, and not require it to be wrapped within a new type (like your <code>Array</code> class). If your intention is just to build realloc() into a simple array wrapper, then the code you have provided will work just fine for that — although you might want to make sure you at least call the destructors in reverse order!

My intention was to go more low-level and implement an operator realloc[], which I personally feel is missing from the C++ language. The benefit of this is that it can be used by only having a pointer to a C++ array, and not require it to be wrapped within a new type (like your Array class).

]]>
By: Anton Shekhovtsov/2011/05/28/implementing-a-true-realloc-in-cpp/#comment-4983 Anton Shekhovtsov Mon, 30 May 2011 09:05:00 +0000 Sorry, I'm not sure I completely understand your question. <code>realloc()</code> is a C library function -- it is not part of the C++ language. Because of this, <code>realloc()</code> does not know about class constructors or destructors, and so does not (can not) call them. The implementation presented here overcomes that limitation. By wrapping the code presented here into a generic container, a complete replacement for <code>std::vector</code> can be created which allows for expansion of the array in-place, avoiding an expensive memory copy. Sorry, I’m not sure I completely understand your question.

realloc() is a C library function — it is not part of the C++ language. Because of this, realloc() does not know about class constructors or destructors, and so does not (can not) call them. The implementation presented here overcomes that limitation.

By wrapping the code presented here into a generic container, a complete replacement for std::vector can be created which allows for expansion of the array in-place, avoiding an expensive memory copy.

]]>
By: Anton Shekhovtsov/2011/05/28/implementing-a-true-realloc-in-cpp/#comment-4969 Anton Shekhovtsov Sun, 29 May 2011 16:58:49 +0000