marko.parse has quadtratic time for some input #219
Description
Some input causes the parser's runtime to grow exponentially. To replicate:
import time
from marko import parse
def t(i):
start = time.time()
parse("X" + " " * i)
return time.time() - start
tokens=[100,1000,10000,100000]
runtimes=[t(i) for i in tokens]
for (i,t) in enumerate(tokens):
increase=int(runtimes[i] / runtimes[i-1] if i > 0 else 0)
print(f"{t},{runtimes[i]},x{increase}")This prints the following on my machine:
100,0.00041794776916503906,x0
1000,0.007384061813354492,x17
10000,0.38972020149230957,x52
100000,37.4679319858551,x96
As you can see, as the number of tokens increases linearly (x10), the runtime increases exponentially...