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 than is 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

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 4

"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.