What is the ideal growth rate for a dynamically allocated array?

Question

C++ has std::vector and Java has ArrayList, and many other languages have their own form of dynamically allocated array. When a dynamic array runs out of space, it gets reallocated into a larger area and the old values are copied into the new array. A question central to the performance of such an array is how fast the array grows in size. If you always only grow it large enough to fit the current push, you'll end up reallocating every time. So it makes sense to double the array size, or multiply it by say 1.5.

Is there an ideal growth factor? 2x? 1.5x? By ideal I mean mathematically justified, best balancing performance and wasted memory. I realize that theoretically, given that your application could have any potential distribution of pushes that this is somewhat application dependent. But I'm curious to know if there's a value that's "usually" best, or is considered best within some rigorous constraint.

I've heard there's a paper on this somewhere, but I've been unable to find it.

Ment

Answer 1

It will entirely depend on the use case. Do you care more about the time wasted copying data around (and reallocating arrays) or the extra memory? How long is the array going to last? If it's not going to be around for long, using a bigger buffer may well be a good idea - the penalty is short-lived. If it's going to hang around (e.g. in Java, going into older and older generations) that's obviously more of a penalty.

There's no such thing as an "ideal growth factor." It's not just theoretically application dependent, it's definitely application dependent.

2 is a pretty common growth factor - I'm pretty sure that's what ArrayList and List<T> in .NET uses. ArrayList<T> in Java uses 1.5.

EDIT: As Erich points out, Dictionary<,> in .NET uses "double the size then increase to the next prime number" so that hash values can be distributed reasonably between buckets. (I'm sure I've recently seen documentation suggesting that primes aren't actually that great for distributing hash buckets, but that's an argument for another answer.)

Pippy

Answer 2

