Delphi and Free Pascal bencmark: array vs TList vs dynamic array

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