classification
Title: Avoid redundant allocations in str.find and like
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.6, Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: serhiy.storchaka Nosy List: christian.heimes, python-dev, serhiy.storchaka, vstinner
Priority: normal Keywords: patch

Created on 2015-03-03 13:53 by serhiy.storchaka, last changed 2015-07-21 05:26 by serhiy.storchaka. This issue is now closed.

Files
File name Uploaded Description Edit
str_find_faster.patch serhiy.storchaka, 2015-03-03 13:53 review
issue23573_bytes_rfind_memrchr.patch serhiy.storchaka, 2015-07-18 14:38 review
Messages (10)
msg237137 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-03-03 13:53
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
msg239171 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-03-24 19:58
New changeset 6db9d7c1be29 by Serhiy Storchaka in branch 'default':
Issue #23573: Increased performance of string search operations (str.find,
https://hg.python.org/cpython/rev/6db9d7c1be29
msg239187 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-03-24 22:01
Looks as this patch makes buildbots crash.
msg239209 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2015-03-25 01:47
> Looks as this patch makes buildbots crash.

Yep. It took me some minutes to find that the crash was caused by this issue :-p

http://buildbot.python.org/all/builders/AMD64%20Windows7%20SP1%203.x/builds/5930/steps/test/logs/stdio

...
[117/393/1] test_bigmem
Assertion failed: 0, file c:\buildbot.python.org\3.x.kloth-win64\build\objects\stringlib/fastsearch.h, line 76
Fatal Python error: Aborted

Current thread 0x000010ec (most recent call first):
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\test\test_bigmem.py", line 294 in test_rfind
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\test\support\__init__.py", line 1641 in wrapper
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\unittest\case.py", line 577 in run
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\unittest\case.py", line 625 in __call__
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\unittest\suite.py", line 122 in run
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\unittest\suite.py", line 84 in __call__
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\unittest\suite.py", line 122 in run
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\unittest\suite.py", line 84 in __call__
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\unittest\runner.py", line 176 in run
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\test\support\__init__.py", line 1773 in _run_suite
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\test\support\__init__.py", line 1807 in run_unittest
  File "C:\buildbot.python.org\3.x.kloth-win64\build\lib\test\test_bigmem.py", line 1252 in test_main
...
msg239211 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2015-03-25 01:58
The problem is that Windows has no memrchr() function, and so fastsearch_memchr_1char() only supports FAST_SEARCH on Windows.
msg239212 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-03-25 02:17
New changeset 3ac58de829ef by Victor Stinner in branch 'default':
Issue #23573: Fix bytes.rfind() and bytearray.rfind() on Windows
https://hg.python.org/cpython/rev/3ac58de829ef
msg239213 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2015-03-25 02:19
It looks like fastsearch_memchr_1char() manipulate pointers for memory alignment. It's not necessary when looking for ASCII or Latin1 characters or for bytes.

I propose to add a new fastsearch_memchr_1byte() function which would be used by bytes and bytearray, but also by str for ASCII and Latin1 strings.

Are you interested to implement this idea Serhiy?

For Windows without memrchr(), the code can be a simple loop.
msg239220 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-03-25 06:21
Many thanks Victor for fixing crashes. Unfortunately I couldn't reproduce a 
crash on my computers, perhaps it is was 64-bit only.

Yes, I'll look how the code can be optimized.
msg246901 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-07-18 14:38
Here is a patch that restores optimization of bytes.rfind() and bytearray.rfind() with 1-byte argument on Linux (it also reverts bc1a178b3bc8).
msg247002 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-07-20 19:59
New changeset 311a4d28631b by Serhiy Storchaka in branch '3.5':
Issue #23573: Restored optimization of bytes.rfind() and bytearray.rfind()
https://hg.python.org/cpython/rev/311a4d28631b

New changeset c06410c68217 by Serhiy Storchaka in branch 'default':
Issue #23573: Restored optimization of bytes.rfind() and bytearray.rfind()
https://hg.python.org/cpython/rev/c06410c68217
History
Date User Action Args
2015-07-21 05:26:24serhiy.storchakasetstatus: open -> closed
stage: patch review -> resolved
resolution: fixed
versions: + Python 3.6
2015-07-20 19:59:11python-devsetmessages: + msg247002
2015-07-18 14:38:46serhiy.storchakasetfiles: + issue23573_bytes_rfind_memrchr.patch

nosy: + christian.heimes
messages: + msg246901

resolution: fixed -> (no value)
stage: resolved -> patch review
2015-03-25 06:21:57serhiy.storchakasetmessages: + msg239220
2015-03-25 02:19:38vstinnersetmessages: + msg239213
2015-03-25 02:17:15python-devsetmessages: + msg239212
2015-03-25 01:58:00vstinnersetmessages: + msg239211
2015-03-25 01:47:05vstinnersetnosy: + vstinner
messages: + msg239209
2015-03-24 22:01:29serhiy.storchakasetstatus: closed -> open

messages: + msg239187
2015-03-24 19:59:49serhiy.storchakasetstatus: open -> closed
assignee: serhiy.storchaka
resolution: fixed
stage: patch review -> resolved
2015-03-24 19:58:17python-devsetnosy: + python-dev
messages: + msg239171
2015-03-03 13:53:30serhiy.storchakacreate