Python string concatenation speed

Question

I am testing the speed of different speed concatenation methods by concatenating the string representation from 1 to a large number(in my case, 20000000). The three methods that I am testing are:

import cProfile

count = 20000000

def profileWrapper(f):
    def wrapper(*args, **argv):
        pr = cProfile.Profile()
        pr.enable()
        string = f(*args, **argv)
        pr.create_stats()
        pr.print_stats()
        return string
    return wrapper

@profileWrapper
def naiveConcat():
    global count
    string = ''
    for i in xrange(count):
        string += `i`
    return string

@profileWrapper
def improvedConcat():
    global count
    string = []
    for i in xrange(count):
        string.append(`i`)
    return ''.join(string)

@profileWrapper
def fastestConcat():
    global count
    return ''.join([`i` for i in xrange(count)])

print 15 * "=", "naiveConcat", 15 * "="
naiveConcat()
print 15 * "=", "improvedConcat", 15 * "="
improvedConcat()
print 15 * "=", "fastestConcat", 15 * "="
fastestConcat()

I am expecting to see the improved method to be faster than the naive one, and it shouldn't' be much slower than the fastest method, but the result doesn't seem like that:

=============== naiveConcat ===============
         3 function calls in 3.951 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 cProfile.py:90(create_stats)
        1    3.951    3.951    3.951    3.951 str_concat.py:18(naiveConcat)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


=============== improvedConcat ===============
         20000004 function calls in 6.990 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 cProfile.py:90(create_stats)
        1    5.196    5.196    6.990    6.990 str_concat.py:26(improvedConcat)
 20000000    1.322    0.000    1.322    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.473    0.473    0.473    0.473 {method 'join' of 'str' objects}


=============== fastestConcat ===============
         4 function calls in 3.043 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 cProfile.py:90(create_stats)
        1    2.539    2.539    3.043    3.043 str_concat.py:34(fastestConcat)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.504    0.504    0.504    0.504 {method 'join' of 'str' objects}

The improved method turned out to be much slower even than the naive method!

This doesn't make sense since the naive method are creating new binding and copying the previous string along with the concatenated string character by character ON EACH ITERATION, this method should take O(n^2), which should be much slower than the other methods which are O(n).

So what makes the improved method so slow? The only reason that I can think of is the append method, but according to this article, the append method takes O(1), so it's definitely not the reason. Then what takes so long in improvedConcat()? Thank you.

You should be more careful. You are timing "append" to but expect result for "join" only. Try a function with basic "%s%s" % (str1, str2). That's the fastest in most situations. — cox
– cox, Commented Feb 5, 2014 at 20:48
@cox, I do need to timing "append" because that is needed in my concatenation function, and I wrote a another function use the way you suggested, turned out it is the slowest of the four, much slower than the naive method. Maybe it is faster for concatenating only a few strings, but is not in the case of concatenating large amount of string segments. — elgoog
– elgoog, Commented Feb 5, 2014 at 21:09
in this case "join" may be an option. The advantage of python/C++/... strings is that the length is cached in object properties. So for basic operations, you may have better results in python than in C. But concatenation is another beast. Wat you do is allocating/filling memory with data - type is not relevant. Maybe a cython function will be faster? — cox
– cox, Commented Feb 5, 2014 at 21:25
In your fastestCount, there is no need to use a list comprehension in your join. You can just use the generator expression, i.e. remove the brackets. I believe this will further improve the performance of that function for you. — 2rs2ts
– 2rs2ts, Commented Feb 5, 2014 at 22:47

Joseph Sheedy · Accepted Answer · 2014-02-05 22:29:38Z

2

The ncalls column of improvedConcat shows that you made 20000004 function calls, compared to just a few for the other algorithms. Function calls aren't super cheap in Python, so try to keep those limited. To demonstrate, I made a new test following your pattern called nop, which merely calls an empty function definition:

def foo():
    pass

@profileWrapper
def nop():
    for i in xrange(count):
        foo()
    return ''

I get similar timing results to your other test, and this NOP (No Operation) test results in

=============== nop ===============
20000003 function calls in 4.386 seconds

So you've got 4.4s of overhead making function calls.

answered Feb 5, 2014 at 22:29

Joseph Sheedy

6,7604 gold badges34 silver badges31 bronze badges

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

3 Comments

2rs2ts Over a year ago

I wonder what the difference would be if OP used string += [i].

Joseph Sheedy Over a year ago

@2rs2ts: "TypeError: cannot concatenate 'str' and 'list' objects". I tried some variations with map(str, array), range instead of xrange, and a generator expression instead of a list comprehension, but didn't improve on fastestConcat.

elgoog Over a year ago

I reduce the total count to 1, count = 1; timeit.timeit('b = improvedConcat()', setup='from __main__ import improvedConcat', number=1), the result still suggests that the improved method is slower: naive: 3.40938568115e-05; improved: 4.10079956055e-05; fastest: 3.09944152832e-05. Moreover, since the function call takes constant time, while the concatenation in the naive method can only take longer as the number to be concatenated increases, so improveConcat will outperform naiveConcat at some point if count is large enough. But when I set count larger, improvedConcat takes even longer

Collectives™ on Stack Overflow

Python string concatenation speed

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related