AddCollection和FragmentableQueue

• 下载示例 - 11.5 KB

目的

在介绍工作原理之前，我想先解释一下“为什么”。

本文介绍的类旨在实现极快的速度，并避免其他集合中与内存消耗和碎片化相关的问题。它们不是通用集合，但针对其功能进行了高度优化。因此，如果您需要以下任一功能，请使用这些类：

• 在内存中存储任意数量的项并尽快进行一次 foreach 迭代；
• 在内存中存储任意数量的项，进行一次 foreach 迭代，并允许已使用的项尽快被回收；
• 在内存中存储任意数量的项，并尽快创建数据的不可变版本，避免新的内存分配或复制。

引言

.NET Framework 包含许多通用集合类，它们实际上执行的功能远超大多数情况所需，或许正是因为做了太多，它们并未针对最常见的使用场景进行优化。

对我而言，最大的例子就是 List<T> 类。在许多情况下，如果我们只是想在执行 foreach 之前将可变数量的数据加载到内存中（如果我们读取文件或从数据库获取数据，并且希望在 foreach 之前关闭此类资源，就会发生这种情况），我们会使用列表将这些数据放入内存中。List<T> 实际上是 .NET 基类库 中可用于完成此类工作的最简单类，因此它似乎是理想的选择……但实际上，可以做得更好，而本文就是关于如何做到这一点的。

大 O 符号

在本文中，我将使用一些 O(n) 和 O(1) 符号。此类符号用于表示集合的方法在考虑集合中实际元素数量时如何工作。

O(n) 意味着特定操作直接受集合中实际项目数量的影响。例如，将一个集合的内容复制到另一个集合是 O(n) 操作，因为必须访问所有项目才能进行复制。

O(1) 意味着特定操作具有恒定的复杂度。无论集合是空的还是包含数百万个项目，这都不重要。通常，获取集合中的项目数量是 O(1)，因为大多数集合将实际项目数量存储在特定字段中，因此无需迭代整个集合即可知道有多少个项目。

需要注意的是，两个 O(1) 操作可能具有不同的速度。O(1) 仅表示操作不会因集合中项目数量的增加而变慢，但它并没有说操作很快，或者它不会时不时地有“不同的决策”。

List<T> 类的缺点

在提出解决方案之前，让我们先了解一下将 List<T> 类用作此类缓冲区的缺点。List<T> 使用一个单一数组来存放所有项，这为 getter 和 setter 提供了 O(1) 的复杂度，但对于 Add() 方法则不然。考虑到 .NET 应用程序的默认配置，这种用于存放所有项的单一数组意味着：

• 时不时地，必须分配一个更大的数组，并且所有项都必须从一个数组复制到另一个数组；
• 我们不能拥有使用超过 2GB 内存的列表，即使计算机中有很多 GB 的空闲内存（请注意，这是数组的字节大小，实际数组长度可能小得多，例如，一个 int 数组在内存中将占用其长度的 4 倍字节）；
• 我们需要一个请求大小的连续空闲内存块。我们的计算机可能拥有足够的空闲内存，但这些内存块可能非常分散；
• 在一段时间内，我们将同时拥有更大和更小的数组在内存中，因为垃圾回收器需要一些时间来运行。

我们实际上可以配置 .NET 应用程序以使用大于 2GB 的数组，但由于这种配置会改变所有数组分配，因此被认为相对不安全（因为这些数组可能会传递给非托管代码），即便如此，数组的 Length 仍将限制为 20 亿个项目（31 位长度），而且我们仍然会遇到其他问题。

性能

据说 List<T>.Add() 的最佳情况复杂度为 O(1)，最差情况复杂度为 O(n)。这甚至被用来比较 List<T> 和 ImmutableList<T> 的性能，例如（您可以在 http://blogs.msdn.com/b/andrewarnottms/archive/2013/01/07/immutable-collection-algorithmic-complexity.aspx 和 上一篇文章 的“性能特征”主题中查看表格）。

这个 O(n) 看起来比实际情况更糟。确实，如果我们在随机时刻添加项目，其中一个操作可能会变成 O(n)，因为在某个时刻，用于在列表中存储项目的内部数组可能需要调整大小。但考虑到这种情况不常发生，我们可以说列表类的平均复杂度为 O(2)。

为了说明这一点，让我们了解 List<T> 类的工作原理。

默认情况下，它从一个包含 4 个元素的数组开始。

