Efficient string concatenation methods

[Oliver Crow]

As a realtive python newb, but an old hack in general, I've been
interested in the impact of having string objects (and other
primitives) be immutable. It seems to me that string concatenation is
a rather common operation, and in Python having immutable strings
results in a performance gotcha for anyone not aware of the impact of
doing lots of concatenation in the obvious way.

I found several sources with advice for how to do concatenation in a
pythonic way (e.g. ref#1), but I hadn't seen any measurements or
comparisons. So, I put together a little test case and ran it through
for six different methods. Here's the results, and my conclusions:

http://www.skymind.com/~ocrow/python_string/

I'd be happy to hear if anyone else has done similar tests and if
there are any other good candidate methods that I missed.

ref #1: http://manatee.mojam.com/~skip/python/fastpython.html#stringcat

Oliver

 

[Peter Hansen]

http://www.skymind.com/~ocrow/python_string/

I'd be happy to hear if anyone else has done similar tests and if
there are any other good candidate methods that I missed.

You left out the StringIO module (having done only the cStringIO
version of that).

Note also that, for any of the ones which do method calls,
you can speed up the call by saving a reference to the
bound method in a local variable. For example, in method 4
you can do "app_list = str_list.append" and then use
"app_list(`num`)" instead of str_list.append(`num`). This
saves an attribute lookup on each loop iteration. It's
not "idiomatic" to do so except in (a) cases of optimization
obsession, or (b) benchmarks. ;-)

Interesting and useful results. Thanks!

-Peter

 

[Anthony Roberts]

..................................


I was curious about this like an hour ago and googled for it, and hit
your page. Thanks! It was quite helpful.

 

[William Park]

As a realtive python newb, but an old hack in general, I've been
interested in the impact of having string objects (and other
primitives) be immutable. It seems to me that string concatenation is
a rather common operation, and in Python having immutable strings
results in a performance gotcha for anyone not aware of the impact of
doing lots of concatenation in the obvious way.

I found several sources with advice for how to do concatenation in a
pythonic way (e.g. ref#1), but I hadn't seen any measurements or
comparisons. So, I put together a little test case and ran it through
for six different methods. Here's the results, and my conclusions:

http://www.skymind.com/~ocrow/python_string/

I'd be happy to hear if anyone else has done similar tests and if
there are any other good candidate methods that I missed.

ref #1: http://manatee.mojam.com/~skip/python/fastpython.html#stringcat

Oliver

Try printing the integers to a file, then read it back. Should be
similar to Method 5.

 

[Roel Schroeven]

I'd be happy to hear if anyone else has done similar tests and if
there are any other good candidate methods that I missed.

I'd like to try out another variant, but I'm unable to run your
script... Where does that timing module come from? I can't find it anywhere.

The method I propose is simply

def method7():
return ''.join(map(str, xrange(loop_count)))

I ran my own little test and it seems to be faster than method6, but I'd
like to run it in your script for more reliable results. Also, I haven't
done any memory measurement, only a timing.

 

[Terry Reedy]

This

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

will run slightly faster modified to this:

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

by factoring the method lookup out of the loop. Ditto for 3 and 5.

Terry J. Reedy

PS. Changing IE's View/TextSize changes size of header fonts but not body
text, which your CSS apparently fixes at a size a bit small for me on
current system.

 

[Oliver Crow]

I'd like to try out another variant, but I'm unable to run your
script... Where does that timing module come from? I can't find it anywhere.

It's George Neville-Neil's timing module. It looks like it used to be
part of the python library, but has been removed in recent versions.
I'm not sure why. Perhaps timeit is the new preferred module.

The method I propose is simply

def method7():
return ''.join(map(str, xrange(loop_count)))

I ran my own little test and it seems to be faster than method6, but I'd
like to run it in your script for more reliable results. Also, I haven't
done any memory measurement, only a timing.

I'll add that test and rerun the results.

Thanks for the suggestion!

Oliver

 

[Oliver Crow]

You left out the StringIO module (having done only the cStringIO
version of that).

I should probably add that one just for reference. I left it out
originally because my instinct was that it would perform less well
than the string += operator. I think it uses ordinary immutable
python strings for internal storage.

Note also that, for any of the ones which do method calls,
you can speed up the call by saving a reference to the
bound method in a local variable. For example, in method 4
you can do "app_list = str_list.append" and then use
"app_list(`num`)" instead of str_list.append(`num`). This
saves an attribute lookup on each loop iteration. It's
not "idiomatic" to do so except in (a) cases of optimization
obsession, or (b) benchmarks. ;-)

I hadn't thought of this, although it makes sense. It looks like I
could do this in methods 3, 4 and 5. But I also feel that it makes
the code a little less readable.

I think the unstated goal I had was to find a method that could be
learned by python programmers and used in real programs without having
to think *too* hard about the various performance trade-offs. So, in
that spirit I should definitely measure the difference, but perhaps
not go so far as to recommend it as part of the best overall approach.

Interesting and useful results. Thanks!

Thanks!
Oliver

 

[Gyoung-Yoon Noh]

def method7():
return ''.join(map(str, xrange(loop_count)))

repr is faster than str. Below is my result. 'method8' is only
replacement of 'str' in 'method7' to 'repr'.

