Dynamic arrays: how they work and how to use them

Let’s talk for a bit about how dynamic arrays work “behind the scenes.” First, a dynamic array primer. If you’re already comfortable with the use of dynamic arrays, you can skip this section:

In the old days, when you needed an array in your Delphi program, the array had to be static, which meant its size had to be known at the time you wrote your code. Those look like this:

  Nums: array[0..8] of Integer;

Way back in Delphi 4, dynamic arrays were added to the language. Dynamic arrays can vary in size.  You don’t need to declare its size when you write your code, and you can programatically change the size of the array. Dynamic arrays look like this:

  Nums: array of Integer;

This creates a reference to the array, but doesn’t actually allocate any memory for the contents of the array. Before we can put something in the array, we need to set its length using the conveniently named SetLength procedure:

SetLength(Nums, 8);

Now that the length is set, we can assign values to the array, just like we could with a static array:

Nums[0] := 1;
Nums[1] := 2;
Nums[2] := 4;
Nums[7] := 128;

(Note that dynamic arrays are zero-indexed, so the highest index in the array is Length – 1)

What happens if, during the course of our program running, the size of the array needs to change? With static arrays, this simply wasn’t possible. With dynamic arrays, it’s easy! Just call SetLength again, then you can use the newly allocated elements in your array:

SetLength(Nums, 16);
Nums[8] := 256;
Nums[15] := 32768;

Even after you’ve changed the size, the original elements are still there – no data is lost (OK, data *IS* lost if you resize an array to be SMALLER than it was before), and you just continue on your way.

So, how does all this magic that makes java developers jealous happen under the hood?

Static arrays are really just pointers to a contiguous area of memory that was allocated to hold the right number of elements for the array. The compiler does the math to turn an array index into a pointer to the into a pointer to a single element in the array.

Dynamic arrays, on the other hand, add a level of indirection. The dynamic array is really a record that holds a few pieces of information about the array, including its size (number of elements), and a pointer to a static array! When you call SetLength, several things happen:

  1. The size field is updated
  2. A new (internal) static array is allocated with the new size
  3. The elements of the old static array are copied to the new array
  4. The static array pointer is changed to the new array
  5. The old static array’s memory is disposed

OK, there’s technically a bit more to it than that. Two points:

  • If there is enough room at the internal static array’s current position to reallocate, AND there is only one variable referencing the array, only step #1 happens. It is, however, good practice to assume that all of this happens every time you change the array’s length.
  • If there are are other variables that refer to the same array, the old static array will not be disposed, because the other variables will continue to point to the old data.

Even with those caveats, for the remainder of this discussion, we’ll assume that all of these steps happen with every change of the dynamic array’s length.

To get the best performance out of your Delphi program, it’s really important to understand the implications of step #3. Whenever you change the size of a dynamic array, the array will be copied, which means iterating through the array in memory. The time this takes is proportional to the size of the array: It takes longer to copy an array of 20 elements than an array of 10.

So what are we to do? We shouldn’t shy away from using dynamic arrays – they’re very useful! We just need to understand best practices for using them. Those best practices depend on the use case.

Here are two common use cases, along with some tips for getting the best dynamic array performance out of them:

First, if you’re reusing a dynamic array variable, but don’t need the old contents after resizing, do the following:

  • Don’t maintain more than one reference to the array. In other words, if A and B are dynamic arrays, never write A := B;
  • Before using SetLength to resize the array, call SetLength(arr, 0); This “resets” the array, and since the new array size is 0, doesn’t copy anything
  • After calling SetLength(arr, 0), call SetLength again to set your dynamic array to its new size

The effects of this are negligible for small arrays, but if you’re using large arrays (how large is hardware-dependent), this will yield significant speed increases. In one of my tests, using this technique shaved almost 10 milliseconds off of the speed of an array resize.

