Submitted by st on
Let's perform a simple benchmark testing the random and sequential access to arrays and lists. I would like to compare:
- static array with predefined size (allocated on stack)
- TList container class (allocated on heap)
- dynamic array (allocated on heap)
- generic Delphi TList or Free Pascal TFPGList (allocated on heap)
I use an array/list of 10M elements of integer and varaint data type. You can change the type definition in "type" section if need to test other cases.
program Bench1; {$APPTYPE CONSOLE} {$R *.res} uses SysUtils, Classes, DateUtils, {$IFDEF FPC}FGL{$ELSE}System.Generics.Collections{$ENDIF}, Math; const MaxDimension = 10000000; type TTestedValueType = integer; PTestedValueType = ^TTestedValueType; TTestGenericList = {$IFDEF FPC}specialize TFPGList<PTestedValueType>{$ELSE}TList<PTestedValueType>{$ENDIF}; var D1, D2: TDateTime; RndAddr: array [0..MaxDimension - 1] of integer; TestArray: array [0..MaxDimension - 1] of TTestedValueType; TestList: TList; TestGenericList: TTestGenericList; TestDynArray: array of TTestedValueType; p: PTestedValueType; i: integer; Sum: double; begin Randomize; writeln('Prepare random access array'); for i := 0 to MaxDimension - 1 do RndAddr[i] := Math.RandomRange(0, MaxDimension); // Static array for i := 0 to MaxDimension - 1 do TestArray[i] := 0; D1 := Now; for i := 0 to MaxDimension - 1 do TestArray[RndAddr[i]] := RndAddr[i]; D2 := Now; writeln('Static array. Random write access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2); Sum := 0; D1 := Now; for i := 0 to MaxDimension - 1 do Sum := Sum + TestArray[i]; D2 := Now; writeln('Static array. Sequential read access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2, '. Sum: ', Sum); // TList writeln('Prepare list'); TestList := TList.Create; TestList.Capacity := MaxDimension; for i := 0 to MaxDimension - 1 do begin new(p); p^ := 0; TestList.Add(p); end; D1 := Now; for i := 0 to MaxDimension - 1 do PTestedValueType(TestList[RndAddr[i]])^ := RndAddr[i]; D2 := Now; writeln('TList. Random write access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2); Sum := 0; D1 := Now; for i := 0 to MaxDimension - 1 do Sum := Sum + PTestedValueType(TestList[i])^; D2 := Now; writeln('TList. Sequential access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2, '. Sum: ', Sum); for i := 0 to MaxDimension - 1 do dispose(PTestedValueType(TestList[i])); TestList.Free; // Dynamic array writeln('Prepare dynamic array'); SetLength(TestDynArray, MaxDimension); for i := 0 to MaxDimension - 1 do TestDynArray[i] := 0; D1 := Now; for i := 0 to MaxDimension - 1 do TestDynArray[RndAddr[i]] := RndAddr[i]; D2 := Now; writeln('Dynamic array. Random write access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2); D1 := Now; Sum := 0; for i := 0 to MaxDimension - 1 do Sum := Sum + TestDynArray[i]; D2 := Now; writeln('Dynamic array. Sequential access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2, '. Sum: ', Sum); SetLength(TestDynArray, 0); // Generic list writeln('Prepare generic list'); TestGenericList := TTestGenericList.Create; TestGenericList.Capacity := MaxDimension; for i := 0 to MaxDimension - 1 do begin new(p); p^ := 0; TestGenericList.Add(p); end; D1 := Now; for i := 0 to MaxDimension - 1 do PTestedValueType(TestGenericList[RndAddr[i]])^ := RndAddr[i]; D2 := Now; writeln('TTestGenericList. Random write access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2); Sum := 0; D1 := Now; for i := 0 to MaxDimension - 1 do Sum := Sum + PTestedValueType(TestGenericList[i])^; D2 := Now; writeln('TTestGenericList. Sequential read access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2, '. Sum: ', Sum); for i := 0 to MaxDimension - 1 do dispose(PTestedValueType(TestGenericList[i])); TestGenericList.Free; end.
Results
For integer data type both static and dynamic arrays are faster than the lists. Now change value type to variant.
type TTestedValueType = variant;
After restarting the test, you can observe the same sample.
Integer | Variant | |||
---|---|---|---|---|
Random write access, sec | Sequential read access, sec | Random write access, sec | Sequential read access, sec | |
Free Pascal | ||||
Static array | 0.20 |
0.04 | 0.77 | 1.02 |
TList | 0.96 | 0.08 | 1.74 | 1.06 |
Dynamic array | 0.20 | 0.04 | 0.74 | 1.06 |
TTestGenericList | 1.37 | 0.10 | 1.87 | 1.23 |
Delphi | ||||
Static array | 0.29 |
0.04 | 0.63 | 0.52 |
TList | 2.29 | 0.05 | 3.59 | 0.54 |
Dynamic array | 0.29 | 0.04 | 0.69 | 0.53 |
TTestGenericList | 2.31 | 0.05 | 3.48 | 0.57 |
Conclusions
For different value types like integer or variant the static or dynamic array are the fastest solutions in Delphi and FPC.
Remember, that "fastest" doesn't mean "better".
Test environment
- HP ProBook 6550b, Intel(R) Core(TM) i5 CPU M 520, RAM 8 GB
- Free Pascal case:
- Ubuntu 14.04 64 bits Linux 3.16.0-60-generic
- Free Pascal Compiler version 3.0.0 [2015/12/05] for x86_64
- O1 optimization level
- Delphi case:
- Windows 10 64 bits
- Delphi 10.2 Tokyo
- Optimization is on