95

As a result of the comments in my answer on this thread, I wanted to know what the speed difference is between the += operator and ''.join()

So what is the speed comparison between the two?

Community
  • 1
  • 1
Wayne Werner
  • 49,299
  • 29
  • 200
  • 290
  • 3
    what are you testing? two strings? two million strings? – SilentGhost Jun 16 '10 at 17:03
  • 1
    This question is similar and has better answers: https://stackoverflow.com/questions/1349311/python-string-join-is-faster-than-but-whats-wrong-here/ – Frank Aug 26 '20 at 15:00

7 Answers7

133

From: Efficient String Concatenation

Method 1:

def method1():
  out_str = ''
  for num in xrange(loop_count):
    out_str += 'num'
  return out_str

Method 4:

def method4():
  str_list = []
  for num in xrange(loop_count):
    str_list.append('num')
  return ''.join(str_list)

Now I realise they are not strictly representative, and the 4th method appends to a list before iterating through and joining each item, but it's a fair indication.

String join is significantly faster then concatenation.

Why? Strings are immutable and can't be changed in place. To alter one, a new representation needs to be created (a concatenation of the two).

alt text

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
Dominic Bou-Samra
  • 14,799
  • 26
  • 100
  • 156
  • 3
    Well I was going to just answer this myself (hence the tag) but it looks like you beat me to the punch! +1, especially for the useful link! – Wayne Werner Jun 16 '10 at 17:12
  • 2
    @Wayne: *Useful link* is copied from the question that you've linked to! – SilentGhost Jun 16 '10 at 17:17
  • 10
    -1. There is no fixed ratio for the speed difference between string.join and + concatenation, because they have completely different **growth rate**/big oh complexity. As the number of string to concatenate grows, string.join will have greater and greater margin compared to string concatenation. – Lie Ryan Jun 16 '10 at 18:14
  • 1
    @nate c: Method 1 is now just a shade slower than method 6 (using Python 2.6), but that's only in CPython. I believe that in Jython, it hasn't been optimised like this, so `''.join(list)` remains considerably faster - see the first point in "Programming Recommendations" in PEP 8. – Chris Morgan Nov 22 '10 at 05:11
  • My point is that the accepted 'popular' answer uses a chart that was about 5 years old when this question was posted. – nate c Nov 22 '10 at 05:25
  • 12
    From PEP 8: “For example, do not rely on CPython's efficient implementation of in-place string concatenation for statements in the form a+=b or a=a+b. Those statements run more slowly in Jython. In performance sensitive parts of the library, the ''.join() form should be used instead. This will ensure that concatenation occurs in linear time across various implementations.” – Neil G Jul 02 '11 at 08:41
  • I don't know about Jython as I never worked on it but in normal python 2.7.x, + is lot faster than list append. – thiruvenkadam Oct 09 '13 at 09:38
  • @thiruvenkadam: It depends how many `+`s you're performing, how large each new item is, etc. Typically, repeated `append`s win asymptotically (for many concatenations), while for a very small number of items, `+` wins. But even for small numbers of items, `''.join` often wins; in a local test on Py 3.5.0, Linux x86-64, `a, b, c, d = bytes(range(100)).decode('ascii'), '1234', bytes(range(100, 200)).decode('latin-1'), '4567'`, it's actually 20% faster to do `''.join((a, b, c, d))` (200 ns) than `a + b + c +d` (251 ns). – ShadowRanger Dec 06 '16 at 16:22
  • @ShadowRanger Your example could not be taken for list join as you are joining a tuple rather than a list. Using a list there, indeed raises 40% of the time. And when I tried a sample example in Python 2.7.6 for smaller number of items, joining a tuple also nearly 50% slower than using +. – thiruvenkadam Dec 07 '16 at 10:47
12

Note: This benchmark was informal and is due to be redone because it doesn't show a full picture of how these methods will perform with more realistically long strings. As mentioned in the comments by @Mark Amery, += is not reliably as fast as using f-strings, and str#join isn't as dramatically slower in realistic use cases.

These metrics are also likely outdated by the significant performance improvements introduced by subsequent CPython versions, and most notably, 3.11.


