Python String Concatenation (again): the revenge of join!

In this second post (the first here) I proposed some benchmarks to investigate the efficiency of string concatenation in Python. I believe that the results are partial for two basic reasons:

1. we benchmark just concatenation of huge amounts of very small strings
2. we are creating the strings in the iteration. As a consequence, we are implicitly penalizing the methods using str.join

In this post I address the second issue. I moved the creation of the list outside the benchmarked code, and simplified the functions accordingly.

def str_sum(seq):
    out_str = ''
    for item in seq:
        out_str += item
    return out_str

def str_sum_b(seq):
    out_str = ''
    for item in seq:
        out_str = out_str + item
    return out_str

def str_join(seq):
    return ''.join(seq)

def str_join_lc(seq):
    return ''.join(item for item in seq)

def string_io(seq):
    file_str = StringIO()
    for item in seq:
        file_str.write(item)
    out_str = file_str.getvalue()
    return out_str

These are the same functions we benchmarked last time simplified where necessary. str_sum and str_sum_b are basically unchanged. On the other hand, str_join is completely different: since the first three lines where used to create the list, now they have completely disappeared.

@old_version
def str_join(loop_count):
    str_list = []
    for num in xrange(loop_count):
        str_list.append(str(num))
    out_str = ''.join(str_list)
    return out_str

As a consequence, the funcion is much shorter. I mantained the _lc variant: however, I will remove it from serious benchmarks as it is inevitably slower than the regular version. I also introduced some new functions to test here:

def str_sum_c(seq):
    return reduce(op.add, seq)

def str_sum_d(seq):
    return reduce(op.iadd, seq)

def str_sum_e(seq):
    return sum(seq, '')

They are also disabled: the _e variant is invalid Python. Calling sum on a sequence of strings gives this instructive error:

TypeError: sum() can't sum strings [use ''.join(seq) instead]

The other two were excluded because they are too slow:

its	str_sum	str_sum_c	str_sum_d
100000	0.010572	2.781853	2.704670

Unfortunately, reduce appear to be very slow. Consider these additional functions:

def str_sum_f(seq):
    return reduce(str.__add__, seq)

def str_sum_g(seq):
    out_str = ''
    for item in seq:
        op.iadd(out_str, item)
    return out_str

its	str_sum_b	str_sum_f	str_sum_g
100000	0.011448	2.812612	0.018933

I decided to benchmark only a relatively small subset of the presented functions. The measures I plotted are the result of 10 executions of the function; the average time can be obtained simply dividing by 10. In the first plot I consider strings composed by numbers of fragments one order of magnitude smaller than the ones benchmarked in my other post.

In this other plot, I present the results with the same order of magnitude. However, the times presented result from 10 executions of the same function: the spikes and irregularities were not eliminated by averaging the times. Consequently, I don't consider the plot meaningful unless I discover the reason of such behavior (which comes completely unexpected).

In the future I will try a benchmark consisting of concatenation of larger strings. Technorati Tags: Algorithms, Efficiency, Optimization, Python, String Append, String Concatenation

Python repeated string concatenation: should we change our habits?

One of the most common errors newbies do is related to string concatenation in Python. In Python, string are immutable objects; consequently, concatenating two string effectively creates a new object (and possibly releases the two former object). The common advise is to build strings using the popular str.join method.

sep.join(string_framents_sequence)

which frequently just turns into:

''.join(string_framents_sequence)

Of course, sometimes the advice goes as far as "never" ever concatenate two strings". In some sense, the advise is good, but it is often given for the wrong reasons. In fact, most of the times the '%' (or format) idiom is simply clearer. Compare:

'[%d:%d] %d %s>' % (min, hour, ret_code, path)

with:

'[' + min + ':' + hour + '] ' + ret_code + ' ' + path + '>'

Anyway, recently it has been disputed whether the str.join alternative is so much faster than repeated concatenation, given the fact that the += operator has been improved. My goal is not to investigate this matter.

Baseline

At first, I decided to benchmark this simple function:

def baseline(loop_count):
    for num in xrange(loop_count):
        str(num)

Since my first testing code is creating strings from a bunch of integer, here I am just benchmarking performance of the bare operation, without actually building the string. The second step is to accumulate all the fragments. The idea is to discover the point where thrashing starts, that is to say the range where the operation behavior remains linear. Outside these zone, we must figure out other factors and in fact the benchmark is not relevant. A third baseline tests uses list comprehensions.

def baseline2(loop_count):
    lst = []
    for num in xrange(loop_count):
        lst.append(str(num))
    return lst

def baseline3(loop_count):
    return [str(int) for int in xrange(loop_count)]

If we examine the plot of the execution times, we can see that when we keep in memory all the string fragments, thrashing starts after 10⁷ iterations. The graph is logarithmic in both axis. As a side note, using list comprehensions is twice as fast than manually adding stuff to the list one by one.

