[issue40879] Strange regex cycle

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

Note that the relatively tiny pattern here extracts just a small piece of the regexp in question. As the output shows, increase the length of a string it fails to match by one character, and the time taken to fail approximately doubles: exponential-time behavior.

>>> import re
>>> c = re.compile(r'(?:[^\s()<>]+)+x')
>>> from time import perf_counter as now
>>> size = 1
>>> while True:
...     s = 'a' * size
...     start = now()
...     junk = c.search(s)
...     finish = now()
...     print(size, finish - start)
...     size += 1
	
1 9.900000009110954e-06
2 1.1800000009998257e-05
3 1.1200000017197453e-05
4 1.2099999992187804e-05
5 1.5200000007098424e-05
6 1.5699999977414336e-05
7 2.119999999194988e-05
8 3.39000000053602e-05
9 4.9599999982774534e-05
10 7.779999998547282e-05
11 0.00014810000001830304
12 0.00034099999999170905
13 0.0006348999999943317
14 0.0012191000000143504
15 0.002482499999985066
16 0.004694100000023127
17 0.009342199999991863
18 0.01954169999999067
19 0.03880150000000526
20 0.0762141000000156
21 0.1472148999999945
22 0.27771670000001336
23 0.6491722000000095
24 1.3553119999999979
25 2.229829699999982
26 4.986566299999993
27 9.567925599999995
28 19.09181079999999
29 42.363349
30 83.57493059999999
31 158.88249489999998
...

The machine was far from quiet while running this, but it doesn't matter: the _point_ is dead obvious regardless.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue40879>
_______________________________________