循环遍历大记录的TList时出现长时间延迟

Question

我在Windows 10中使用Delphi 10.1 Berlin.

我有两个不同大小的记录.我编写代码来遍历其中两个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,而不是2的幂,所以内存访问经常是错误对齐的.使用Double或Real哪个是别名Double.