Dynamic Arrays: Growth factors and memory tradeoffs

Dynamic arrays are one of the most popular types of data structure available in most modern programming languages in the current landscape. But there is very little discussion, and very few posts, explaining their implementation and tradeoffs. I decided to take a closer look at them, and I was surprised to learn there is a lot going on. Let me unpack them here. Before I go on, let me quickly mention that I do a lot of Python programming; I basically made my career out of it. My perspective comes from using Python, Java, and JavaScript versions of the data structure.

Dynamic Arrays 101

A dynamic array (aka vector, list, or ArrayList) is a data structure backed by a contiguous block of pre-allocated memory. In contrast to static arrays, which are also a contiguous block of memory, dynamic arrays can expand as you add elements to them.

It works as follows:

When you create a dynamic array, you create an array with size n. You can add or pop elements from this dynamic array. When you try to add more than n elements, more than n elements, the array is expanded. You create a new array with double the original size, copy the elements in the old one over to the new one, and continue inserting.

Dynamic arrays internally track the free space, or the lack thereof, with the help of two variables. Let’s call them size and capacity for the sake of this article. size represents the number of elements added to the array, and capacity represents the number of elements the array can accommodate. If size reaches capacity, we need to resize.

Amortised O(1)

Dynamic arrays perform almost the same on all operations that static arrays perform: O(1) random access, random element update, etc. The operations that are specific to dynamic arrays are appending and popping: adding an element to the end and deleting the last element. Dynamic arrays can append and pop elements at the end in O(1) most of the time. When size < capacity, this holds true. The only exception is during resizing. When you hit the limit, the array needs to perform O(n) operations: copy each element over to the new array. This is the amortised O(1). The idea is that when you double the size of the array every time the array hits the limit, the number of times the array is resized is logarithmic. It happens only once in a while.

But here is the thing that most people overlook: when you hit the limit, the insertion takes O(n) time. Occasionally, an append operation will take O(n). This latency spike might not be preferred in all applications. This is why you try to keep the number of such reallocations to the minimum. But that is also not the only problem. Imagine you have an array of a billion elements, and you have hit the maximum capacity and are trying to add one more element. What happens? You create a new array with a billion more free slots. If each array element is 1 byte, you would be using roughly 1 GB of memory more so that you can add one more element to the array. That sounds about right.

Sample implementation

This is a sample implementation of dynamic arrays in Python:

class DynamicArray:
   GROWTH_FACTOR = 2

   def __init__(self):
      self.data = [None] * DynamicArray.GROWTH_FACTOR
      self.size = 0
      self.capacity = DynamicArray.GROWTH_FACTOR

   def _resize(self, new_size):
      new_data = [None] * new_size
      for index, item in enumerate(self.data):
         new_data[index] = item
      self.data = new_data
      self.capacity = new_size

   def expand(self):
      new_capacity = self.capacity * DynamicArray.GROWTH_FACTOR
      self._resize(new_capacity)
      
   def append(self, item):
      if self.size == self.capacity:
         self.expand()

      self.data[self.size] = item
      self.size += 1
      
   def pop(self):
      self.size -= 1
      temp = self.data[self.size]

      self.data[self.size] = None 
      return temp
      
   def __getitem__(self, index):
      if index in range(0, self.size):
         return self.data[index]

   def __setitem__(self, index, val):
      if index in range(0, self.size):
         self.data[index] = val

The above piece of code demonstrates whatever was discussed in the previous sections.

Growth factor and tradeoffs

As mentioned in the previous section, dynamic arrays might face two distinct problems:

a) When the arrays hit maximum capacity, the reallocation is going to cause a latency spike in insertion. b) When the array size is huge, reallocation would cause a massive increase in memory.

Let’s take a look at the second problem first. How do we prevent ourselves from allocating huge amounts of memory whenever there is a limit increase? Simple: we allocate less memory than the “2x” that we are currently doing. The factor by which you increase your memory is called the growth factor. By keeping the growth factor low, you make sure that there is less memory wastage on huge array sizes. For example, instead of 2, if you were to keep the growth factor as 1.5, you would only be requesting 500 MB of memory rather than 1 GB, as in the case before.

