Why startswith is slower than slicing

Question

Why is the startwith implementation slower than slicing?

 In [1]: x = 'foobar' In [2]: y = 'foo' In [3]: %timeit x.startswith(y) 1000000 loops, best of 3: 321 ns per loop In [4]: %timeit x[:3] == y 10000000 loops, best of 3: 164 ns per loop 

Surprisingly, even including length calculation, slicing still looks much faster:

 In [5]: %timeit x[:len(y)] == y 1000000 loops, best of 3: 251 ns per loop 

Note: the first part of this behavior is noted in Python for data analysis (chapter 3), but no explanation is offered for this.

.

If useful: here is the C code for startswith ; and here is the output of dis.dis :

 In [6]: import dis In [7]: dis_it = lambda x: dis.dis(compile(x, '<none>', 'eval')) In [8]: dis_it('x[:3]==y') 1 0 LOAD_NAME 0 (x) 3 LOAD_CONST 0 (3) 6 SLICE+2 7 LOAD_NAME 1 (y) 10 COMPARE_OP 2 (==) 13 RETURN_VALUE In [9]: dis_it('x.startswith(y)') 1 0 LOAD_NAME 0 (x) 3 LOAD_ATTR 1 (startswith) 6 LOAD_NAME 2 (y) 9 CALL_FUNCTION 1 12 RETURN_VALUE 

Answer 1

Some performance difference can be explained by considering the time it takes for the operator . To complete your task:

 >>> x = 'foobar' >>> y = 'foo' >>> sw = x.startswith >>> %timeit x.startswith(y) 1000000 loops, best of 3: 316 ns per loop >>> %timeit sw(y) 1000000 loops, best of 3: 267 ns per loop >>> %timeit x[:3] == y 10000000 loops, best of 3: 151 ns per loop 

Another part of the difference can be explained by the fact that startswith is a function, and even calls to the no-op function take a little time:

 >>> def f(): ... pass ... >>> %timeit f() 10000000 loops, best of 3: 105 ns per loop 

This does not fully explain the difference, since the version using slicing and len calls the function and is still faster (compare with sw(y) above - 267 ns):

 >>> %timeit x[:len(y)] == y 1000000 loops, best of 3: 213 ns per loop 

My only suggestion is that Python may be optimizing search time for inline functions, or that len calls are highly optimized (which is probably true). Perhaps it will be possible to check with the user-defined function len . Or perhaps this is where the differences noted by LastCoder are revealed . Notice also larsmans , which indicates that startswith is actually faster for longer lines. The whole line of reasoning above applies only to those cases where the overhead costs that I am talking about really matter.

Answer 2

The comparison is not fair, since you only measure the case where startswith returns True .

 >>> x = 'foobar' >>> y = 'fool' >>> %timeit x.startswith(y) 1000000 loops, best of 3: 221 ns per loop >>> %timeit x[:3] == y # note: length mismatch 10000000 loops, best of 3: 122 ns per loop >>> %timeit x[:4] == y 10000000 loops, best of 3: 158 ns per loop >>> %timeit x[:len(y)] == y 1000000 loops, best of 3: 210 ns per loop >>> sw = x.startswith >>> %timeit sw(y) 10000000 loops, best of 3: 176 ns per loop 

Also, for much longer lines, startswith is much faster:

 >>> import random >>> import string >>> x = '%030x' % random.randrange(256**10000) >>> len(x) 20000 >>> y = r[:4000] >>> %timeit x.startswith(y) 1000000 loops, best of 3: 211 ns per loop >>> %timeit x[:len(y)] == y 1000000 loops, best of 3: 469 ns per loop >>> sw = x.startswith >>> %timeit sw(y) 10000000 loops, best of 3: 168 ns per loop 

This is still true if there is no match.

 # change last character of y >>> y = y[:-1] + chr((ord(y[-1]) + 1) % 256) >>> %timeit x.startswith(y) 1000000 loops, best of 3: 210 ns per loop >>> %timeit x[:len(y)] == y 1000000 loops, best of 3: 470 ns per loop >>> %timeit sw(y) 10000000 loops, best of 3: 168 ns per loop # change first character of y >>> y = chr((ord(y[0]) + 1) % 256) + y[1:] >>> %timeit x.startswith(y) 1000000 loops, best of 3: 210 ns per loop >>> %timeit x[:len(y)] == y 1000000 loops, best of 3: 442 ns per loop >>> %timeit sw(y) 10000000 loops, best of 3: 168 ns per loop 

So, startswith is probably slower for short lines because it is optimized for long lines.

(Trick to get random strings taken from this answer .)

Answer 3

startswith harder than slicing ...

 2924 result = _string_tailmatch(self, 2925 PyTuple_GET_ITEM(subobj, i), 2926 start, end, -1); 

This is not a simple character comparison cycle for the needle at the beginning of the haystack that occurs. We look at the for loop, which iterates through vector / tuple (subobj) and calls another function ( _string_tailmatch ) on it. Multiple function calls have overheads regarding the stack, checking argument reasoning, etc ...

startswith is a library function, while slicing seems to be built into the language.

 2919 if (!stringlib_parse_args_finds("startswith", args, &subobj, &start, &end)) 2920 return NULL; 

Answer 4

To quote the docs by startswith , you might think more:

str.startswith(prefix[, start[, end]])

Return True if the string begins with a prefix, otherwise return False . the prefix can also be a tuple for the prefixes to look for. With the optional start, a test line starting at this position. With an extra end, stop comparing the line at that position.

Answer 5

Function calls are quite expensive. I do not know, however, if this is also the case for built-in functions written in C.

Remember, however, that slicing can also include calling a function, depending on the object being used.