Skip to content

Possible slowdown of regex searching in 3.11 #91404

Closed
Closed
Possible slowdown of regex searching in 3.11#91404
Assignees
gpshead
Labels
3.11only security fixesperformancePerformance or resource usagerelease-blockertopic-regex

Description

@markshannon
markshannon
opened on Apr 7, 2022
BPO 47248
Nosy @markshannon, @serhiy-storchaka, @animalize, @sweeneyde

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 = None
created_at = <Date 2022-04-07.11:30:33.473>
labels = ['3.11', 'performance']
title = 'Possible slowdown of regex searching in 3.11'
updated_at = <Date 2022-04-08.07:22:53.130>
user = 'https://github.com/markshannon'

bugs.python.org fields:

activity = <Date 2022-04-08.07:22:53.130>
actor = 'malin'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = []
creation = <Date 2022-04-07.11:30:33.473>
creator = 'Mark.Shannon'
dependencies = []
files = []
hgrepos = []
issue_num = 47248
keywords = ['3.11regression']
message_count = 4.0
messages = ['416923', '416928', '416959', '416961']
nosy_count = 4.0
nosy_names = ['Mark.Shannon', 'serhiy.storchaka', 'malin', 'Dennis Sweeney']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue47248'
versions = ['Python 3.11']

Activity

  1. markshannon commented on Apr 7, 2022

    @markshannon
    markshannon
    on Apr 7, 2022
    MemberAuthor

    The 3 regular expression benchmarks in the pyperformance suite, regex_v8, regex_effbot and regex_dna show slowdowns between 3% and 10%.

    Looking at the stats, nothing seems wrong with specialization or the memory optimizations.

    Which strongly suggests a regression in the sre module itself, but I can't say so for certain.

  2. markshannon
    added
    3.11only security fixes
    performancePerformance or resource usage
    on Apr 7, 2022

  3. animalize commented on Apr 7, 2022

    @animalize
    animalizemannequin
    on Apr 7, 2022
    Mannequin

    Could you give the two versions? I will do a git bisect.

    I tested 356997c~1 and 356997c [1], msvc2022 non-pgo release build:

    # regex_dna ###
    an +- std dev: 151 ms +- 1 ms -> 152 ms +- 1 ms: 1.01x slower
    t significant

    # regex_effbot ###
    an +- std dev: 2.47 ms +- 0.01 ms -> 2.46 ms +- 0.02 ms: 1.00x faster
    t significant

    # regex_v8 ###
    an +- std dev: 21.7 ms +- 0.1 ms -> 22.4 ms +- 0.1 ms: 1.03x slower
    gnificant (t=-30.82)

    356997c

  4. sweeneyde commented on Apr 8, 2022

    @sweeneyde
    sweeneyde
    on Apr 8, 2022
    Member

    Possibly related to the new atomic grouping support from #76163?

  5. animalize commented on Apr 8, 2022

    @animalize
    animalizemannequin
    on Apr 8, 2022
    Mannequin

    Possibly related to the new atomic grouping support from #76163?

    It seems not likely.
    I will do some benchmarks for this issue, more information (version/platform) is welcome.

  6. ezio-melotti
    transferred this issue fromon Apr 10, 2022

  8. brandtbucher commented on Apr 13, 2022

    @brandtbucher
    brandtbucher
    on Apr 13, 2022
    Member

    Not sure how we're supposed to be linking issues to PRs yet, but check out #91495.

  9. brandtbucher
    added a commit that references this issue on Apr 15, 2022

    gh-91404: Use computed gotos and reduce indirection in re (#91495)

    1b34b56

  10. brandtbucher commented on Apr 15, 2022

    @brandtbucher
    brandtbucher
    on Apr 15, 2022
    Member

    Leaving this open, since it may still be worth exploring where the prior 3.10-to-3.11 slowdown came from.

  11. serhiy-storchaka
    added
    topic-regex
    on Apr 15, 2022

  12. Hello71 commented on Jun 6, 2022

    @Hello71
    Hello71
    on Jun 6, 2022

    Chromium build effectively hangs with Python 3.11 due to re slowdown. generate_about_tracing_contents takes 6 seconds on Python 3.10, and I killed it after 1 hour on Python 3.11.

    Reduced example:

    re.findall(r'(?:(?:/[^\n]*)?\n)*/', '../utils/common":3}],15:[function(t,e,a){"use strict";e.exports=function(){this.input=null,this.next_in=0,this.avail_in=0,this.total_in=0,this.output=null,this.next_out=0,this.avail_out=0,this.total_out=0,this.msg="",this.state=null,this.data_type=2,this.adler=0}},{}],"/":[function(t,e,a){"use strict";var i={};(0,t("./lib/utils/common").assign)(i,t("./lib/deflate"),t("./lib/inflate"),t("./lib/zlib/constants")),e.exports=i},{"./lib/deflate":1,"./lib/inflate":2,"./lib/utils/common":3,"./lib/zlib/constants":6}]},{},[])("/")});\n')

    takes about 0.02 seconds on Python 3.10, and 8.6 seconds on Python 3.11.

    Full example: slow.tar.gz

  13. sweeneyde commented on Jun 6, 2022

    @sweeneyde
    sweeneyde
    on Jun 6, 2022
    Member

    I git-bisected @Hello71's "Reduced example" slowdown to commit 6e3eee5

    Author: Ma Lin <animalize@users.noreply.github.com>
Date:   Mon Apr 4 00:16:20 2022 +0800

    bpo-23689: re module, fix memory leak when a match is terminated by a signal or memory allocation failure (GH-32283)
  15. sweeneyde
    added
    release-blocker
    on Jun 7, 2022

  17. gpshead commented on Jun 15, 2022

    @gpshead
    gpshead
    on Jun 15, 2022
    Member

    #93882 proposed to rollback
    6e3eee5

    there were a few other changes to re after that landed so the rollback required some hand edits.

  18. gpshead commented on Jun 15, 2022

    @gpshead
    gpshead
    on Jun 15, 2022
    Member

    I can confirm that the PR fixes the performance regression in @Hello71 's reproducer - thanks @sweeneyde for tracking that down.

  19. gpshead
    self-assigned this
    on Jun 15, 2022
  20. gpshead
    added a commit that references this issue on Jun 17, 2022

    gh-91404: Revert "bpo-23689: re module, fix memory leak when a match …

    4beee0c
  21. miss-islington
    added 2 commits that reference this issue on Jun 17, 2022

    pythongh-91404: Revert "bpo-23689: re module, fix memory leak when a …

    3c948e8

    gh-91404: Revert "bpo-23689: re module, fix memory leak when a match …

    029835d
  22. gpshead
    closed this as completedon Jun 17, 2022
  23. serhiy-storchaka
    added a commit that references this issue on Jun 26, 2022

    Revert 30935 defer bpo45162 to 312 (#94285)

    1ffde3e
  24. CAM-Gerlach
    added 2 commits that reference this issue on Oct 19, 2022

    Add Brandt's pythongh-91404 regex speedup from Optimizations to Misc …

    076e331

    Remove pythongh-91404 re entry from Optimizations to add to Faster CP…

    e7a1a01
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

3.11only security fixesperformancePerformance or resource usagerelease-blockertopic-regex

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions