Allocation-Free Collections

假设你有一个方法，通过创建临时的List来收集某些数据，并根据这些数据来统计信息，然后销毁这个临时列表。这个方法被经常调用，导致大量内存分配和释放以及增加的内存碎片。此外，所有这些内存管理都需要时间，并且可能会影响性能。

对于这些情况，您可能希望将所有数据保留在堆栈（stack）中，并完全避免内存分配。我们向您展示了几种可以实现此目的的方法。

即使这些用例对你来说不适用，但你也可能会发现本文很有用，因为它使用了一些有趣的概念和Delphi语言功能。

堆栈与堆，值与参考类型（Stack vs Heap, Value vs Reference Types）

首先，让我们先了解一些术语。你可能已经知道本节中的所有内容，但无论如何我们都要回顾一下。

内部存储器有两种主要类型：堆栈和堆。堆栈被用于存储方法的局部变量和可能的其他数据（如在许多平台返回地址）。堆存储动态分配的内存，包括字符串，动态数组和对象。

当您了解了这些类型的内存时，您可能会在同一段落或章节中阅读有关值和引用类型的内容，因为这两者有些相关。值类型直接在存储器位置存储了一些值，而 参考类型存储的指针则指向位于别处（通常，但不是必须在一个值堆）。值类型的示例是整数，浮点数，布尔值，枚举，字符，记录和静态数组。引用类型的示例是字符串，对象，对象接口，动态数组和指针。

关于类和对象之间的区别存在争议，它们有时可以互换使用。我个人认为两者是不同的：一个类描述了契约（字段，方法，属性和事件），一个对象是一个类的特定实例。

只有值类型可以存储在堆栈中。在堆栈上声明引用类型时，只是其指针值存储在堆栈中 ; 实际值是在堆上分配的（如果没有，则为nil）。

procedure StackVsHeap;
var
  A: Integer;
  B: TList<Integer>;
begin
  A := ;
  B := TList<Integer>.Create;
  B.Add();
  B.Add();
end;

这导致以下内存布局（内存位置仅供参考）：

正如你所见，在创建TList 并在至少分配两个堆存储器来增加一些项目的结果：一个存储列表对象的实例数据（FItems，FCount以及一些其他字段）和一个用于存储物品的动态数组。在此示例中，动态数组可容纳4个项目，其中2个项目使用。动态数组将根据需要增长以容纳新项目。

基于堆栈的集合

您可能会遇到这些堆内存分配不理想的情况。它们可能会增加内存碎片，从而导致内存使用量增加。此外，分配和释放动态内存并不是一种廉价的操作，每秒多次创建临时列表可能会影响性能。另一方面，堆栈上的“分配”内存通常是零成本操作。它只涉及在方法开始时调整堆栈指针，编译器在大多数情况下都会这样做。

如果您可以完全在堆栈上创建一个集合（也就是说，集合属性FCount和实际项目都应该存在于堆栈中），则可以解决这些问题。实际上，您之前可能已经使用过这些类型的集合：

procedure StaticArray;
var
  Items: array [..] of Integer;
  Count: Integer;
begin
  ...
end;

本地静态数组本质上是基于堆栈的集合，尽管不是用户友好的集合。为了使这个数组更像列表，我们可以用方法将它包装在一个记录中。

一个简单的基于堆栈的列表

一个简单的实现可能如下所示：

type
  TStackList<T: record> = record
  private type
    P = ^T;
  private
    FData: array [..] of Byte;
    FCapacity: Integer;
    FCount: Integer;
    function GetItem(const AIndex: Integer): T;
  public
    procedure Initialize;
    procedure Clear;
    procedure Add(const AItem: T);

    property Count: Integer read FCount;
    property Items[const AIndex: Integer]: T read GetItem; default;
  end;

您可以在AllocationFreeCollections目录中的GitHub上的JustAddCode存储库中找到此代码的更多文档版本（以及本文中的所有其他代码）。

你可能会发现这个名字TStackList有点令人困惑。这里，单词“stack”  不是指类似堆栈的数据结构，而是指列表应该存在于内存堆栈中的事实。如果你要创建一个存在于内存堆栈中的类似堆栈的集合，那么就可以调用它TStackStack。

这里有几点需要注意：