Let’s look at the first problem: latency spikes. Of course, you want to keep the number of latency spikes to a minimum. If things like P95 or P99 matter more to you, you will want to avoid such latency spikes as much as possible. This means keeping the growth factor as high as possible.

This is why choosing the growth factor is critical, because you cannot solve both problems. If you choose a higher growth factor, you will have more free memory in your dynamic arrays. If you choose a low growth factor, you will have more latency spikes during insertions.

Optimising for runtime (minimising latency spikes)

If you decide you need performance, you can just go with the 2x strategy. Set the growth factor as 2 and don’t look back, because nothing else matters more. Some implementations use this strategy, although they also provide a mechanism, an API call, to shrink-fit the array to prevent large memory sitting in the heap unused. In the case of Java ArrayList, this is called trimToSize(). Similar methods exist in other implementations that use this strategy. Other examples include Rust’s Vec and C++’s standard std::vector implementations, which follow a similar strategies.

Optimising for memory

When you decide to optimise for memory, on the other hand, the tradeoffs get more interesting. If you reallocate too often, there may be too many latency spikes which negate the effects of the “amortised O(1)”. The “amortised” part requires you to keep the reallocations to a minimum. You need to walk a fine line between not wasting memory and avoiding bad performance. It is generally a good bet to go with 1.5 or 1.7. There are other implementations, like Python’s list, that use 1.2 as they are very conscious of memory use.

Shrinking

If you are optimising for memory, shrinking the size of the array when it goes beyond a certain threshold might be a very good way to reduce memory wastage. It doesn’t make much sense to have an array with a capacity of a million and have only a few thousand elements. But when you shrink, it is a good idea to have at least half the capacity as free so that you can accommodate insertions. If you shrank the array and have no free space, then if you alternately insert and delete elements, you will end up reallocating on every operation. This scenario is referred to as thrashing.

Growth factor on smaller vs larger arrays

It makes sense to use 1.5 or 1.3 when you have a million elements, but when you are starting out, which is the most common use case, you don’t have that many elements. In those cases, you will be frequently reallocating. For this reason, most implementations that use a less-than-double growth factor use a growth function to determine the growth factor dynamically. Based on the current size of the array, the growth factor changes. The prime example is Go, which uses a function to smooth out the growth factor. Another example is Python, which uses a similar idea to have a large growth factor on smaller array sizes and a gradually reduced growth factor as the array grows bigger.

Other optimisations

Some implementations, like FBVector, Facebook’s implementation of std::vector in C++, claim that using a 1.5x growth factor actually has the same, if not better, performance compared to the 2x strategy. This is due to the fact that modern allocators often reuse the freed memory more efficiently with a 1.5x growth factor.

Tradeoffs when compared to other alternatives

For many common use cases, there are very few reasons to use linked lists instead of dynamic arrays because, for most use cases, dynamic arrays perform as well as linked lists with the added advantage of simplicity in the code and reasoning.

If you know the number of elements that will go in the array, it is better to use a static array. You don’t need to worry about the reallocation tradeoffs if you know the max size beforehand.

But dynamic arrays perform well when you don’t know the number of elements and you only need to insert and/or delete the elements at the end. They beat the performance of linked lists in iteration due to the fact that dynamic arrays have elements located next to each other. This allows the CPU to cache the data and access elements faster.

So to summarise, dynamic arrays:

have a tradeoff between speed and memory based on the growth factor.
can waste less memory with a lower growth factor and have higher performance with a higher growth factor.
can shrink to save memory.
require a higher growth factor on smaller array sizes even if you want to save memory on bigger array sizes.
are very much suitable for use cases where the array size is not known beforehand and inserts and deletes are only done at the end.

Dynamic Arrays 101#

Amortised O(1)#

Sample implementation#

Growth factor and tradeoffs#

Optimising for runtime (minimising latency spikes)#

Optimising for memory#

Shrinking#

Growth factor on smaller vs larger arrays#

Other optimisations#

Tradeoffs when compared to other alternatives#