因此，添加第一个、第二个、第三个和第四个元素每个操作都是 O(1)，因为元素只是简单地放入内部数组中。因此，4 个操作的总复杂度为 O(4)，因为我们有四次 Add() 调用。

然后，为了添加第五个元素，需要分配一个新数组（其长度是前一个数组的两倍，因此在本例中为 8），然后需要复制 4 个原始元素（一个 O(4) 操作），最后添加新元素（一个 O(1) 操作）。这意味着仅第 5 次插入就是 O(5)，插入 5 个元素总共需要 O(9)（请注意，数组分配不计入 O() 计算，但应考虑其对性能的影响）。

因此，如果我们只是想一次性插入 5 个项目（而不是在随机时刻插入 5 个项目），我们可以说每个操作都接近 O(2)（非常精确地说是 1.8）。考虑到模式始终相同，新的重新调整大小将在添加第 9 个项目、第 17 个项目、第 33 个项目等时发生，并且重新调整大小之间的所有其他操作都将是 O(1)。这使得当我们有更多项目时，平均结果更接近 O(2)。

因此，如果您只想使用列表在单个方法中插入随机数量的项并返回它，我们可以真正认为列表的 Add() 操作是 O(2)，所以要插入 1000 个项，我们可以说它的总复杂度接近 O(2000)。

这已经很不错了。它本可以更好（Add() 始终为 O(1)），但考虑到 CPU 缓存的工作方式，将项目从较小数组复制到较大数组的速度非常快，这意味着对于同时发生的添加操作，我们不会看到列表所需时间是 O(1) 集合的两倍，它可能只多出 10% 的时间。

因此，List<T> 在最坏情况下为 O(n)，但实际上它非常快，因为最坏情况随着我们拥有更多项目而变得不那么常见，并且因为 CPU 缓存在此最坏情况下有所帮助。对于一次性插入所有项目的方法，我们确实可以说每个操作的平均复杂度为 O(2)，但由于这是一个常数，我们应该说它是 O(1)，即使这个 1 比它应该的要慢一点。

做得更好

如果我们的目的是将一些数据放入内存，然后进行 foreach 循环，我们可以做得更好。

这个想法是，我们不是每次需要“调整大小”时都将数组中的项目复制到一个更大的数组中，而是分配一个新的数组，但我们只是简单地将一个数组“链接”到另一个数组（我们将有带数组的节点）。也就是说，旧数组保留用于第一个项目，新项目直接放入新数组中。这使得 Add() 调用变为 O(1)，因为从不复制以前的项目。

然后，要进行 foreach，每次我们读完一个数组中的所有项目时，就转到下一个数组。

“链接”数组而不是复制它们的事实也意味着我们不会在调整大小后在内存中丢失一些数组等待回收，这自然会支持略有碎片化的内存。

细节

我们必须意识到，那些 O(1) 插入可能会 谎报 实际性能。如果我将每个项目都放在自己的节点中（就像一个链表），我将得到一个相当慢的 O(1) 操作（是的，LinkedList<T> 几乎从不是解决方案，即使它是末尾插入的 O(1) 列表）。这就是我决定使用数组的原因，这样在一段时间内我可以将项目直接放入数组中，避免新的分配。

这也是我使用增加新数组大小规则的原因（这与 List<T> 的做法非常相似，但没有复制）。由于我不需要所有内容都在一个大型数组中，因此我还对这些数组的大小施加了限制。默认限制（可配置）是 100 万个项目。对于一个 int 集合，这意味着这些数组的大小限制为 4 MB（对于引用类型，在 32 位处理器上也将是 4 MB，在 64 位处理器上将是 8 MB）。

考虑到这种大小限制，我们可以获得出色的性能，并且集合还可以使用碎片化的内存，而实际上不会成为碎片化的来源（就像我们每次添加都分配一个新节点一样）。此外，考虑到我们可以分配任意数量的数组，我们没有 2 GB 的限制。除了 Count 属性（它仅供参考），我们可以真正地说我们可以支持任何大小的集合，只要计算机支持它。

实现 O(1) Add() 方法的代码如下

public void Add(T item)
{
  if (_countInActualArray == _actualArray.Length)
  {
    long count = _count;
    int maximumSize = _getMaximumBlockSize();

    if (maximumSize < 1)
      throw new InvalidOperationException("The GetMaximumBlockSize delegate returned an invalid value.");

    if (count > maximumSize)
      count = maximumSize;

    var newNode = new _Node(count);
    _actualNode._nextNode = newNode;
    _actualNode = newNode;
    _actualArray = newNode._array;
    _countInActualArray = 0;
  }

  _actualArray[_countInActualArray] = item;
  _count++;
  _countInActualArray++;
}

