Skip to content

bytes.find consistently hangs in a particular scenario #86138

@Zeturic

Description

@Zeturic
mannequin
BPO 41972
Nosy @gvanrossum, @tim-one, @rhettinger, @gpshead, @cfbolz, @taleinat, @pmp-p, @ambv, @serhiy-storchaka, @MojoVampire, @ammaraskar, @corona10, @sweeneyde, @Zeturic
PRs
  • bpo-41972: Use the "Two-Way" algorithm when searching for long substrings #22679
  • bpo-41972: Use the two-way algorithm for string searching #22904
  • bpo-41972: Add whatsnew note for GH-22904 #24672
  • bpo-41972: Tweak fastsearch.h string search algorithms #27091
  • Files
  • reproducer.py
  • fastsearch.diff
  • fastsearch.py: Pure-python two-way string search algorithm translated from glibc
  • fastsearch.h: Drop-in replacement for Objects/stringlib/fastsearch.h using the two-way algorithm
  • bench_results.txt
  • random_bench.py: Test str in str on random words of a language with a Zipf distribution
  • bench_table.txt
  • twoway-benchmark-results-2020-10-28.txt
  • Table of benchmarks on lengths.jpg
  • length_benchmarks.txt
  • twoway_demo.py: Added Checkbox for using shift-table
  • comparison.jpg: Benchmarks of Two-Way algorithm versus adaptive algorithm on Zipf benchmarks
  • 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 = None
    closed_at = <Date 2021-07-19.15:25:54.659>
    created_at = <Date 2020-10-07.23:31:59.517>
    labels = ['3.9', '3.10', 'performance']
    title = 'bytes.find consistently hangs in a particular scenario'
    updated_at = <Date 2021-07-19.15:25:54.658>
    user = 'https://github.com/Zeturic'

    bugs.python.org fields:

    activity = <Date 2021-07-19.15:25:54.658>
    actor = 'lukasz.langa'
    assignee = 'none'
    closed = True
    closed_date = <Date 2021-07-19.15:25:54.659>
    closer = 'lukasz.langa'
    components = []
    creation = <Date 2020-10-07.23:31:59.517>
    creator = 'Zeturic'
    dependencies = []
    files = ['49499', '49503', '49507', '49508', '49511', '49512', '49518', '49545', '49577', '49578', '49674', '49746']
    hgrepos = []
    issue_num = 41972
    keywords = ['patch']
    message_count = 77.0
    messages = ['378197', '378209', '378210', '378221', '378222', '378225', '378229', '378233', '378260', '378263', '378301', '378329', '378372', '378420', '378423', '378470', '378472', '378534', '378537', '378541', '378543', '378556', '378576', '378578', '378579', '378582', '378583', '378584', '378585', '378590', '378600', '378635', '378652', '378736', '378737', '378739', '378742', '378750', '378751', '378753', '378793', '378828', '378834', '378836', '378842', '378843', '378844', '378847', '378916', '378917', '378920', '378922', '378923', '378924', '378979', '379388', '379391', '379422', '379494', '379822', '379825', '380473', '380474', '380476', '380477', '380487', '382905', '385169', '387717', '387790', '387791', '387792', '387813', '397277', '397787', '397788', '397805']
    nosy_count = 14.0
    nosy_names = ['gvanrossum', 'tim.peters', 'rhettinger', 'gregory.p.smith', 'Carl.Friedrich.Bolz', 'taleinat', 'pmpp', 'lukasz.langa', 'serhiy.storchaka', 'josh.r', 'ammar2', 'corona10', 'Dennis Sweeney', 'Zeturic']
    pr_nums = ['22679', '22904', '24672', '27091']
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'performance'
    url = 'https://bugs.python.org/issue41972'
    versions = ['Python 3.9', 'Python 3.10']

    Metadata

    Metadata

    Assignees

    No one assigned

      Labels

      3.10only security fixes3.9only security fixesperformancePerformance or resource usage

      Projects

      No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions