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

Jump to bottom

Python3.10.5 Pattern Matching Excessive Memory Consumption #93671

Closed
tom-p-reichel opened this issue Jun 10, 2022 · 4 comments · Fixed by #93680
Closed

Python3.10.5 Pattern Matching Excessive Memory Consumption #93671

tom-p-reichel opened this issue Jun 10, 2022 · 4 comments · Fixed by #93680
Assignees
@pablogsal @brandtbucher
Labels
3.10 3.11 3.12 type-crash

Comments

@tom-p-reichel
Copy link

@tom-p-reichel tom-p-reichel commented Jun 10, 2022

Crash report

While writing some code to match a particularly complicated AST, I accidentally wrote a function whose definition causes the Python 3.10.5 interpreter to rapidly consume memory. On my system, it consumed approximately 24 GBs of memory before being killed.

The function is as follows:

def defines(self):
        match self.ast:
                case [S('CoqAst'), [[S('v'), [_, _, [S('expr'), [S('VernacDefinition'), [S('NoDischarge'), S('Definition')], [[[S('v'), [S('Name'), [S('Id'), S(name)]]], _], []], [S('DefineBody'), [], [], [_, _], []]]]]], _]]
                | [S('CoqAst'), [[S('v'), [[S('control'), []], [S('attrs'), []], [S('expr'), [S('VernacStartTheoremProof'), S('Theorem'), [[[[[S('v'), [S('Id'), name]], _], []], _]]]]]], _]]:
                        return name

To replicate, paste the above function into a python file and run it.

Error messages

OOM killing produced no output, save for Killed.

Your environment

  • CPython versions tested on: 3.10.5
  • Operating system and architecture: Tested on both Windows 10 and ArchLinux.
@tom-p-reichel tom-p-reichel added the type-crash label Jun 10, 2022
@Fidget-Spinner
Copy link
Member

@Fidget-Spinner Fidget-Spinner commented Jun 10, 2022

Wow. I can reproduce this on 3.11 and 3.12(main) too.

@kumaraditya303
Copy link
Contributor

@kumaraditya303 kumaraditya303 commented Jun 10, 2022

This seems like a parser issue.

Linux perf output:

Samples: 36K of event 'cpu-clock:pppH', Event count (approx.): 9100000000
Overhead  Command  Shared Object       Symbol
   7.30%  python   python              [.] _PyPegen_expect_token
   6.68%  python   [kernel.kallsyms]   [k] clear_page_erms
   6.28%  python   [kernel.kallsyms]   [k] __do_page_fault
   4.64%  python   python              [.] closed_pattern_rule
   4.09%  python   python              [.] _PyArena_Malloc
   3.36%  python   python              [.] signed_real_number_rule
   3.09%  python   libc-2.31.so        [.] _int_malloc
   3.05%  python   python              [.] or_pattern_rule
   2.84%  python   python              [.] unicodekeys_lookup_unicode

@dignissimus
Copy link
Contributor

@dignissimus dignissimus commented Jun 10, 2022

It might be the related to the depth of the statement, the following also produces a crash

match p:
    case [[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]:
        pass

pablogsal added a commit to pablogsal/cpython that referenced this issue Jun 10, 2022
@pablogsal
pythongh-93671: Avoid exponential backtracking in deeply nested seque…
182cf77 
…nce patterns in match statements
@pablogsal pablogsal mentioned this issue Jun 10, 2022
Merged
@pablogsal
Copy link
Member

@pablogsal pablogsal commented Jun 10, 2022

Thanks, @tom-p-reichel and @dignissimus for the report and thanks a lot @kumaraditya303 for the initial investigation. Great work!

pablogsal added a commit to pablogsal/cpython that referenced this issue Jun 10, 2022
@pablogsal
pythongh-93671: Avoid exponential backtracking in deeply nested seque…
3d9c7eb 
…nce patterns in match statements
pablogsal added a commit to pablogsal/cpython that referenced this issue Jun 10, 2022
@pablogsal
pythongh-93671: Avoid exponential backtracking in deeply nested seque…
e042cbb 
…nce patterns in match statements
ambv added a commit that referenced this issue Jun 10, 2022
@pablogsal @ambv
gh-93671: Avoid exponential backtracking in deeply nested sequence pa…
53a8b17 
…tterns in match statements (GH-93680)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>
miss-islington pushed a commit to miss-islington/cpython that referenced this issue Jun 10, 2022
@pablogsal @miss-islington
pythongh-93671: Avoid exponential backtracking in deeply nested seque…
af70c4f 
…nce patterns in match statements (pythonGH-93680)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit 53a8b17)

Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>
miss-islington added a commit that referenced this issue Jun 10, 2022
@miss-islington @pablogsal
gh-93671: Avoid exponential backtracking in deeply nested sequence pa…
f9d0240 
…tterns in match statements (GH-93680)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit 53a8b17)

Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>
pablogsal added a commit to pablogsal/cpython that referenced this issue Jun 10, 2022
@pablogsal
[3.10] pythongh-93671: Avoid exponential backtracking in deeply neste…
fd56269 
…d sequence patterns in match statements (pythonGH-93680)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>.
(cherry picked from commit 53a8b17)

Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>
pablogsal added a commit that referenced this issue Jun 10, 2022
@pablogsal
[3.10] gh-93671: Avoid exponential backtracking in deeply nested sequ…
8f36c73 
…ence patterns in match statements (GH-93680) (#93690)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>.
(cherry picked from commit 53a8b17)

Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@pablogsal pablogsal

@brandtbucher brandtbucher

Labels
3.10 3.11 3.12 type-crash
Projects
None yet
Milestone
No milestone
6 participants
@pablogsal @dignissimus @Fidget-Spinner @brandtbucher @tom-p-reichel @kumaraditya303