Why is ''.join() faster than += in Python?
<p>I'm able to find a bevy of information online (on Stack&nbsp;Overflow and otherwise) about how it's a very inefficient and bad practice to use <code>+</code> or <code>+=</code> for concatenation in Python.</p>

<p>I can't seem to find WHY <code>+=</code> is so inefficient. Outside of a mention <a href="http://stackoverflow.com/a/1350289/3903011" title="What is the most efficient string concatenation method in python?">here</a> 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.</p>

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

<p>I think this behaviour is best explained in <a href="https://www.lua.org/pil/11.6.html">Lua's string buffer chapter</a>.</p>

<p>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):</p>

<pre><code>s = ""
for l in some_list:
  s += l
</code></pre>

<p>Assume that each <code>l</code> is 20 bytes and the <code>s</code> has already been parsed to a size of 50 KB. When Python concatenates <code>s + l</code> it creates a new string with 50,020 bytes and copies 50 KB from <code>s</code> 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</p>

<pre><code>s += l
</code></pre>

<p>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.</p>

<p>And, at the end:</p>

<blockquote>
  <p>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 <code>StringBuffer</code> to ameliorate the problem.)</p>
</blockquote>

<p>Python strings are also <a href="http://stackoverflow.com/a/9098038/1190388">immutable objects</a>.</p>

python optimization