循环遍历大记录的 TList 时延迟很长

Question

我在 Windows10.

中使用 Delphi 10.1 柏林

我有两条不同大小的记录。我编写了代码来遍历这些记录中的两个 TList<T> 以测试经过的时间。循环遍历较大记录的列表运行s 慢得多。

任何人都可以解释原因，并提供使循环运行更快的解决方案吗？

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

有几种方法可以避免这种复制：

将基础类型更改为引用类型。这改变了内存管理要求。您可能有充分的理由想要使用值类型。
使用可以 return 项目地址而不是项目副本的容器 class。
从 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 的别名。

循环遍历大记录的 TList 时延迟很长

Long delay when looping through a TList of big records

delphi

record

tlist

delphi-10.1-berlin