Saturday 12 June 2004

Extending arrays

This may seem trivial, but I often see code that does something like:

  Ints: array of Integer;
  I: Integer;
  SetLength(Ints, 1);
  for I := 1 to SomeLargeNumber do
    SetLength(Ints, Length(Ints) + 1);
    Ints[Length(Ints) - 1] := SomeIntegerValue;

Instead of a for loop, sometimes a while loop is used, especially when the number of items to expect is unknown.

This way of constantly adding to the end of the array looks natural, since the array now only contains as many elements as required to hold all values, but this has some serious disadvantages.

When SetLength is used, and the new memory size of the array is larger than the block used for the old array, then new memory must be allocated, and the contents of the array must be copied over. If you do this many times, this could not only fragment memory (this depends a little on what other memory allocations are going on), but it will also get slow, since each time, a larger number of items must be copied around.

To avoid this, you can do a few things:

  • Dimension the array according to the expected number of items. In the loop above, this would be dependent on SomeLargeNumber. But even if you don't know the exact number of items to expect, then be sure to "guesstimate" it, and don't estimate it too low.
  • Since the array dimension is not the same as the number of of valid items it contains, you must keep track of the actual number of items stored.
  • Each time you add an item, you increment the count of actual values. If this reaches the size of the allocated array, you'll have to redimension it. But don't redimension in chunks of one element each. Redimension by a fixed fraction of the already allocated array, for instance add half of the current size, or more.

Of course, if you do this often, this can get tedious to do, so it could be a good idea to wrap this into a class, with methods to add items, get the count, perhaps even insert items, etc. As an example, you can use the source code for TList in the file Classes.pas (if this comes with your edition of Delphi). Or you can have a look at this simple Integer array class on my website.

Rudy Velthuis