您应该注意，我总是存储实际的数组（最后一个），所以对于新的 Add() 调用，我不需要导航到最后一个来添加项。

不可变性：ForEachCollection

在讨论性能时，我提到了不可变集合的链接。不可变性解决方案出现了一个新的“热潮”，因为这种不可变性提供了一些自动保证，例如支持并行访问而无需任何形式的锁，并保证您可以将集合传递给任何方法，而知道该方法不会“破坏”您的集合内容。此外，对于接收不可变集合的方法，它保证内容不会在某个随机时间被集合创建者更改，因此如果它想确保内容不会更改，则无需复制内容。

考虑到实际类永远不会替换其内部数组中的任何项（它只能添加新项），我们可以通过将对第一个节点的引用和项数复制到另一个类中，轻松创建它的不可变视图。这将非常快（O(1) 操作），因为我们不需要复制数组的内容，并且它将具有完全的不可变性保证。即使我们继续向原始 AddCollection 添加项，不可变视图也将知道它可以读取多少项，因此新添加的项不会被不可变视图看到。

我将此集合命名为 ForEachCollection，因为这是它唯一优化执行的操作（在 AddCollection 前面加上 Immutable 似乎不正确，因为它不再执行添加操作）。

ForEachCollection 的实际代码复制了更多信息（如最后一个数组和该最后一个数组中的项目数量），但这只是为了提高性能，不影响不可变性特性。

这是它的代码

public sealed class ForEachCollection<T>
{
  private readonly AddCollection<T>._Node _firstNode;
  private readonly T[] _lastArray;
  private readonly int _countInLastArray;
  private readonly long _count;

  internal ForEachCollection(AddCollection<T>._Node firstNode, T[] lastArray, int countInLastArray, long count)
  {
    _firstNode = firstNode;
    _lastArray = lastArray;
    _countInLastArray = countInLastArray;
    _count = count;
  }

  public long Count
  {
    get
    {
      return _count;
    }
  }

  public Enumerator GetEnumerator()
  {
    return new Enumerator(_firstNode, _lastArray, _countInLastArray);
  }
  
  // Note: The real code has some more methods and most of the work
  // actually happens in the Enumerator. But you can already see that
  // this class is immutable, as all its fields are readonly.
}

请注意，这些集合在添加新项时比 List<T> 和 ImmutableList<T> 都要快（如果您真的想比较，也比 LinkedList<T> 快）。在枚举项时，这些集合应该几乎与 List<T> 一样快（我不知道为什么，但在我所有的测试中，这些集合的枚举和 ToArray() 都比 List<T> 快，即使我预期 List<T> 会更快一点）。显然，这些集合的功能远不如 List<T> 和 ImmutableList<T>，因为它们不应该用作可以搜索项、删除项等的列表。

如果您的目的是将一些数据放入内存，然后对其进行迭代（无论是否使其成为不可变对象），那么这些类非常适合这项工作。

Clear() 方法

如果您查看 AddCollection，您会发现它有一个 Clear() 方法。那么这会破坏 ForEachCollection 的不可变性吗？

答案是否定的。Clear() 方法不会更改现有节点和数组（可能正在被 ForEachCollection 使用）的内容。它只是分配一个新的第一个数组和节点，并设置其他字段以表明它处于该节点的开始位置。所以，不用担心，即使有方法清除 AddCollection，它也不会影响 ForEachCollection 的不可变性。

IEnumerable<T>、IReadOnlyCollection<T>、IReadOnlyList<T> 和 LINQ

当我最初创建这些类时，我实现了 IReadOnlyList<T> 接口，这随之实现了 IEnumerable<T> 和 IReadOnlyCollection<T> 接口。

我最初认为这没问题，但后来我改变了主意。这很糟糕。非常糟糕。

由于是 IEnumerable<T>，因此可以使用 LINQ 方法。但是 LINQ 方法，如 Count()、ToArray() 和 ElementAt()，实际上只查找非只读接口，即使这些方法本身是只读的。

这意味着如果有人收到被视为 IEnumerable<T> 的 AddCollection 或 ForEachCollection，调用 Count()、ToArray() 或 ElementAt() 会非常慢，因为 LINQ 方法会搜索可变接口，如果找不到，则使用遍历所有项的默认算法（在 ToArray() 的特殊情况下，还会创建大量中间副本，就像 List<T> 类所做的那样）。

