python成员str性能太慢了

Question

在python 2.7.3中添加str类成员时遇到了一个奇怪的性能问题.我知道访问局部变量更快,但是,在下面的问题中,两个循环之间的速度差异超过100倍.访问a.accum_的那个快速启动但速度慢,就像str iadd是str (长度为n)的O(n ^ 2)一样.

有谁知道原因？

# Fast ( < 1sec):
accum = str()
for ii in range(1000000):
    if (ii % 10000) == 0:
        print 'fast cnt', ii
    accum += 'zzzzz\n'

# Much slower ( > 5 mins):
class Foo:
    pass
a = Foo()
a.accum_ = str()
for ii in range(1000000):
    if (ii % 10000) == 0:
        print 'slow cnt', ii
    a.accum_ += 'zzzzz\n'

Answer 1

对于第一个例子,很明显它是单引用优化的情况(实际上有两个引用:一个来自对象本身,一个LOAD_FAST; unicode_concatenate将尝试在传递控制之前将其减少为1 PyUnicode_Append)由CPython使用此unicode_modifiable函数完成:

static int
unicode_modifiable(PyObject *unicode)
{
    assert(_PyUnicode_CHECK(unicode));
    if (Py_REFCNT(unicode) != 1)
        return 0;
    if (_PyUnicode_HASH(unicode) != -1)
        return 0;
    if (PyUnicode_CHECK_INTERNED(unicode))
        return 0;
    if (!PyUnicode_CheckExact(unicode))
        return 0;
#ifdef Py_DEBUG
    /* singleton refcount is greater than 1 */
    assert(!unicode_is_singleton(unicode));
#endif
    return 1;
}

但在第二种情况下,由于实例数据存储在Python dict而不是简单变量中,因此事情变得微不足道.

a.accum_ += 'foo'

实际上需要预取值a.accum_并将其存储到堆栈中.所以,现在字符串至少有三个引用:一个来自实例字典,一个来自DUP_TOP,另一个来自PyObject_GetAttr使用LOAD_ATTR.因此,Python无法优化这种情况,因为就地修改其中一个也会影响其他引用.

>>> class A:
    pass
...
>>> a = A()
>>> def func():
    a.str = 'spam'
    print a.str
    return '_from_func'
...
>>> a.str = 'foo'
>>> a.str += func()
spam

你会期望这里的输出是'spam_from_func',但它会有所不同,因为a.str之前func()被Python存储的原始值被调用.

>>> a.str
'foo_from_func'

字节代码:

>>> import dis
>>> def func_class():
        a = Foo()
        a.accum = ''
        a.accum += 'zzzzz\n'
...
>>> dis.dis(func_class)
  2           0 LOAD_GLOBAL              0 (Foo)
              3 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
              6 STORE_FAST               0 (a)

  3           9 LOAD_CONST               1 ('')
             12 LOAD_FAST                0 (a)
             15 STORE_ATTR               1 (accum)

  4          18 LOAD_FAST                0 (a)
             21 DUP_TOP
             22 LOAD_ATTR                1 (accum)
             25 LOAD_CONST               2 ('zzzzz\n')
             28 INPLACE_ADD
             29 ROT_TWO
             30 STORE_ATTR               1 (accum)
             33 LOAD_CONST               0 (None)
             36 RETURN_VALUE

请注意,此优化是在2004年左右完成的(CPython 2.4),以防止用户缓慢a += b或a = a + b因此,它主要用于简单变量,仅在下一条指令是STORE_FAST(局部变量),STORE_DEREF(闭包)和时才起作用STORE_NAME.它不是一般解决方案,在Python中执行此操作的最佳方法是创建列表并使用其连接项str.join.

CPython的实现细节:如果s和t都是字符串,一些Python实现如CPython的通常可以执行就地优化形式的分配s = s + t或s += t.如果适用,此优化使得二次运行时间的可能性大大降低.此优化依赖于版本和实现.对于性能敏感的代码,最好使用str.join()确保版本和实现之间一致的线性级联性能的 方法.

Answer 2

Python 字符串是不可变的，因此不能有__iadd__方法。您在第一个示例中看到的是 CPython 解释器的微观优化。在第一个示例中，解释器注意到它有一个引用计数为 1 的局部变量。因此，解释器可以厚颜无耻地对字符串进行适当的修改。尽管这违反了 的合同str，但在程序执行期间，任何时候都不会明显地看出该合同被短暂违反。

在后一个示例中，没有实现这种微观优化，这就是它如此缓慢的原因。看起来可以应用优化，所以我不确定为什么不应用它。

一般来说，如果构建字符串，请整理列表中的子字符串，然后用于str.join创建最终产品。