Тест скорости: array vs TList vs dynamic array

Пишет Serguei_Tarassov,

Проведем небольшой замер скорости случайного и последовательного доступа, используя:

  • статический массив (array, должен размещаться на стеке)
  • класс-контейнер TList (размещается в куче)
  • динамический массив (тоже размещается в куче)

Используем массив из 10 миллионов элементов имеющих типы данных "integer" и "varaint". При необходимости вы можете легко изменить тип в соответствующей секции программы.

program Bench1;
 
uses
  SysUtils,
  Classes,
  DateUtils,
  Math;
 
const
  MaxDimension = 10000000;
 
type
  TTestedValueType = integer;
  PTestedValueType = ^TTestedValueType;
 
var
  D1, D2: TDateTime;
  RndAddr: array [0..MaxDimension - 1] of integer;
  TestArray: array [0..MaxDimension - 1] of TTestedValueType;
  TestList: TList;
  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 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 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 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 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);
end.

Результаты

Для целого типа данных оба массива ожидаемо более быстры для случайного доступа, чем список. При последовательном доступе разница не такая существенная.

Prepare random access array
Simple array. Random access. Elapsed, sec: 0.12
Simple array. Sequential access. Elapsed, sec: 0.03. Sum:  3.16025412697520E+013
Prepare list
TList. Random access. Elapsed, sec: 1.01
TList. Sequential access. Elapsed, sec: 0.05. Sum:  3.16025412697520E+013
Prepare dynamic array
Dynamic array. Random access. Elapsed, sec: 0.13
Dynamic array. Sequential access. Elapsed, sec: 0.03. Sum:  3.16025412697520E+013

Теперь изменим тип на variant:

type
  TTestedValueType = variant;

Относительная разница для значений структурного типа, коим является variant, в целом не меняется, просто увеличивается общее время обработки за счет увеличения размера выделенной под массивы памяти.

Но для списка общее время случайного доступа почти не изменилось. Это объясняется структурой: в списке хранятся указатели, а они во всех тестах имеют одинаковый размер.

Prepare random access array
Simple array. Random access. Elapsed, sec:  0.60
Simple array. Sequential access. Elapsed, sec:  0.74. Sum:  3.16119039688220E+013
Prepare list
TList. Random access. Elapsed, sec:  1.08
TList. Sequential access. Elapsed, sec:  0.76. Sum:  3.16119039688220E+013
Prepare dynamic array
Dynamic array. Random access. Elapsed, sec:  0.57
Dynamic array. Sequential access. Elapsed, sec:  0.73. Sum:  3.16119039688220E+013

Как можно видеть для разных типов данных, простых и структурных, статический или динамический массивы являются более быстрым решением при случайном или последовательном доступе к элементам.

Но именно более быстрыми, а не "лучшими". Во многих случаях управление списками при помощи TList и его аналогов может оказаться не только проще, но и производительнее за счет отсутствия необходимости реорганизации памяти при вставке/удалении элементов.