Free Pascal bencmark: array vs TList vs dynamic array

Submitted by Serguei_Tarassov on

Let's make a simple benchmark test for random and sequential access. I will compare:

  • array with predefined size (allocated on stack)
  • TList container class (allocated on heap)
  • dynamic array (allocated on heap)
  • generic TFPGList (allocated on heap)

I use an array of 10M elements having integer and varaint data type. You can easily change its type definition in "type" section if need.

program Bench1;
 
uses
  SysUtils,
  Classes,
  DateUtils,
  FGL,
  Math;
 
const
  MaxDimension = 10000000;
 
type
  TTestedValueType = variant;
  PTestedValueType = ^TTestedValueType;
  TTestFPGList = specialize TFPGList<PTestedValueType>;
 
var
  D1, D2: TDateTime;
  RndAddr: array [0..MaxDimension - 1] of integer;
  TestArray: array [0..MaxDimension - 1] of TTestedValueType;
  TestList: TList;
  TestFPGList: TTestFPGList;
  TestDynArray: array of TTestedValueType;
  p: ^TTestedValueType;
  i: integer;
  Sum: double;
begin
  Randomize;
  writeln('Prepare random access array');
  for i := 0 to MaxDimension - 1 do
    RndAddr[i] := Math.RandomRange(0, MaxDimension);
  // Simple 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('Simple 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('Simple 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');
  TestFPGList := TTestFPGList.Create;
  TestFPGList.Capacity := MaxDimension;
  for i := 0 to MaxDimension - 1 do
  begin
    new(p);
    p^ := 0;
    TestFPGList.Add(p);
  end;
  D1 := Now;
  for i := 0 to MaxDimension - 1 do
    PTestedValueType(TestFPGList[RndAddr[i]])^ := RndAddr[i];
  D2 := Now;
  writeln('TTestFPGList. 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(TestFPGList[i])^;
  D2 := Now;
  writeln('TTestFPGList. Sequential read access. Elapsed, sec: ',
    DateUtils.SecondSpan(D2, D1):5:2,
    '. Sum: ', Sum);
  for i := 0 to MaxDimension - 1 do
    dispose(PTestedValueType(TestFPGList[i]));
  TestFPGList.Free;
end.

Results

For integer data type both arrays are more efficient.

Prepare random access array
Simple array. Random write access. Elapsed, sec:  0.20
Simple array. Sequential read access. Elapsed, sec:  0.04. Sum:  3.1609327369835000E+013
Prepare list
TList. Random write access. Elapsed, sec:  0.96
TList. Sequential access. Elapsed, sec:  0.08. Sum:  3.1609327369835000E+013
Prepare dynamic array
Dynamic array. Random write access. Elapsed, sec:  0.20
Dynamic array. Sequential access. Elapsed, sec:  0.04. Sum:  3.1609327369835000E+013
Prepare generic list
TTestFPGList. Random write access. Elapsed, sec:  1.37
TTestFPGList. Sequential read access. Elapsed, sec:  0.10. Sum:  3.1609327369835000E+013

Now change value type to variant:

type
  TTestedValueType = variant;

Prepare random access array
Simple array. Random write access. Elapsed, sec:  0.77
Simple array. Sequential read access. Elapsed, sec:  1.02. Sum:  3.1615978366404000E+013
Prepare list
TList. Random write access. Elapsed, sec:  1.74
TList. Sequential access. Elapsed, sec:  1.06. Sum:  3.1615978366404000E+013
Prepare dynamic array
Dynamic array. Random write access. Elapsed, sec:  0.74
Dynamic array. Sequential access. Elapsed, sec:  1.06. Sum:  3.1615978366404000E+013
Prepare generic list
TTestFPGList. Random write access. Elapsed, sec:  1.87
TTestFPGList. Sequential read access. Elapsed, sec:  1.23. Sum:  3.1615978366404000E+013

As you can see, for different value types like integer or variant the static or dynamic array are the fastest solutions. Not "better" but faster.

Integer Variant
Random write access, sec Sequential read access, sec Random write access, sec Sequential read access, sec
Simple 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
TFPGList 1.37 0.10 1.87 1.23

Test environment

  • HP ProBook 6550b, Intel(R) Core(TM) i5 CPU M 520, RAM 8 GB
  • 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