"Let's make a giant string!" code example is not representative

[zed]

add_string_with_plus() and add_string_with_join() take the same time in the example. It implies that CPython's += optimization is in effect (unrelated to the example in the very next section with a possibly misleading title: "String concatenation interpreter optimizations" -- the example is more about string interning, string literals than string concatination -- the linked StackOverflow answer explains it quite well).

The explanation in "Let's make a giant string!" claims quadratic behavior for str + str + str + ... in Python (correct) but the example add_string_with_plus() uses CPython += optimizations -- the actual times are linear on my machine (in theory the worst case is still O(n²) -- it depends on realloc() being O(n) in the worst case on the given platform -- unlike for Python lists x1.125 overallocation (add_string_with_join() is linear) is not used for str):

In [2]: %timeit add_string_with_plus(10000)
1000 loops, best of 3: 1.1 ms per loop

In [3]: %timeit add_string_with_format(10000)
1000 loops, best of 3: 539 µs per loop

In [4]: %timeit add_string_with_join(10000)
1000 loops, best of 3: 1.1 ms per loop

In [5]: L = ["xyz"]*10000

In [6]: %timeit convert_list_to_string(L, 10000)
10000 loops, best of 3: 118 µs per loop

In [7]: %timeit add_string_with_plus(100000)
100 loops, best of 3: 11.9 ms per loop

In [8]: %timeit add_string_with_join(100000)
100 loops, best of 3: 11.8 ms per loop

In [9]: %timeit add_string_with_plus(1000000)
10 loops, best of 3: 121 ms per loop

In [10]: %timeit add_string_with_join(1000000)
10 loops, best of 3: 116 ms per loop

Increasing iters x10, increases the time x10 -- linear behavior.

If you try the same code with bytes on Python 3; you get quadratic behavior (increasing x10 leads to x100 time) -- no optimization:

In [11]: def add_bytes_with_plus(n):
    ...:     s = b""
    ...:     for _ in range(n):
    ...:         s += b"abc"
    ...:     assert len(s) == 3*n
    ...:     

In [12]: %timeit add_bytes_with_plus(10000)
100 loops, best of 3: 10.8 ms per loop

In [13]: %timeit add_bytes_with_plus(100000)
1 loop, best of 3: 1.26 s per loop

In [14]: %timeit add_bytes_with_plus(1000000)
1 loop, best of 3: 2min 37s per loop

Here's a detailed explanation in Russian (look at the timings, follow the links in the answer).

[satwikkansal]

Ah, Thanks for such an detailed analysis of the situation and relevant providing explanation. I'll try to put everything in a short example with concise explanation (a little occupied for next few days due to my campus placements).

[satwikkansal]

Done 🎉 Thanks a lot @zed. Please do let me know if there are any corrections/suggestions (ea29aa0)