4 окт. 2019 г.

Правильный обход матрицы

    В статье Романа Кунина "Оптимизация кода: память" рассмотрены две функции на C++, которые суммируют элементы матрицы. Они практически одинаковы, только первая функция обходит элементы матрицы по строкам, а вторая по столбцам. Проведем подобный тест на Delphi 7 и Delphi 10.3.2.
    В отличии от оригинального теста, в котором суммируют элементы матрицы я предлагаю еще измерить скорость заполнения матрицы.
program Matrix;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  SysUtils;

const
  ciMaxIndex = 9999;

procedure ByRow;
var
  a: Array of Array of Integer;
  c, i, j, iSum: Integer;
  dt: TDateTime;
begin
  SetLength(a, ciMaxIndex + 1, ciMaxIndex + 1);

  dt := Now;
  for c := 1 to 10 do
    for i := 0 to ciMaxIndex do
      for j := 0 to ciMaxIndex do
        a[i, j] := 1;
  Writeln(FormatDateTime('ss.zzz', (Now - dt) /10));

  iSum := 0;
  dt := Now;
  for c := 1 to 10 do
    for i := 0 to ciMaxIndex do
      for j := 0 to ciMaxIndex do
        Inc(iSum, a[i, j]);
  Writeln(FormatDateTime('ss.zzz', (Now - dt) /10));

  SetLength(a, 0);
  WriteLn(iSum);
end;

procedure ByCol;
var
  a: Array of Array of Integer;
  c, i, j, iSum: Integer;
  dt: TDateTime;
begin
  SetLength(a, ciMaxIndex + 1, ciMaxIndex + 1);

  dt := Now;
  for c := 1 to 10 do
    for i := 0 to ciMaxIndex do
      for j := 0 to ciMaxIndex do
        a[j, i] := 1;
  Writeln(FormatDateTime('ss.zzz', (Now - dt) /10));

  iSum := 0;
  dt := Now;
  for c := 1 to 10 do
    for i := 0 to ciMaxIndex do
      for j := 0 to ciMaxIndex do
        Inc(iSum, a[j, i]);
  Writeln(FormatDateTime('ss.zzz', (Now - dt) /10));

  SetLength(a, 0);
  Writeln(iSum);
end;

begin
  ByRow;
  ByCol;
end.
Результаты:
КомпиляторЗаполнениеЧтение
по строкампо столбцамразницапо строкампо столбцамразница
Delphi 70.055 мс1.281 мс23.290.140 мс1.194 мс8.53
Delphi 10.3.2 32-бит0.055 мс0.692 мс12.580.141 мс0.712 мс5.05
Delphi 10.3.2 64-бит0.134 мс0.661 мс4.930.159 мс0.732 мс4.60
Эта была матрица значений типа integer, теперь заменим "Array of Array of Integer" на "Array of Array of Int64" и проверим скорость работы с матрицей, содержащей значения типа int64.
КомпиляторЗаполнениеЧтение
по строкампо столбцамразницапо строкампо столбцамразница
Delphi 70.109 мс0.881 мс8.080.167 мс1.161 мс6.95
Delphi 10.3.2 32-бит0.108 мс0.823 мс7.620.166 мс1.065 мс6.416
Delphi 10.3.2 64-бит0.142 мс0.849 мс5.980.165 мс1.029 мс6.24

    Как видно из таблиц с результатами, скорость обработки матрицы по строкам со времен Delphi 7 не изменилась. А вот скорость обработки ее по столбцам, значительно выросла. Так, что плюсик в карму разработчикам Delphi.
    Такого впечатляющего результата как у Романа (разницы в 25 раз), у меня не получилось (будем патриотично думать, что Delphi работает с памятью лучше, чем C++), но мои тесты тоже показывают, что двумерный массив правильно обходить по строкам.
"Когда мы работаем над данными, желательно чтобы они находились в памяти рядом. Обход матрицы по столбцам имеет плохую локальность, потому что матрица хранится в памяти построчно."
©2016 Роман Кунин "Оптимизация кода: память"

Комментариев нет: