why python dict update insanely slow?

Question

I had a python program which reads lines from files and puts them into dict, for simple, it looks like:

data = {'file_name':''}
with open('file_name') as in_fd:
    for line in in_fd:
        data['file_name'] += line

I found it took hours to finish.

And then, I did a bit change to the program:

data = {'file_name':[]}
with open('file_name') as in_fd:
    for line in in_fd:
        data['file_name'].append(line)
    data['file_name'] = ''.join(data['file_name'])

It finished in seconds.

I thought it's += makes the program slow, but it seems not. Please take a look at the result of the following test.

I knew we could use list append and join to improve performance when concat strings. But I never thought such a performance gap between append and join and add and assign.

So I decided to do some more tests, and finally found it's the dict update operation makes the program insanely slow. Here is a scripts:

import time
LOOPS = 10000
WORD = 'ABC'*100

s1=time.time()
buf1 = []
for i in xrange(LOOPS):
    buf1.append(WORD)
ss = ''.join(buf1)

s2=time.time()
buf2 = ''
for i in xrange(LOOPS):
    buf2 += WORD

s3=time.time()
buf3 = {'1':''}
for i in xrange(LOOPS):
    buf3['1'] += WORD

s4=time.time()
buf4 = {'1':[]}
for i in xrange(LOOPS):
    buf4['1'].append(WORD)
buf4['1'] = ''.join(buf4['1'])

s5=time.time()
print s2-s1, s3-s2, s4-s3, s5-s4

In my laptop(mac pro 2013 mid, OS X 10.9.5, cpython 2.7.10), it's output is:

0.00299620628357 0.00415587425232 3.49465799332 0.00231599807739

Inspired by juanpa.arrivillaga's comments, I did a bit change to the second loop:

trivial_reference = []
buf2 = ''
for i in xrange(LOOPS):
    buf2 += WORD
    trivial_reference.append(buf2)  # add a trivial reference to avoid optimization

After the change, now the second loops takes 19 seconds to complete. So it seems just a optimization problem just as juanpa.arrivillaga said.

Answer 1

+= performs really bad when building large strings but can be efficient in one-case in CPython.^{mentioned below}

For sure-shot faster string concatenation use str.join().

---

From String Concatenation section under Python Performance Tips:

Avoid this:

s = ""
for substring in list:
    s += substring

Use s = "".join(list) instead. The former is a very common and catastrophic mistake when building large strings.

---

Why s += x is faster than s['1'] += x or s[0] += x?

From Note 6:

CPython implementation detail: If s and t are both strings, some Python implementations such as CPython can usually perform an in-place optimization for assignments of the form s = s + t or s += t. When applicable, this optimization makes quadratic run-time much less likely. This optimization is both version and implementation dependent. For performance sensitive code, it is preferable to use the str.join() method which assures consistent linear concatenation performance across versions and implementations.

The optimization in case of CPython is that if a string has only one reference then we can resize it in-place.

/* Note that we don't have to modify *unicode for unshared Unicode objects, since we can modify them in-place. */

Now latter two are not simple in-place additions. In fact these are not in-place additions at all.

s[0] += x

is equivalent to:

temp = s[0]  # Extra reference. `S[0]` and `temp` both point to same string now.
temp += x
s[0] = temp

Example:

>>> lst = [1, 2, 3]
>>> def func():
...     lst[0] = 90
...     return 100
...
>>> lst[0] += func()
>>> print lst
[101, 2, 3]  # Not [190, 2, 3]

---

But in general never use s += x for concatenating string, always use str.join on a collection of strings.

---

Timings

LOOPS = 1000
WORD = 'ABC'*100


def list_append():
    buf1 = [WORD for _ in xrange(LOOPS)]
    return ''.join(buf1)


def str_concat():
    buf2 = ''
    for i in xrange(LOOPS):
        buf2 += WORD


def dict_val_concat():
    buf3 = {'1': ''}
    for i in xrange(LOOPS):
        buf3['1'] += WORD
    return buf3['1']


def list_val_concat():
    buf4 = ['']
    for i in xrange(LOOPS):
        buf4[0] += WORD
    return buf4[0]


def val_pop_concat():
    buf5 = ['']
    for i in xrange(LOOPS):
        val = buf5.pop()
        val += WORD
        buf5.append(val)
    return buf5[0]


def val_assign_concat():
    buf6 = ['']
    for i in xrange(LOOPS):
        val = buf6[0]
        val += WORD
        buf6[0] = val
    return buf6[0]


>>> %timeit list_append()
1000 loops, best of 3: 1.31 ms per loop
>>> %timeit str_concat()
100 loops, best of 3: 3.09 ms per loop
>>> %run so.py
>>> %timeit list_append()
10000 loops, best of 3: 71.2 us per loop
>>> %timeit str_concat()
1000 loops, best of 3: 276 us per loop
>>> %timeit dict_val_concat()
100 loops, best of 3: 9.66 ms per loop
>>> %timeit list_val_concat()
100 loops, best of 3: 9.64 ms per loop
>>> %timeit val_pop_concat()
1000 loops, best of 3: 556 us per loop
>>> %timeit val_assign_concat()
100 loops, best of 3: 9.31 ms per loop

val_pop_concat is fast here because by using pop() we are dropping reference from the list to that string and now CPython can resize it in-place(guessed correctly by @niemmi in comments).