14

Building a string through repeated string concatenation is an anti-pattern, but I'm still curious why its performance switches from linear to quadratic after string length exceeds approximately 10 ** 6:

# this will take time linear in n with the optimization
# and quadratic time without the optimization
import time
start = time.perf_counter()
s = ''
for i in range(n):
    s += 'a'
total_time = time.perf_counter() - start
time_per_iteration = total_time / n

For example, on my machine (Windows 10, python 3.6.1):

  • for 10 ** 4 < n < 10 ** 6, the time_per_iteration is almost perfectly constant at 170±10 µs
  • for 10 ** 6 < n, the time_per_iteration is almost perfectly linear, reaching 520 µs at n == 10 ** 7.

Linear growth in time_per_iteration is equivalent to quadratic growth in total_time.

The linear complexity results from the optimization in the more recent CPython versions (2.4+) that reuse the original storage if no references remain to the original object. But I expected the linear performance to continue indefinitely rather than switch to quadratic at some point.

My question is based made on this comment. For some odd reason running

python -m timeit -s"s=''" "for i in range(10**7):s+='a'"

takes incredibly long time (much longer than quadratic), so I never got the actual timing results from timeit. So instead, I used a simple loop as above to obtain performance numbers.

Update:

My question might as well have been titled "How can a list-like append have O(1) performance without over-allocation?". From observing constant time_per_iteration on small-size strings, I assumed the string optimization must be over-allocating. But realloc is (unexpectedly to me) quite successful at avoiding memory copy when extending small memory blocks.

5
  • Use the full timiet module so you can control the number of times the code is executed: timeit.timeit('for i in range(10**7): s += "a"', 's=""', number=1) I believe the default number is 1e6, so that is why it's not terminating Jun 11, 2017 at 19:02
  • Also, for what it's worth, that took about 1.1 seconds on my machine, and switching to 10**8 took about 12 seconds, so it seems that on my Python 3.5.2 the optimization still holds for big numbers. Jun 11, 2017 at 19:06
  • @juanpa.arrivillaga the default when called from command line (which is what I did) should be auto-determined based on how long each execution takes. And I'm running python 3.6.1, so something is weird. Can you try my loop with time.perf_counter() instead of timeit? And what's your platform?
    – max
    Jun 11, 2017 at 19:14
  • Yep, I tried it. I'm getting linear performance. Given the answers below, perhaps the total memory available on the machine affects the probability of the system allocator finding unused memory adjacent to the string? I'm running with about 8 gigabytes of free memory... Jun 11, 2017 at 19:18
  • @juanpa.arrivillaga I doubt it's the amount of free memory, since I have 20 GB free out of 32 GB total. Which OS do you use? And how high can you go before it hits quadratic? :)
    – max
    Jun 11, 2017 at 19:26

3 Answers 3

15

In the end, the platform C allocators (like malloc()) are the ultimate source of memory. When CPython tries to reallocate string space to extend its size, it's really the system C realloc() that determines the details of what happens. If the string is "short" to begin with, chances are decent the system allocator finds unused memory adjacent to it, so extending the size is just a matter of the C library's allocator updating some pointers. But after repeating this some number of times (depending again on details of the platform C allocator), it will run out of space. At that point, realloc() will need to copy the entire string so far to a brand new larger block of free memory. That's the source of quadratic-time behavior.

Note, e.g., that growing a Python list faces the same tradeoffs. However, lists are designed to be grown, so CPython deliberately asks for more memory than is actually needed at the time. The amount of this overallocation scales up as the list grows, enough to make it rare that realloc() needs to copy the whole list-so-far. But the string optimizations do not overallocate, making cases where realloc() needs to copy far more frequent.

11
  • Ahhh it doesn't over-allocate! I somehow assumed it does; but it makes sense: this is just an optimization that's not guaranteed by the language anyway, so it's not as sophisticated as list.append(). Out of curiosity though, apart from memory usage, is there any downside to over-allocating in string optimizations?
    – max
    Jun 11, 2017 at 19:30
  • 1
    Strings are immutable so it's a total waste of space if you overallocate. It's just an "implementation detail" that this (quite uncommon) way of string concatenation could be optimized.
    – MSeifert
    Jun 11, 2017 at 19:45
  • Don't you still have to copy the memory? Allocation hardly seems like the issue here.
    – user541686
    Jun 12, 2017 at 0:19
  • 2
    @Mehrdad Yes and yes (at least for CPython and the question is tagged CPython). There are lots of safety checks that make sure it doesn't happen in case it could go wrong. But the example in the question is specifically designed to "go into the realloc path".
    – MSeifert
    Jun 12, 2017 at 1:35
  • 1
    @Mehrdad, note that all the references supplied in these answers emphasize that this optimization is specific to CPython, and is very limited. That's key to understanding your objection wrt threads: in CPython, the GIL (Global Interpreter Lock) guarantees only one thread is running CPython internals during the bits of the C implementation that decide whether resizing is safe (and, if so, go on to do the realloc). That's all a single atomic operation so far as threads in CPython are concerned.
    – Tim Peters
    Jun 12, 2017 at 1:54