The second case is if your array is going to “live” for a long time, growing continuously. This is typical of any kind of aggregation scenario: an array of strings for a log, and array of numbers being collected for later analysis, etc….

  • Choose a “reasonable” initial length for your array. Make your best guess as to how many elements it might need to hold in a typical situation.
  • NEVER increase the length of your array by 1, or 2, or any constant amount. Never do anything that looks like this: SetLength(arr, Length(arr) + 1);
  • When the time comes to reallocate the array, double its size: SetLength(arr, Length(arr) * 2). Research shows that this strikes the ideal balance between time and space for most cases.
  • Consider using a TList. TList isn’t always the most efficient way to handle a “continuous growth” data structure, but its ease of use might make up for it. For very small arrays (less than a couple hundred element), TList will be just as fast as using a dynamic array with the size-doubling technique, but for anything larger, the dynamic array will be faster.

In a nutshell: dynamic arrays are very useful, precisely because they can be resized, but understanding how to best resize them is important for getting the best speed and memory performance out of your applications.

Take your Delphi programming to the next level with Castalia for Delphi, an advanced code editor for Delphi, integrated right into your favorite IDE.

10 Responses to Dynamic arrays: how they work and how to use them

  1. A. Bouchez January 28, 2014 at 8:42 am #

    Instead of writing SetLength(arr, 0), you may write Finalize(arr) which is cleaner and easier to understand.

    We wrote an open source wrapper which add object-oriented methods against any dynamic array, like Add/Delete/Sort/Find/Save/Load/Clear and an optional external Count integer variable, which makes in-place growing much faster, as you stated in your article. It also feature optional custom JSON serialization, if needed.
    See http://blog.synopse.info/post/2011/03/12/TDynArray-and-Record-compare/load/save-using-fast-RTTI

    • jacob January 28, 2014 at 8:46 am #

      That’s cool, Arnaud. Thanks for sharing!

    • Kryvich January 30, 2014 at 2:29 am #

      Great addition! I like dynamic arrays, they are everywhere in my code.

      And interesting article, Jacob.

  2. David Heffernan January 28, 2014 at 10:03 am #

    SetLength(arr, 0);
    arr := nil;

    are all identical and interchangeable.

    FWIW I think it is a shame that your static array has length 9, but the first dynamic array example has length 8.

    Nums: array[0..7] of Integer;

    would make more sense to me

  3. Mason Wheeler January 28, 2014 at 4:46 pm #

    “So, how does all this magic that makes java developers jealous happen under the hood?”

    There appears to be a verb missing from this sentence.

    • jacob January 28, 2014 at 4:51 pm #

      Mason, parse it this way:

      So, how does all this magic ^ happen under the hood?

      Where ^ is “that makes java developers jealous,” as an adjective phrase describing “all this magic.”


      • LachlanG January 29, 2014 at 4:37 pm #

        It was a hard sentence to read correctly on the first pass. Rearrange the commas and it reads much easier.

        “So how does all this magic, that makes java developers jealous, happen under the hood?”

        Enough procrastinating, time to get down to work.

        Nice article.

  4. Giedrius January 29, 2014 at 3:31 am #

    And how does this make Java developers jealous ?

  5. Thomas Mueller January 30, 2014 at 10:08 am #

    Doubling the size might be overkill, I usually increase the size by a factor of 1.5. It depends on the size of the data stored in each element obviously and the speed your array grows.

  6. A. Bouchez February 4, 2014 at 4:21 am #

    You wrote:
    “The dynamic array is really a record that holds a few pieces of information about the array, including its size (number of elements), and a pointer to a static array! ”

    In fact, this is not true. There is no such record with a nested pointer.
    A dynamic array is like a reference-counted string: it is a pointer, which contains:
    – nil for length=0;
    – points to the data if length>0.

    That is, you can write pointer(aDynArray) to point to either nil, or the first element of the data.

    The actual array length is stored BEFORE the data, with the reference count.
    See System.pas:
    TDynArrayRec = packed record
    {$IFDEF CPUX64}
    _Padding: LongInt; // Make 16 byte align for payload..
    RefCnt: LongInt;
    Length: NativeInt;

For programmers, by a programmer

Hi. My name is Jacob, and I'm the creator of Castalia.

I starting programming in 1986, learning Lightspeed Pascal on a Mac Classic. Today, I'm a professional programmer, teacher, and entrepreneur.

I have a Master's Degree in Computer Science, and I still love Pascal and Delphi.

I believe that writing code is the heart and soul of software development, and I love helping programmers write code more effectively.