[snip]
$ python strcat.py
method 6 : 1.474309
process: 1 kb

method 7 : 1.415451
process: 1 kb

method 8 : 1.221584
process: 1 kb

 

[Peter Hansen]

I should probably add that one just for reference. I left it out
originally because my instinct was that it would perform less well
than the string += operator. I think it uses ordinary immutable
python strings for internal storage.

Actually (I just checked the source) it uses a list, more like
example 4, but with some automated joining to the string form
at different times, depending on what's going on with reads()
and seeks() and such. I didn't bother trying to understand
it all, just to verify that it actually uses lists too.

-Peter

 

[Raymond Hettinger]

As a realtive python newb, but an old hack in general, I've been
interested in the impact of having string objects (and other
primitives) be immutable. It seems to me that string concatenation is
a rather common operation, and in Python having immutable strings
results in a performance gotcha for anyone not aware of the impact of
doing lots of concatenation in the obvious way.

I found several sources with advice for how to do concatenation in a
pythonic way (e.g. ref#1), but I hadn't seen any measurements or
comparisons. So, I put together a little test case and ran it through
for six different methods. Here's the results, and my conclusions:

http://www.skymind.com/~ocrow/python_string/

I'd be happy to hear if anyone else has done similar tests and if
there are any other good candidate methods that I missed.

Nice work. Beautifully presented.

A few thoughts:

* The relative speed of list.append() and list comprehensions versus
other approaches will improve dramatically in Py2.4. IOW, the
rankings are version specific. Also, append works faster if you
precompute the attribute lookup before the loop: build =
str_list.append.

* The underlying issue has little to do with the immutability of
strings. The underlying C code is fearless and would mutate the heck
out of it if that is what it took without being visible through the
API. The real issue is how much space to allocate for the final
string. When iterating, as you do, there is little forewarning about
how many more entries to expect or the length of each. If too little
space is allocated, then room for a larger string needs to be created
and the previous result recopied (giving the O(n**2) behavior you're
trying to get rid of).

* For arrays, the advantage of mutability does not play out through
the fromstring() method (which suffers the previously mentioned
allocation issues). The way to capitalize is to make a long array all
at once and then make slice assignments into it to add the strings.
This is essentially what str.join() does under the hood (it loops over
the input once and adds up the string lengths, allocates all necessary
space, and re-loops making slice assignments) -- this is how it gets
its O(n) behavior. For arrays, I suspect the overhead of tracking the
slice pointer would overwhelm the benefits for small values of n. An
interesting comparison is to time "ans=[]; build=ans.append; for i in
xrange(n): build(i)" versus "ans=[None]*n: for i in xrange(n):
ans=i".


Raymond Hettinger

 

[Bengt Richter]

On 2 May 2004 18:52:27 -0700, (e-mail address removed) (Raymond Hettinger) wrote:
[...]

Nice work. Beautifully presented.

A few thoughts:

* The relative speed of list.append() and list comprehensions versus
other approaches will improve dramatically in Py2.4. IOW, the
rankings are version specific. Also, append works faster if you
precompute the attribute lookup before the loop: build =
str_list.append.

* The underlying issue has little to do with the immutability of
strings. The underlying C code is fearless and would mutate the heck
out of it if that is what it took without being visible through the
API. The real issue is how much space to allocate for the final
string. When iterating, as you do, there is little forewarning about
how many more entries to expect or the length of each. If too little
space is allocated, then room for a larger string needs to be created
and the previous result recopied (giving the O(n**2) behavior you're
trying to get rid of).

Perhaps a capacity keyword arg for the str constructor?, E.g.,
s = str(capacity=1000)
s => ''
s += 'abc' # just mutates the capacious object if ref count is one.
....etc

* For arrays, the advantage of mutability does not play out through
the fromstring() method (which suffers the previously mentioned
allocation issues). The way to capitalize is to make a long array all
at once and then make slice assignments into it to add the strings.
This is essentially what str.join() does under the hood (it loops over
the input once and adds up the string lengths, allocates all necessary
space, and re-loops making slice assignments) -- this is how it gets
its O(n) behavior. For arrays, I suspect the overhead of tracking the
slice pointer would overwhelm the benefits for small values of n. An
interesting comparison is to time "ans=[]; build=ans.append; for i in
xrange(n): build(i)" versus "ans=[None]*n: for i in xrange(n):
ans=i".

ans = list(capacity=whatever) # ?

Similarly for arrays.

Regards,
Bengt Richter

 

[jtd]

API. The real issue is how much space to allocate for the final
string. When iterating, as you do, there is little forewarning about
how many more entries to expect or the length of each. If too little
space is allocated, then room for a larger string needs to be created
and the previous result recopied (giving the O(n**2) behavior you're
trying to get rid of).

Is there any particular reason why the space allocated does not
increase *exponentially*, say with a factor of 1.5 or 2? That's how
the string class is implemented in C++, IIRC. That'd give you
amortized linear rather than quadratic time.

 

[Josiah Carlson]

Is there any particular reason why the space allocated does not
increase *exponentially*, say with a factor of 1.5 or 2? That's how
the string class is implemented in C++, IIRC. That'd give you
amortized linear rather than quadratic time.

The C++ string class is mutable. When you have immutable strings,
having extra space at the end is useless.

- Josiah