The existing answers are very well-written and researched, but here's another answer for the Python 3.6 era, since now we have literal string interpolation (AKA, f-strings):

>>> import timeit
>>> timeit.timeit('f\'{"a"}{"b"}{"c"}\'', number=1000000)
0.14618930302094668
>>> timeit.timeit('"".join(["a", "b", "c"])', number=1000000)
0.23334730707574636
>>> timeit.timeit('a = "a"; a += "b"; a += "c"', number=1000000)
0.14985873899422586

Test performed using CPython 3.6.5 on a 2012 Retina MacBook Pro with an Intel Core i7 at 2.3 GHz.

Jules
  • 14,200
  • 13
  • 56
  • 101
  • 2
    Please see this answer to a similar question: https://stackoverflow.com/a/1350289/1202214 += should NOT be used, its performance gains is an illusion. – Andreas Bergström Nov 06 '18 at 18:45
  • @AndreasBergström nice find. re-running the informal benchmark on the same machine using `a = "a"; a = a + "b"; a = a + "c"` yields a slight slowdown of `0.1739`. – Jules Nov 07 '18 at 01:06
  • This is not a fair benchmark. You are not creating the list in a loop which is a significant performance optimization that is not applicable to the general case. Check Dominic's answer for how a fair benchmark should look. – Stefan Fabian Mar 01 '21 at 10:42
  • @StefanFabian Creating a list in a loop just to pass it to `.join` is suboptimal and timing such a process shouldn't be part of any benchmark; Dominc's answer is unfairly skewing things against `.join` by doing so. `.join` can take an arbitrary iterable of strings; it needn't be a *list*. As soon as you're joining a significant number of elements, using a generator as the iterable you pass to `.join` is going to be measurably faster than building a list and passing that to `.join`. – Mark Amery Jan 22 '23 at 13:51
  • This answer gives the impression that `.join` is slower than other kinds of concatenation, but that's only the case because you're only joining three short strings together. Expand this to concatenating large numbers of strings (by either using `.join`, or using `+=` *in a loop*) and the results will dramatically reverse, since given an iterable `strings` containing *n* strings, `result = ''; for x in strings: result += x` has *O(n²)* time complexity while `result = ''.join(strings)` has *O(n)* time complexity. – Mark Amery Jan 22 '23 at 13:55
  • Thanks @MarkAmery! I've added a note to the top of this answer explaining why the original benchmark isn't complete and is likely out of date. I may revisit this later to add more realistic updated benchmarks. – Jules Jan 23 '23 at 13:56
11

My original code was wrong, it appears that + concatenation is usually faster (especially with newer versions of Python on newer hardware)

The times are as follows:

Iterations: 1,000,000       

Python 3.3 on Windows 7, Core i7

String of len:   1 took:     0.5710     0.2880 seconds
String of len:   4 took:     0.9480     0.5830 seconds
String of len:   6 took:     1.2770     0.8130 seconds
String of len:  12 took:     2.0610     1.5930 seconds
String of len:  80 took:    10.5140    37.8590 seconds
String of len: 222 took:    27.3400   134.7440 seconds
String of len: 443 took:    52.9640   170.6440 seconds

Python 2.7 on Windows 7, Core i7

String of len:   1 took:     0.7190     0.4960 seconds
String of len:   4 took:     1.0660     0.6920 seconds
String of len:   6 took:     1.3300     0.8560 seconds
String of len:  12 took:     1.9980     1.5330 seconds
String of len:  80 took:     9.0520    25.7190 seconds
String of len: 222 took:    23.1620    71.3620 seconds
String of len: 443 took:    44.3620   117.1510 seconds

On Linux Mint, Python 2.7, some slower processor

String of len:   1 took:     1.8840     1.2990 seconds
String of len:   4 took:     2.8394     1.9663 seconds
String of len:   6 took:     3.5177     2.4162 seconds
String of len:  12 took:     5.5456     4.1695 seconds
String of len:  80 took:    27.8813    19.2180 seconds
String of len: 222 took:    69.5679    55.7790 seconds
String of len: 443 took:   135.6101   153.8212 seconds

And here is the code:

