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

---

我知道的

当添加的字符串的引用计数为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处的列表中.
对于这个短时间,解释器仍然在列表中具有旧版本的字符串并且不能在适当的位置执行修改.
如果您查看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].如果nasty()在访问之前对其进行了评估l[0],那么结果将是'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(DUP_TOP_TWO在Py3中)直接BINARY_SUBSCR使用它PyObject_GetItem.因此,字符串的引用计数现在至少为3.

g没有这个问题.当项目被推送时LOAD_FAST,它会创建一个额外的引用,给出引用计数为2,即VM堆栈上项目的最小数量,以便它可以进行优化.