Large dynamic array - slow writing

Question

I have a routine that adds ordinal elements ("Day" or "Night" enumerated type) to a multi-dimensional dynamic array, which is declared as:

TShiftType = (stDay, stNight);
TScheduleArray =  array of array of array [1..DaysPerWeek] of TShiftType;

The array could contain anything between 1 element (e.g. (Day, Day, Day, Day, Day, Night, Night)) and over 20,000 elements. Each element may itself have sub-elements depending on how many weeks are being processed.

So one element in a two-week array could look like:

((stDay, stDay, stDay, stDay, stDay, stNight, stNight), (stDay, stDay, stDay, stDay, stDay, stNight, stNight))

This runs extremely fast and works very well when the number of elements is relatively low (about under 1000). Once the number of weeks and elements increases, just adding a new element to the array (after calling SetLength to increase the length of the array by one) starts to slow down exponentially.

Sometimes I also get an Access Violation. When I use the "Find Error" facility in Delphi, it takes me to the @DynArrayAsg method in the CPU window. But I never get the EOutOfMemory exception that the Delphi help says I would get if not enough memory was available to reallocate the variable.

Is this slowing down of access to memory expected behaviour? I am using Delphi 6.

Answer 1

Yes, because when you reallocate it, if there's not enough contiguous space to just add one element on the end of the existing array, it has to find another block that's big enough, allocate it, copy your entire existing array, and then deallocate the original. The bigger your array, the longer the copy becomes.

TList helps to mitigate this problem by allocating its internal array in powers-of-two sizes, instead of "exactly as big as I need", and then using a Count variable to mark the upper bounds of what's actually being used. Maybe you could do something similar?

Also, if you don't already have it, get FastMM. It's much better at allocating and reallocating memory than Delphi 6's built-in memory manager.