Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Create a framework for detecting quadratic time regressions #257

marcusklaas opened this Issue Mar 27, 2019 · 2 comments


None yet
1 participant
Copy link

commented Mar 27, 2019

There's a bunch of test cases provided by @andersk on which pulldown_cmark previously exhibited quadratic time behaviour. Many should be fixed now, but at the moment there is no (automated) way of ensuring that we don't regress on them.

We would ideally have a test pass which runs those examples one-by-one in release mode and make sure they don't time out (and thereby providing some assurance that we haven't regressed horribly).

Here's one way of doing it:

  • create a separate test module, so it can be easily skipped or singled out
  • create a single test in that module, ensuring that no two time-out tests run simultaneously
  • loop through a static array of function pointers generating a testcases (Fn() -> String), for each we
    • create timeout thread, which returns after a fixed time
    • create an execution thread, which parses and renders to html into a std::io::Sink
    • wait for the first thread to return and make sure the execution thread returned first

Some care will have to be taken to pick the right testcase size and timeout time. Luckily, if we truly regressed to quadratic behaviour, execution time will blow up very quickly. Therefore, we have some margin to work with.

You could try with sizing your testcases so that they return in ~50ms on your local machine and then setting the timeout multiplier to 50. That should make sure that we don't get too many spurious failures on machines that are much weaker or under heavy load. This will likely require some tweaking.

Of course, this is just one approach. There may very well be more robust approaches. Feel free to get creative!

Edit: I think benchmarks can have assertions. It may be best to implement this as a benchmark module. That automatically guarantees release compilation and that no two tests are run simultaneously.


This comment has been minimized.

Copy link
Collaborator Author

commented Mar 27, 2019

Added note: besides the issue tracker, many example test cases should also end up in benches/


This comment has been minimized.

Copy link
Collaborator Author

commented Apr 5, 2019

Another approach that could work is to have input generating functions that produce markdown inputs proportional in length to some given number.

For example, this test case would have a function like this

fn quadratic_test_case_1(size: usize) -> String {
    std::iter::repeat("[*_a").take(size / 4).collect()

and then check the parse time increase after increasing the size 10x. If there's quadratic behaviour, it will be ~100x longer. Otherwise, it probably shouldn't be over 15x or 20x. This doesn't rule out O(n log n) performance, but I think that's difficult to do reliably anyway.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.