Increase speed of a tight loop with little action :)

Question

I have started using Lazarus, a Free Pascal Delphi-version. And... today's computers handle quite a lot of bytes in one CPU-cycle... which brings me to my problem and question.

I have a tight loop where I want to move part of an array of bytes up or down, always by only one byte. Consider the code:

LowBound := 7;
HighBound := 245; // Always the last record in the array.
// Shrink the array
For x := LowBound to Highbound-1 DO ByteArray[x] := ByteArray[x+1];
SetLength(ByteArray,HIGH(ByteArray)); // Shrinks the array by one.

// Next Part as an example of my Expanding.
LowBound := 18;
HighBound := 207; // Always the last record in the array.
SetLength(ByteArray,HIGH(ByteArray)+2); // Expands the array by one.
For x := HighBound DownTo LowBound DO ByteArray[x+1] := ByteArray[x];

Supposing that 32bit code can shift 4 bytes at each CPU-cycle, and 64bit code can shift 8 bytes in one CPU-cycle, my simple 1 Byte at a time approach seems to be not at all efficient.

Maybe casting the array as an array of Cardinal (32 bit) or INT64 (64 bit) and then do some shifting/moving? Anybody have ideas on this? Grateful for answers, Morten.

Answer 1

After being made aware of the MOVE-function

I have done some experiments on FOR --> DO loops versus this MOVE function. My work on Bytes has been paused because I can not yet get my routines to work, so I performed some testing on arrays of Cardinals.

First I made two arrays of 1 000 000 (1 million) cardinals. Second I filled the first array with random numbers (took less than 1 second) Third, I Indexed this array using the second array, hence sorting the numbers using the second array. Here are my results:

1. Using FOR --> DO loops for shifting the index, Total time: 11m33s
2. Using the function MOVE for shifting the index, Total time: 2m 2s

Without going into details about my sorting routine, the fact remains that a variable part of the index is shifted up by 1 position close to 1 000 000 (1 million) times. Doing this using a loop is simply very very costly in terms of CPU-cycles.

Where data is constantly being moved, it is well worth the time investigating the MOVE-function.

---

The MOVE-function is almost 6 times faster than looping.

Note: Since the move-function moves a specified number of bytes, the amount of records to move must be multiplied by 4. Cardinal = 4 bytes.

VAR
  DataArray : ARRAY [0..100] OF Cardinal;

Move(DataArray[5],DataArray[6],4); // Equals: DataArray[6] := DataArray[5];
Move(DataArray[5],DataArray[6],(100-5)*4); // Shifts the whole array from pos 5 one position up.