Resources | Resources |



Adaptive reallocation

When an application needs to generate a string (such as a JSON or XML string) or build a dynamic array, it may not know in advance how much memory is required to store the result. It may need to start by allocating a fixed or best-guess amount of memory. If that turns out to be insufficient, it will need to reallocate the memory to get more. This not only requires another allocation, it will usually require copying the contents of the previous memory to the newly allocated memory.

The common method used for reallocations is to increase the size of the currently allocated block by a fixed reallocation increment, often the same size as the initial block allocation. This works well enough if the initial allocation is only slightly too small, but has terrible performance if the initial allocation and reallocation increment are significantly smaller than the required size.

For example, if the initial allocation size and increment are both 128 bytes and the final result requires 4096 bytes, the fixed-increment strategy will require 31 memory allocations beyond the initial allocation and will copy 63488 bytes of data before it is complete.

A better strategy is to double the allocation size whenever more memory is needed rather than add a fixed increment. This strategy leads to exponential reallocation increments as opposed to linear increment with fixed size reallocation. For small final allocations, this is about the same as the fixed-increment strategy, but for final allocations that are considerably larger than the initial allocation this performs much better. Using this strategy in the example above requires only 5 reallocations and 3968 bytes of data being copied. While this approach can result in a larger final allocation than the fixed-increment approach, adaptive reallocation is generally preferable to a fixed-increment approach.