+
Skip to content

marko.parse has quadtratic time for some input #219

@plaflamme

Description

@plaflamme

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...

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions

      点击 这是indexloc提供的php浏览器服务,不要输入任何密码和下载