[New-bugs-announce] [issue23573] Avoid redundant allocations in str.find and like

[Serhiy Storchaka]

New submission from Serhiy Storchaka:

Currently str.find() and similar methods can make a copy of self or searched string if they have different kinds. In some cases this is redundant because the result can be known before trying to search. Longer string can't be found in shorter string and wider string can't be found in narrower string. Proposed patch avoid creating temporary widened copies in such corner cases. It also adds special cases for searching 1-character strings.

Some sample microbenchmark results:

$ ./python -m timeit -s "a = 'x'; b = 'x\U00012345'" -- "b.find(a)"
Unpatched: 1000000 loops, best of 3: 1.92 usec per loop
Patched:   1000000 loops, best of 3: 1.03 usec per loop

$ ./python -m timeit -s "a = 'x'; b = 'x\U00012345'" -- "a in b"
Unpatched: 1000000 loops, best of 3: 0.543 usec per loop
Patched:   1000000 loops, best of 3: 0.25 usec per loop

$ ./python -m timeit -s "a = '\U00012345'; b = 'x'*1000" -- "b.find(a)"
Unpatched: 100000 loops, best of 3: 4.58 usec per loop
Patched:   1000000 loops, best of 3: 0.969 usec per loop

$ ./python -m timeit -s "a = 'x'*1000; b = '\U00012345'" -- "b.find(a)"
Unpatched: 100000 loops, best of 3: 3.77 usec per loop
Patched:   1000000 loops, best of 3: 0.97 usec per loop

$ ./python -m timeit -s "a = 'x'*1000; b = '\U00012345'" -- "a in b"
Unpatched: 100000 loops, best of 3: 2.4 usec per loop
Patched:   1000000 loops, best of 3: 0.225 usec per loop

----------
components: Interpreter Core
files: str_find_faster.patch
keywords: patch
messages: 237137
nosy: serhiy.storchaka
priority: normal
severity: normal
stage: patch review
status: open
title: Avoid redundant allocations in str.find and like
type: performance
versions: Python 3.5
Added file: http://bugs.python.org/file38315/str_find_faster.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue23573>
_______________________________________