Большая задержка при циклическом просмотре TList больших записей

Я использую Delphi 10.1 Berlin в Windows 10.

У меня есть две записи разных размеров. Я написал код, чтобы пройти через два TList<T> из этих записей для проверки истекшего времени. Циклический просмотр списка больших записей выполняется намного медленнее.

Может кто-нибудь объяснить причину и предоставить решение для ускорения цикла?

type
  tTestRecord1 = record
    Field1: array[0..4] of Integer;
    Field2: array[0..4] of Extended;
    Field3: string;
  end;

  tTestRecord2 = record
    Field1: array[0..4999] of Integer;
    Field2: array[0..4999] of Extended;
    Field3: string;
  end;

procedure TForm1.Button1Click(Sender: TObject);
var
  _List: TList<tTestRecord1>;
  _Record: tTestRecord1;
  _Time: TTime;
  i: Integer;
begin
  _List := TList<tTestRecord1>.Create;

  for i := 0 to 4999 do
  begin
    _List.Add(_Record);
  end;

  _Time := Time;

  for i := 0 to 4999 do
  begin
    if _List[i].Field3 = 'abcde' then
    begin
      Break;
    end;
  end;

  Button1.Caption := FormatDateTime('s.zzz', Time - _Time); // 0.000

  _List.Free;
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  _List: TList<tTestRecord2>;
  _Record: tTestRecord2;
  _Time: TTime;
  i: Integer;
begin
  _List := TList<tTestRecord2>.Create;

  for i := 0 to 4999 do
  begin
    _List.Add(_Record);
  end;

  _Time := Time;

  for i := 0 to 4999 do
  begin
    if _List[i].Field3 = 'abcde' then
    begin
      Break;
    end;
  end;

  Button2.Caption := FormatDateTime('s.zzz', Time - _Time); // 0.045

  _List.Free;
end;
Источник

1 ответ

Решение

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

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

Ваша программа делает очень мало, кроме выделения памяти и доступа к памяти. Следовательно, производительность этих операций с памятью доминирует.

Теперь, ваш выбор времени - только код, который читает из списков. Таким образом, разница в производительности копирования памяти по заполнению не является частью выполненного вами теста. Ваши временные различия в основном сводятся к чрезмерному копированию памяти при чтении, как я объясню ниже.

Рассмотрим этот код:

if _List[i].Field3 = 'abcde' then

Так как _List[i] это запись, тип значения, вся запись копируется в неявную скрытую локальную переменную. Код фактически эквивалентен:

var
  tmp: tTestRecord2;
...
tmp := _List[i]; // copy of entire record
if tmp.Field3 = 'abcde' then

Есть несколько способов избежать этой копии:

  1. Измените базовый тип на ссылочный тип. Это изменяет требования к управлению памятью. И у вас может быть веская причина хотеть использовать тип значения.
  2. Используйте контейнерный класс, который может возвращать адрес элемента, а не копию элемента.
  3. Переключиться с TList<T> в динамический массив TArray<T>, Это простое изменение позволит компилятору получать доступ к отдельным полям напрямую, не копируя целые записи.
  4. Использовать TList<T>.List получить доступ к базовому массиву объекта списка, содержащего данные. Это будет иметь тот же эффект, что и предыдущий элемент.

Пункт 4 выше - самое простое изменение, которое вы можете сделать, чтобы увидеть большую разницу. Вы бы заменили

if _List[i].Field3 = 'abcde' then

с

if _List.List[i].Field3 = 'abcde' then

и это должно привести к очень значительным изменениям в производительности.

Рассмотрим эту программу:

{$APPTYPE CONSOLE}

uses
  System.Diagnostics,
  System.Generics.Collections;

type
  tTestRecord2 = record
    Field1: array[0..4999] of Integer;
    Field2: array[0..4999] of Extended;
    Field3: string;
  end;

procedure Main;
const
  N = 100000;
var
  i: Integer;
  Stopwatch: TStopwatch;
  List: TList<tTestRecord2>;
  Rec: tTestRecord2;
begin
  List := TList<tTestRecord2>.Create;
  List.Capacity := N;

  for i := 0 to N-1 do
  begin
    List.Add(Rec);
  end;

  Stopwatch := TStopwatch.StartNew;
  for i := 0 to N-1 do
  begin
    if List[i].Field3 = 'abcde' then
    begin
      Break;
    end;
  end;
  Writeln(Stopwatch.ElapsedMilliseconds);
end;

begin
  Main;
  Readln;
end.

Мне пришлось скомпилировать его для 64 бит, чтобы избежать нехватки памяти. Выход на моей машине около 700. Поменять List[i].Field3 в List.List[i].Field3 и вывод в отдельных цифрах. Время довольно грубое, но я думаю, что это демонстрирует смысл.

Проблема большой записи, не являющейся дружественной к кешу, остается С этим сложнее разобраться, и потребуется подробный анализ того, как код реального мира работает с его данными.

Кроме того, если вы заботитесь о производительности, то вы не будете использовать Extended, Поскольку он имеет размер 10, а не степень двойки, доступ к памяти часто не совпадает. использование Double или же Real который является псевдонимом для Double,

Источник
Другие вопросы по тегам