4
[XXXXXXXXXXXXXXXXXX............]
 \________________/\__________/
     used space      reserved
                      space

When growing a contiguous array data structure (illustrated above) through appending to it, linear performance can be achieved if the extra space reserved while reallocating the array is proportional to the current size of the array. Obviously, for large strings this strategy is not followed, most probably with the purpose of not wasting too much memory. Instead a fixed amount of extra space is reserved during each reallocation, resulting in quadratic time complexity. To understand where the quadratic performance comes from in the latter case, imagine that no overallocation is performed at all (which is the boundary case of that strategy). Then at each iteration a reallocation (requiring linear time) must be performed, and the full runtime is quadratic.

2
  • most probably with the purpose of not wasting too much memory: I guess overallocating is only good if there's a high probability the growth will continue in the future (to justify the use of extra memory). And while the growth will very often continue after list.append(), it was probably deemed to be unlikely that string concatenation will repeat many times, this being an anti-pattern?
    – max
    Jun 11, 2017 at 19:28
  • 1
    @max, CPython never intended to resize strings in-place. That optimization was added more than a dozen years after Python was first released. Some core developers were opposed to it even then. Note that the ability to overallocate costs memory even if it's never used(!): then the object needs to store not only the current size, but also the amount currently allocated. Blowing an extra 8 bytes to store the character "k" just in case someone wants to extend it later is not attractive ;-) Multiply that by millions (programs slinging millions of strings are pretty common).
    – Tim Peters
    Jun 12, 2017 at 3:29
4

TL;DR: Just because string concatenation is optimized under certain circumstances doesn't mean it's necessarily O(1), it's just not always O(n). What determines the performance is ultimatly your system and it could be smart (beware!). Lists that "garantuee" amortized O(1) append operations are still much faster and better at avoiding reallocations.


This is an extremly complicated problem, because it's hard to "measure quantitativly". If you read the announcement:

String concatenations in statements of the form s = s + "abc" and s += "abc" are now performed more efficiently in certain circumstances.

If you take a closer look at it then you'll note that it mentions "certain circumstances". The tricky thing is to find out what these certain cirumstances are. One is immediatly obvious:

  • If something else holds a reference to the original string.

Otherwise it wouldn't be safe to change s.

But another condition is:

  • If the system can do the reallocation in O(1) - that means without needing to copy the contents of the string to a new location.

That's were it get's tricky. Because the system is responsible for doing a reallocation. That's nothing you can control from within python. However your system is smart. That means in many cases you can actually do the reallocation without needing to copy the contents. You might want to take a look at @TimPeters answer, that explains some of it in more details.

I'll approach this problem from an experimentalists point of view.

You can easily check how many reallocations actually need a copy by checking how often the ID changes (because the id function in CPython returns the memory adress):

changes = []
s = ''
changes.append((0, id(s)))
for i in range(10000):
    s += 'a'
    if id(s) != changes[-1][1]:
        changes.append((len(s), id(s)))

print(len(changes))

This gives a different number each run (or almost each run). It's somewhere around 500 on my computer. Even for range(10000000) it's just 5000 on my computer.

But if you think that's really good at "avoiding" copies you're wrong. If you compare it to the number of resizes a list needs (lists over-allocate intentionally so append is amortized O(1)):

import sys

changes = []
s = []
changes.append((0, sys.getsizeof(s)))
for i in range(10000000):
    s.append(1)
    if sys.getsizeof(s) != changes[-1][1]:
        changes.append((len(s), sys.getsizeof(s)))

len(changes)

That only needs 105 reallocations (always).


I mentioned that realloc could be smart and I intentionally kept the "sizes" when the reallocs happened in a list. Many C allocators try to avoid memory fragmentation and at least on my computer the allocator does something different depending on the current size:

# changes is the one from the 10 million character run

%matplotlib notebook   # requires IPython!

import matplotlib.pyplot as plt
import numpy as np

fig = plt.figure(1)
ax = plt.subplot(111)

