CPython字符串加法优化失败案例

Question

问题

为什么在CPython中

def add_string(n):
    s = ''
    for _ in range(n):
        s += ' '

需要线性时间，但是

def add_string_in_list(n):
    l = ['']
    for _ in range(n):
        l[0] += ' '

占用二次时间?

---

证明:

Timer(partial(add_string, 1000000)).timeit(1)
#>>> 0.1848409200028982
Timer(partial(add_string, 10000000)).timeit(1)
#>>> 1.1123797750042286

Timer(partial(add_string_in_list, 10000)).timeit(1)
#>>> 0.0033865350123960525
Timer(partial(add_string_in_list, 100000)).timeit(1)
#>>> 0.25131178900483064

---

What I know

当被添加的字符串的引用计数为1时，CPython对字符串添加进行了优化。

这是因为Python中的字符串是不可变的，所以通常它们不能被编辑。如果一个字符串存在多个引用，并且该字符串发生了变化，则两个引用都将看到改变的字符串。这显然是不希望发生的，因此不能在多个引用中发生突变。

如果只有一个对字符串的引用，但是，改变值只会改变该引用的字符串，该引用希望改变字符串。您可以测试这是一个可能的原因，如下:

from timeit import Timer
from functools import partial
def add_string_two_references(n):
    s = ''
    for _ in range(n):
        s2 = s
        s += ' '
Timer(partial(add_string_two_references, 20000)).timeit(1)
#>>> 0.032532954995986074
Timer(partial(add_string_two_references, 200000)).timeit(1)
#>>> 1.0898985149979126

我不确定为什么因子只有30倍，而不是预期的100倍，但我相信这是开销。

---

我不知道的

那么为什么列表版本创建了两个引用呢?这就是阻碍优化的原因吗?

你可以检查它没有区别对待普通对象:

class Counter:
    def __iadd__(self, other):
        print(sys.getrefcount(self))
s = Counter()
s += None
#>>> 6
class Counter:
    def __iadd__(self, other):
        print(sys.getrefcount(self))
l = [Counter()]
l[0] += None
#>>> 6

Answer 1

在基于列表的方法中，从列表的索引0中获取字符串并进行修改，然后将其放回到索引0的列表中。
在这一小段时间里，解释器在列表中仍然是旧版本的string，不能执行就地修改。
如果看一下Python的源代码，就会发现它不支持就地修改列表中的元素。所以对象(在这个例子中是字符串)必须从列表中检索，修改，然后放回。
换句话说，list类型完全不知道+=算子是否支持str类型。

并考虑以下代码:

l = ['abc', 'def']
def nasty():
    global l
    l[0] = 'ghi'
    l[1] = 'jkl'
    return 'mno'
l[0] += nasty()

l的值为['abcmno', 'jkl']，证明'abc'是从列表中取出的，然后执行nasty()修改列表的内容，串接字符串'abc'和'mno'，将结果赋值给l[0]。如果在访问l[0]之前对nasty()求值并对其进行修改，那么结果将是'ghimno'。

Answer 2

那么为什么列表版本创建了两个引用呢?

在l[0] += ' '中，一个引用在l[0]中。临时创建一个引用来执行+=。

下面是两个更简单的函数来显示效果:

>>> def f():
...     l = ['']
...     l[0] += ' '
...     
>>> def g():
...     s = ''
...     s += ' '
...     

拆解它们得到

>>> from dis import dis
>>> dis(f)
  2           0 LOAD_CONST               1 ('')
              3 BUILD_LIST               1
              6 STORE_FAST               0 (l)
  3           9 LOAD_FAST                0 (l)
             12 LOAD_CONST               2 (0)
             15 DUP_TOPX                 2
             18 BINARY_SUBSCR       
             19 LOAD_CONST               3 (' ')
             22 INPLACE_ADD         
             23 ROT_THREE           
             24 STORE_SUBSCR        
             25 LOAD_CONST               0 (None)
             28 RETURN_VALUE        
>>> dis(g)
  2           0 LOAD_CONST               1 ('')
              3 STORE_FAST               0 (s)
  3           6 LOAD_FAST                0 (s)
              9 LOAD_CONST               2 (' ')
             12 INPLACE_ADD         
             13 STORE_FAST               0 (s)
             16 LOAD_CONST               0 (None)
             19 RETURN_VALUE        

在f中，BINARY_SUBSCR(切片)指令将l[0]置于VM堆栈的顶部。DUP_TOPX复制堆栈上的顶部n项。两个函数(参见ceval.c)都增加引用计数;DUP_TOPX (Py3中的DUP_TOP_TWO)直接执行此操作，而BINARY_SUBSCR使用PyObject_GetItem。因此，字符串的引用计数现在至少为3。

g没有这个问题。当使用LOAD_FAST推送项目时，它会创建一个额外的引用，给出2的refcount，这是VM堆栈中项目的最小值，因此它可以进行优化。