我也可以实现可变接口，但是 AddCollection 没有实现 Remove() 或索引器 set 等方法。实现这些方法是不可能的，否则会破坏其不可变视图所需的保证。更糟糕的是，作为不可变类的 ForEachCollection，如果实现可变接口并保持只读状态，会显得很糟糕。

最后，由于我们的类型支持 64 位 Count，而不仅仅是 32 位，我决定最好避免使用任何接口，如果您确实需要，您可以轻松创建一个适配器来实现您需要的接口（无论是只读接口还是可变接口，以便充分利用 LINQ 方法的性能）。为整个集合创建适配器也是一个 O(1) 操作，所以应该不会太差。

您可以查看示例下载，因为我已经提供了两个扩展类，它们允许您在需要时创建实现这些接口的适配器。

还能做得更好吗？

实际上，如果我们的需求是将大量项目放入内存并迭代这些项目一次或多次，无论是否需要不可变集合，AddCollection 都可以被认为是优于 List<T> 类的。

但我经常看到的一个常见情况是，人们将所有数据库记录加载到内存集合中，以便尽快关闭连接（我认为这是一种不好的做法，但一些 DBA 坚持认为数据应该这样读取）。然后代码对内存集合执行 foreach 操作，进行一些可能需要数小时的事务性工作。

这里的重点是：所有数据都需要一次性加载（通常非常快，加载数百万条记录可能需要几秒钟），但一旦处理完就可以立即回收。但普通的列表（或 AddCollection）不允许已处理的项从内存中移除，直到整个集合可以被垃圾回收。

那么，我们能改善这种情况吗？

答案：是也不是

我们无法更改 AddCollection 类来删除已读取的项，因为这将破坏 ForEachCollection 的不可变性保证，但我们可以创建一个类似于 AddCollection 的类，针对此场景进行优化。

我将此类命名为 FragmentableQueue。它的 Enqueue() 操作与 AddCollection.Add() 方法非常相似，但在 Dequeuing（或使用枚举器或 foreach 迭代）时，此类总是删除刚刚读取的项（在数组中放置 default(T) 值），并且当它到达数组末尾时，它允许整个数组/节点被回收。

如果此集合用于快速 foreach，则可能比 AddCollection/ForEachCollection 慢，因为它具有清除已读项的额外逻辑。但是，如果它用于非常大（且耗时）的批处理，它具有允许已处理项的内存被回收的优点。

它还具有另一个可能在某些特定情况下有用的特性，即您可以在迭代时实际 Enqueue() 新项目，并且这些项目将被正在运行的 foreach 看到。如果某些项目实际上可以生成相同类型的子项目，这会很有用。

与 .NET 的 Queue<T> 类型相比，它具有以下重要区别：

• 它没有 Peek()、Contains()、CopyTo()、ToArray() 或 TrimExcess() 方法；
• 它拥有 64 位的 Count；
• 它在执行 foreach 时实际上会移除项；
• 它允许在执行 foreach 时将新项入队；
• 如果你一直入队然后出队特定数量的项，它会分配新的数组，而 .NET 的数组在（可能需要的初始调整大小之后）能够重新利用相同的数组。

与 ImmutableQueue<T> 的比较是最难的。在该性能/复杂度表中，Enqueue() 是一个 O(1) 操作，但没有关于 Dequeue() 如何工作的信息。实际上，似乎第一次 Dequeue() 是 O(N)，然后其他的都是 O(1)。我不太确定，因为我没有看到最终的实现，但我已经看到一些文档解释了如何基于两个不可变栈创建一个不可变队列，其中一个栈必须在第一次使用时反转，我看到 ImmutableQueue<T> 使用了这样的不可变栈。

这也意味着 ImmutableQueue<T> 比其他解决方案使用更多的内存，并且如果我们不断入队新项同时出队（我没有测试，但我相信在每次 Enqueue() 之后，下一个 Dequeue() 将再次变成 O(N)），它可能会更慢。

因此，考虑到用于存储所有项的内存量，Enqueue() 和 Dequeue() 的 O(1) 复杂度，以及出队项和数组可以被回收的事实，我看不出 FragmentableQueue 如何不是赢家。此外，重要的是要注意，即使 ImmutableQueue<T> 在访问时是线程安全的，诸如 queue = queue.Enqueue(value); 这样的操作也不是，所以如果您需要两个线程并行入队/出队项，您将需要使用锁或替代技术，而不是简单地设置 queue 变量，因为在创建带有添加/删除项的新队列和设置该变量之间存在竞态条件。

