动态分配的阵列的理想增长率是多少？

Question

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

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

我听说有一篇关于这个的文章,但我一直都找不到.

Answer 1

我记得多年前读过为什么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个字节(向上舍入).

Answer 2

它完全取决于用例.您是否更关心浪费复制数据(以及重新分配数组)或额外内存的时间？阵列要持续多久？如果它不会长时间存在,使用更大的缓冲区可能是一个好主意 - 惩罚是短暂的.如果它会徘徊(例如在Java中,进入老一代和老一代),那显然更多的是惩罚.

没有"理想的增长因素"这样的东西.它不仅在理论上依赖于应用程序,它肯定取决于应用程序.

2是一个很常见的生长因子-我敢肯定,这就是ArrayList和List<T>在.NET使用.ArrayList<T>在Java中使用1.5.

编辑:正如Erich所指出的,Dictionary<,>在.NET中使用"加倍大小然后增加到下一个素数",这样哈希值可以在桶之间合理分配.(我敢肯定,我最近看到的文档表明素数实际上并不适合分发哈希桶,但这是另一个答案的论据.)

Answer 3

理想情况下(在极限为n →∞),它是黄金比例:φ= 1.618 ......

在实践中,你想要一些接近的东西,比如1.5.

原因是您希望能够重用较旧的内存块,以利用缓存并避免不断使操作系统为您提供更多的内存页.你要解决的方程式确保减少到x ^{n - 1} - 1 = x ^{n + 1} - x ⁿ,对于大n,其解接近x =φ .

Answer 4

在回答这样的问题时,一种方法就是"欺骗"并看看流行的图书馆做了什么,假设一个广泛使用的图书馆至少没有做一些可怕的事情.

因此,只需快速检查,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,所以使用bitshifts和三元运算符的表达式实际上只是计算过度分配.

Answer 5

假设您通过增加数组大小x.所以假设你从大小开始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个分配时的内存需求,以便我们可以重用以前释放的内存.

例如,如果我们希望能够在第3步(即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

请注意,增长因素必须小2于此x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Answer 6

另外两分钱

• 大多数计算机都有虚拟内存！在物理内存中，您可以随处拥有随机页面，这些页面在程序的虚拟内存中显示为单个连续空间。间接解析由硬件完成。虚拟内存耗尽在 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 是一个很好的默认值。除此之外，还要根据具体情况而定。

Answer 7

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

\n

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

\n

特别是，如果您进行数学计算¹，您会发现增长率的上限是黄金比例\xcf\x95 = 1.618\xe2\x80\xa6 。增长率大于\xcf\x95（如 2x）意味着您将永远无法重用旧的内存块。增长率仅略低于\xcf\x95意味着您将无法重用旧内存块，直到经过多次重新分配之后，在此期间您将浪费内存。所以你希望远低于\xcf\x95因此，您希望在不牺牲太多性能的情况下尽可能

\n

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

\n

\n
• \xe2\x89\x881.466x （ x ⁴ =1+ x + x ²的解决方案）允许在仅 3 次重新分配后重用内存，一次比 1.5x 允许的早，而重新分配的频率只是稍微高一点
\n
• \xe2\x89\x881.534x （ x ⁵ =1+ x + x ² + x ³的解决方案）允许在 4 次重新分配后重用内存，与 1.5x 相同，同时重新分配的频率稍微降低以提高性能
\n
• \xe2\x89\x881.570x （ x ⁶ =1+ x + x ² + x ³ + x ⁴的解决方案）仅允许在 5 次重新分配后重用内存，但重新分配的频率会更低，以进一步提高性能（勉强）
\n

\n

显然，那里存在一些收益递减的情况，所以我认为全局最优可能就是其中之一。另请注意，1.5x 非常接近实际的全局最优值，并且具有极其简单的优点。

\n

¹感谢@user541686 这个优秀的来源。

\n

Answer 8

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

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

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

显示对最大有用数据大小的依赖关系的高分辨率图表位于： https: //i.stack.imgur.com/Ld2yJ.png。

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

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

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

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

模拟片段是在 Windows 10（内部版本 19043）上构建的g++.exe simulator.cpp -o simulator.exe，g++ 版本如下。

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

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