Tested Code

These are the functions I actually benchmarked. Full code for the benchmark can be found in my git repository.

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

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

def str_join_lc(loop_count):
    return ''.join(str(num) for num in xrange(loop_count))

def string_io(loop_count):
    file_str = StringIO()
    for num in xrange(loop_count):
        file_str.write(str(num))
    out_str = file_str.getvalue()
    return out_str

str_sum is essentially string concatenation using operator +=. str_join and str_join_lc are string concatenations performed with str.join. The str_join_lc variant uses list comprehensions. string_io is a StringIO based method (here it is the StringIO from cStringIO). Code has been adapted from the code benchmarked here. However, I decided not to use the `` operator, even though it is faster. Since it is going away from Python, I believe it is not relevant anymore. Moreover, using str in place of `` uniformly slows down all the methods.

Results

In this graph, I present results relative to Python2.6. Essentially, nowadays the faster method to create the strings has been proven to be the once advised str.join. However, I believe that difference is not great enough to change habits.

Here I present also plots for Python 2.7 and Python 2.6; essentially there is no significative difference with relative results. Python 2.7 is just faster than Python 2.6 with every considered method (and Python 2.5 is slower).

So, it appears that indeed concatenating strings with the += operator is simply faster. Out of curiosity I also tried a variant:

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

and I found no real difference with the variant with +=. Wow! The benchmark was executed on my MacPro. Python2.5 and Python2.6 are the Python variants distributed with the OS (Snow Leopard). Python 2.7 has been dowloaded from Python.org. In this other post I investigated string concatenation using pre-built list of string fragments. The results are quite different, indeed! Technorati Tags: Python, Optimization, Efficiency, String Concatenation, String Append

Anagrams and (brains vs. cpu)

In AI there is a vast category of algorithms which follow a (blind) generate and test strategy. They essentially "generate" the solutions (as a whole or step by step) and then test if the solution complies with an acceptance function. Unfortunately, this simple strategy is usually ineffective. The cost is often exponential in the size of the input and since there is no "intelligence" all solutions (even dumb ones) are explored). In AI it is customary to use smarter search techniques (A*) or to "change" the problem so that even smarter solutions are viable. An apparently unrelated example, is "finding the anagrams of a word". The trivial (and generate and test) solution is:

1. [generate]: try all the permutations of the word
2. [test]: check if the word is in the dictionary

and this strategy also shares the very same problems of the other generate and test strategies. All the permutation of a k characters word are k! = k(k-1)(k-1)...2. It is customary to see algorithms like:

def yield_anagrams(dictionary, word):
return [word for word in
(''.join(candidate) for candidate in it.permutations(word))
if word in dictionary]

which in other languages are even longer and less attractive. This approach is rather tempting for very small words. I got some interesting wordlists from here. As a good starting point I used the 12Dict list and in particular the 2of12.txt file. More info on the lists can be found in the ReadMes. In the rest of the post we are going to work with that dictionary. This graph shows the distribution of word lengths: This other graph shows how many groups of words with the same anagram we have by word length: For those preferring tabular data:

Size of the word	Number of groups
2	8
3	97
4	319
5	313
6	329
7	239
8	124
9	73
10	30
11	27
12	9
13	4
14	2

As we can see, the longest words with anagrams are 14 characters long. Even though most anagrams are very short word, our algorithm should work reasonably well with every input. The code I showed cannot. For example, let us consider the time required to compute the anagrams of words of increasing size:

scoreless	9	0,174
praetorian	10	1,828
rationalize	11	21,03
indiscreetly	12	269,0

In the first graph, we both axes are linear. If we do not believe me when I say that the growth is exponential, then look at this other graph: here the y axis is in logarithmic scale. Exponential means that if you simply change the implementation or the implementation language, things are going to blow up once again a couple of steps later. So, let us sum up: we have 41238 words. Of these words, 5644 have 12 or more characters. If we suppose that anagrams for words longer than 12 character cost exactly as anagrams for words 12 characters long, the whole process is going to take 1518236 seconds, that is to say more than 17 days. In fact, the whole process is going to be far more expensive. I have a full table (excel -- here you may want to download the file --, csv) with times estimated using the formula derived from our 4 values. Of course, this is not extremely precise, but the sheer magnitude of the computed values should make the point clear. To compute all the anagrams for all the words up to size 11 (included) it takes one day. If you want to reach size 13 it is going to take one year. However, it is still a long way to process all the words... for example, in order to discover that our dictionary words with anagrams of length 15, our program is going to run for more than 38 years. The conclusion that no words longer than 14 has an anagram (according to our dictionary) takes more than 4000000 years. Of course, I did not wait all that time to gather these results... tomorrow I am showing a smarter strategy which drops the required time from 4000000 years to 0.16 seconds.

Technorati Tags: Efficiency, Optimization, Python, Algorithms, Anagram

It was better when it was worse (and the RAM...)

