python - 为什么朴素的字符串连接在一定长度以上会变成二次方？

Question

通过重复字符串连接构建字符串是一种反模式，但我仍然很好奇为什么在字符串长度超过大约 10 ** 6 后它的性能从线性切换到二次:

# this will take time linear in n with the optimization
# and quadratic time without the optimization
import time
start = time.perf_counter()
s = ''
for i in range(n):
    s += 'a'
total_time = time.perf_counter() - start
time_per_iteration = total_time / n

例如，在我的机器上(Windows 10，python 3.6.1):

• 10 ** 4 < n < 10 ** 6 , time_per_iteration几乎完全恒定在 170±10 µs
• 10 ** 6 < n , time_per_iteration几乎是完全线性的，在 n == 10 ** 7 处达到 520 µs .

线性增长 time_per_iteration相当于 total_time 的二次增长.

线性复杂度来自 optimization在最近的 CPython 版本(2.4+)中 reuse the original storage如果没有对原始对象的引用。但我预计线性性能会无限期地持续下去，而不是在某个时候切换到二次方。

我的问题是基于 this comment 提出的.出于某种奇怪的原因运行

python -m timeit -s"s=''" "for i in range(10**7):s+='a'"

需要非常长的时间(比二次方长得多)，所以我从来没有从 timeit 得到实际的计时结果.因此，我使用上面的简单循环来获取性能数据。

更新:

我的问题还不如标题为“一个类似列表的 append 如何在没有过度分配的情况下获得 O(1) 的性能？”。来自观察常量time_per_iteration在小字符串上，我假设字符串优化一定是过度分配。但是realloc在扩展小内存块时(出乎我的意料)在避免内存复制方面非常成功。

Answer 1

最后，平台 C 分配器(如 malloc())是内存的最终来源。当 CPython 尝试重新分配字符串空间以扩展其大小时，实际上是系统 C realloc() 决定了发生的细节。如果字符串一开始就“短”，系统分配器很可能会找到与其相邻的未使用内存，因此扩展大小只是 C 库的分配器更新一些指针的问题。但在重复多次之后(再次取决于平台 C 分配器的详细信息)，它将耗尽空间。那时，realloc() 需要将整个字符串复制到一个全新的更大的空闲内存块。这就是二次时间行为的来源。

请注意，例如，增加 Python 列表面临相同的权衡。然而，列表设计是为了增长，所以 CPython 故意要求比当时实际需要更多的内存。这种过度分配的数量随着列表的增长而增加，足以使 realloc() 很少需要复制整个列表。但是字符串优化不会过度分配，使得 realloc() 需要更频繁地复制的情况。