71

I'm able to find a bevy of information online (on Stack Overflow and otherwise) about how it's a very inefficient and bad practice to use + or += for concatenation in Python.

I can't seem to find WHY += is so inefficient. Outside of a mention here that "it's been optimized for 20% improvement in certain cases" (still not clear what those cases are), I can't find any additional information.

What is happening on a more technical level that makes ''.join() superior to other Python concatenation methods?

Improve this question
11
  • 1
    Related. stackoverflow.com/questions/34008010/… Commented Sep 3, 2016 at 23:14
  • 4
    += behaves differently for string, integers. it is possible that Python takes more time in figuring the type of data on which += to operate on i.e. its addition if they are integers while concat if they are strings. While in ' '.join() operation, it expects string elements only - which makes Python to not worry about type of data its dealing with. Commented Sep 3, 2016 at 23:19
  • @cricket_007 linked to a great post providing more insight. However I have accepted mgilson's answer. Commented Sep 3, 2016 at 23:36
  • @BryanOakley Examining the source code didn't even cross my mind. This is another good solution to the problem. Commented Sep 3, 2016 at 23:40
  • 7
    You may find the story of Shlemiel the painter (originally told here) helpful when trying to understand the potential performance costs of doing a lot of += concatenation with strings. The exact reason += may be O(N) in Python is not exactly the same reason strcat is O(N) in C, but it's similar. Commented Sep 4, 2016 at 0:02

2 Answers 2

Reset to default
84

Let's say you have this code to build up a string from three strings:

x = 'foo'
x += 'bar'  # 'foobar'
x += 'baz'  # 'foobarbaz'

In this case, Python first needs to allocate and create 'foobar' before it can allocate and create 'foobarbaz'.

So for each += that gets called, the entire contents of the string and whatever is getting added to it need to be copied into an entirely new memory buffer. In other words, if you have N strings to be joined, you need to allocate approximately N temporary strings and the first substring gets copied ~N times. The last substring only gets copied once, but on average, each substring gets copied ~N/2 times.

With .join, Python can play a number of tricks since the intermediate strings do not need to be created. CPython figures out how much memory it needs up front and then allocates a correctly-sized buffer. Finally, it then copies each piece into the new buffer which means that each piece is only copied once.

There are other viable approaches which could lead to better performance for += in some cases. E.g. if the internal string representation is actually a rope or if the runtime is actually smart enough to somehow figure out that the temporary strings are of no use to the program and optimize them away.

However, CPython certainly does not do these optimizations reliably (though it may for a few corner cases) and since it is the most common implementation in use, many best-practices are based on what works well for CPython. Having a standardized set of norms also makes it easier for other implementations to focus their optimization efforts as well.

Improve this answer
Sign up to request clarification or add additional context in comments.

17 Comments

Image
When I read your answer for the first time, I thought "how does the interpreter know it needs to allocate space for 'foobar'? Does it read my mind, knowing I'm going to join those at some point?" I think you're assuming there's code like foo += bar + baz. Your answer would make a little more sense if you showed the code that would cause the allocation.
Image
@BryanOakley: foo += bar; foo += baz; will behave exactly as this post describes. foo = foo+ bar + baz; as well. foo += bar + baz works subtly differently, but no faster.
Image
@MooingDuck: I understand. That's not the point. The point is, neither the original question nor the answer shows the expression foo += bar. A beginner may stumble on this answer and wonder why python allocates space for "foobar" in the absence of an expression.
Image
@Random832 -- It actually is true. join does go through the input twice. It accomplishes this by creating a sequence from the input before the first run-through.
Image
@freakish -- FWIW, it's pretty well documented (at least on Stackoverflow) that joining a list comprehension is slightly faster than joining a generator expression. The real world time difference is very minimal however so I disagree that one way or the other is preferred (e.g. I've never seen it in a style-guide). Personally I usually still use the generator to be consistent with other code that I write, but in a code review, I will let it slide when I wouldn't let something like sum([x for x in ...]) (why waste the memory?)...
|
9

I think this behaviour is best explained in Lua's string buffer chapter.

To rewrite that explanation in context of Python, let's start with an innocent code snippet (a derivative of the one at Lua's docs):

s = ""
for l in some_list:
  s += l

Assume that each l is 20 bytes and the s has already been parsed to a size of 50 KB. When Python concatenates s + l it creates a new string with 50,020 bytes and copies 50 KB from s into this new string. That is, for each new line, the program moves 50 KB of memory, and growing. After reading 100 new lines (only 2 KB), the snippet has already moved more than 5 MB of memory. To make things worse, after the assignment

s += l

the old string is now garbage. After two loop cycles, there are two old strings making a total of more than 100 KB of garbage. So, the language compiler decides to run its garbage collector and frees those 100 KB. The problem is that this will happen every two cycles and the program will run its garbage collector two thousand times before reading the whole list. Even with all this work, its memory usage will be a large multiple of the list's size.

And, at the end:

This problem is not peculiar to Lua: Other languages with true garbage collection, and where strings are immutable objects, present a similar behavior, Java being the most famous example. (Java offers the structure StringBuffer to ameliorate the problem.)

Python strings are also immutable objects.

Improve this answer

5 Comments

Image
It's worth noting that CPython (the main Python interpreter) cheats a bit with respect to strings being immutable (this is the "optimization" that's been vaguely alluded to). If it sees you do += and the name on the left side is bound to a string with exactly one reference, it tries to resize that string's buffer in place (which may or may not work depending on some low-level memory allocation details). It makes repeated += operations much faster when it works (indeed, using a loop with += may be faster than "".join). The big reason not to use it is for cross-interpreter compatibility.
Image
LuaJIT eats this sort of loop for breakfast and I seriously doubt you'd get more than 2-3 allocations here. I'd love to be proven wrong though.
Image
@Blckknght Could you explain more on "cross-interpreter compatibility"?
Image
@Blckknght And what do you think of the accepted answer, it says So for each += that gets called, the entire contents of the string and whatever is getting added to it need to be copied into an entirely new memory buffer..
Image
How does answer have this fewer upvotes? What is going on here?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.