Slower string concatenation in CPython 3.11

[zephyr111]

Hello,

We have found a regression between CPython 3.10.8 and CPython 3.11 resulting in string concatenation to be significantly slower in loops on Windows 10. This is described in details in this StackOverflow post.

Here is a minimal, reproducible example of benchmarking code:

import time
a = 'a'

start = time.time()
for _ in range(1000000):
    a += 'a'
end = time.time()

print(a[:5], (end-start) * 1000)

CPython 3.11.0 is about 100 times slower than CPython 3.10.8 due to a quadratic running time (as opposed to a linear running time for CPython 3.10.8).

The analysis shows that CPython 3.10.8 was generating an INPLACE_ADD instruction so PyUnicode_Append is called at runtime, while CPython 3.11.0 new generates a BINARY_OP instruction so PyUnicode_Concat is actually called. The later function creates a new bigger string reducing drastically the performance of the string appending loop in the provided code. This appears to be related to the issue #89799 . I think if we want to replace INPLACE_ADD with a BINARY_OP, then an optimization checking the number of references (so to eventually do an in-place operation) is missing in the code of CPython 3.11.0. What do you think about it?

My environment is an embedded CPython 3.10.8 and an embedded CPython 3.11.0, both running on Windows 10 (22H2) with a x86-64 processor (i5-9600KF).

[ned-deily]

@brandtbucher @pablogsal

[sweeneyde]

Python 3.11 has a specialized (a la PEP 659) instruction called BINARY_OP_INPLACE_ADD_UNICODE:

cpython/Python/ceval.c

Lines 2064 to 2098 in 5bbf8ed

	TARGET(BINARY_OP_INPLACE_ADD_UNICODE) {
	assert(cframe.use_tracing == 0);
	PyObject *left = SECOND();
	PyObject *right = TOP();
	DEOPT_IF(!PyUnicode_CheckExact(left), BINARY_OP);
	DEOPT_IF(Py_TYPE(right) != Py_TYPE(left), BINARY_OP);
	_Py_CODEUNIT true_next = next_instr[INLINE_CACHE_ENTRIES_BINARY_OP];
	assert(_Py_OPCODE(true_next) == STORE_FAST ||
	_Py_OPCODE(true_next) == STORE_FAST__LOAD_FAST);
	PyObject **target_local = &GETLOCAL(_Py_OPARG(true_next));
	DEOPT_IF(*target_local != left, BINARY_OP);
	STAT_INC(BINARY_OP, hit);
	/* Handle `left = left + right` or `left += right` for str.
	*
	* When possible, extend `left` in place rather than
	* allocating a new PyUnicodeObject. This attempts to avoid
	* quadratic behavior when one neglects to use str.join().
	*
	* If `left` has only two references remaining (one from
	* the stack, one in the locals), DECREFing `left` leaves
	* only the locals reference, so PyUnicode_Append knows
	* that the string is safe to mutate.
	*/
	assert(Py_REFCNT(left) >= 2);
	_Py_DECREF_NO_DEALLOC(left);
	STACK_SHRINK(2);
	PyUnicode_Append(target_local, right);
	_Py_DECREF_SPECIALIZED(right, _PyUnicode_ExactDealloc);
	if (*target_local == NULL) {
	goto error;
	}
	// The STORE_FAST is already done.
	JUMPBY(INLINE_CACHE_ENTRIES_BINARY_OP + 1);
	DISPATCH();
	}

However, this optimization was restricted to only local variables within a function, not global/module-scope variables.

Does the regression go away if you put the code in a function?

def f():
    a = ''
    for _ in range(1000000):
        a += 'a'

[zephyr111]

Does the regression go away if you put the code in a function?

Indeed, this is significantly faster when the code is put in a function: 90 ms in a function in CPython 3.11.0 while it takes 140 ms in CPython 3.10.8. Thank you for this information. Thus, the problem is only for global variables. Solving this could be useful for people working directly in an interactive interpreter console (like IPython).

[pablogsal]

for _ in range(1000000):
    a += 'a'
end = time.time()

that code is quadratic and the only reason is not quadratic in reality is because we do some hacks in the eval loop to reuse the same string, but by the fact that strings are immutable it keeps being quadratic in nature. As I see it, there is not a lot of reason to spend a lot of resources to speed up this particular code, especially if the regression involves globals.

The correct idiom for this should be:

parts = []
for _ in range(100000):
    parts.append('a')
a = "".join(parts)

I am inclined to suggest to close this as "won't fix" unless someone thinks strongly otherwise

[eendebakpt]

Closing this issue is fine with me as well, but I was surprised to find out global/module level code can be slower in 3.11 than local code. Is the behaviour documented somewhere? I could not find it in the 3.11 release notes or in https://github.com/python/cpython/blob/main/Python/adaptive.md.

[gvanrossum]

There are many situations where globals are slower than locals, due to the nature of locals. This is nothing new.

(Update: I initially wrote faster, should be slower.)

[markshannon]

FTR, the linear time behavior will be restored for globals (and nonlocals) in 3.12, as a side-effect of the register VM.

[markshannon]

We aren't implementing a register VM, so the performance in 3.12+ will be like 3.11.

Moving the iteration into a function will restore the n ln(n) performance.

[terryjreedy]

I closed #115645 as a duplicate of this.

3.10 and whenever before had a hack of internally treated strings like lists by over-allocating space and doing additions in place instead of creating a new string with copies of both strings. This particularly benefited toy examples of creating a very long string a character at a time.

Trying to sum iterables of strings with sum results in TypeError: sum() can't sum strings [use ''.join(seq) instead]. I vaguely remember a FAQ entry. The string doc says There is also no mutable string type, but str.join() or io.StringIO can be used to efficiently construct strings from multiple fragments. Perhaps something similar should be added after the discussion of +.