12

How would I efficiently resize an array allocated using some standards-conforming C++ allocator? I know that no facilities for reallocation are provided in the C++ alloctor interface, but did the C++11 revision enable us to work with them more easily? Suppose that I have a class vec with a copy-assignment operator foo& operator=(const foo& x) defined. If x.size() > this->size(), I'm forced to

  1. Call allocator.destroy() on all elements in the internal storage of foo.
  2. Call allocator.deallocate() on the internal storage of foo.
  3. Reallocate a new buffer with enough room for x.size() elements.
  4. Use std::uninitialized_copy to populate the storage.

Is there some way that I more easily reallocate the internal storage of foo without having to go through all of this? I could provide an actual code sample if you think that it would be useful, but I feel that it would be unnecessary here.

Community
  • 1
  • 1
void-pointer
  • 14,247
  • 11
  • 43
  • 61
  • Interesting link - I also had a [question](http://stackoverflow.com/questions/8003233/does-stdvector-have-to-move-objects-when-growing-capacity-or-can-allocator) about that. – Kerrek SB Jan 12 '12 at 02:39
  • 1
    Already at the one-object level you simply cannot move the underlying memory of a general C++ object, and there's no way around that. If the memory has to move, you *have* to construct new objects. Mind you, any decent standard library will already specialize for PODs and do `memmove` or something like that. – Kerrek SB Jan 12 '12 at 02:40
  • I think that the answer provided to your question answers mine, as well. This seems like a very disappointing limitation of C++, since we're forced to go through steps 1-4 instead of just being able to "extend" the internal buffer using some reallocation function. – void-pointer Jan 12 '12 at 02:42
  • I imagine that the use case is so rare that it doesn't matter in practice. `vector` is still one of the fastest containers on account of its memory locality, and the geometric growth means that you'll not be doing a lot of trivial growing anyway. – Kerrek SB Jan 12 '12 at 02:46
  • You only need to go through that when `x.size() > this->capacity()`. That gives a little headroom - depends on implementation and usage but it might end up happening about as often as the heap could resize in-place. If you want to - I can't see what's stopping you from writing `vec` to use `realloc`, placement `new` for construction etc..... – Tony Delroy Jan 12 '12 at 02:53
  • 1
    @TonyDelroy: Because the spec for `realloc`: "The function may move the memory block to a new location, in which case the new location is returned". That invalidates existing pointers, you have to use a copy or move constructor and not just blit areas of memory. Typical approaches to this problem involve a `could_reallocate` function that never moves the content, either resizes the block in-place or fails. – Ben Voigt Jan 12 '12 at 03:05
  • @Ben: yes - that is true for certain types of data... good point. – Tony Delroy Jan 12 '12 at 03:25

6 Answers6

4

Based on a previous question, the approach that I took for handling large arrays that could grow and shrink with reasonable efficiency was to write a container similar to a deque that broke the array down into multiple pages of smaller arrays. So for example, say we have an array of n elements, we select a page size p, and create 1 + n/p arrays (pages) of p elements. When we want to re-allocate and grow, we simply leave the existing pages where they are, and allocate the new pages. When we want to shrink, we free the totally empty pages.

The downside is the array access is slightly slower, in that given and index i, you need the page = i / p, and the offset into the page i % p, to get the element. I find this is still very fast however and provides a good solution. Theoretically, std::deque should do something very similar, but for the cases I tried with large arrays it was very slow. See comments and notes on the linked question for more details.

There is also a memory inefficiency in that given n elements, we are always holding p - n % p elements in reserve. i.e. we only ever allocate or deallocate complete pages. This was the best solution I could come up with in the context of large arrays with the requirement for re-sizing and fast access, while I don't doubt there are better solutions I'd love to see them.

Community
  • 1
  • 1
SmacL
  • 22,555
  • 12
  • 95
  • 149
  • This advice was really useful when I was doing some experimentation, and seems to be the most viable workaround for the limitations in C++. – void-pointer Feb 15 '12 at 14:59
1

A similar problem also arises if x.size() > this->size() in foo& operator=(foo&& x).

No, it doesn't. You just swap.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
1

There is no function that will resize in place or return 0 on failure (to resize). I don't know of any operating system that supports that kind of functionality beyond telling you how big a particular allocation actually is.

All operating systems do however have support for implementing realloc, however, that does a copy if it cannot resize in place.

So, you can't have it because the C++ language would not be implementable on most current operating systems if you had to add a standard function to do it.

MSN
  • 53,214
  • 7
  • 75
  • 105
  • Edited my answer to reflect the content posted here previously. – void-pointer Jan 13 '12 at 02:18
  • Some OSes/libraries can actually move a memory block without copying the data, by modifying the page table. At least libc on linux does that, if realloc() cannot grow a somewhat large chunk of memory in place. For small data blocks, realloc() still resorts to a classical copy, though. – Kai Petzke Sep 17 '13 at 18:38
0

There are the C++11 rvalue reference and move constructors.

There's a great video talk on them.

David C. Bishop
  • 6,437
  • 3
  • 28
  • 22
  • I'm familiar with rvalue references, move constructors, std::forward, etc., but they don't really help solve the problem that the Allocator interface provides no functionality for reallocation. I have a solution designed using Ben Voigt's suggestion that I hope to test and post soon, though it is not guaranteed to work for any allocator. – void-pointer Jan 12 '12 at 03:59
0

Even if re-allocate exists, actually, you can only avoid #2 you mentioned in your question in a copy constructor. However in the case of internal buffer growing, re-allocate can save these four operations.

  1. Is internal buffer of your array continuous? if so see the answer of your link
  2. if not, Hashed array tree or array list may be your choice to avoid re-allocate.
Community
  • 1
  • 1
Chang
  • 3,953
  • 2
  • 30
  • 43
  • I was looking for an answer that uses the native array, since my application of this information is for numerical computation, where I could really use the speed of native array access. Shane MacLaughlin's answer still uses a native array, at the cost of slightly more expensive array accesses. I'm testing a non-standard solution right now that uses the allocator hint parameter. – void-pointer Jan 12 '12 at 09:34
  • 1
    @void-pointer what is your platform which you worked on? does it support virtual memory? Does it have the API to allocate virtue space without real memory? for example, in windows platform, you can use VirtualAlloc to request a reasonable huge contiguous memory region, and just commit physical memory as need. you can check http://g.oswego.edu/dl/html/malloc.html, although it is intended to replace malloc/free/realloc, I believe you can get idea for your problem. – Chang Jan 12 '12 at 12:14
0

Interestingly, the default allocator for g++ is smart enough to use the same address for consecutive deallocations and allocations of larger sizes, as long as there is enough unused space after the end of the initially-allocated buffer. While I haven't tested what I'm about to claim, I doubt that there is much of a time difference between malloc/realloc and allocate/deallocate/allocate.

This leads to a potentially very dangerous, nonstandard shortcut that may work if you know that there is enough room after the current buffer so that a reallocation would not result in a new address. (1) Deallocate the current buffer without calling alloc.destroy() (2) Allocate a new, larger buffer and check the returned address (3) If the new address equals the old address, proceed happily; otherwise, you lost your data (4) Call allocator.construct() for elements in the newly-allocated space.

I wouldn't advocate using this for anything other than satisfying your own curiosity, but it does work on g++ 4.6.

void-pointer
  • 14,247
  • 11
  • 43
  • 61