Задержка при зацикливании через TList больших записей

Question

Я использую 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; 

Answer 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.