from __future__ import print_function
import time

def strcat(string):
    newstr = ''
    for char in string:
        newstr += char
    return newstr

def listcat(string):
    chars = []
    for char in string:
        chars.append(char)
    return ''.join(chars)

def test(fn, times, *args):
    start = time.time()
    for x in range(times):
        fn(*args)
    return "{:>10.4f}".format(time.time() - start)

def testall():
    strings = ['a', 'long', 'longer', 'a bit longer', 
               '''adjkrsn widn fskejwoskemwkoskdfisdfasdfjiz  oijewf sdkjjka dsf sdk siasjk dfwijs''',
               '''this is a really long string that's so long
               it had to be triple quoted  and contains lots of
               superflous characters for kicks and gigles
               @!#(*_#)(*$(*!#@&)(*E\xc4\x32\xff\x92\x23\xDF\xDFk^%#$!)%#^(*#''',
              '''I needed another long string but this one won't have any new lines or crazy characters in it, I'm just going to type normal characters that I would usually write blah blah blah blah this is some more text hey cool what's crazy is that it looks that the str += is really close to the O(n^2) worst case performance, but it looks more like the other method increases in a perhaps linear scale? I don't know but I think this is enough text I hope.''']

    for string in strings:
        print("String of len:", len(string), "took:", test(listcat, 1000000, string), test(strcat, 1000000, string), "seconds")

testall()
90Percent
  • 3
  • 2
Wayne Werner
  • 49,299
  • 29
  • 200
  • 290
  • 1
    Your test is wrong. Your strcat will return output as string * len(string) whereas your listcat will always return just the string. How can you compare them? Test with newstr += char or with chars.append(string). This actually proves the point of @bwawok that + is faster than list append. – thiruvenkadam Oct 09 '13 at 09:35
  • Good catch - that should be newstr += **char**. Whoops. Fixed, and updated. – Wayne Werner Oct 09 '13 at 22:31
  • On my Win 10, desktop Haswell i5, `Python 2.7.10` and `3.5.2` machine results are the opposite: strcat is slightly faster: http://pastebin.com/sVVuExBa – Dan M. Aug 28 '16 at 14:11
  • 1
    @DanM.: Did you mean `listcat` is slightly faster? Because that's what it shows in the Pastebin. – ShadowRanger Dec 06 '16 at 16:24
  • @ShadowRanger values in the second column are lower, isn't it supposed to represent `strcat` (according to print)? – Dan M. Dec 06 '16 at 18:07
  • @DanM. Aren't the values in the second column higher as the string grows in size? What? Why is this so confusing? – Manan Mehta Jul 03 '17 at 23:29
  • @MananMehta Well, according to the code in this answer first the result of `test(listcat, 1000000, string)` is printed and than `strcat` (some sort of headers really had to be added xD). So in my tests for longest (`443`) len for py the results are `33.0310 21.9950 seconds` and for `py3`: `32.2237 24.9165 seconds`. So, `strcat`, being the second, it looks like it's about `30%` faster on my PC (while it's much slower than `listcat`in the answer above). – Dan M. Jul 03 '17 at 23:47
  • @DanM. That is weird! I just ran method6 and method1 from [Efficient String Concatenation](https://waymoot.org/home/python_string/) in the py3 interpreter with loop_count being 5,000,000. method6 took 3-4 seconds while method1 took over a minute and yet no result! – Manan Mehta Jul 04 '17 at 00:00
  • @MananMehta well, the @Wayne Werner's benchmark is testing entirely different and weird thing. He get's a string and benches the speed of appending all chars in this string. So he builds a new array of chars in `listcat` case before appending and that's actually what takes the most time. – Dan M. Jul 04 '17 at 00:53
  • @DanM. Just ran method4 from the same link in my previous comment with loop_count 5,000,000. I got the result in 6-7 seconds but again, method1 takes over a minute without any results. I am so lost! xD I don't know what the right solution is... – Manan Mehta Jul 04 '17 at 01:15
1

If I expect well, for a list with k string, with n characters in total, time complexity of join should be O(nlogk) while time complexity of classic concatenation should be O(nk).

That would be the same relative costs as merging k sorted list (efficient method is O(nlkg), while the simple one, akin to concatenation is O(nk) ).

GDS
  • 21
  • 1
0

I rewrote the last answer, could jou please share your opinion on the way i tested?

import time

start1 = time.clock()
for x in range (10000000):
    dog1 = ' and '.join(['spam', 'eggs', 'spam', 'spam', 'eggs', 'spam','spam', 'eggs', 'spam', 'spam', 'eggs', 'spam'])

end1 = time.clock()
print("Time to run Joiner = ", end1 - start1, "seconds")


start2 = time.clock()
for x in range (10000000):
    dog2 = 'spam'+' and '+'eggs'+' and '+'spam'+' and '+'spam'+' and '+'eggs'+' and '+'spam'+' and '+'spam'+' and '+'eggs'+' and '+'spam'+' and '+'spam'+' and '+'eggs'+' and '+'spam'

end2 = time.clock()
print("Time to run + = ", end2 - start2, "seconds")

NOTE: This example is written in Python 3.5, where range() acts like the former xrange()

The output i got:

Time to run Joiner =  27.086106206103153 seconds
Time to run + =  69.79100515996426 seconds

Personally i prefer ''.join([]) over the 'Plusser way' because it's cleaner and more readable.

Gerard Kool
  • 129
  • 1
  • 4
0

If I say it algorithmically, if you choose [ += ] then it generates a new object and it will be O(n)**2. But if you use [ .join ] then it will be O(n).

Ilya
  • 1
  • 5
  • 18
-3

This is what silly programs are designed to test :)