I usually deride this kind of arguments. I believe that although specific issue can worsen with time (a part from the obvious ones, such as oil shortage), most things somewhat improve. This is especially true in the computer science/math/science fields. We have better algorithms and better hardware.

My (not so) cheap netbook (which I am using to write this post) would have been a super-computer for the standards of when I started using a computer. I am not only talking about the 14h of autonomy (back then I
don't think the concept of laptop was widespread)... even my crappy Atom CPU would have been a wonder.

I'm usually not very sympathetic with the ones who actually complain about the resources needed to run modern applications (Mind child, when I was your age I had only 640 KB of RAM and I did this and that! -- which in turn must have been generated by some condescending unix hacker or some punched card freak comparing populous with pong when they were young).

In fact their argument is flawed in the sense that modern programs tend to do lots of stuff that their ancestors did not (which can be useless stuff, compare Word 2007 with Word 5.1 for Mac...). Moreover, modern computers have to do lots of stuff older computer did not have to do, operating systems are more complex, we expect stuff like plug and pray to work etc etc etc. It is like complaining why stuff cost less money many years ago: e.g., in "How Blue Can You Get" B.B. King sung about buying his woman a 10 dollar dinner, meant to be a very expensive one (while she thought it was just a snack). By today standards its the price of a fast food meal.

However, there are some constants. Vim is a fast editor. It does not matter: 10 year ago it was a fast editor. Today it is a fast editor (and improved as well the functionality). On the other hand, while Java as a platform improved a lot in the last fifteen years, Java IDEs are always heavyweight. I was there when Eclipse was just a beta, just something more than a proof of concept. And it was slow. And huge. And now... well, it improved, of course... but I have a quad-core MacPro and its barely passable. I let you wonder how it is on the EEE.

By the way, I don't want to criticize too much Eclipse (Idea is much in the same condition....). Yes, I hate the fact that you have to put everything in a workspace. I hate that it is so much project based that you basically have to create projects for everything. But I have to admit that those tools are necessary to make developing in Java bearable (and productive). Moreover, I quite like the idea... small core, everything is a plugin. Reminds me of Emacs; just with less configuration hassle (which is good). Perhaps in another 15 year it will run smoothly on the machines they will have; Emacs took a lot of time to run fluidly on home-computers afterall.

O yeah, and I have to absolutely buy some RAM because otherwise those IDEs are going to make me die of old age while I try to finish my tasks.

Multi-scheme implementation of roman: performance

In order to confront the different implementations of simplify-all with multiple scheme variants, I removed all the racket specific code. I implemented by hand missing functions (foldl) or got their implementations otherwise (sort, from Freeley in the gambit lib directory). I also have some measures of different implementations all in Racket.

The resulting program still runs with racket, of course. In fact, I found rather annoying to perform the test as, for example, some implementaion provide an add1 function (so I have to comment out the definition) while some others miss that builtin (and they need my implementation).

Benchmarking code has become:

(define benchmark
  (let ([numbers (build-list 2000 add1)])
    (lambda ()
      (for-each
       (lambda (simplify-all)
         (let* ([integer->roman (integer->roman-builder simplify-all)])
           (time (map integer->roman numbers))))
    simplify-all-versions))))

We tried the code with Larceny (about good names...), Gambit, Racket and Chicken.

Time executions of the programs with different scheme implementations

Essentially on this benchmark  Chicken Scheme is the fastest. I compiled the sources with the following options:
csc -inline -block -local -unsafe -fixnum-arithmetic -lambda-lift -inline -disable-interrupts -disable-stack-overflow-checks

The differences in performance among the different programs are negligible. Moreover, with different runs, the relative differences tended to change.

Compiled racket is just a bit slower. Here we can spot that the "imperative" variant is significantly slower. Its slowness is amplified in the non compiled variant. On the other hand, with gambit, it seems that the imperative variant is the fastest. Unfortunately the time delta is so small that it could be a statistical variation: besides, differences are so small they are negligible.

Larceny is the slowest. I suppose I was unable to use the proper runtime options.

I also put in a graph the times spent in garbage collection.

Time spent garbage collecting by the different scheme implementations

Here we notice that most implementations spend comparatively the same time garbage collecting all the different programs. Larceny is the one spending less time (which is surprising, given the slow execution times). Compiled Racket comes second and Chicken comes third.

I believe I missed some compilation optimization with gambit, since to my knowledge it is one of the fastest scheme implementations.

I find the graph for Interpreted Racket the most interesting. In fact, we can see that execution times peaks   occur where garbage collection times peaks occur. I put in a graph the difference between the running time and the time spent garbage collecting. This means that it is the time spent in actual computations.

Running time without considering GC

Now that we removed time spent garbage collecting, Program A is on par with other programs with Racket Interpreted. Still, the "imperative version" (program D) remains slower. Nothing really changes for compiled Racket.