Growable Array Performance

Here’s a subject to which everyone can relate in one way or another: growable arrays. An array is a contiguous memory block that provides O(1) random access via indexing. “Growable” means that the array has the ability to expand, accommodating more elements as needed. I’ve seen numerous homegrown implementations for “generic arrays”, “dynamic arrays”, “generic block arrays” – all written by myself and fellow teammates over the years. We rolled our own because the Standard Template Library has taken quite some time to reach an equal footing on all platforms (SGI, AIX, Solaris, Linux, Windows, etc.).

The growable array is an interesting container to study. There are two ways to grow, both fundamentally similar:

• Supposing you’re using simple data types (non-objects), your best bet is to use the heap function realloc for allocating and growing your array. At best, realloc simply expands the memory block you’re using, returning the same pointer. At worst, realloc is unable to expand and must find a new block to meet your needs – and copy your data across.

• If you’re using objects (that have meaningful construction/destruction behavior), you’re stuck using new/delete, because the C-runtime heap functions will not call your ctor/dtor. Also, there is no equivalent “realloc” for C++ objects – so you always have to allocate the larger space, copy the objects across, and release the old memory.

The takeaway: when the growable array expands, growing is expensive. Assuming the latter case (not able to use realloc) – the array elements (objects) must be copied from the old array to the new array – every object element must constructed in the new array and destructed in the old, possibly thousands or millions of times.

The solution? To cut down on number of times you’ll need to grow, grow the array in large chunks. Taken to the extreme, you could simply allocate the maximum number of elements you’d ever expect, avoiding the growing step in all but extreme outlier cases… In the vast majority of cases, however, this would lead to extreme memory waste.

It is trivial to conduct a performance study on growth rates versus memory waste. Consider my findings based on small to very-large memory target sizes (~100 elements to 75 million elements):

The results speak for themselves – the larger the growth rate (chunk size), the better the performance – but you waste the most memory. On the flip-side, if you grow your array slowly, we see struggling performance, but more efficient memory usage.

Here’s what missing from the equation: context. In almost every situation, you as the developer have context that can help this situation immensely: you know the problem you’re trying to solve. The key knowledge is this: you have some sense of the target size of the array. With this knowledge, you can construct your growable array with an initial size that meets the vast majority of your algorithm’s needs, both maximizing performance and minimizing waste.

It should be no surprise then, that STL’s vector class has a reserve(size_type) method, allowing you to specify an initial array size.

Take a look around your code. Is there a homegrown growable array? Can you reserve an initial size? Do you use STL vector – are you using the reserve() method? Depending on your algorithms and the pressure placed on your growable arrays, this small change can make a measurable performance difference.

We did this a couple of years ago in ACIS: after a fair amount of study, my buddy Jeff discovered that the vast majority of our LIST_HEADER usages contained 16 elements or less. After modifying LIST_HEADER to always start with 16 elements, Jeff’s simple change improved ACIS’ overall performance around 5% – a simple change with a huge result.