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

by

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.

More Related Contents:

  1. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  2. When to use a linked list over an array/array list?
  3. Unnest multiple arrays in parallel
  4. Print two-dimensional array in spiral order
  5. How can a scalar be passed to a vector (1D array) to a Fortran subroutine?
  6. ReDim Preserve to a multi-dimensional array in VB6
  7. How can I initialize an array using a function? [duplicate]
  8. How to increase array size on-the-fly in Fortran?
  9. Vector multiplication using MATMUL in Fortran
  10. Please help me access nested array
  11. remove an index number from array
  12. Correctly allocating multi-dimensional arrays
  13. Creating an Array from a Range in VBA
  14. Element-wise array replication in Matlab
  15. Select the values of one property on all objects of an array in PowerShell
  16. Swift: Creating an Array with a Default Value of distinct object instances
  17. DIR output into BAT array?
  18. What are the differences between ArrayList and Vector?
  19. Return rows matching elements of input array in plpgsql function
  20. How can I convert a buffer of a slice of bytes (&[u8]) to an integer?
  21. How to filter an array of objects based on values in an inner array with jq?
  22. Is there a Perl shortcut to count the number of matches in a string?
  23. Pipe complete array-objects instead of array items one at a time?
  24. Assign to a bash array variable indirectly, by dynamically constructed variable name
  25. Maximum single-sell profit
  26. Unmarshal 2 different structs in a slice
  27. Swift: What’s the best way to pair up elements of an Array
  28. Why are Arrays invariant, but Lists covariant?
  29. Time Complexity for Java ArrayList
  30. How to copy an array in Bash?

Leave a Comment