c# - 在 .net 中分配新数组的大 O 成本

Question

在 .Net 中分配数组的大 O 时间复杂度是多少？

我猜测如果数组足够小以适合临时段，它应该是 O(1)，但是随着 n 变大，找到足够的内存变得更加困难，因此它可能会改变。

此外，大对象堆可能会碎片化，因此如果 n 足够大以使数组适合 LOH，则它可能不会是 O(1)。

Answer 1

大多数人可能都知道，一个新数组将被分配到两个不同的堆中，这取决于它的大小(大小阈值为 85000 字节):

小对象堆 - 此处的分配发生在所谓的分配上下文中，该上下文是预置零的内存区域，位于临时段内。这里可能发生两种情况:

当前分配上下文中有足够的空间用于新数组 - 在这种情况下，我们可以将其视为 O(1) 操作，只需返回数组的地址(以及下一个对象的指针)

那里没有足够的空间 - 如果可能(就像它位于临时段的末尾)，将尝试通过分配量(通常约为 8kB)扩大分配上下文。在这里，我们达到了将 8kB 归零的成本，因此它要大得多。更糟糕的是，分配上下文可能无法扩大 - 因为它可能位于已分配的对象之间。在这种情况下，将创建一个新的分配上下文 - 在空闲列表的帮助下在临时段内的某处创建，以利用碎片。在这种情况下，成本更大——遍历空闲列表以找到合适的位置，然后将其归零。尽管如此，成本并不直接取决于数组大小并且是“常数”，因此我们可以像以前一样将其视为 O(1)。

大对象堆 - 因为默认情况下这里的分配频率要低得多，它使用“临时”分配上下文 - 每次分配发生在这里时，GC 在空闲列表的帮助下搜索适当的位置并将其归零。同样，空闲列表遍历和内存归零的成本都在这里发生，但由于这里的对象很大，它主要以归零成本为主。这里我们可以谈谈 O(n) 成本。

在 LOH 分配的情况下，应该注意额外的隐藏“成本”——这种分配不会在后台 GC 的某些部分发生(因为两者都在空闲列表上运行)。因此，如果碰巧您有很多长时间的后台 GC，LOH 分配将暂停，等待 GC 结束。这显然会给您的线程带来不必要的延迟。