title: Why does concatenation in Python appear to be getting slower?
body: <p>Why does it appear that concatenation in Python 3 is slower in some cases than in Python 2?</p>
  
  <p>The most impacted method of concatenation appears to be successive concatenation of <code>bytes</code> objects, which has gone from an O(n) to O(n²) operation.</p>
  
  <p>The bulk of my profiling code is here:</p>
  
  <pre><code>#!/usr/bin/env python
  
  from operator import concat
  from sys import version, version_info
  from timeit import timeit  # Compatibility: ver &gt;= 2.6
  
  # ver = version.partition('\n')[0].rstrip()
  ver = '.'.join(str(v) for v in version_info[:3])
  print(ver)
  
  if version_info[0] == 2:
      from StringIO import StringIO
  else:
      from io import StringIO
      from functools import reduce
      xrange = range
  
  
  def build_plus():
      output = ''
      for _ in xrange(input_len):
          output += 'a'
      return output
  
  
  def build_join():
      return ''.join('a' for _ in xrange(input_len))
  
  
  def build_bytes_plus():
      output = b''
      for _ in xrange(input_len):
          output += b'a'
      return output
  
  
  def build_stringio():
      output = StringIO()
      for _ in xrange(input_len):
          output.write('a')
      return output.getvalue()
  
  
  def build_reduce():
      return reduce(concat, ('a' for _ in xrange(input_len)))
  
  
  builds = {'str+': build_plus,
            'join': build_join,
            'reduce': build_reduce,
            'bytes+': build_bytes_plus,
            'StringIO': build_stringio}
  
  if version_info[0] == 2:
      import cStringIO
  
      def build_cstringio():
          output = cStringIO.StringIO()
          for _ in xrange(input_len):
              output.write('a')
          return output.getvalue()
  
      builds['cStringIO'] = build_cstringio
  else:
      from io import BytesIO
  
      def build_bytesio():
          output = BytesIO()
          for _ in xrange(input_len):
              output.write(b'a')
          return output.getvalue()
  
      builds['BytesIO'] = build_bytesio
  
  resfile = open('times.csv', 'a')
  size_range = 50  # Number of points over the size axis
  min_order = 1.0  # 10^x byte input min
  max_order = 5.0  # 10^x byte input max
  
  for allow_gc in (False, True):
      setup = 'gc.enable()' if allow_gc else 'pass'
  
      for build_name, build_fun in builds.items():
          # For a roughly constant confidence interval, aim for uniform sample density across the
          # (logarithmic) input size axis.
          for size_index in range(size_range+1):
              input_len = int(10**((max_order-min_order)*size_index/size_range + min_order))
  
              # Rather than repeating many measurements at one input size, perform one measurement
              # per input size for a continuous range of input sizes and apply smoothing later.
              dur = timeit(build_fun, setup, number=1)
  
              resfile.write('"%s",%s,"%s",%d,%.6g\n' % (ver, str(allow_gc).upper(), build_name,
                                                        input_len, dur))
  </code></pre>
  
  <p>Some graphs from my R script shown here:</p>
  
  <p><a href="https://i.stack.imgur.com/rKfng.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/rKfng.jpg" alt="String append across Python versions"></a></p>
  
  <p><a href="https://i.stack.imgur.com/YiqkP.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/YiqkP.png" alt="String append time complexity"></a></p>