Speed up s.startswith()

[gvanrossum]

People keep discovering that, embarrassingly, checking whether a string starts with a given substring is slower with s.startswith("foo") than with s[:3] == "foo". The reason is that startswith requires a name lookup. I think we now have the machinery to special-case selected built-in method in the specializer? This would be a good candidate.

[brandtbucher]

FWIW, we already do this with list.append (CALL_LIST_APPEND). The same pattern could be followed for any other builtin methods without too much hassle.

[serhiy-storchaka]

It is in the debug build, but startswith is actually faster:

$ ./python -m timeit -s 's = "abcdef"' 's.startswith("abc")'
2000000 loops, best of 5: 189 nsec per loop
$ ./python -m timeit -s 's = "abcdef"' 's[:3] == "abc"'
1000000 loops, best of 5: 283 nsec per loop

[gvanrossum]

I think @JelleZijlstra showed that in a fully optimized build it is still slower. I repeated his experiments and got the same results:

(.venv) ~$ python3.13 -m timeit -s 'x = "......"' 'x[:3] == "..."'
10000000 loops, best of 5: 32 nsec per loop
(.venv) ~$ python3.13 -m timeit -s 'x = "......"' 'x[:3].startswith("...")'
5000000 loops, best of 5: 64.4 nsec per loop
(.venv) ~$ python3.13 -V
Python 3.13.0a5

EDIT: The second timing is wrong, see corrected timing below.

[brandtbucher]

Your second timing does both the slice and method call. :)

[gvanrossum]

Your second timing does both the slice and method call. :)