• 我选择在这里创建一个通用列表。如今，几乎不需要非通用列表。
• type参数T具有记录约束。这意味着列表只能保存值类型（暂时）。这在某种程度上简化了该列表的实现。
• 嵌套type P = ^T;声明对您来说可能是新的。它声明了一个指向列表中项目类型的类型指针。这在访问列表项的实现中很有用。
• 该列表将其项保存在256字节的静态数组中，这意味着它总是消耗256字节的（堆栈）内存，而不管类型如何T。因此，如果用于创建整数列表，则列表最多可以包含64个项目（因为整数大小为4个字节）。
• 您必须调用该Initialize方法来初始化或创建列表。此方法的作用类似于构造函数。由于记录不能没有参数的构造函数（至少在当前的Delphi版本中没有），我选择添加一个Initialize方法。您也可以选择返回列表的静态方法（如class function Create: TStackList<T>; static;），但从函数返回大型记录效率不高。
• 虽然你可以TStackList在一个对象中声明一个字段，但这并不是这个列表的目的而只是浪费内存。此类型旨在仅在方法中声明为局部变量。

实现非常简单。Initialize方法只计算集合可以容纳的项目数，并将该FCount字段设置为0（因为在堆栈上声明时，记录中的字段未初始化为0）。

procedure TStackList<T>.Initialize;
begin
  if IsManagedType(T) then
    raise EInvalidOperation.Create(
      'A stack based collection cannot contain managed types');

  FCapacity := SizeOf(FData) div SizeOf(T);
  FCount := ;
end;

它还检查类型参数T是否为托管类型，如果是，则引发异常。这可能值得一些解释。尽管type参数T具有记录约束，但这并不意味着T不能包含托管类型。例如，记录约束阻止Delphi编译：

var
  List: TStackList<String>;

但不是从编译这个：

type
  TStringWrapper = record
    Value: String;
  end;
var
  List: TStackList<TStringWrapper>;

当type参数T是引用类型或托管类型时，我们需要一些额外的代码来防止内存泄漏。我们稍后会谈到这一点并且暂时保持简单，不允许这样做。

添加项目的工作方式如下：

procedure TStackList<T>.Add(const AItem: T);
var
  Target: P;
begin
  if (FCount >= FCapacity) then
    raise EInvalidOperation.Create('List is full');

  Target := @FData[FCount * SizeOf(T)];
  Target^ := AItem;
  Inc(FCount);
end;

由于此列表的容量是固定的，因此我们需要在列表满时引发异常。我们稍后会看一个替代方案。

因为该FData字段只是一个字节数组，所以我们需要一个技巧来将类型的项T放入这个数组中。这是type P = ^T;宣言派上用场的地方。我们计算FData数组的偏移量并将其地址分配给Target类型的变量P。然后，我们可以取消引用此变量来分配值。检索项目的工作方式类似：

function TStackList<T>.GetItem(const AIndex: Integer): T;
var
  Item: P;
begin
  if (AIndex < ) or (AIndex >= FCount) then
    raise EArgumentOutOfRangeException.Create('List index out of range');

  Item := @FData[AIndex * SizeOf(T)];
  Result := Item^;
end;

您可以按如下方式使用此基于堆栈的列表（请参阅repo中的E01SimpleStackList示例）：

procedure SimpleStackListExample;
var
  List: TStackList<Integer>;
  Error: Boolean;
  I: Integer;
