delphi – 循环访问大记录的TList时出现长时间延迟

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;

首先,我想考虑整个代码,甚至填充列表的代码,我知道你没有定时.由于第二个记录的大小较大,因此在分配该记录类型时需要复制更多内存.此外,当您从列表中读取时,较大的记录比影响性能的较小记录的缓存友好性较低.后一种效应可能不如前者显着.

与此相关的是,在添加项目时,必须调整列表的内部记录数组的大小.有时,调整大小会导致无法就地执行重新分配.当发生这种情况时,将分配新的内存块,并将先前的内容复制到此新块.对于较大的记录,该副本显然是非常昂贵的.如果您知道它的长度,可以通过预先分配数组来缓解这个问题.列表容量是要使用的机制.当然,你并不总是提前知道它的长度.

您的程序在内存分配和内存访问方面做得很少.因此,这些存储器操作的性能占主导地位.

现在,您的时间只是从列表中读取的代码.因此,人口中的内存复制性能差异不是您执行的基准测试的一部分.你的时间差异主要取决于阅读时过多的记忆复制,我将在下面解释.

考虑以下代码：

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

因为_List [i]是一个记录,一个值类型,所以整个记录被复制到一个隐含的隐藏局部变量.代码实际上相当于：

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

有几种方法可以避免此副本：

>将基础类型更改为引用类型.这会改变内存管理要求.您可能有充分的理由想要使用值类型.
>使用可以返回项目地址而不是项目副本的容器类.
>从TList切换< T>到动态数组TArray< T>.这个简单的更改将允许编译器直接访问各个字段而无需复制整个记录.
>使用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的别名.