STINNER Victor <vstin...@python.org> added the comment:
redos_python2.py: Updated benchmark. I confirm that PR 24391 fix a worst case performance, starting with 100 characters. Since the complexity is quadratic, strings longer 10^4 characters are likely to hang a client for several minutes. == Reference (vulnerable) == simple: Mean +- std dev: 2.10 us +- 0.05 us repeat 10: Mean +- std dev: 3.85 us +- 0.13 us repeat 10^2: Mean +- std dev: 133 us +- 3 us repeat 10^4: Mean +- std dev: 1.23 sec +- 0.05 sec == With the PR 24391 fix == simple: Mean +- std dev: 2.15 us +- 0.15 us repeat 10: Mean +- std dev: 2.44 us +- 0.04 us repeat 10^2: Mean +- std dev: 7.45 us +- 0.17 us repeat 10^4: Mean +- std dev: 574 us +- 28 us == Comparison == simple: Mean +- std dev: [ref] 2.10 us +- 0.05 us -> [fix] 2.15 us +- 0.15 us: 1.02x slower repeat 10: Mean +- std dev: [ref] 3.85 us +- 0.13 us -> [fix] 2.44 us +- 0.04 us: 1.58x faster repeat 10^2: Mean +- std dev: [ref] 133 us +- 3 us -> [fix] 7.45 us +- 0.17 us: 17.80x faster repeat 10^4: Mean +- std dev: [ref] 1.23 sec +- 0.05 sec -> [fix] 574 us +- 28 us: 2152.36x faster Geometric mean: 15.59x faster ---------- Added file: https://bugs.python.org/file49938/redos_python2.py _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue43075> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
