Python performance : why Counter(r) is NOT 100 times faster than {c:r.count(c) for c in set(r)}?

Question

Let r be a string,we want to count the number of each character in r. If we reason quickly:

Counter(r)

is about 100 times faster than

{c:r.count(c) for c in set(r)}

Indeed: in a normal text, there is about 100 distinct characters (cap/uncap/punctuation/numbers...) hence .count will run 100 times over all the string r instead of Counter which will run only one time.

However, timing does not agree with the above reasoning (r is the content of all the "Lord of the Ring" books):

In [71]: %timeit d = collections.Counter(r)
10 loops, best of 3: 98.8 ms per loop

In [72]: %timeit d = {c:r.count(c) for c in set(r)}
10 loops, best of 3: 114 ms per loop

In [73]: len(r)
Out[73]: 972550

Even if we increase the size of the string, the ratio is the same

In [74]: r = r*100

In [79]: %time d = collections.Counter(r)
CPU times: user 9.9 s, sys: 12 ms, total: 9.91 s
Wall time: 9.93 s

In [81]: %time d = {c:r.count(c) for c in set(r)}
CPU times: user 11.5 s, sys: 0 ns, total: 11.5 s
Wall time: 11.6 s

I've read the source of .count, it does not do any caching/operation (unless I did not look at the good implementation function): https://hg.python.org/cpython-fullhistory/file/tip/Objects/stringlib/fastsearch.h . How do you explain this fact ?

EDIT : my config : Python 3.4.3 (default, Mar 26 2015, 22:07:01) on Lubuntu 15.04.

Interesting question. Once again I am astonished at just how well Python does with tasks which I intuitively would have thought it would be slow at (given that it is interpreted rather than compiled). Maybe you can test Unicode strings which have a great deal more than 100 distinct characters and see if you see more of a difference. — John Coleman, Feb 11 '16 at 22:38
http://stackoverflow.com/questions/2522152/python-is-a-dictionary-slow-to-find-frequency-of-each-character http://stackoverflow.com/questions/14186533/why-is-collections-counter-much-slower-than-count — Padraic Cunningham, Feb 11 '16 at 22:42

score 3 · Answer 1 · answered Feb 11 '16 at 22:45

While Counter is written in Python, string.count() is written in C. It is not unusual for there to be 100x differences in performance between typical Python and C implementations. You can look at the Counter source code here:

def update(*args, **kwds):
    ...
    for elem in iterable:
        self[elem] = self_get(elem, 0) + 1

You can see that for every character in the string, the Counter will call at least two different functions written in Python (self.__setitem__ and self.get) and probably allocate an integer on the heap.

By comparison, look at the string.count source code, which calls stringlib_count, which calls fastsearch:

for (i = 0; i < n; i++) {
    if (s[i] == p[0]) {
        count++;
        if (count == maxcount)
            return maxcount;
    }
}
return count;

The main loop has no allocations, no function calls, just a quick iteration across a region of memory.

This is Python 3.4, so `Counter.update` actually does have a fast path written in C, but it still needs to go through a bunch of dynamic language overhead that `string.count` gets to skip. — user2357112, Feb 12 '16 at 01:07

Python performance : why Counter(r) is NOT 100 times faster than {c:r.count(c) for c in set(r)}?

1 Answers1