➜

This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author vstinner
Recipients orsenthil, serhiy.storchaka, vstinner, yetingli
Date 2021-04-07.11:25:55
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1617794755.29.0.0131400865931.issue43075@roundup.psfhosted.org>
In-reply-to
Content 
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
History
Date User Action Args
2021-04-07 11:25:55vstinnersetrecipients: + vstinner, orsenthil, serhiy.storchaka, yetingli
2021-04-07 11:25:55vstinnersetmessageid: <1617794755.29.0.0131400865931.issue43075@roundup.psfhosted.org>
2021-04-07 11:25:55vstinnerlinkissue43075 messages
2021-04-07 11:25:55vstinnercreate