New submission from yannvgn <h...@yannvgn.io>:
On complex cases, parsing regular expressions takes much, much longer on Python
>= 3.7
Example (ipython):
In [1]: import re
In [2]: char_list = ''.join([chr(i) for i in range(0xffff)])
In [3]: long_char_list = char_list * 10
In [4]: pattern = f'[{re.escape(long_char_list)}]'
In [5]: %time compiled = re.compile(pattern)
The test was run on Amazon Linux AMI 2017.03.
On Python 3.6.1, the regexp compiled in 2.6 seconds:
CPU times: user 2.59 s, sys: 30 ms, total: 2.62 s
Wall time: 2.64 s
On Python 3.7.3, the regexp compiled in 15 minutes (~350x increase in this
case):
CPU times: user 15min 6s, sys: 240 ms, total: 15min 7s
Wall time: 15min 9s
Doing some profiling with cProfile shows that the issue is caused by
sre_parse._uniq function, which does not exist in Python <= 3.6
The complexity of this function is on average O(N^2) but can be easily reduced
to O(N).
The issue might not be noticeable with simple regexps, but programs like text
tokenizers - which use complex regexps - might really be impacted by this
regression.
----------
components: Regular Expressions
messages: 348771
nosy: ezio.melotti, mrabarnett, yannvgn
priority: normal
severity: normal
status: open
title: important performance regression on regular expression parsing
type: performance
versions: Python 3.7, Python 3.8, Python 3.9
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue37723>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
