Dynamic arrays are the most popular type of data structure that is available in the all the programming langauges in the current lanscape. But there is very little discussion or posts explaining the implementation and their various 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 made my career basically as that. My perspective comes from using python, java and javascript versions of the data structure.
Dynamic Arrays 101
Dynamic arrays (sometimes refered to as vectors, but each language has a unique name) are a data structure where you have a contiguous block of pre-allocated memory. In contrast to static arrays which is 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 elements than the size of the current block (more than n elements) then the array is expanded. You create a new array with double the original size, you copy the elements in the old one over to the new one and you continue inserting.
The dynamic arrays internally track the free space (or the lack thereof) with the help of two
variables. Lets call them size and capacity for the sake of this article. size represents
the amount of elements added to the array, and capacity represents the amount elements the array can accomodate. If size exceeds 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. Randomly your array would take O(n). This latency spike might not be prefered 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 million elements, and you have hit the maximum capacity and you are trying to add one more element. What happens? Yes you create a new element with million more free space. If each array element is 1 byte, you would be using 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 the 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 shows whatever was discussed on the previous sections. This is more or less what is happening in the java’s ArrayList implementation.
Growth factor and tradeoffs
As mentioned in the previous section, dynamic array 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.
Lets take a look at the second problem first. How do prevent ourselves from allocating huge amounts of memory whenever there is a limit increase. Simple we allocate lesser 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 500MB of memory rather than a 1GB as in the case before.
Lets 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 low as possible.
This is why choosing the growth factor is critical, because you cannot solve both the problems. You choose a higher growth factor, you will have more free memory on 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 2x strategy. Set the growth factor as 2 and don’t look back, because nothing else matters more. Most implementations do this, 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 Vector and C++’s standard std::vector implementations. These all follow the same strategy.
Optimising for memory
When you decide to optimise for memory on the other hand, you are in for a ride. Because you need to walk the fine line between not wasting memory and avoiding bad performance. If you reallocate too often, you cannot say that your implementation still is “Amortised O(1)”. The ‘amortised’ part requires you to keep the reallocations as minimum as possible. 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 the 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 achieve memory wastage. It doesn’t make much sense to have an array with capacity of a million and have only a few thousand elements. But when you shrink, it is a good idea to have atleast half the capacity as free so that you can accomodate for insertions. If you shrinked 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 refered 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 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. The prime example is go, which uses a function to smooth out the growth factor. And another example is python, which uses similar idea to have a large growth factor on smaller array size and gradually reduced growth factor as the array grows bigger.
Other optimisations
Some implementations like FBVector, the facebook’s implementation of the 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 effeciently on growth factor 1.5x.
Trade Offs when compared to other alternatives
Dynamic arrays don’t perform well when you need to insert or delete values in the middle rather than in the end. If your use case involves deleting values in the middle, it is better to use a linked list which provides better performance. Once you have the reference to the element that needs to be deleted, it can be removed in O(1) time whereas the same in dynamic arrays will take O(n) due to the fact that you now need to move the arrays after the point of insertion/deletion.
Also 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 before hand.
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 in the cache 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 lower growth factor and high performance on higher growth factor.
- shrinking can save memory
- requires 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 before hand and inserts and deletes are only done at the end.