96

C++ 有 std::vector，Java 有 ArrayList，许多其他语言都有自己的动态分配数组形式。当动态数组空间不足时，它会被重新分配到更大的区域，并将旧值复制到新数组中。这种阵列性能的核心问题是阵列的大小增长速度有多快。如果您总是只增长到足以适应当前的推动，那么您最终每次都会重新分配。因此，将数组大小加倍或乘以 1.5 倍是有意义的。

有没有理想的生长因子？2倍？1.5 倍？理想我的意思是数学上合理的，最好的平衡性能和浪费的内存。我意识到理论上，鉴于您的应用程序可能具有任何潜在的推送分布，这在某种程度上取决于应用程序。但是我很想知道是否有一个“通常”最好的值，或者在某些严格的约束下被认为是最好的。

我听说某处有关于这方面的论文，但我一直找不到。

4

12 回答 12

115

我记得很多年前读过为什么 1.5 比两个更受欢迎，至少在应用于 C++ 时（这可能不适用于托管语言，运行时系统可以随意重定位对象）。

理由是这样的：

  1. 假设您从 16 字节分配开始。
  2. 当您需要更多时，分配 32 个字节，然后释放 16 个字节。这会在内存中留下一个 16 字节的漏洞。
  3. 当您需要更多时，分配 64 个字节，释放 32 个字节。这会留下一个 48 字节的空洞（如果 16 和 32 相邻）。
  4. 当您需要更多时，分配 128 个字节，释放 64 个字节。这会留下一个 112 字节的漏洞（假设所有先前的分配都是相邻的）。
  5. 等等等等。

这个想法是，通过 2 倍扩展，没有时间点产生的空洞会大到足以重用于下一次分配。使用 1.5x 分配，我们有这个：

  1. 从 16 个字节开始。
  2. 当您需要更多时，分配 24 个字节，然后释放 16 个，留下一个 16 字节的孔。
  3. 当您需要更多时，分配 36 字节，然后释放 24 字节，留下 40 字节的漏洞。
  4. 当您需要更多时，分配 54 个字节，然后释放 36 个，留下一个 76 字节的孔。
  5. 当你需要更多时，分配 81 个字节，然后释放 54 个，留下一个 130 字节的空缺。
  6. 当您需要更多时，使用 130 字节孔中的 122 字节（向上取整）。
于 2009-07-08T20:36:52.397 回答
52

在n → ∞ 的极限中，这将是黄金比例： φ = 1.618...

对于有限n，您需要接近的值，例如 1.5。

原因是您希望能够重用较旧的内存块，以利用缓存并避免不断使操作系统为您提供更多内存页面。您为确保后续分配可以重用所有先前的块而求解的方程减少到x n - 1 - 1 = x n + 1 - x n，其解接近x = φ 对于大n。在实践中n是有限的，您希望能够在每几次分配中重用最后几个块，因此 1.5 非常适合确保这一点。
（有关更详细的说明，请参阅链接。）

于 2013-12-09T21:31:22.983 回答
47

这将完全取决于用例。您是否更关心浪费在复制数据（和重新分配数组）或额外内存上的时间？阵列将持续多长时间？如果它不会持续很长时间，那么使用更大的缓冲区可能是个好主意——惩罚是短暂的。如果它会继续存在（例如在 Java 中，进入老一代和老一代），那显然更多的是一种惩罚。

没有“理想的生长因子”这样的东西。它不仅在理论上依赖于应用程序，而且绝对依赖于应用程序。

2 是一个非常常见的增长因素 - 我很确定这就是.NET 使用ArrayList的内容。在 Java 中使用 1.5。List<T>ArrayList<T>

编辑：正如 Erich 所指出的，Dictionary<,>在 .NET 中使用“将大小加倍然后增加到下一个素数”，以便哈希值可以在存储桶之间合理分配。（我敢肯定，我最近看到文档表明素数实际上对于分发散列桶并不是那么好，但这是另一个答案的论据。）

于 2009-07-08T20:25:40.670 回答
16

