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.9 (EOL)end of lifeperformancePerformance or resource usage
      No fields configured for issues without a type.

      Projects

      No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions