Faster way of initializing arrays in Delphi

Question

I'm trying to squeeze every bit of performance in my Delphi application and now I came to a procedure which works with dynamic arrays. The slowest line in it is

SetLength(Result, Len);

which is used to initialize the dynamic array. When I look at the code for the SetLength procedure I see that it is far from optimal. The call sequence is as follows:

_DynArraySetLength -> DynArraySetLength

DynArraySetLength gets the array length (which is zero for initialization) and then uses ReallocMem which is also unnecessary for initilization.

I was doing SetLength to initialize dynamic array all the time. Maybe I'm missing something? Is there a faster way to do this?

EDIT: Describing the main algorithm would take a lot of space and really is unnecessary because it'm trying to optimize a small part of it. In general terms it's a veriant of Vehicle Routing Problem (http://en.wikipedia.org/wiki/Vehicle_routing_problem). I do need zillions of allocations, because I have to keep all the data, and keep it separately. Probalby it would help if I could think of some clever data structure here, but anything I can think of would greatly increase the complexity of the code. Basically I've done everything I could on the algorithmic level, so now I'm trying to get everything I can from the lowlevel things. So this is rather narrow question: is there any possibility to increase this particular call. And I think that to do this I need to write my own initialization function based on the SetLength code. And make it inline.

Answer 1

This is more of a comment, but since posting large blocks of code in comments isn't pretty, I post it here instead.

Sometimes, if you do not know how many elements you will end up with in the end, it might be tempting to write code like this:

var
  Arr: array of cardinal;

procedure AddElement(const NewElement: cardinal);
begin
  SetLength(Arr, length(Arr) + 1);
  Arr[high(Arr)] := NewElement;
end;

This is very bad, for then the memory needs to be reallocated each time you add a new element. A much better approach (if possible) is to find an upper bound for the number of elements, such as MAX_ELEMENTS = 100000; and then set the length initially:

SetLength(Arr, MAX_ELEMENTS);

Then you create a variable like

var
  ActualNumberOfElements: cardinal = 0;

and write

procedure AddElement(const NewElement: cardinal);
begin
  Arr[ActualNumberOfElements] := NewElement;
  inc(ActualNumberOfElements);
end;

When you are done filling the array, simply truncate it:

SetLength(Arr, ActualNumberOfElements);

Answer 2

If you're only calling it once and it's taking a long time then you're requesting more RAM then it's available, causing the OS to swap-out other stuff in an attempt to make room for you. Fix: add more RAM, use smaller arrays.

If you're calling it in a loop then the "realloc" is the problem. Every time you call it, increasing the length of the array little-by-little, Delphi is re-allocating your whole array, and then it's copying everything from the old array to the new array. Not exactly efficient.

Answer 3

"Premature optimization is the root of all evil."
I doubt you'd have to care about a once in a lifetime initialization...
That is unless you call it a zillion times, then I suggest you redesign your code.

Answer 4

Max wrote :

I have a zillion calls to a function which does one time SetLength( Result, Len ).

Check on how you use your function : do you really need a zillion distinct calls to this allocating function ? can you, as Francois suggested, redesign your code to lower the number of calls ?

If you really need one zillion distinct calls to your function, and need to speed things up, I think you will need to leave dynamic arrays and use a different structure.

But before doing that, and enter a complete debugging hell, I would strongly join Francois suggestion, and try to redesign the code.

Maybe you can tell us a bit more about your algorithm ? Is it about handling graphical 3D structures ?

[EDIT] Ok, if it's about solving NP-complete problems, I would try to avoid allocating as much as possible.

Most of the time, you can give an upper bound to the size of your arrays/stacks/structures - e.g : #cities, #vehicles + #drivers, #roads * #cities ...

For those parts, I would suggest allocating once the biggest possible array, and handling manually the fact that you use only the first n rows or such.

Given the computing time it can save afterwards, even allocating structures in n^2 or n^3 can be acceptable.

Optimizing SetLength : what you suggest makes sense.

However, if dynamic arrays are well adapted to writing Delphi code - mainly because of their "automatic constructor" semantics - they are, IMHO, not well adapted to high performance computations - it relies heavily on RTTI, reference counting can give you surprises every now and then...
What you are suggesting is a change in dynamic arrays semantics. Try to see if the solution "changing your data type" is really that impossible to write & debug.

Answer 5

The slowest part of SetLength is not "unnessesary calls" or something - it's allocation of memory, which is performed by memory manager (and ReallocMem in your case will be simple GetMem, since source pointer is nil).

So, what memory manager do you use? Are you, by any chance, on D7 without FastMM?

Try to install FastMM and see if it helps a bit.

Answer 6

Instead of calling a function that contains SetLength a zillion times, rather preallocate the storage, and pass the preallocated arrays into the function. One such way is something like this:

const
  NUM_ARRAYS = 1000;
  ARRAY_SIZE = 1000;
type
  TMyArray = array [0..ARRAY_SIZE] of Integer;
var
  MyStorage: array[0..NUM_ARRAYS] of TMyArray;

procedure DoWork(var AArray: TMyArray);
begin
  Blah;
end;

procedure MainLoop;
var
  i: Integer;
begin
  for i := 0 to High(MyStorage) do
  begin
    DoWork(MyStorage[i]);
  end;
end;

This will be significantly faster than calling SetLength inside an inner loop. The main thing to watch out for is using too much memory for the hardware.