回答此类问题的一种方法是“作弊”，看看流行的图书馆做了什么，假设一个广泛使用的图书馆至少没有做一些可怕的事情。

所以只要快速检查一下，Ruby (1.9.1-p129) 在附加到数组时似乎使用 1.5x，而 Python (2.6.2) 使用 1.125x 加上一个常量 (in Objects/listobject.c)：

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsize以上是数组中元素的数量。请注意，它newsize被添加到new_allocated，因此带有移位和三元运算符的表达式实际上只是计算过度分配。

于 2009-07-08T20:41:11.233 回答
13

假设您将数组大小增加x. 所以假设你从 size 开始T。下次你增加数组时，它的大小将是T*x. 然后它将是T*x^2等等。

如果您的目标是能够重用之前创建的内存，那么您需要确保您分配的新内存小于您释放的先前内存的总和。因此，我们有这个不等式：

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

我们可以从两边删除 T。所以我们得到这个：

x^n <= 1 + x + x^2 + ... + x^(n-2)

通俗地说，在nth分配时，我们希望我们之前释放的所有内存大于或等于第 n 次分配时的内存需求，以便我们可以重用之前释放的内存。

例如，如果我们希望能够在第三步（即n=3）做到这一点，那么我们有

x^3 <= 1 + x

这个等式对所有 x 都是正确的，使得0 < x <= 1.3（大致）

看看我们在下面得到的不同 n 的 x：

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

请注意，增长因子必须小于2since x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2。

于 2012-12-04T05:15:34.803 回答
3

这真的取决于。有些人分析常见用例以找到最佳数量。

我以前见过 1.5x 2.0x phi x 和 2 的幂。

于 2009-07-08T20:38:51.020 回答
3

如果你有一个数组长度的分布，并且你有一个实用函数来说明你喜欢浪费空间与浪费时间的程度，那么你绝对可以选择最佳的调整大小（和初始大小）策略。

之所以使用简单的常数倍数，显然是为了使每个附加都具有摊销的常数时间。但这并不意味着您不能对小尺寸使用不同的（更大的）比率。

在 Scala 中，您可以使用查看当前大小的函数覆盖标准库哈希表的 loadFactor。奇怪的是，可调整大小的数组只是加倍，这是大多数人在实践中所做的。

我不知道有任何加倍（或 1.5*ing）数组实际上会捕获内存不足错误并且在这种情况下增长较少。似乎如果你有一个巨大的单个数组，你会想要这样做。

我还要补充一点，如果您将可调整大小的数组保持足够长的时间，并且随着时间的推移您更喜欢空间，那么最初显着过度分配（对于大多数情况）然后重新分配到正确的大小可能是有意义的完毕。

于 2009-07-08T21:00:58.243 回答
3

另外两分钱

  • 大多数计算机都有虚拟内存！在物理内存中，您可以在任何地方都有随机页面，这些页面在程序的虚拟内存中显示为单个连续空间。间接解析由硬件完成。虚拟内存耗尽在 32 位系统上是一个问题，但它真的不再是问题了。因此，填补漏洞不再是问题（特殊环境除外）。由于 Windows 7 甚至微软都支持 64 位，而不需要额外的努力。@ 2011
  • 任何r > 1 因子都达到 O(1) 。相同的数学证明不仅适用于 2 作为参数。
  • r = 1.5 可以计算，old*3/2因此不需要浮点运算。（我说/2是因为编译器会在他们认为合适的情况下用生成的汇编代码中的位移来替换它。）
  • MSVC 选择r = 1.5，因此至少有一个主要编译器不使用 2 作为比率。

正如某人所说，2 感觉比 8 好。而且 2 感觉比 1.1 好。

我的感觉是 1.5 是一个很好的默认值。除此之外，这取决于具体情况。

于 2017-01-03T16:42:55.080 回答
3

最近，我对关于事物浪费内存方面的实验数据着迷。下图显示了“开销因子”，计算为开销空间量除以可用空间，x 轴显示增长因子。我还没有找到一个很好的解释/模型来解释它所揭示的内容。

