关于字符串连接的优化的评论

注意：代码链接指向CPython3.8.5，这是编写本文时的最新版本。

最近有人问我关于在CPython中对字符串对象使用+=和+进行的性能优化。有些人可能已经知道，如果您使用+=或+字符串，有时它的速度可能与'；'；'；.join一样快。问题是解释何时无法执行该优化。

Def fast_1()："；"；"；字符串追加是快速(O(1))，如果只有一个对字符串的引用："；"；"；s="；"；for_in range(500_000)：s+="；x"；def low_1()："；"；"；第二个引用使追加O(N)："；"；s="；"；for_in range(500_000)：s+="；x"；r=s#存储对s def fast_2()的第二个引用："；"；"；s=s+c"；仍然很快？"；"；s="；"；For_in范围(500_000)：s=s+"；x"；def low_2()："；"；"；但这也很慢：为什么？第二个引用在哪里？"；"；"；s=["；"；]for_in range(500_000)：s[0]+="；x"；

顾名思义，其中两个是快的(O(1)append)，两个是慢的(O(N)append)。

>；>；&>dis.dis(FAST_1)5 0 LOAD_CONST 1('；'；)2 STORE_FAST 0(S)6 4 LOAD_GLOBAL 0(范围)6 LOAD_CONST 2(500000)8 CALL_Function 110 GET_ITER&>&>12 FOR_ITER 12(至26)14 STORE_FAST 1(_)7 16 LOAD_FAST 0(S)18 LOAD_CONST 3('；)20 INPLACE_ADD 22 STORE_FAST 0(S)24 JUMP_Absolute 12&>；26 LOAD_CONST 4(无)28 RETURN_VALUE。

7 16 LOAD_FAST 0(S)18 LOAD_CONST 3('；x'；)20 INPLACE_ADD 22 STORE_FAST 0(S)。

要理解优化，我们需要了解inplace_add指令在解释器循环中是如何处理的。

案例目标(Inplace_Add)：{PyObject*Right=POP()；PyObject*Left=top()；PyObject*SUM；IF(PyUnicode_CheckExact(左)&；&；PyUnicode_CheckExact(右)){SUM=UNICODE_CONCATENATE(tstate，LEFT，RIGHT，f，NEXT_INSTR)；/*UNICODE_CONCATENATE向左使用引用*/}Else{SUM=PyNumber。IF(SUM==NULL)转到错误；Dispatch()；}

这将检查堆栈上最上面的两个值，如果它们都是PyUnicodeObject(Python字符串对象，不包括子类)，则委托给UNICODE_CONCATENATE。如果这两个对象不完全是PyUnicodeObjects，则使用泛型PyNumber_Add函数。

需要注意的是，inplace_add并不负责重新分配变量，而是由许多store_*指令中的一条指令来处理。在fast_1中，这被视为一个store_fast，用于没有关闭或从另一个堆栈帧捕获的局部变量。

鉴于s和"；x"；都是Unicode对象，我们应该使用UNICODE_CONCATENATE：

Static PyObject*UNICODE_CONCATENATE(PyThreadState*tstate，PyObject*v，PyObject*w，PyFrameObject*f，CONST_Py_CODEUNIT*NEXT_instr){PyObject*res；if(Py_REFCNT(V)==2){/*在通常情况下，执行+=时，有两个对存储在'；变量'；中的值*的引用：一个在*值堆栈上。我们现在尝试删除变量以将*the refcnt减少到1。*/int opcode，oparg；NEXTOPARG()；switch(Opcode){case store_fast：{PyObject**fast locals=f->；f_localplus；if(GETLOCAL(Oparg)==v)SETLOCAL(oparg，null)；Break；}case store_DEREF：{PyObject**freevars=(。PyObject*c=freevars[oparg]；if(PyCell_get(C)==v){PyCell_Set(c，null)；Py_DECREF(V)；}Break；}case store_name：{PyObject*Names=f->；f_code->；co_Names；PyObject*Name=GETITEM(Names，oparg)；PyObject*Locals=f->；f_locals；PyDict_CheckExact(局部变量){PyObject*w=PyDict_GetItemWithError(局部变量，名称)；IF(w==v&；&；PyDict_DelItem(局部变量，名称)！=0)||(w==NULL&；&；_PyErr_Occurated(Tstate)){Py_DECREF(V)；return null；}}Break；}res=v。

第一个检查是查看Py_REFCNT(V)==2。这意味着正好有两个对左侧参数的引用。正如检查下面的注释所解释的那样，我们正在寻找这样的情况：一个引用由命名变量拥有，而堆栈上有第二个引用。

在循环的第一次迭代中，v=s="；"；。因为字符串是不可变的，所以所有空字符串实际上都是同一个对象，所以"；"；是"；"；。如果存在对"；"；的其他引用，则Py_REFCNT(V)将远远大于2，我们直接转到PyUnicode_APPEND案例。当"；"；，这只是设置res=w：https://github.com/python/cpython/blob/580fbb018fd0844806119614d752b41fc69660f9/Objects/unicodeobject.c#L11351-L11356，，速度非常快。

在循环的第二次迭代中，s="；x"；。重要的是，由于PyUnicode_Append中的优化，s指向与字符串文字相同的对象，该字符串也属于fast_1'；这意味着在循环的第二次迭代中，当我们检查Py_REFCNT(V)==2时，v将在co_consts中至少有一个额外的引用，这意味着我们不能进入快速路径代码。由于这个额外的引用，我们也不能在PyUnicode_Append中优化太多。循环的第二次迭代是唯一的简单字符串连接。这种简单的连接将创建一个。

在第三次迭代和所有后续迭代中，v将保存第二次迭代的朴素串联结果。此时朴素串联结果将有两个引用：命名变量s和堆栈上的引用。因此，我们将进入if(Py_REFCNT(V)==2)分支。在此分支中，将检查下一条指令。此处对存储指令的子集有特殊处理：

开关(操作码){CASE STORE_FAST：{/*...*/}CASE STORE_DEREF：{/*...*/}CASE STORE_NAME：{/*...*/}}。

在FAST_1中，inplace_add后跟store_fast，因此我们输入跳转到此条件。在这里，我们检查赋值目标(左侧)是否与串联的左侧是同一对象：

这里的f是堆栈帧，GETLOCAL(Oparg)返回STORE_FAST指令引用的局部变量。

如果赋值目标与连接的左侧对象相同(我相信来自CPython编译器的字节码必须始终如此)，则通过使用SETLOCAL(oparg，null)将LOCAL设置为NULL来临时删除局部变量。此SETLOCAL宏会执行正确的引用计数管理。这是在Python代码中执行等效的del。通过删除v的本地变量版本，Py_REFCNT(V)==1，这是在Python代码中执行等效的del。通过删除v的本地变量版本，Py_REFCNT(V)=1，这是在Python代码中执行等效的del。通过删除v的本地变量版本，Py_REFCNT(V)==1，

如果(UNICODE_MODIFIEBLE(左)&；&；PyUnicode_CheckExact(右)&；&；PyUnicode_KIND(右)<；=PyUnicode_KIND(左)/*不要调整ascii+=latin1的大小。将ascii转换为latin1需要更改结构大小，但是字符存储在结构之后，因此需要移动所有字符，这与复制字符串没有太大区别。*/&；&；！(PyUnicode_IS_ASCII(左)&；&；！PyUnicode_IS_ASCII(右)){/*原地追加*/if(UNICODE_RESIZE(p_Left，new_len)！=0)转到错误；/*将'；Left'；*/_PyUnicode_FastCopyCharacters(*p)复制到新分配的'；Left'；*/_PyUnicode_FastCopyCharacters(*p。}。

此分支首先检查左侧是否可修改，右侧是否也是兼容的Exact Unicode对象。仅检查Exact Unicode对象，因为子类可能会重载__radd__。如果此分支为真，则会在可能的情况下就地调整对象的大小，然后将新数据复制到新分配的空间中。

UNICODE_MODIFIEBLE检查几项内容，但它首先检查的是引用计数：

Static int UNICODE_MODIFIED(PyObject*UNICODE){ASSERT(_PyUNICODE_CHECK(UNICODE))；IF(Py_REFCNT(UNICODE)！=1)返回0；IF(_PyUNICODE_HASH(UNICODE)！=-1)返回0；IF(PyUNICODE_CHECK_INTERED(UNICODE))返回0；IF(！PyUnicode_CheckExact(Unicode))返回0；#ifdef Py_DEBUG/*单例引用计数大于1*/Assert(！Unicode_is_singleton(Unicode))；#endif返回1；}

散列检查很重要。因为Python经常使用字符串键控的字典，所以字符串对象缓存__hash__的结果。这使得在字典中查找字符串的速度大大加快，代价是每个字符串额外增加一个整数。如果已经计算了散列，则更改内容会改变散列值，因此会出现问题。稍后我们将探讨这个概念。

Slow_1看起来与带有额外赋值的FAST_1几乎完全相同。通过捕获对s的第二个引用并将其保存在r中，我们将始终拥有对s的额外引用，从而禁用UNICODE_CONCATENATE中的Py_REFCNT(V)==2检查。因此，我们将在PyUNICODE_APPED内的此备选分支中结束：

ELSE{maxchar=PyUnicode_MAX_CHAR_VALUE(左)；maxchar2=PyUnicode_MAX_CHAR_VALUE(右)；maxchar=Py_MAX(maxchar，maxchar2)；/*连接两个Unicode字符串*/res=PyUnicode_New(new_len，maxchar)；if(res==null)转到错误；_PyUnicode_FastCopyCharacters(res，0，Left，0，Left_len)。*p_left=分辨率；}。

这里创建了一个完整的新Unicode对象，并将左右两个字符复制到其中。

FAST_2与FAST_1类似，但不是使用s+="；x"；，而是手动扩展为s=s+"；x"；。

24 16 LOAD_FAST 0(S)18 LOAD_CONST 3('；x'；)20 BINARY_ADD 22 STORE_FAST 0(S)。

7 16 LOAD_FAST 0(S)18 LOAD_CONST 3('；x'；)20 INPLACE_ADD 22 STORE_FAST 0(S)。

Case target(BINARY_ADD)：{PyObject*right=POP()；PyObject*Left=top()；PyObject*sum；/*注意(Haypo)：请不要试图使用字节码在CPython上微优化int+int，这根本没有价值。有关讨论，请参阅http://bugs.python.org/issue21955和http://bugs.python.org/issue10044。简而言之，没有补丁显示出对实际基准测试的任何影响，只是对微基准测试进行了很小的加速。*/if(PyUnicode_CheckExact(左)&；&；PyUnicode_CheckExact(右)){SUM=UNICODE_CONCATENATE(tSTATE，LEFT，RIGHT，f，NEXT_INSTR)；/*UNICODE_CONCATENATE向左消耗REF*/}ELSE{SUM=PyNumber_ADD(左，右)；Py_DECREF(左)；}Py_DECREF(右)；SET_TOP

BINARY_ADD和INPLACE_ADD的处理程序之间的唯一区别是非Unicode情况：BINARY_ADD调用：PyNumber_add，其中inplace_add调用PyNumber_InPlaceAdd.记住，存储仍然是inplace_add中的一个单独步骤，因此当BINARY_ADD后面紧跟着STORE_FAST时，我们得到的优化与+=相同。

Slow_2使用列表内的字符串而不是局部变量。这不应该改变引用计数，只需将所有者从堆栈帧移动到列表即可。

22 DUP_TOP_TWO 24 BINARY_SUBSCR 26 LOAD_CONST 4('；x'；)28 INPLACE_ADD 30 ROT_THAY 32 STORE_SUBSCR 34 JUMP_AUTAL 14。

这比FAST_1和FAST_2复杂得多，它们不需要担心重复值或旋转。

首先要注意的是，inplace_add后面跟的是rot_Three，而不是store_*指令。这意味着即使引用计数正确，我们也不会在下一条指令中进入快速路径。请记住，快速路径指令是：

开关(操作码){CASE STORE_FAST：{/*...*/}CASE STORE_DEREF：{/*...*/}CASE STORE_NAME：{/*...*/}}。

另一件值得注意的事情是，即使指令和堆栈被重新排序为不需要ROT_Three，STORE_SUBSCR也没有快速路径，这是因为Python想要通知容器新的赋值。如果字符串就地连接在一起，那么如果从__setattr__中的对象读回键，它就已经显示了会引起混淆的变化值。

基于我们已经看到的各种优化，让我们构造一些新的慢速案例来测试我们的理解。

我们知道，这种就地连接的关键之一是我们需要一个BINARY_ADD或INPLACE_ADD，后面紧跟一个STORE_*指令。如果我们试图在它们之间获得额外的指令，会发生什么呢？

4 16 LOAD_FAST 0(S)18 LOAD_CONST 3('；x'；)20 BINARY_ADD 22 DUP_TOP 24 STORE_FAST 0(S)26 POP_TOP。

通过使用赋值表达式，我们在BINARY_ADD和STORE_FAST之间添加了额外的DUP_TOP，因此我们不再获得优化，而降级为线性时间追加。

我们知道，只有当对象是可修改的时，PyUnicode_Append才会执行就地追加。对于要修改的对象，还不能为字符串计算散列。

通过计算散列，即使字节码具有正确的模式，引用计数也是正确的，我们仍然无法获得就地连接。

注意：我相信在这种情况发生后，通过重新计算散列，在CPython中仍然可以对此进行优化，不过我不确定这是否会打破其他情况。