0

I want to implement a container. The data will be stored in a dynamically allocated array. I need advice on memory reallocation.

Basically, i want a formula on how much bigger i should make the array when it is full. I think a constant value would be sub-optimal, since the larger the array is, the longer it takes to copy it.

For example, if an array can store 1000000 doubles and it becomes full, reallocating for 1000005 doubles would be stupid. Going for 1001000 would be a better idea. On the contrary, if i have an array of 5 doubles and it gets full, enlarging it to 1005 units is equally stupid. Maybe enlarging it by 10% (or like by 20+10% so that it feels ok on small arrays too) every time would be a better idea. Any advice on this?

Improve this question
6
  • 3
    There is no proper answer to this question. That being said, AFAIK most std::vector<> implementations double the current capacity of the vector when reallocation is needed. Commented Sep 6, 2013 at 18:05
  • 2
    Since you're probably reinventing a standard container, why not go the distance? Profile your code, gather usage data, develop your own predictive model of how big the container is likely to get, and use that to determine the formula. Commented Sep 6, 2013 at 18:08
  • 3
    The usual way is to follow a geometric progression of sizes, as @sbabbi implied (e.g., this is basically required to meet the "amortized constant" requirements for std::vector). Current implementations seem to use a factor of 1.5 more often than 2, but the same basic idea still applies. Commented Sep 6, 2013 at 18:10
  • See also stackoverflow.com/questions/2625006/…. Commented Sep 6, 2013 at 18:12
  • As Beta and sbabbi said, there is no general answer, since it heavily depends on how the data to be stored in the container is generated. Moreover a optimality criterion cannot be absolute, but it will depends on a variety of factors. For example, if you are on a modern workstation with GiBs of memory, you could afford to constantly increase the memory reserved for the container. But if you are on a memory constrained platform (smartphone?), you may also consider to shrink a container to free some memory for other data structures and avoid out-of-memory errors in your app. Commented Sep 6, 2013 at 18:17

1 Answer 1

Reset to default
1

I would start by reusing std::vector. Don't re-implement what already works well.

If you know something about the size of your data, then use the reserve() function to ensure you don't allocate more often than you need to. Feel free to reserve 20%, or 40% extra space if you dont know exactly how much data you have.

If you don't know something about the size of your data, then std::vector is optimized for good performance without knowing anything. If you know nothing about the size of your data, you are equally likely to have 10001 entries and have vector wastefully allocate lots of space as you are to have 9999 entries and have vector avoid 4 or 5 wasteful copies that a less aggressive algorithm chose. Std::vector implementations are fine tuned over many hundreds of man hours to ensure optimal behavior when the user has no information on sizing.

The only time I'd start to deviate from that is when you start getting up into the gigabyte data sets. Then it's nice to make sure that you don't allocate something too big to fit into memory.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.