Oof. :-( But it's still slower: 40 vs. 32:

(.venv) ~$ python3.13 -m timeit -s 'x = "......"' 'x.startswith("...")'
5000000 loops, best of 5: 40.3 nsec per loop

[serhiy-storchaka]

Yes, for comparison with https://github.com/faster-cpython/ideas/issues/671#issuecomment-2030202497, on the same computer:

$ ./python -m timeit -s 's = "abcdef"' 's.startswith("abc")'
5000000 loops, best of 5: 84.3 nsec per loop
$ ./python -m timeit -s 's = "abcdef"' 's[:3] == "abc"'
5000000 loops, best of 5: 65.9 nsec per loop

startswith is 25-30% slower.

The difference is larger for 1-character prefix (because the overhead of making a 1-character substring is much smaller):

$ ./python -m timeit -s 's = "abcdef"' 's.startswith("a")'
5000000 loops, best of 5: 83.6 nsec per loop
$ ./python -m timeit -s 's = "abcdef"' 's[:1] == "a"'
5000000 loops, best of 5: 51 nsec per loop
$ ./python -m timeit -s 's = "abcdef"' 's[0] == "a"'
10000000 loops, best of 5: 22.3 nsec per loop

[eendebakpt]

There is also some overhead in the argument parsing for startswith. On my system

(env312) python -m timeit -s "s = 'abcdef'" "s.startswith('abc')"
5000000 loops, best of 5: 63.8 nsec per loop

(env312) python -m timeit -s "s = 'abcdef'" "s[:3] == 'abc'"
5000000 loops, best of 5: 47.6 nsec per loop

Adding a simple fast path for the single argument case of startswith results in

(env312) python -m timeit -s "s = 'abcdef'" "s.startswith('abc')"
5000000 loops, best of 5: 42.3 nsec per loop

The fast path I implemented is https://github.com/python/cpython/compare/main...eendebakpt:cpython:startswith. That might not be the best approach, but this was just a quick test. The asciilib_parse_args_finds could perhaps also be improved, for example eliminate the copy at https://github.com/python/cpython/blob/c741ad3537193c63fe697a8f0316aecd45eeb9ba/Objects/stringlib/find.h#L97

[markshannon]

The reason is that startswith requires a name lookup.

This is not true. It is the call that is slow, not the attribute lookup.

The attribute lookup gets specialized to LOAD_ATTR_METHOD_NO_DICT which is as fast as an attribute lookup can be (in tier 1).

The call is slow for two reasons.

1. str.startwith is a METH_VARARGS function. It should be METH_FASTCALL
2. As @eendebakpt says, there is no fast path for the the common case.

def foo(s):
   for _ in range(1000):
       s.startswith("foo")

>>> dis.dis(foo, adaptive=True)
  1           RESUME_CHECK             0

  2           LOAD_GLOBAL              1 (range + NULL)
              LOAD_CONST               1 (1000)
              CALL                     1
              GET_ITER
      L1:     FOR_ITER_RANGE          20 (to L2)
              STORE_FAST               1 (_)

  3           LOAD_FAST                0 (s)
              LOAD_ATTR_METHOD_NO_DICT 3 (startswith + NULL|self)
              LOAD_CONST               2 ('foo')
              CALL                     1
              POP_TOP
              JUMP_BACKWARD           22 (to L1)

  2   L2:     END_FOR
              POP_TOP
              RETURN_CONST             0 (None)

[markshannon]

We should probably replace all METH_VARARGS with METH_FASTCALL, in the long run.

In the short term, we should change the methods on builtin objects. git grep METH_VARARGS | grep "Objects/" gives me 49 results, so it wouldn't be that much work.

[erlend-aasland]

We should probably replace all METH_VARARGS with METH_FASTCALL, in the long run.

FYI: With python/cpython#107984, Argument Clinic got the ability to deprecate keyword use of parameters. Oh, they're already positional-only. Sorry for the noise.

[erlend-aasland]

METH_FASTCALL gives a significant speedup[^1]:

$ ./python.exe -m timeit -s "s = 'abcdef'" "s[:3] == 'abc'"
2000000 loops, best of 5: 177 nsec per loop
$ ./python.exe -m timeit -s "s = 'abcdef'" "s.startswith('abc')"
5000000 loops, best of 5: 58.3 nsec per loop

[^1]: debug build

[gvanrossum]

@eendebakpt Can you turn that into a PR then?

[eendebakpt]

@eendebakpt Can you turn that into a PR then?

Yes, I will pick that up

@erlend-aasland Did you use argument clinic in testing the METH_FASTCALL?

[erlend-aasland]

@eendebakpt: yes. See my draft PR.

[erlend-aasland]

Resolved by:

• python/cpython#117495
• python/cpython#117466

Argument Clinic (and METH_FASTCALL) FTW.

[erlend-aasland]

@eendebakpt is also working on further optimisations in stringlib 🚀

[eendebakpt]

With the recent conversion to vectorcall by Erland there is not much to gain in the implementation of startswith (and endswith). The computation time for x.startswith('a') can be split into the following components (all numbers are rough estimates, details in the section below)

• Attribute lookup of startswith on x: 2.7 ns
• Python method call overhead: 21.8 ns
• Time for adding the single argument a: 1.5 ns
• Argument parsing: 0.6 ns
• Calculations with the start and end parameters, type checking: 2.6 ns
• Actual string comparison: 8.4 ns
• Total: 37.6 ns

The implementation of the actual string comparison can be improved a bit, for the single character case a few ns. See #117782

Our baseline is `x.startswith('a')` which takes about 37.6 ns: ``` x.startswith('a'): Mean +- std dev: 37.6 ns +- 0.1 ns ``` That time can be roughly divided into: * 2.7 ns: lookup of `startswith` on the string `x` ``` x_startswith('a'): Mean +- std dev: 34.9 ns +- 0.2 ns ``` * 21.8 ns: python method call overhead. Determined by adding ``` if (nargs==0) return Py_None; ``` at the start of `unicode_startswith` and benchmarking `x.startswith()` ``` x.startswith(): Mean +- std dev: 24.5 ns +- 0.4 ns ``` * 1.5 ns: additional time required for adding a single argument `a`. Determined by adding ``` if (args[0]==Py_None) return Py_None; ``` at the start of `unicode_startswith` and benchmarking `x.startswith(None)` ``` x.startswith(None): Mean +- std dev: 26.0 ns +- 0.3 ns ``` * 0.6 ns = 26.6 - 26.0 ns. The time for argument parsing for the single argument case is (measured by adding to the start of `unicode_startswith_impl` ``` if (subobj == Py_None) { // measure minimum time for call with argument processing return Py_None; } ``` and comparing to the previous. ``` x.startswith(None): Mean +- std dev: 26.6 ns +- 0.7 ns ``` * The implementation `unicode_startswith_impl` checks the type of the first argument and then calls `tailmatch` which performs a few simple checks with the (optional) `start` and `end` arguments of `startswith`. In the case of an empty substring no work needs to be done ``` x.startswith(''): Mean +- std dev: 29.2 ns +- 0.2 ns ``` * Comparing x.startswith('a') with x.startswith('') shows about 8.4 ns is used for the actual string comparison. * Adding additional arguments to `startswith` is rather expensive. This is mainly due to adding the arguments to the call, and partly due to the parameter processing with calls `_PyEval_SliceIndex`. ``` x.startswith('a', 0, 10): Mean +- std dev: 54.3 ns +- 0.3 ns ```

Performance of x.startswith('a', 0, 10) is about 54.3 ns, which seems high. A large part of that time is in the preparation of the three arguments. A small part is in the argument parsing, in particular the calls to _PyEval_SliceIndex. That method can be improved, since in the common path (e.g. indices of type int) we can avoid an incref/decref and some type checks. With this https://github.com/python/cpython/compare/main...eendebakpt:cpython:pynumber performance improves

x.startswith('a', 0, 10): Mean +- std dev: [main] 54.4 ns +- 1.1 ns -> [p] 52.3 ns +- 0.3 ns: 1.04x faster

The performance gain is not very large, but PyNumber_AsSsize_t is used in many places so things might be worthwhile. The implementation is short and localized, but not very pretty as it adds an ad-hoc variable do_decref. I am not yet sure how to implement this better, so feedback is welcome.