An algorithm for space allocation:
**Mathematical Basis.**
This scheme of doubling memory is denoted as x2
**Conclusion:**
**Known uses/references:**
**Lack of uses:**
*k* times
as much again, then (in the limit of large *N*)
*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.

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

- 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).

- 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

- 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.

- 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.

- 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)

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

- 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.

- 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.)

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

EditText of this page (last edited May 24, 2007) or FindPage with title or text search