Repository navigation
gh-117431: Improve performance of startswith and endswith - #117782
eendebakpt wants to merge 17 commits into
Conversation
Sorry, something went wrong.
erlend-aasland
left a comment
There was a problem hiding this comment.
Quick-and-dirty initial review.
Sorry, something went wrong.
Co-authored-by: Erlend E. Aasland <erlend.aasland@protonmail.com>
|
Do you still see the "two-character fail head" slowdown? |
Sorry, something went wrong.
…e-117431.ZxdAFN.rst Co-authored-by: Erlend E. Aasland <erlend.aasland@protonmail.com>
Yes, and this is to be expected. For the two-character case we can either i) Check the first character and then the last (e.g. the second character). This is the current implementation in main The result is that main is faster for "abc".startswith("xb"), but this PR is faster for "abc".startswith("ax"). From an application point of view I am not sure whether one case is more important than the other. In the PR we trade performance for these two cases, but gain performance for several other (e.g. matching single character, matching multi character). I have put some though into whether we could keep this PR more conservative (e.g. no cases with performance loss, but several cases with performance gain). The best I can create so far is main...eendebakpt:tailmatch_v3. There are some more branches and the memcmp does a bit more work than required, but just like this PR it should improve matching the single-character and two-character case. |
Sorry, something went wrong.
|
This PR is stale because it has been open for 30 days with no activity. |
Sorry, something went wrong.
Improve performance of startswith and endswith by eliminating double work in tailmatch.
Benchmark results:
single-character match: x.startswith('a'): Mean +- std dev: [main_startswith] 80.6 ns +- 0.7 ns -> [v2_startswith] 69.8 ns +- 0.8 ns: 1.15x faster single-character fail: x.startswith('q'): Mean +- std dev: [main_startswith] 67.8 ns +- 0.6 ns -> [v2_startswith] 68.4 ns +- 0.7 ns: 1.01x slower two-character match: x.startswith('ab'): Mean +- std dev: [main_startswith] 81.3 ns +- 2.1 ns -> [v2_startswith] 75.9 ns +- 0.6 ns: 1.07x faster two-character fail head: x.startswith('qb'): Mean +- std dev: [main_startswith] 68.0 ns +- 1.1 ns -> [v2_startswith] 76.0 ns +- 0.9 ns: 1.12x slower two-character fail tail: x.startswith('aq'): Mean +- std dev: [main_startswith] 73.0 ns +- 3.3 ns -> [v2_startswith] 68.5 ns +- 0.9 ns: 1.07x faster multi-character match: x.startswith('abcdefghijkl'): Mean +- std dev: [main_startswith] 84.9 ns +- 1.1 ns -> [v2_startswith] 78.7 ns +- 2.3 ns: 1.08x faster multi-character fail midle: x.startswith('abcdef_hijkl'): Mean +- std dev: [main_startswith] 85.3 ns +- 2.0 ns -> [v2_startswith] 78.6 ns +- 0.8 ns: 1.09x faster Benchmark hidden because not significant (3): empty: x.startswith(''), multi-character different kind match: xu.startswith('abcdefghijkl'), multi-character different kind fail: xu.startswith('abcdef_hijkl') Geometric mean: 1.03x fasterimport pyperf runner = pyperf.Runner() setup=""" x = 'abcdefghijklmnop' y = 'abcdefghijklmnop_bbbbbbbbbbbbbbbbbb' xu = x + '\u1234' yu = y + '\u1234' l = 'a' * 1000 + 'b' x_startswith = x.startswith """ # Tested with ./python sw.py --rigorous -o main_startswith.json if 1: runner.timeit(name="empty: x.startswith('')", stmt="x.startswith(''); y.startswith('')", setup=setup) runner.timeit(name="single-character match: x.startswith('a')", stmt="x.startswith('a'); y.startswith('a')", setup=setup) runner.timeit(name="single-character fail: x.startswith('q')", stmt="x.startswith('q'); y.startswith('q')", setup=setup) runner.timeit(name="two-character match: x.startswith('ab')", stmt="x.startswith('ab'); y.startswith('ab')", setup=setup) runner.timeit(name="two-character fail head: x.startswith('qb')", stmt="x.startswith('qb'); y.startswith('qb')", setup=setup) runner.timeit(name="two-character fail tail: x.startswith('aq')", stmt="x.startswith('aq'); y.startswith('aq')", setup=setup) runner.timeit(name="multi-character match: x.startswith('abcdefghijkl')", stmt="x.startswith('abcdefghijkl'); y.startswith('abcdefghijkl')", setup=setup) runner.timeit(name="multi-character fail midle: x.startswith('abcdef_hijkl')", stmt="x.startswith('abcdef_hijkl'); y.startswith('abcdef_hijkl')", setup=setup) runner.timeit(name="multi-character different kind match: xu.startswith('abcdefghijkl')", stmt="xu.startswith('abcdefghijkl'); yu.startswith('abcdefghijkl')", setup=setup) runner.timeit(name="multi-character different kind fail: xu.startswith('abcdef_hijkl')", stmt="xu.startswith('abcdefghijkl'); yu.startswith('abcdefghijkl')", setup=setup)