New subject: str.count is slow

27 Feb 2006

      ...
From comp.lang.python:
chrisperkins99@gmail.com wrote:
It seems to me that str.count is awfully slow.  Is there some reason
for this?
Evidence:
######## str.count time test ########
import string
import time
import array
s = string.printable * int(1e5) # 10**7 character string
a = array.array('c', s)
u = unicode(s)
RIGHT_ANSWER = s.count('a')
def main():
    print 'str:    ', time_call(s.count, 'a')
    print 'array:  ', time_call(a.count, 'a')
    print 'unicode:', time_call(u.count, 'a')
def time_call(f, *a):
    start = time.clock()
    assert RIGHT_ANSWER == f(*a)
    return time.clock()-start
if __name__ == '__main__':
    main()
###### end ########
On my machine, the output is:
str:     0.29365715475
array:   0.448095498171
unicode: 0.0243757237303
If a unicode object can count characters so fast, why should an str
object be ten times slower?  Just curious, really - it's still fast
enough for me (so far).
This is with Python 2.4.1 on WinXP.
Chris Perkins
Your evidence points to some unoptimized code in the underlying C
implementation of Python.  As such, this should probably go to the
python-dev list (http://mail.python.org/mailman/listinfo/python-dev).

The problem is that the C library function memcmp is slow, and
str.count calls it frequently.  See lines 2165+ in stringobject.c
(inside function string_count):

        r = 0;
        while (i < m) {
                if (!memcmp(s+i, sub, n)) {
                        r++;
                        i += n;
                } else {
                        i++;
                }
        }

This could be optimized as:

        r = 0;
        while (i < m) {
                if (s[i] == *sub && !memcmp(s+i, sub, n)) {
                        r++;
                        i += n;
                } else {
                        i++;
                }
        }

This tactic typically avoids most (sometimes all) of the calls to
memcmp.  Other string search functions, including unicode.count,
unicode.index, and str.index, use this tactic, which is why you see
unicode.count performing better than str.count.

The above might be optimized further for cases such as yours, where a
single character appears many times in the string:

        r = 0;
        if (n == 1) {
                /* optimize for a single character */
                while (i < m) {
                        if (s[i] == *sub)
                                r++;
                        i++;
                }
        } else {
                while (i < m) {
                        if (s[i] == *sub && !memcmp(s+i, sub, n)) {
                                r++;
                                i += n;
                        } else {
                                i++;
                        }
                }
        }

Note that there might be some subtle reason why neither of these
optimizations are done that I'm unaware of... in which case a comment
in the C source would help. :-)

--Ben

Re: [Python-Dev] str.count is slow

Ben Cartwright

Fredrik Lundh

martin＠v.loewis.de

Fredrik Lundh

Greg Ewing

Fredrik Lundh

Greg Ewing

Guido van Rossum

Fredrik Lundh

James Y Knight

Bill Janssen

Greg Ewing

Greg Ewing

Ulrich Berning

Wolfgang Langner

Wolfgang Langner

Barry Warsaw

martin＠v.loewis.de

Walter Dörwald

Michael Urman

martin＠v.loewis.de

Fredrik Lundh

Stephen J. Turnbull

Greg Ewing

martin＠v.loewis.de

martin＠v.loewis.de

martin＠v.loewis.de

Stephen J. Turnbull

Anthony Baxter

Stephen J. Turnbull

Armin Rigo

tags

participants (16)