[Python] How does iterated application of the `+=` operator to a string variable manage to...

I am kinda confused. I was sure that due do immutability of str operation like s += "abc" need to copy whole s content to another place in memory so effectively adding character to very long string will consume much time.

I wrote snippet to prove my theory:

import timeit

def foo(i):
res = ""
for _ in range(i):
res += "a"
return res


def foo2(i):
res = []
for _ in range(i):
res.append("a")
return "".join(res)


iterations = 100000
print(timeit.timeit('foo(iterations)', globals=globals(), number=100))
print(timeit.timeit('foo2(iterations)', globals=globals(), number=100))


However it looks like

1. foo execution time grows linearly based on iterations
2. foo2 is barely two times faster than foo

I tried to inspect bytecode searching for some hidden optimizations. I tried to change constant string to randomized one with proper length to deny interning as well but couldn't find any explanation of that behaviour.

Was I wrong then? Does += depend on string length or not? If so, how can I prove that?

Continue reading...