模拟片段：https ://gist.github.com/gubenkoved/7cd3f0cb36da56c219ff049e4518a4bd 。

模拟显示的形状和绝对值都不是我所期望的。

显示对最大有用数据大小的依赖性的更高分辨率图表在这里：https ://i.stack.imgur.com/Ld2yJ.png 。

开销大小

更新。经过更多思考，我终于想出了正确的模型来解释模拟数据，并希望它能很好地匹配实验数据。这个公式很容易推断，只需查看我们需要包含的给定数量的元素所需的数组大小。

公式

较早引用的 GitHub gist已更新，包括scipy.integrate用于数值积分的计算，允许创建下面的图，该图很好地验证了实验数据。

模型

更新 2.但是应该记住，我们在那里建模/模拟的内容主要与虚拟内存有关，这意味着过度分配的开销可以完全留在虚拟内存领域，因为物理内存占用仅在我们第一次发生时才会发生访问一个虚拟内存页面，因此可以访问malloc一大块内存，但在我们第一次访问这些页面之前，我们所做的只是保留虚拟地址空间。我已经使用 CPP 程序更新了 GitHub要点，该程序具有非常基本的动态数组实现，允许更改增长因子和多次运行它以收集“真实”数据的 Python 片段。请参阅下面的最终图表。

结论可能是，对于虚拟地址空间不是限制因素的 x64 环境，不同增长因素之间的物理内存占用量可能几乎没有差异。此外，就虚拟内存而言，上述模型似乎做出了相当不错的预测！

模拟片段是g++.exe simulator.cpp -o simulator.exe在 Windows 10 (build 19043) 上构建的，g++ 版本如下。

