str.count is slow

[Ben Cartwright]

chrisperkins99 at 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