Quadratic time consumption on pathological input

[DemiMarie]

See commonmark/cmark#218. Comrak is also vulnerable:

$ python -c 'print("[a](<b"*50000)' | time comrak >/dev/null
comrak > /dev/null  6.78s user 0.01s system 99% cpu 6.810 total

[kivikakk]

Is this actually quadratic right now?

$ time python -c 'print("[a](<b" * 50000)' | target/debug/comrak > /dev/null
target/debug/comrak > /dev/null  1.39s user 0.02s system 98% cpu 1.431 total
$ time python -c 'print("[a](<b" * 100000)' | target/debug/comrak > /dev/null
target/debug/comrak > /dev/null  2.93s user 0.05s system 99% cpu 3.007 total
$ time python -c 'print("[a](<b" * 200000)' | target/debug/comrak > /dev/null
target/debug/comrak > /dev/null  5.41s user 0.07s system 99% cpu 5.505 total

Time taken is roughly doubling with each doubling of input size.

[DemiMarie]

I think my most recent patch fixed it.

…

On Aug 27, 2017 8:41 PM, "Ashe Connor" ***@***.***> wrote: Is this actually quadratic right now? $ time python -c 'print("[a](<b" * 50000)' | target/debug/comrak > /dev/null target/debug/comrak > /dev/null 1.39s user 0.02s system 98% cpu 1.431 total $ time python -c 'print("[a](<b" * 100000)' | target/debug/comrak > /dev/null target/debug/comrak > /dev/null 2.93s user 0.05s system 99% cpu 3.007 total $ time python -c 'print("[a](<b" * 200000)' | target/debug/comrak > /dev/null target/debug/comrak > /dev/null 5.41s user 0.07s system 99% cpu 5.505 total Time taken is roughly doubling with each doubling of input size. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#31 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGGWBwixjYeDZJ_suigcEvPtF9HsBOnKks5scgzNgaJpZM4Ounhm> .

[kivikakk]

Oh, you're totally right. I was not awake when I checked this issue last, sorry. Thanks again for #33!