delphi - 循环遍历大记录 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

首先，我想考虑整个代码，甚至是填充列表的代码，我确实意识到您没有计时。由于第二条记录的大小较大，因此在分配该记录类型时需要复制更多内存。此外，当您从列表中读取时，较大的记录比较小的记录对缓存不太友好，这会影响性能。后一种影响可能不如前一种显着。

与此相关的是，当您添加项目时，列表的内部记录数组必须调整大小。有时，调整大小会导致无法就地执行的重新分配。当发生这种情况时，会分配一个新的内存块，并将以前的内容复制到这个新 block 中。对于更大的记录来说，该副本显然非常昂贵。如果您知道数组的长度，则可以通过预先分配数组来缓解这种情况。列表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 的别名。