I remember reading many years ago why 1.5 is preferred over two, at least as applied to C++ (this probably doesn't apply to managed languages, where the runtime system can relocate objects at will).

The reasoning is this:

1. Say you start with a 16-byte allocation.
2. When you need more, you allocate 32 bytes, then free up 16 bytes. This leaves a 16-byte hole in memory.
3. When you need more, you allocate 64 bytes, freeing up the 32 bytes. This leaves a 48-byte hole (if the 16 and 32 were adjacent).
4. When you need more, you allocate 128 bytes, freeing up the 64 bytes. This leaves a 112-byte hole (assuming all previous allocations are adjacent).
5. And so and and so forth.

The idea is that, with a 2x expansion, there is no point in time that the resulting hole is ever going to be large enough to reuse for the next allocation. Using a 1.5x allocation, we have this instead:

1. Start with 16 bytes.
2. When you need more, allocate 24 bytes, then free up the 16, leaving a 16-byte hole.
3. When you need more, allocate 36 bytes, then free up the 24, leaving a 40-byte hole.
4. When you need more, allocate 54 bytes, then free up the 36, leaving a 76-byte hole.
5. When you need more, allocate 81 bytes, then free up the 54, leaving a 130-byte hole.
6. When you need more, use 122 bytes (rounding up) from the 130-byte hole.

Prototrophic

A random forum post I found (objectmix.com/c/…) reasons similarly. A poster claims that (1+sqrt(5))/2 is the upper limit for reuse. – Bema

If that claim is correct, then phi (== (1 + sqrt(5)) / 2) is indeed the optimal number to use. – Prototrophic

I like this answer because it reveals the rationale of 1.5x versus 2x, but Jon's is technically most correct for the way I stated it. I should have just asked why 1.5 has been recommended in the past :p – Ment

Facebook uses 1.5 in it's FBVector implementation, article here explains why 1.5 is optimal for FBVector. – Millard

This may be less important in some managed languages, because the GC can rearrange the heap. – Nich

@Nich Right, exactly as my answer noted: "this probably doesn't apply to managed languages, where the runtime system can relocate objects at will". – Prototrophic

Are there any benchmarks that show 1.5x to by faster than 2.0x? The Facebook article doesn't include any. – Superfetation

@AndrewBainbridge The choice of 1.5x isn't because it's faster than 2x. It's that for non-relocating memory allocators, it doesn't leave large unusable gaps in the memory. Obviously, if you're using a platform (like JVM) that does relocate memory, this doesn't matter. – Prototrophic

@Chris OK, thanks for that. The FBVector article mentions that 2x is "cache unfriendly". I took their implication to be that there 1.5x is more cache friendly and therefore faster in some cases. I guess I read too much into that remark. – Superfetation

I'll go with 2x. Just try to allocate the new 1x past the end and then "placement new" there. – Forlini

Dead link by @Bema now links to adv. Cached link: archive.li/ykdHM – Munafo

This answer would have been correct if memory was allocated sequentially. This is not the case in any modern high-preformance allocator. In fact, allocations of different sizes come from different blocks of memory, thus the allocation of larger size can never reuse memory that was previously used for allocation of smaller size. – Fowle

I don't understand. Why would you want to use the previsouly freed memory anyway?? – Abstractionist

Answer 3

In the limit as n → ∞, it would be the golden ratio: ϕ = 1.618...

For finite n, you want something close, like 1.5.

The reason is that you want to be able to reuse older memory blocks, to take advantage of caching and avoid constantly making the OS give you more memory pages. The equation you'd solve to ensure that a subsequent allocation can re-use all prior blocks reduces to x^{n − 1} − 1 = x^{n + 1} − xⁿ, whose solution approaches x = ϕ for large n. In practice n is finite and you'll want to be able to reusing the last few blocks every few allocations, and so 1.5 is great for ensuring that.
(See the link for a more detailed explanation.)

Multiplicate

(Not sure why you deleted all of both of our comments, but I'd like to add some neutral clarifications for anyone who encounters this.) To clarify, n in this answer is not the size of the array, it's the minimum number of reallocations before you'll be able to reuse memory. So n → ∞ doesn't mean "as the array grows to infinity", it means that the higher your tolerance for wasted memory is, the closer to the golden ratio you'd want your growth factor to be. Note this calculation only makes practical sense for small n and growth rates further from ϕ, because – Patriarchate

large but finite n, with growth rates approaching ϕ, would mean you would only be able to reuse older memory blocks after many many reallocations; if your use case is so insensitive to wasted memory, a growth rate of 2x would perform better than a rate near ϕ. – Patriarchate

Answer 4

One approach when answering questions like this is to just "cheat" and look at what popular libraries do, under the assumption that a widely used library is, at the very least, not doing something horrible.

So just checking very quickly, Ruby (1.9.1-p129) appears to use 1.5x when appending to an array, and Python (2.6.2) uses 1.125x plus a constant (in Objects/listobject.c):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsize above is the number of elements in the array. Note well that newsize is added to new_allocated, so the expression with the bitshifts and ternary operator is really just calculating the over-allocation.

Loathing

So it grows the array from n to n + (n/8 + (n<9?3:6)), which means the growth factor, in the question's terminology, is 1.25x (plus a constant). – Avoirdupois

Wouldn't it be 1.125x plus a constant? – Loathing

Answer 5

Let's say you grow the array size by x. So assume you start with size T. The next time you grow the array its size will be T*x. Then it will be T*x^2 and so on.

If your goal is to be able to reuse the memory that has been created before, then you want to make sure the new memory you allocate is less than the sum of previous memory you deallocated. Therefore, we have this inequality:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

We can remove T from both sides. So we get this:

x^n <= 1 + x + x^2 + ... + x^(n-2)

Informally, what we say is that at nth allocation, we want our all previously deallocated memory to be greater than or equal to the memory need at the nth allocation so that we can reuse the previously deallocated memory.

For instance, if we want to be able to do this at the 3rd step (i.e., n=3), then we have

x^3 <= 1 + x 

This equation is true for all x such that 0 < x <= 1.3 (roughly)

See what x we get for different n's below:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

Note that the growing factor has to be less than 2 since x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Milewski

You seem to claim that you can already reuse the previously deallocated memory at the 2nd allocation with a factor of 1.5. This is not true (see above). Let me know if I misunderstood you. – Glomma

At 2nd allocation you are allocating 1.5*1.5*T = 2.25*T while total deallocation you will be doing until then is T + 1.5*T = 2.5*T. So 2.5 is greater than 2.25. – Milewski

Ah, I should read more carefully; all you say is that the total deallocated memory will be more than the allocated memory at the nth allocation, not that you can reuse it at the nth allocation. – Glomma

Answer 6

Another two cents

• Most computers have virtual memory! In the physical memory you can have random pages everywhere which are displayed as a single contiguous space in your program's virtual memory. The resolving of the indirection is done by the hardware. Virtual memory exhaustion was a problem on 32 bit systems, but it is really not a problem anymore. So filling the hole is not a concern anymore (except special environments). Since Windows 7 even Microsoft supports 64 bit without extra effort. @ 2011
• O(1) is reached with any r > 1 factor. Same mathematical proof works not only for 2 as parameter.
• r = 1.5 can be calculated with old*3/2 so there is no need for floating point operations. (I say /2 because compilers will replace it with bit shifting in the generated assembly code if they see fit.)
• MSVC went for r = 1.5, so there is at least one major compiler that does not use 2 as ratio.

As mentioned by someone 2 feels better than 8. And also 2 feels better than 1.1.

My feeling is that 1.5 is a good default. Other than that it depends on the specific case.

Shrieve

It would be better to use n + n/2 to delay overflow. Using n*3/2 cuts your possible capacity by half. – Actinomorphic

@Actinomorphic True. But when n*3 does not fit but n*1.5 fits we are talking about a lot of memory. If n is 32 bit unsigend then n*3 overflows when n is 4G/3, that is 1.333G approx. That is a huge number. That is lot's of memory to have in a single allocation. Evern more if elements are not 1 byte but for example 4 bytes each. Wondering about the use case... – Shrieve

It's true that it may be an edge case, but edge cases are what usually bite. Getting in the habit of looking for possible overflow or other behaviors that may hint at a better design is never a bad idea, even if it may seem farfetched in the present. Take 32-bit addresses as an example. Now we need 64... – Actinomorphic

Answer 7

The top-voted and the accepted answer are both good, but neither answer the part of the question asking for a "mathematically justified" "ideal growth rate", "best balancing performance and wasted memory". (The second-top-voted answer does try to answer this part of the question, but its reasoning is confused.)

The question perfectly identifies the 2 considerations that have to be balanced, performance and wasted memory. If you choose a growth rate too low, performance suffers because you'll run out of extra space too quickly and have to reallocate too frequently. If you choose a growth rate too high, like 2x, you'll waste memory because you'll never be able to reuse old memory blocks.

In particular, if you do the math¹ you'll find that the upper limit on the growth rate is the golden ratio ϕ = 1.618… . Growth rate larger than ϕ (like 2x) mean that you'll never be able to reuse old memory blocks. Growth rates only slightly less than ϕ mean you won't be able to reuse old memory blocks until after many many reallocations, during which time you'll be wasting memory. So you want to be as far below ϕ as you can get without sacrificing too much performance.

Therefore I'd suggest these candidates for "mathematically justified" "ideal growth rate", "best balancing performance and wasted memory":

• ≈1.466x (the solution to x⁴=1+x+x²) allows memory reuse after just 3 reallocations, one sooner than 1.5x allows, while reallocating only slightly more frequently
• ≈1.534x (the solution to x⁵=1+x+x²+x³) allows memory reuse after 4 reallocations, same as 1.5x, while reallocating slightly less frequently for improved performance
• ≈1.570x (the solution to x⁶=1+x+x²+x³+x⁴) only allows memory reuse after 5 reallocations, but will reallocate even less infrequently for even further improved performance (barely)

Clearly there's some diminishing returns there, so I think the global optimum is probably among those. Also, note that 1.5x is a great approximation to whatever the global optimum actually is, and has the advantage being extremely simple.

¹ Credits to @user541686 for this excellent source.

Patriarchate

Answer 8

I recently was fascinated by the experimental data I've got on the wasted memory aspect of things. The chart below is showing the "overhead factor" calculated as the amount of overhead space divided by the useful space, the x-axis shows a growth factor. I'm yet to find a good explanation/model of what it reveals.

Simulation snippet: https://gist.github.com/gubenkoved/7cd3f0cb36da56c219ff049e4518a4bd.

Neither shape nor the absolute values that simulation reveals are something I've expected.

Higher-resolution chart showing dependency on the max useful data size is here: https://i.stack.imgur.com/Ld2yJ.png.

UPDATE. After pondering this more, I've finally come up with the correct model to explain the simulation data, and hopefully, it matches experimental data nicely. The formula is quite easy to infer simply by looking at the size of the array that we would need to have for a given amount of elements we need to contain.

Referenced earlier GitHub gist was updated to include calculations using scipy.integrate for numerical integration that allows creating the plot below which verifies the experimental data pretty nicely.

UPDATE 2. One should however keep in mind that what we model/emulate there mostly has to do with the Virtual Memory, meaning the over-allocation overheads can be left entirely on the Virtual Memory territory as physical memory footprint is only incurred when we first access a page of Virtual Memory, so it's possible to malloc a big chunk of memory, but until we first access the pages all we do is reserving virtual address space. I've updated the GitHub gist with CPP program that has a very basic dynamic array implementation that allows changing the growth factor and the Python snippet that runs it multiple times to gather the "real" data. Please see the final graph below.

The conclusion there could be that for x64 environments where virtual address space is not a limiting factor there could be really little to no difference in terms of the Physical Memory footprint between different growth factors. Additionally, as far as Virtual Memory is concerned the model above seems to make pretty good predictions!

Simulation snippet was built with g++.exe simulator.cpp -o simulator.exe on Windows 10 (build 19043), g++ version is below.

g++.exe (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0

PS. Note that the end result is implementation-specific. Depending on implementation details dynamic array might or might not access the memory outside the "useful" boundaries. Some implementations would use memset to zero-initialize POD elements for whole capacity -- this will cause virtual memory page translated into physical. However, std::vector implementation on a referenced above compiler does not seem to do that and so behaves as per mock dynamic array in the snippet -- meaning overhead is incurred on the Virtual Memory side, and negligible on the Physical Memory.

Dollop

Could you elaborate on how you derived the formula? Do it’s input and output correspond directly to the x and y axes? – Ment

The formula is derived as follows -- the central piece there is alpha^ceil(log(n, alpha)) -- this is the dynamic array capacity required to contain n items with a given growth rate (alpha). Then it's trivial to get an overhead factor (beta) as a ratio of overhead to the useful size (n), so it gives us alpha^ceil(log(n, alpha)) - n / n. The last step is to find an average case (math expectancy) for that we integrate over the n on a range [min, max] dividing by width such interval. Input/output (which is alpha/beta or growth rate/overhead factor) do correspond to x and y axes. – Dollop

Answer 9

It really depends. Some people analyze common usage cases to find the optimal number.

I've seen 1.5x 2.0x phi x, and power of 2 used before.

Pricilla

Phi! That's a nice number to use. I should start using it from now on. Thanks! +1 – Prototrophic

I don't understand...why phi? What properties does it have that makes it suitable for this? – Loathing

@Jason: phi makes for a Fibonacci sequence, so the next allocation size is the sum of the current size and the previous size. This allows for moderate rate of growth, faster than 1.5 but not 2 (see my post as to why >= 2 is not a good idea, at least for unmanaged languages). – Prototrophic

@Jason: Also, according to a commenter to my post, any number > phi is in fact a bad idea. I haven't done the math myself to confirm this, so take it with a grain of salt. – Prototrophic

@ChrisJester-Young To be clear, any growth rate even close to phi (≈ 1.618) is bad if your goal is reuse memory. Any growth rate ≥ phi, including 2x, will never be able to reuse memory, and growth rates only slightly less than phi will waste a lot of memory before being able to reuse any. You want to be much less than phi in order to reuse memory sooner and waste less, but that has to be balanced against more frequent reallocations and copies: https://mcmap.net/q/144162/-what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array – Patriarchate

Answer 10

If you have a distribution over array lengths, and you have a utility function that says how much you like wasting space vs. wasting time, then you can definitely choose an optimal resizing (and initial sizing) strategy.

The reason the simple constant multiple is used, is obviously so that each append has amortized constant time. But that doesn't mean you can't use a different (larger) ratio for small sizes.

In Scala, you can override loadFactor for the standard library hash tables with a function that looks at the current size. Oddly, the resizable arrays just double, which is what most people do in practice.

I don't know of any doubling (or 1.5*ing) arrays that actually catch out of memory errors and grow less in that case. It seems that if you had a huge single array, you'd want to do that.

I'd further add that if you're keeping the resizable arrays around long enough, and you favor space over time, it might make sense to dramatically overallocate (for most cases) initially and then reallocate to exactly the right size when you're done.

Egyptology

Answer 11

I know it is an old question, but there are several things that everyone seems to be missing.

First, this is multiplication by 2: size << 1. This is multiplication by anything between 1 and 2: int(float(size) * x), where x is the number, the * is floating point math, and the processor has to run additional instructions for casting between float and int. In other words, at the machine level, doubling takes a single, very fast instruction to find the new size. Multiplying by something between 1 and 2 requires at least one instruction to cast size to a float, one instruction to multiply (which is float multiplication, so it probably takes at least twice as many cycles, if not 4 or even 8 times as many), and one instruction to cast back to int, and that assumes that your platform can perform float math on the general purpose registers, instead of requiring the use of special registers. In short, you should expect the math for each allocation to take at least 10 times as long as a simple left shift. If you are copying a lot of data during the reallocation though, this might not make much of a difference.

Second, and probably the big kicker: Everyone seems to assume that the memory that is being freed is both contiguous with itself, as well as contiguous with the newly allocated memory. Unless you are pre-allocating all of the memory yourself and then using it as a pool, this is almost certainly not the case. The OS might occasionally end up doing this, but most of the time, there is going to be enough free space fragmentation that any half decent memory management system will be able to find a small hole where your memory will just fit. Once you get to really bit chunks, you are more likely to end up with contiguous pieces, but by then, your allocations are big enough that you are not doing them frequently enough for it to matter anymore. In short, it is fun to imagine that using some ideal number will allow the most efficient use of free memory space, but in reality, it is not going to happen unless your program is running on bare metal (as in, there is no OS underneath it making all of the decisions).

My answer to the question? Nope, there is no ideal number. It is so application specific that no one really even tries. If your goal is ideal memory usage, you are pretty much out of luck. For performance, less frequent allocations are better, but if we went just with that, we could multiply by 4 or even 8! Of course, when Firefox jumps from using 1GB to 8GB in one shot, people are going to complain, so that does not even make sense. Here are some rules of thumb I would go by though:

If you cannot optimize memory usage, at least don't waste processor cycles. Multiplying by 2 is at least an order of magnitude faster than doing floating point math. It might not make a huge difference, but it will make some difference at least (especially early on, during the more frequent and smaller allocations).

Don't overthink it. If you just spent 4 hours trying to figure out how to do something that has already been done, you just wasted your time. Totally honestly, if there was a better option than *2, it would have been done in the C++ vector class (and many other places) decades ago.

Lastly, if you really want to optimize, don't sweat the small stuff. Now days, no one cares about 4KB of memory being wasted, unless they are working on embedded systems. When you get to 1GB of objects that are between 1MB and 10MB each, doubling is probably way too much (I mean, that is between 100 and 1,000 objects). If you can estimate expected expansion rate, you can level it out to a linear growth rate at a certain point. If you expect around 10 objects per minute, then growing at 5 to 10 object sizes per step (once every 30 seconds to a minute) is probably fine.

What it all comes down to is, don't over think it, optimize what you can, and customize to your application (and platform) if you must.

Daughtry

Of course n + n >> 1 is the same as 1.5 * n. It is fairly easy to come up with similar tricks for every practical growth factor you can think of. – Baiel

This is a good point. Note, however, that outside of ARM, this at least doubles the number of instructions. (Many ARM instructions, including the add instruction, can do an optional shift on one of the arguments, allowing your example to work in a single instruction. Most architectures can't do this though.) No, in most cases, doubling the number of instructions from one to two is not a significant issue, but for more complex growth factors where the math is more complex, it could make a performance difference for a sensitive program. – Daughtry

@Rybec - While there may be some programs that are sensitive to timing variations by one or two instructions, it's very unlikely that any program that uses dynamic reallocations will ever be concerned that. If it needs to control the timing that finely, it will probably be using statically allocated storage instead. – Actinomorphic

I do games, where one or two instructions can make a significant performance difference in the wrong place. That said, if memory allocation is handled well, it shouldn't happen frequently enough for a few instructions to make a difference. – Daughtry

I think talking about the performance of integer arithmetic vs. floating point is largely irrelevant in context of dynamic arrays as this single calculation per reallocation is totally negligible comparing to other processes that need to take place. – Dollop

This "single calculation" is actually 3+ instructions (two memory operations, and one+ math), that can take 20+ cycles each on many architectures. It's easy to forget that the vast majority of processors used now don't have sub-10 cycle float operations. Pre ARMv8 ARM processors can take 20+ cycles per float operation (not sure on ARMv8). Most other embedded microcontrollers have even slower floats or have to do software floats (which can take hundreds of cycles). Like I said though, minimizing reallocations can make this less relevant. – Daughtry

@RybecArethdar, a few (even a hundred) extra instructions will be in the rounding error against the work to allocate the memory. – Overreact

Note that phi ~ 42/25 so is fairly easy to do as integer math. – Koy

Answer 12

I agree with Jon Skeet, even my theorycrafter friend insists that this can be proven to be O(1) when setting the factor to 2x.

The ratio between cpu time and memory is different on each machine, and so the factor will vary just as much. If you have a machine with gigabytes of ram, and a slow CPU, copying the elements to a new array is a lot more expensive than on a fast machine, which might in turn have less memory. It's a question that can be answered in theory, for a uniform computer, which in real scenarios doesnt help you at all.

Chism

To elaborate, doubling the array size means that you get amotized O(1) inserts. The idea is that every time you insert an element, you copy an element from the old array as well. Lets say you have an array of size m, with m elements in it. When adding element m+1, there is no space, so you allocate a new array of size 2m. Instead of copying all the first m elements, you copy one every time you insert a new element. This minimize the variance (save for the allocation of the memory), and once you have inserted 2m elements, you will have copied all elements from the old array. – Hispidulous

@Hispidulous how does that work with random access exactly...? I don't see a way how to do that without branching, seems like copying would be faster overall, that's assuming you need to copy at all. – Dives

@Hispidulous Any growth factor, r, gives an amortized complexity of O(1) for insertions. The mathematical proof imagines that each time an element is inserted, a "debt" of copying 1/(r-1) elements is paid. Since this number is constant, the amortized complexity is O(1). However, when reallocation occurs (and that cannot happen in-place), there is no lazy copying. All existing elements are copied right away, so the worst case complexity of insertion is O(n). Otherwise, there would be no point in talking about amortized complexity. – Hereon