#ax.plot(sizes, num_changes, label='str')
ax.scatter(np.arange(len(changes)-1), 
           np.diff([i[0] for i in changes]),   # plotting the difference!
           s=5, c='red',
           label='measured')
ax.plot(np.arange(len(changes)-1), 
        [8]*(len(changes)-1),
        ls='dashed', c='black',
        label='8 bytes')
ax.plot(np.arange(len(changes)-1), 
        [4096]*(len(changes)-1),
        ls='dotted', c='black',
        label='4096 bytes')
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_xlabel('x-th copy')
ax.set_ylabel('characters added before a copy is needed')
ax.legend()
plt.tight_layout()

enter image description here

Note that the x-axis represents the number of "copies done" not the size of the string!

That's graph was actually very interesting for me, because it shows clear patterns: For small arrays (up to 465 elements) the steps are constant. It needs to reallocate for every 8 elements added. Then it needs to actually allocate a new array for every character added and then at roughly 940 all bets are off until (roughly) one million elements. Then it seems it allocates in blocks of 4096 bytes.

My guess is that the C allocator uses different allocation schemes for differently sized objects. Small objects are allocated in blocks of 8 bytes, then for bigger-than-small-but-still-small arrays it stops to overallocate and then for medium sized arrays it probably positions them where they "may fit". Then for huge (comparativly speaking) arrays it allocates in blocks of 4096 bytes.

I guess the 8byte and 4096 bytes aren't random. 8 bytes is the size of an int64 (or float64 aka double) and I'm on a 64bit computer with python compiled for 64bits. And 4096 is the page size of my computer. I assume there are lots of "objects" that need have these sizes so it makes sense that the compiler uses these sizes because it could avoid memory fragmentation.

You probably know but just to make sure: For O(1) (amortized) append behaviour the overallocation must depend on the size. If the overallocation is constant it will be O(n**2) (the greater the overallocation the smaller the constant factor but it's still quadratic).

So on my computer the runtime behaviour will be always O(n**2) except for lengths (roughly) 1 000 to 1 000 000 - there it really seems to undefined. In my test run it was able to add many (ten-)thousand elements without ever needing a copy so it would probably "look like O(1)" when timed.

Note that this is just my system. It could look totally different on another computer or even with another compiler on my computer. Don't take these too seriously. I provided the code to do the plots yourself, so you can analyze your system yourself.


You also asked the question (in the comments) if there would be downsides if you over-allocate strings. That's really easy: Strings are immutable. So any overallocated byte is wasting ressources. There are only a few limited cases where it really does grow and these are considered implementation details. The developers probably don't throw away space to make implementation details perform better, some python developers also think that adding this optimization was a bad idea.

5
  • Alex's speech is amazing :) As for the number of reallocations, I still think it's really impressively small. 105 vs 5000 is not a big deal because it still manages to avoid materially impacting the time to incrementally build up a string character by character: it's still linear rather than quadratic as it "should" be. But either way, I agree it's an absolutely horrible practice to rely on it, so I was interested merely for education purposes. Re: intelligent realloc that adjusts to memory request patterns: cool! Though I suppose it's not done yet in any mainstream OS (win/linux)?
    – max
    Jun 11, 2017 at 22:06
  • 1
    @MSeifert, just to drive home how system-dependent this is, on my Win10 box just now under Python 3.6.1, your string loop reallocated about 180 times for 10 thousand iterations, and about 2400 for 10 million iterations.(versus about 50 and 105 times for the list loop).
    – Tim Peters
    Jun 11, 2017 at 22:08
  • @max I updated the post. After some looking around "smart memory allocation based on past allocation history" is more a theoretical concept than actual implementation. :( I also included a graph that shows why it's quadratic for strings greater than 1 million elements on my computer (and it's pretty to look at I think xD).
    – MSeifert
    Jun 12, 2017 at 1:01
  • @MSeifert, FYI, if you're running a current version of Python 3, "almost all" memory allocations are given to CPython's own "small block allocator" (obmalloc.c) first. If the request doesn't exceed 512 bytes, obmalloc handles it itself. And obmalloc then rounds the size up to the nearest multiple of 8 bytes. That's why you see "jump at every 8" so long as the string remains short. Above 512 bytes, you're seeing what your platform C library does (malloc() and realloc()).
    – Tim Peters
    Jun 12, 2017 at 3:04
  • Awesome answer! Years later, on Python 3.9 on Windows 10, I get pretty much the same patterns as in your plot, except 16 bytes instead of 8. But on Colab it looks totally different: Overallocate by 8 bytes until length 464, then by about 25% all the way up to length ten million. Oct 17, 2020 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.