Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Avoid redundant allocations in str.find and like #67761

Closed
serhiy-storchaka opened this issue Mar 3, 2015 · 10 comments
Closed

Avoid redundant allocations in str.find and like #67761

serhiy-storchaka opened this issue Mar 3, 2015 · 10 comments
Assignees
Labels
interpreter-core Interpreter core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@serhiy-storchaka
Copy link
Member

serhiy-storchaka commented Mar 3, 2015

BPO 23573
Nosy @vstinner, @tiran, @serhiy-storchaka
Files
  • str_find_faster.patch
  • issue23573_bytes_rfind_memrchr.patch
  • Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = 'https://github.com/serhiy-storchaka'
    closed_at = <Date 2015-07-21.05:26:24.382>
    created_at = <Date 2015-03-03.13:53:30.918>
    labels = ['interpreter-core', 'performance']
    title = 'Avoid redundant allocations in str.find and like'
    updated_at = <Date 2015-07-21.05:26:24.380>
    user = 'https://github.com/serhiy-storchaka'

    bugs.python.org fields:

    activity = <Date 2015-07-21.05:26:24.380>
    actor = 'serhiy.storchaka'
    assignee = 'serhiy.storchaka'
    closed = True
    closed_date = <Date 2015-07-21.05:26:24.382>
    closer = 'serhiy.storchaka'
    components = ['Interpreter Core']
    creation = <Date 2015-03-03.13:53:30.918>
    creator = 'serhiy.storchaka'
    dependencies = []
    files = ['38315', '39944']
    hgrepos = []
    issue_num = 23573
    keywords = ['patch']
    message_count = 10.0
    messages = ['237137', '239171', '239187', '239209', '239211', '239212', '239213', '239220', '246901', '247002']
    nosy_count = 4.0
    nosy_names = ['vstinner', 'christian.heimes', 'python-dev', 'serhiy.storchaka']
    pr_nums = []
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'performance'
    url = 'https://bugs.python.org/issue23573'
    versions = ['Python 3.5', 'Python 3.6']

    @serhiy-storchaka
    Copy link
    Member Author

    serhiy-storchaka commented Mar 3, 2015

    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

    @serhiy-storchaka serhiy-storchaka added interpreter-core Interpreter core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Mar 3, 2015
    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Mar 24, 2015

    New changeset 6db9d7c1be29 by Serhiy Storchaka in branch 'default':
    Issue bpo-23573: Increased performance of string search operations (str.find,
    https://hg.python.org/cpython/rev/6db9d7c1be29

    @serhiy-storchaka
    Copy link
    Member Author

    serhiy-storchaka commented Mar 24, 2015

    Looks as this patch makes buildbots crash.

    @vstinner
    Copy link
    Member

    vstinner commented Mar 25, 2015

    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
    ...

    @vstinner
    Copy link
    Member

    vstinner commented Mar 25, 2015

    The problem is that Windows has no memrchr() function, and so fastsearch_memchr_1char() only supports FAST_SEARCH on Windows.

    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Mar 25, 2015

    New changeset 3ac58de829ef by Victor Stinner in branch 'default':
    Issue bpo-23573: Fix bytes.rfind() and bytearray.rfind() on Windows
    https://hg.python.org/cpython/rev/3ac58de829ef

    @vstinner
    Copy link
    Member

    vstinner commented Mar 25, 2015

    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.

    @serhiy-storchaka
    Copy link
    Member Author

    serhiy-storchaka commented Mar 25, 2015

    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.

    @serhiy-storchaka
    Copy link
    Member Author

    serhiy-storchaka commented Jul 18, 2015

    Here is a patch that restores optimization of bytes.rfind() and bytearray.rfind() with 1-byte argument on Linux (it also reverts bc1a178b3bc8).

    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented Jul 20, 2015

    New changeset 311a4d28631b by Serhiy Storchaka in branch '3.5':
    Issue bpo-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 bpo-23573: Restored optimization of bytes.rfind() and bytearray.rfind()
    https://hg.python.org/cpython/rev/c06410c68217

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    interpreter-core Interpreter core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage
    Projects
    None yet
    Development

    No branches or pull requests

    2 participants