内存消耗

在比较普通的可变集合和新的不可变集合时，不仅仅是性能或不可变性保证重要，了解内存影响也很重要，这可以看作是内存消耗和垃圾回收。

文章中有所提及，但并未明确说明，因此我将在此处总结：

• List<T> 和 Queue<T> 使用单个数组作为它们的存储库，因此它们只在内部数组需要调整大小时生成垃圾。此外，为了避免过多的调整大小，数组长度会加倍。这意味着如果我们正好在调整大小后停止添加项目，我们将会有大量的未使用空间；
• ImmutableList<T> 和 ImmutableQueue<T> 为每个项目使用一个新节点。这意味着每个项目比普通的可变列表占用更多内存，但从不会分配带有空位的数组。在某些情况下，它可以使用更少的内存，但在我的大多数测试中，这些集合比 List<T> 使用更多内存。无论它们使用多少内存，通过将节点作为独立对象（并通过创建新节点进行修改），不可变集合会生成大量需要回收的垃圾；
• 本文介绍的类同时使用了节点和数组。但节点不是按项分配，而是按数组分配，数组大小从 32 开始，可以增长到 100 万 项（这两个值都可配置）。添加新项时，从不生成垃圾。如果您添加超过 100 万项，最大的浪费空间（如果您在那个糟糕的时刻停止添加项）是一个包含 999,999 个未使用项的数组。然而，在大多数情况下，它将比 List<T> 使用更少的内存（当它确实使用更多内存时，只会是几字节的差异，由节点引起），同时在大多数情况下，它将比不可变集合使用更少的内存（ImmutableList<T> 使用的每个项一个节点的开销如此之大，以至于对于 120 万个 int，它使用了 18 MB，而 List<T> 使用了 8 MB，而此解决方案使用了 7 MB）。

对于队列的特殊情况，我们必须知道：

• 用作队列的列表（枚举一次）在列表本身被回收之前，不允许任何项被回收；
• 可变队列将允许所有出队的项尽快被回收，但用于存储项的内部数组在队列本身被回收之前不会被回收；
• FragmentableQueue 将允许项目在出队后立即被回收，并且将允许内部数组（节点）在其所有项目都被读取后单独被回收。这确实是一个“中间”情况，因为数组不会立即被回收，但我们不需要完成使用整个队列来释放一些数组；
• ImmutableQueue<T> 允许每个节点在出队时被回收，但实际上它即使在出队时也会分配内存，这在某些极端情况下可能导致异常，并且似乎是错误的，因为我们只是简单地“出队”。

无论如何，我们必须记住，对于大型队列，数据要么分配在 大对象堆 中，要么可能会一直存活到第 2 代，因此立即释放内存不会是一个很大的优势（我们必须再次记住，在大多数情况下，不可变集合确实会使用更多内存）。

数百万个项目

我有时可能会有点极端（大多数时候？）。在我的例子中，我总是谈论数百万个项目。但是如果我们只需要使用一些项目，比如 10 或 30 个呢？

答案是所有的集合都经过优化，从小开始，当它们很小的时候，我认为没有什么可担心的。列表、队列、不可变列表、不可变队列或本文介绍的解决方案都将正常工作，您可能永远不会发现与这些小集合相关的问题。

我专注于极端情况，例如拥有数百万个项目，因为那是在哪里我们会看到是否存在问题，无论是大量的垃圾回收（这也意味着速度变慢），无论是由于内存不足（即使我们实际拥有足够的内存，但内存碎片化）引起的异常，无论是即使我们没有垃圾回收也导致的一般性能损失。

我并不是说我们应该将数百万个项目放入内存中（在大多数情况下我们可以找到更好的解决方案），但如果我们需要这样做，我们必须做好准备应对。

结论

我希望这些类对您像对我一样有用。我真的相信它们是加载未知数量数据并仅枚举一次（FragmentableQueue）或使其不可变以便可以提供给任何需要不可变集合的方法的最佳选择，最重要的是，它们比使用 ImmutableList<T>（即使使用构建器）快得多，并且使用更少的内存。

示例

示例应用程序进行了一些速度比较，并试图显示使用了多少内存。我认为查看这些类的工作方式和它们的速度很有用，但我们不应该只关注数字。

无论哪个集合更快或更慢，对于 1000 万个项目来说，差异微不足道，在实际情况中，CPU 缓存可能不会如此频繁地使用（因为我们不会仅仅进行空枚举，而是在继续枚举之前实际对数据做一些事情）。因此，最好从内存消耗、碎片化、性能和预期用途的总和来判断，而不是仅仅从性能或内存消耗来判断。