g++.exe (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0

PS。请注意，最终结果是特定于实现的。根据实现细节，动态数组可能会也可能不会访问“有用”边界之外的内存。一些实现将使用memset对整个容量的 POD 元素进行零初始化——这将导致虚拟内存页面转换为物理内存页面。但是，std::vector上面引用的编译器上的实现似乎并没有这样做，因此其行为与代码段中的模拟动态数组一样——这意味着在虚拟内存方面会产生开销，而在物理内存上可以忽略不计。

仿真结果

于 2021-11-04T11:13:31.843 回答
2

最高投票和接受的答案都很好，但都没有回答要求“数学上合理”“理想增长率”，“最佳平衡性能和浪费记忆”的问题部分。（投票第二多的答案确实试图回答这部分问题，但它的推理很混乱。）

该问题完美地确定了必须平衡的两个考虑因素，性能和浪费的内存。如果您选择的增长率太低，性能会受到影响，因为您将很快耗尽额外空间并且必须过于频繁地重新分配。如果您选择的增长率太高，例如 2x，您将浪费内存，因为您将永远无法重用旧的内存块。

特别是，如果你做数学1，你会发现增长率的上限是黄金比例φ = 1.618...。大于φ的增长率（如 2 倍）意味着您将永远无法重用旧的内存块。增长率仅略低于φ意味着您将无法重用旧内存块，直到经过多次重新分配，在此期间您将浪费内存。因此，您希望在不牺牲太多性能的情况下尽可能地低于ϕ 。

因此，我建议将这些候选者用于“数学上合理的”“理想增长率”、“最佳平衡性能和浪费的内存”：

  • ≈1.466x（x 4 =1+ x + x 2的解）仅允许在 3 次重新分配后重用内存，比 1.5x 允许的快一次，而重新分配的频率仅略高一些
  • ≈1.534x（x 5 =1+ x + x 2 + x 3的解）允许在 4 次重新分配后重用内存，与 1.5x 相同，同时为了提高性能，重新分配的频率略低
  • ≈1.570x（x 6 =1+ x + x 2 + x 3 + x 4的解决方案）仅允许在 5 次重新分配后重用内存，但为了进一步提高性能（几乎没有），重新分配的频率会更低

显然那里有一些收益递减，所以我认为全局最优可能就是其中之一。另外，请注意，1.5x 是全局最优值的一个很好的近似值，并且具有非常简单的优点。

1归功于 @user541686 这个优秀的来源。

于 2021-05-22T10:50:34.263 回答
0

我同意 Jon Skeet 的观点，即使我的理论工匠朋友也坚持认为，当将因子设置为 2x 时，这可以被证明是 O(1)。

cpu时间和内存之间的比例在每台机器上是不同的，所以这个因素也会有很大的不同。如果您有一台具有千兆字节内存和慢速 CPU 的机器，则将元素复制到新数组比在快速机器上要昂贵得多，而快速机器反过来可能内存更少。这是一个理论上可以回答的问题，对于一台统一的计算机，这在实际场景中对您没有任何帮助。

于 2009-07-08T20:35:19.200 回答
0

我知道这是一个老问题，但是每个人似乎都缺少几件事。

首先，这是乘以 2：size << 1。这是乘以1 和 2 之间的任何值：int(float(size) * x)，其中 x 是数字，* 是浮点数学，处理器有运行附加指令以在 float 和 int 之间进行转换。换句话说，在机器级别，加倍需要一条非常快速的指令来找到新的大小。乘以 1 到 2 之间的值至少需要一条指令将 size 转换为 float，一条指令用于乘法（这是 float 乘法，因此它可能需要至少两倍的周期，如果不是 4 甚至 8 倍），还有一条指令将其转换回 int，并且假设您的平台可以在通用寄存器上执行浮点数学运算，而不需要使用特殊寄存器。简而言之，您应该期望每个分配的数学运算时间至少是简单左移的 10 倍。但是，如果您在重新分配期间复制大量数据，这可能不会产生太大影响。

其次，也可能是最大的问题：每个人似乎都认为被释放的内存既与自身相邻，也与新分配的内存相邻。除非您自己预先分配所有内存，然后将其用作池，否则几乎可以肯定情况并非如此。操作系统可能偶尔会最终会这样做，但大多数时候，将有足够的可用空间碎片，任何半体面的内存管理系统都能够找到一个适合您的内存的小洞。一旦你得到真正的小块，你更有可能最终得到连续的块，但到那时，你的分配已经足够大，以至于你没有足够频繁地执行它们以使其不再重要。简而言之，想象使用一些理想的数字将允许最有效地使用可用内存空间是很有趣的，但实际上，除非您的程序在裸机上运行（例如，没有操作系统），否则它不会发生在它下面做出所有决定）。

我对这个问题的回答？不，没有理想的数字。它是如此特定于应用程序，以至于没有人真正尝试过。如果您的目标是理想的内存使用率，那么您就很不走运了。就性能而言，分配频率越低越好，但如果我们这样做，我们可以乘以 4 甚至 8！当然，当 Firefox 一下子从 1GB 跳到 8GB 时，人们会抱怨，所以这甚至没有意义。以下是我会遵循的一些经验法则：

如果你不能优化内存使用，至少不要浪费处理器周期。乘以 2 至少比浮点运算快一个数量级。它可能不会产生巨大的差异，但至少会产生一些差异（尤其是在早期，在更频繁和更小的分配期间）。

不要想太多。如果你只是花了 4 个小时试图弄清楚如何去做已经做过的事情，那你只是在浪费你的时间。老实说，如果有比 *2 更好的选择，它会在几十年前在 C++ 向量类（和许多其他地方）中完成。

最后，如果你真的想优化，不要为小事操心。现在，没有人关心浪费了 4KB 的内存，除非他们在嵌入式系统上工作。当您获得 1GB 的对象时，每个对象的大小在 1MB 到 10MB 之间，加倍可能太多了（我的意思是，在 100 到 1,000 个对象之间）。如果您可以估计预期的扩张率，您可以将其拉平到某个点的线性增长率。如果您预计每分钟大约 10 个对象，那么以每步 5 到 10 个对象大小（每 30 秒到一分钟一次）的速度增长可能没问题。

归根结底是，不要想太多，尽可能优化，如果必须的话，可以定制你的应用程序（和平台）。

于 2016-05-21T04:44:13.227 回答