Double After Full

An algorithm for space allocation:

When a container gets full, reallocate with twice as much space as last time.

It sounds like it will be too greedy to work out. In practice, it's usually a good space/time tradeoff.

Mathematical Basis.

This scheme of doubling memory is denoted as x2

• Q/. Does this copy memory a lot of times?
• A/. For SufficientlyLarge values of N, the algorithm allocates and copies 2N copies of the data. Thus in big O notation the algorithm is O(N).
• Q/. What about other values other than x2 allocation?
• A/. All multiplicative schemes x1.5 x1e99 x1.001 are all in big O notation, k O(N).

See basic Mathematics text for 'sum of geometric series'. Note how this demonstrates the lie of big O analysis. Big O notation ignores all 'k' values, but for the x1.001 algorithm the 'k' is likely to actually be the only important part for many practical values of N.

• Q/. So why x2 and not x3 or x1.5?
• A/. x2 has been found to work for many people and many problems :) (It's fashionable, and easy to compute, and computer folk have a fetish for powers of two)
• A2. For any memory reuse, the GoldenRatio is the best growth factor if there is no memory allocated for bookeeping purposes - if there is then a smaller growth factor (i.e. x1.5) is better. There are some long discussions on what is the best growth factor here: http://tinyurl.com/6awz7 -- JamesKeogh

A more controversial but accurate statement and analysis.

• Q/. are there other enhancements ?
• A/. For vector <T *> A; Don't start at N=1 the allocator will probably frequently give you 12-16 bytes of RAM any away. The time taken to double memory when N is small is represented by k + O(N) where O(N) << k and thus the O(N) may be ignored!!!! Ignoring that term results in O(ln(N)) for the whole doubling sequence of the algorithm and more generally O(ln(N/S)) where S is the value of the initial allocation size.

Conclusion:

• The doubling is mathematically sound.
• Other versions using Multipliers sufficiently near 2 are also mathematically and practically sound.
• 2 is fashionable. Make measurements to prove a different value is 'better' in your case.
• All the following really nifty people use two too.

Known uses/references:

• The GNU C++ StandardTemplateLibrary container classes
• Smalltalk-80
• DonaldKnuth proves that doubling when full is the optimal allocation strategy in TheArtOfComputerProgramming, Chapter 2 (I couldn't find this. What page was it on?)
• IntroductionToAlgorithms (Cormen et. al.) Chapter 18 Amortized Analysis: Dynamic tables (p. 367)

Lack of uses:

• Java's ArrayList also seems to use the GoldenRatio algorithm. It multiplies by 3/2 (or half-again after full).

I am not Knuth, but I don't think anyone else authoring this page is either:

• Doubling (x2) for SufficientlyLarge N results in, on average, 2N allocations and copies. 1 + 1/2 + 1/4 + 1/8 + ... On average, it uses 50% more memory than is needed and can never reuse its own deallocated memory. This is ONE cost benefit trade off.
• Java's alg (x1.5) for SufficientlyLarge N results in, on average, 3N allocations and copies. 1 + 2/3 + 4/9 + ... On average, it uses <25% more memory than is needed, but can reuse deallocated memory after growing a few times. This is another ONE cost benefit trade off.

In general, if when you run out of space you allocate k times as much again, then (in the limit of large N)

• each item of data gets allocated/copied about k/(k-1) times;
• you use, on average, (k-1)/log(k) times as much memory as the theoretical minimum. (That's the natural logarithm, not log to base 10 or base 2.)

We can redline the bogosity meter and claim that the best overall efficiency comes when the product of these two inefficiency factors is as small as possible; that means you're minimizing k/log(k), which happens when k=e. Ha.

(In reality, you should take little notice of this sort of analysis. Try some different schemes and measure.) False. This type of analysis is as (not more) important as experimenting. Anyone who does (or is only capable of) only one of the two is doomed to mediocrity.

---

Suppose your data structures can shrink as well as grow. You might think that you should double your allocation when you fill up, and halve your allocation when you can. That's a bad idea, because if the size happens to wobble around near the boundary you'll spend all your time growing and shrinking. So you should build in some hysteresis: grow and shrink by a factor of k, but don't shrink until you're too large by a factor of k1, where k1>k.

Example: Double when full, halve when one quarter full.