Speed of string += string

achrist at easystreet.com achrist at easystreet.com
Sun Apr 13 04:59:13 CEST 2003

We went around on this one about 4 years ago. Is this a url:


About 6 messages into the thread, Tim Peters came up with a way that
was about 5 times faster than string.join().

Now, which is preferred:

	if astring == "":


	if len(astring) == 0:



Alex Martelli wrote:
> Mads Orbesen Troest wrote:
> > Given that strings are immutable, is it exceedingly slow (and memory
> > spiking) to do a lot of "string += string" operations in one's code? IOW,
> Yes -- it's THE one major performance trap in naively coded Python,
> since, when "a lot" is a sufficiently large N, a lot of += on short
> strings ends up being O(N squared) where O(N) approaches would be
> available.  And turning something potentially O(N) into something
> O(N squared) is the kind of performance hit that profiling won't
> necessarily catch, because it shows up (as unboundedly bad) only
> for N sufficiently large...
> So, it's basically the one performance trap I find it most necessary
> to teach even to total beginners!
> > does each and every += evaluation lead to a new concatenated copy of the
> > previous string (now freed for garbage collection) and the new string, so
> Exactly (it's not necessarily the case that the previous string is freed
> for garbage collection, but whether it is, or not, a new concatenated copy
> is indeed unavoidable).
> > that the longer the string to which stuff is appended is, the longer times
> > each += operation takes?
> Again, exactly -- s += l takes roughly O(len(s)+len(l)) time (as it
> necessarily has to copy the len(s) previous chars followed by the len(l)
> new ones).
> Building up lists of strings with mylist.append(piece), then joining
> them together at the end with ''.join(mylist), is the canonical solution;
> others, which I've seen already pointed out to you, include using cStringIO.
> Alex

More information about the Python-list mailing list