以下是应用程序的示例结果：

This application only uses some methods of the classes AddCollection,
ForEachCollection and FragmentableQueue. It is only useful if you actually
see its code as the tests done here only prove the collections are working.

If you use this sample to see the performance comparison, you should compile it
in Release mode and you should execute it outside Visual Studio to see how well
it performs.


Testing AddCollection<string>
Adding 10000000 items: 00:00:03.0040895
ToArray: 00:00:00.0378765
Iterating the immutable version: 00:00:01.6909224
Memory used in MB: 304

Testing .NET List<string>
Adding 10000000 items: 00:00:03.0394706
ToArray: 00:00:00.0399380
Iterating: 00:00:01.7178831
Memory used in MB: 330


Testing FragmentableQueue<string>
Enqueuing 10000000 items: 00:00:03.1558260
Memory used with all items in MB: 304
Dequeuing half the number of items: 00:00:00.8744547
Memory used now in MB: 156

Testing .NET Queue<string>
Enqueuing 10000000 items: 00:00:03.2705367
Memory used with all items in MB: 330
Dequeuing half the number of items: 00:00:00.8774198
Memory used now in MB: 197


Testing FragmentableQueue<int>
Enqueuing 100000000 items: 00:00:00.8012018
Memory used with all items in MB: 381
Dequeuing half the number of items: 00:00:00.5150972
Memory used now in MB: 194

Testing .NET Queue<int>
Enqueuing 100000000 items: 00:00:01.3980741
Memory used with all items in MB: 512
Dequeuing half the number of items: 00:00:00.3947550
Memory used now in MB: 512

Tests finished. Press [ENTER] to quit.

简要分析结果，我们得到：

• AddCollection<string> 稍微快一点，并且比 .NET List<string> 使用更少的内存；
• 当所有项都加载完毕时，FragmentableQueue<string> 使用的内存量与 AddCollection<string> 完全相同。同样的规则适用于 .NET 的 List<string> 与 Queue<string> 的比较；
• 在出队一些项目后，FragmentableQueue<string> 能够释放 148 MB（48%），而 Queue<string> 仅释放 133 MB（40%）；
• 在处理 int 类型时，FragmentableQueue 仍然能够释放内存（从 381 MB 减少到 194 MB，内存消耗减少了 49%），而 .NET 的 Queue 则继续使用相同的内存量。这发生的原因是 .NET 队列移除了未使用的项（允许收集 string，但 int 没有可收集的内容），但它从未减少其内部数组的大小；
• 与 .NET 类相比，FragmentableQueue<int> 在出队项时速度较慢。这是它唯一速度较慢的情况，但考虑到它允许内存被回收，这可能是中间发生回收的结果。也许重新运行测试可以得到不同的结果。

我没有列出 ImmutableList<T> 和 ImmutableQueue<T> 的结果，但在这些测试中，不可变版本使用了更多的内存并且速度更慢（即使使用构建器，ImmutableList<T> 也慢了近 9 倍）。如果您愿意，请下载示例，添加 Microsoft.Bcl.Immutable 并取消注释 #define IMMUTABLE_TEST，以便运行这些测试。

最令我印象深刻的是 ImmutableQueue<int> 的测试。普通的 .NET Queue<int> 对于 1 亿个项目使用了 512 MB，而不可变版本使用了 1525 MB。而且，在出队时，它没有释放内存，反而崩溃了。这是因为即使在出队时也会分配新对象。它确实允许旧节点被回收，但它使用了如此多的内存，以至于没有帮助。

源文件

最重要的源文件是：

• AddCollection.cs：这实际上是 AddCollection 和 ForEachCollection 的代码。这两个类在同一个文件中，因为我认为如果您只是想复制一个文件并让这些类工作，那会更容易，而且，这些类确实协同工作；
• FragmentableQueue.cs：此文件仅包含 FragmentableQueue 类，它可以独立于示例项目中的任何其他文件使用，因此如果您愿意，可以自由地将其复制到您的项目中。

还有两个 Extensions 文件。它们实际上为 AddCollection 和 ForEachCollection 添加了扩展方法，以创建适配器，这样您就可以通过 IReadOnly* 接口或可变接口来查看它们。它们实际上并没有完全实现可变接口，但通过可变接口查看这些对象可能有助于使用某些 LINQ 方法。

这些扩展在单独的文件中，因为我理解有些用户可能不需要或不希望支持这些接口。