Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficient Array Reallocation in C++

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.

like image 360
void-pointer Avatar asked Jan 12 '12 02:01

void-pointer


People also ask

Are arrays dynamically allocated in C?

Dynamically allocated arrays are allocated on the heap at run time. The heap space can be assigned to global or local pointer variables that store the address of the allocated heap space (point to the first bucket).

Is Realloc costly?

More often than not new memory block will be allocated of desired (requested) size, then data will be copied from old location to new location, this is why realloc is said to be expensive call.

How we store array in memory in C?

When we declare an array, space is reserved in the memory of the computer for the array. The elements of the array are stored in these memory locations. The important thing about arrays is that array elements are always stored in consecutive memory locations.


1 Answers

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.

like image 65
SmacL Avatar answered Sep 27 '22 21:09

SmacL