CPython string addition optimisation failure case

Question

The Question Why, in CPython, does ``` def add_string(n): s = '' for _ in range(n): s += ' ' ``` take linear time, but ``` def add_string_in_list(n): l = [''] for _ in range(n): l[0] += ' ' ``` take quadratic time? Proof: ``` 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 CPython has an optimisation for string addition when the string being added to has a reference count of 1. This is because strings in Python are immutable, and so normally they cannot be edited. If multiple references exist to a string and it is mutated, both references will see the changed string. This is obviously not wanted, so mutation cannot happen with multiple references. If there is only one reference to the string, however, mutating the v…

Accepted Answer

In the list based approach, string from index 0 of the list is taken and modified before being put back to the list at index 0. For this short moment interpreter still has the old version of string in the list and can't perform in place modification. If you take a look at Python's source then you'll see that there is no support for modifying the element of the list in place. So the object (string in this case) has to be retrieved from the list, modified and then put back. In other words `list` type is completely agnostic of the `str` type support for `+=` operator.

And consider the following code:

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

The value of `l` is `['abcmno', 'jkl']` which proves that `'abc'` was taken from the list, then `nasty()` got executed modifying the contents of the list, strings `'abc'` and `'mno'` got concatenated and result was assigned to `l[0]`. If `nasty()` was evaluated before accessing `l[0]` to modify it in place, then the result would be `'ghimno'`.

CPython string addition optimisation failure case

Solution

Problem