begin
  List.Initialize;

  { TStackList<Integer> can contain up to 256 bytes of data. An Integer
    is 4 bytes in size, meaning the list can contain up to 64 Integers. }
  for I :=  to  do
    List.Add(I);

  { Adding 64'th item should raise an exception. }
  Error := False;
  try
    List.Add();
  except
    Error := True;
  end;
  Assert(Error);

  { Check contents }
  Assert(List.Count = );
  for I :=  to List.Count -  do
    Assert(List[I] = I);
end;

具有可配置大小的堆栈列表

您可能会发现256字节的存储空间太少或太多。如果这个尺寸是可配置的，那将是很好的。如果Delphi更像C ++，我们可以使用这样的模板参数：

type
  TStackList<T: record; N: Integer> = record
  private
    FData: array [..N - ] of Byte;
  end;

var
  List: TStackList<Double, >;

但是Delphi不是C ++，而泛型不是模板。那么我们怎样才能完成类似的事情？我们可以使用另一个类型参数而不是模板参数，其唯一目的是为列表项提供存储：

type
  TStackList<T: record; TSize: record> = record
  private
    FData: TSize;
    ...

然后我们可以声明一个存储为1024字节的堆栈列表，如下所示：

type
  T1024Bytes = record Data: array [..] of Byte end;

var
  List: TStackList<Double, T1024Bytes>;

它的用法与前面介绍的固定大小的列表相同，可以在代码库中的E02StackListWithSize例子中找到此版本。

请注意，该T1024Bytes类型声明包含在记录中的静态数组。因为TSize受记录限制，静态数组本身不能用作类型，所以需要对记录封装一下。

该记录的实现也与前一个记录非常相似。但由于FData不再是静态数组，我们需要不同的代码来计算项目的地址：

procedure TStackList<T, TSize>.Add(const AItem: T);
var
  Target: P;
begin
  if (FCount >= FCapacity) then
    raise EInvalidOperation.Create('List is full');

  Target := @FData;
  Inc(Target, FCount);
  Target^ := AItem;

  Inc(FCount);
end;

由于P是一个类型指针，我们可以使用简单的指针逻辑处理运算。首先，我们设置Target指向数组中第一个项的地址，然后用当前的增量来增加FCount。作为参考，下面是完成相同计算的两种替代方法：

{$POINTERMATH ON}
Target := P(@FData) + FCount;

这会将计数直接添加到地址，而无需单独的Inc语句。但这需要将P进行类型转换并启用POINTERMATH指令。

另一种方法是手动明确地进行整个计算：

Item := P(IntPtr(@FData) + (FCount * SizeOf(T)));

在，我们首先需要将地址转换为整数类型，最好是类型，IntPtr以便在所有平台上兼容。之后，我们需要使用计数乘以列表项类型的大小来递增值。最后，我们需要对整个事物进行类型化P。这是一种更复杂的方式来实现相同的东西，但它是编译器在幕后转换前两个版本的方式。所以很高兴知道发生了什么。

具有托管类型的列表

但是如果你想要一个字符串或对象列表呢？类型参数的记录约束T当前不允许这样做。我们可以删除此约束，但是我们需要确保管理列表中的托管类型。E03StackListWithManagedTypes示例显示了执行此操作的方法。

首先，FData当在堆栈上声明列表时，该字段通常包含随机数据。如果我们将此数据解释为托管类型的项目，那么这很可能会导致访问冲突，因为Delphi将尝试使用随机地址更新字符串（或其他托管类型）的引用计数。

所以我们需要FData在Initialize方法中明确：

procedure TStackList<T, TSize>.Initialize;
begin
  ...
  if IsManagedType(T) then
    FillChar(FData, SizeOf(FData), );
end;

请注意，仅当T是托管类型时才需要这样做，用IsManagedType检查。

IsManagedType是一个“编译器魔术”函数，这意味着if在编译时而不是运行时评估条件。因此，当TStackList<Integer>编译a时，检查和FillChar语句将从代码中完全删除。另一方面，当TStackList<String>编译a时，if-check也会从代码中删除，但FillChar语句仍然存在。该编译器的神奇功能（和其他编译器的魔法功能，如HasWeakRef和GetTypeKind）可以在创建避免运行时检查效率的代码有帮助。

此外，我们Finalize现在需要一种方法（必须在一个finally部分中调用）来释放列表中的托管项目。这个方法相当于析构函数：

procedure TStackList<T, TSize>.Finalize;
begin
  Clear;
end;

procedure TStackList<T, TSize>.Clear;
begin
  if IsManagedType(T) then
  begin
    FinalizeArray(@FData, TypeInfo(T), FCount);
    FillChar(FData, FCount * SizeOf(T), );
  end;
  FCount := ;
end;

它使用单元中的FinalizeArray例程System来减少数组中项目的引用计数（取决于它们的类型）。如果没有这个，数组中的项将永远不会被释放，这会导致内存泄漏。

代码的其他部分保持不变。您可能想知道这部分代码是否仍能正常工作：

var
  Target: P;
begin
  Target := @FData;
  Inc(Target, FCount);
  Target^ := AItem;
end;

因为P可能是指向托管类型的指针，您可能想知道此代码是否会绕过任何引用计数。不是这种情况。当Delphi为托管类型编译此代码时，它将确保分配Target^将减少原始项目的引用计数（如果有）并增加新分配项目的引用计数。

一个可成长的堆栈列表

如果您事先知道列表将保留的最大项目数，则上面讨论的示例可以正常工作。再添加将导致异常。但是，如果你想利用堆栈的优势，但仍然能够在需要时增加集合呢？

因此，对于最后一个示例，我们将了解如何创建一个使用堆栈达到一定数量的列表，但是如果需要可以扩展到堆中。这可能提供两全其美：如果项目数量保持较低，则完全避免使用动态内存; 但如果需要，你仍然可以毫无问题地增加收藏。

您可以在repo中的E04GrowableStackList示例中找到此版本。此版本不允许其项目的托管类型，因此我们可以专注于“可增长”部分。

type
  TStackList<T: record; TSize: record> = record
  private
    FStackData: TSize;
    FStackCapacity: Integer;
    FHeapData: Pointer;
    FHeapCapacity: Integer;
    FCount: Integer;
    ...

现在，当我们添加一个项目时，我们检查它是否仍然适合堆栈，如果没有，我们将在堆上增加集合：

procedure TStackList<T, TSize>.Add(const AItem: T);
var
  Target: P;
  Index: Integer;
begin
  if (FCount < FStackCapacity) then
    { We can still add this item to the memory stack. }
    Target := @FStackData;
    Inc(Target, FCount);
  else
  begin
    { We need to add this item to heap memory.
      First calculate the index into heap memory. }
    Index := FCount - FStackCapacity;

    { Grow heap memory if needed to accommodate Index }
    if (Index >= FHeapCapacity) then
      Grow;

    Target := FHeapData;
    Inc(Target, Index);
  end;

  Target^ := AItem;
  Inc(FCount);
end;

该FStackData字段将保留第一FStackCapacity项。堆上分配了任何其他项。该FHeapData字段是指向最多可容纳FHeapCapacity项目的数组的指针。达到此容量时，它将增加此内存块：

{$IF (RTLVersion < 33)}
procedure TStackList<T, TSize>.Grow;
begin
  { Pre-Rio growth strategy: double collection size }
  if (FHeapCapacity = ) then
    FHeapCapacity :=
  else
    FHeapCapacity := FHeapCapacity * ;
  ReallocMem(FHeapData, FHeapCapacity * SizeOf(T));
end;
{$ELSE}
procedure TStackList<T, TSize>.Grow;
begin
  { Delphi Rio introduced a user-configurable growth strategy }
  FHeapCapacity := GrowCollection(FHeapCapacity, FHeapCapacity + );
  ReallocMem(FHeapData, FHeapCapacity * SizeOf(T));
end;
{$ENDIF}

在这里，我们利用Delphi Rio引入的用户可配置增长策略。当使用较旧的Delphi版本时，我们默认将集合大小加倍。

检索项目时，我们还必须立即检查项目是在堆栈上还是在堆上：

function TStackList<T, TSize>.GetItem(const AIndex: Integer): T;
var
  Item: P;
begin
  if (AIndex < ) or (AIndex >= FCount) then
    raise EArgumentOutOfRangeException.Create('List index out of range');

  if (AIndex < FStackCapacity) then
  begin
    Item := @FStackData;
    Inc(Item, AIndex);
  end
  else
  begin
    Item := FHeapData;
    Inc(Item, AIndex - FStackCapacity);
  end;

  Result := Item^;
end;

最后，我们应该确保在Finalize方法中释放任何已分配的堆数据。

何时不使用堆栈集合

基于堆栈的集合肯定有其用途，但好处取决于具体情况。如果您偶尔只需要一个临时列表，那么使用堆栈列表通常没有意义，您应该利用“常规”列表的灵活性。

此外，堆栈列表会占用堆栈上的内存。这通常不是问题，因为现在所有平台都提供了相当大的堆栈。但是如果在递归例程中使用堆栈列表，那么在某些时候可能会遇到堆栈溢出。所以我的建议是将堆栈列表的大小保持在几KB之内。如果你需要更多，那么内存碎片和速度可能不是你的瓶颈，常规列表就足够了。

因此，一如既往地使用，不仅仅是因为你可以。

如果您遇到基于堆栈的集合的任何有趣用例，请告诉我。

原文地址：https://blog.grijjy.com/2019/01/25/allocation-free-collections/

源码地址：https://github.com/grijjy/JustAddCode/tree/master/AllocationFreeCollections