Use plus

import time

if __name__ == '__main__':
    start = time.clock()
    for x in range (1, 10000000):
        dog = "a" + "b"

    end = time.clock()
    print "Time to run Plusser = ", end - start, "seconds"

Output of:

Time to run Plusser =  1.16350010965 seconds

Now with join....

import time
if __name__ == '__main__':
    start = time.clock()
    for x in range (1, 10000000):
        dog = "a".join("b")

    end = time.clock()
    print "Time to run Joiner = ", end - start, "seconds"

Output Of:

Time to run Joiner =  21.3877386651 seconds

So on python 2.6 on windows, I would say + is about 18 times faster than join :)

bwawok
  • 14,898
  • 7
  • 32
  • 43
  • 3
    Your test only uses small string - which gives misleading output, because once you try with longer strings (see my answer) you'll probably see some different results. Also you should use xrange which is cheaper on memory, and you can also omit the `1` in your call to range. – Wayne Werner Jun 16 '10 at 17:20
  • Thanks for the tips :) I am still learning Python, more of a side hobby when I need a break from Java. – bwawok Jun 16 '10 at 17:28
  • 6
    this is broken on more than one place. check how much is `'a'.join('b')` - it is 'b'. What you meant is ''.join(['a', 'b']). Also, 'a'+'b' will likely be optimized to constant during compilation, so what are you testing then, assignment? – Nas Banov Jun 17 '10 at 04:42
  • Adding to @NasBanov, even if you fixed it, testing very short concatenations isn't going to test the strengths of `join`. `join` wins when it reduces N concatenations (1 allocate, 2 `memcpy` ops for each concatenation) to a 1 allocation followed by N `memcpy` operations. Because it involves (expensive) method calls, it will never win in the two operands case. But at least on Python 3.5, you can actually get a win with (in [my test case](https://stackoverflow.com/questions/3055477/how-slow-is-pythons-string-concatenation-vs-str-join/3055536#comment69208819_3055541)) as little as 4 operands. – ShadowRanger Dec 06 '16 at 16:33
  • Also, as a weird consequence of how CPython works, it's actually faster (at least on CPython 3.5) to do `mylist += (a,)` than to do `mylist.append(a)`. Creating an anonymous `tuple` (small tuples are cached in a free list, so no allocation occurs) and invoking operator `+=`, both syntax based with direct support in the bytecode interpreter, is cheaper than calling a method (generic, without special optimizations). For small concatenations, the overhead of stuff like this exceeds the asymptotic expense of the actual concatenations. – ShadowRanger Dec 06 '16 at 16:38