{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang-nursery/regex/issues/215","repository_url":"https://api.github.com/repos/rust-lang-nursery/regex","labels_url":"https://api.github.com/repos/rust-lang-nursery/regex/issues/215/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang-nursery/regex/issues/215/comments","events_url":"https://api.github.com/repos/rust-lang-nursery/regex/issues/215/events","html_url":"https://github.com/rust-lang-nursery/regex/issues/215","id":151234015,"number":215,"title":"Finding matches with capturing subgroups anchored at beginning depends on length of haystack?","user":{"login":"birkenfeld","id":144359,"avatar_url":"https://avatars.githubusercontent.com/u/144359?v=3","gravatar_id":"","url":"https://api.github.com/users/birkenfeld","html_url":"https://github.com/birkenfeld","followers_url":"https://api.github.com/users/birkenfeld/followers","following_url":"https://api.github.com/users/birkenfeld/following{/other_user}","gists_url":"https://api.github.com/users/birkenfeld/gists{/gist_id}","starred_url":"https://api.github.com/users/birkenfeld/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/birkenfeld/subscriptions","organizations_url":"https://api.github.com/users/birkenfeld/orgs","repos_url":"https://api.github.com/users/birkenfeld/repos","events_url":"https://api.github.com/users/birkenfeld/events{/privacy}","received_events_url":"https://api.github.com/users/birkenfeld/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-04-26T20:41:29Z","updated_at":"2016-04-26T22:06:26Z","closed_at":null,"body":"Please refer to the following gist for the test code: https://gist.github.com/birkenfeld/ffc2f0da8b93da33f9fbd5a08a8790f3\r\n\r\nIn short, I'm experimenting with porting Pygments to Rust. The main task is implementing a scanner/lexer using lists of regexes for each state of the scanner. The scanner is an `Iterator`, and on each iteration, it goes through the regex list in order and tries to match every regex against the remaining text (all regexes are anchored at the beginning with `\\A`, in Python `re.match()` is used). When a match is found, the remaining string is updated, and the search begins at the beginning of the list on the next iteration. The scanner uses `captures()` instead of `find()` because I want to use subgroups to assign different token types to them within one match, without having to use states for that.\r\n\r\nNow, I've noticed that making the haystack longer, e.g. by appending copies of the test input, makes the matching slower and slower. You can see that in the benchmark output in the gist, where the timing is for scanning through the same string every time, but within a slice that is 1x, 2x, etc. this base string. I.e. the timings should stay constant (and they do when using `.find()`).\r\n\r\nIt seems strange to me that when the patterns are anchored at the start of the haystack, and are structured like the ones in the example (i.e. there are no patterns that have to scan through to the end of the haystack) that the time to match should not depend on the haystack length. Is this a problem of optimization (e.g. looking in the whole haystack for literals without applying the special constraints due to the `\\A` assertion)?\r\n\r\nSorry for the long issue and code, hope it's understandable."},"comment":{"url":"https://api.github.com/repos/rust-lang-nursery/regex/issues/comments/214902426","html_url":"https://github.com/rust-lang-nursery/regex/issues/215#issuecomment-214902426","issue_url":"https://api.github.com/repos/rust-lang-nursery/regex/issues/215","id":214902426,"user":{"login":"BurntSushi","id":456674,"avatar_url":"https://avatars.githubusercontent.com/u/456674?v=3","gravatar_id":"","url":"https://api.github.com/users/BurntSushi","html_url":"https://github.com/BurntSushi","followers_url":"https://api.github.com/users/BurntSushi/followers","following_url":"https://api.github.com/users/BurntSushi/following{/other_user}","gists_url":"https://api.github.com/users/BurntSushi/gists{/gist_id}","starred_url":"https://api.github.com/users/BurntSushi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/BurntSushi/subscriptions","organizations_url":"https://api.github.com/users/BurntSushi/orgs","repos_url":"https://api.github.com/users/BurntSushi/repos","events_url":"https://api.github.com/users/BurntSushi/events{/privacy}","received_events_url":"https://api.github.com/users/BurntSushi/received_events","type":"User","site_admin":false},"created_at":"2016-04-26T22:06:26Z","updated_at":"2016-04-26T22:06:26Z","body":"OK. This is an awesome (and valid) bug report. Thank you.\r\n\r\nI'll start off by baking your noodle. I take it you decided to stop benchmarking at 20x, because clearly, a pattern had formed! But, alas, you were deceived! If you continued, you'd see this:\r\n\r\n```\r\ntest bench_001x ... bench:     445,333 ns/iter (+/- 1,398)\r\ntest bench_002x ... bench:     563,531 ns/iter (+/- 5,479)\r\ntest bench_003x ... bench:     670,828 ns/iter (+/- 3,312)\r\ntest bench_005x ... bench:     901,192 ns/iter (+/- 2,839)\r\ntest bench_010x ... bench:   1,566,748 ns/iter (+/- 4,172)\r\ntest bench_020x ... bench:   3,538,074 ns/iter (+/- 5,703)\r\ntest bench_100x ... bench:     669,923 ns/iter (+/- 708)\r\ntest bench_200x ... bench:     671,756 ns/iter (+/- 8,083)\r\ntest bench_300x ... bench:     672,581 ns/iter (+/- 23,761)\r\n```\r\n\r\nNote the last three. *Wat*. :-)\r\n\r\nSo it turns out that there are two distinct matching engines in this crate that can compute capture locations. One of them is based on the Thompson NFA construction (the \"Pike VM\") and the other uses *backtracking*. It turns out that backtracking is actually pretty fast---when it doesn't go exponential. The problem is, we really want to guarantee matching in linear time, so we actually use a *bounded backtracking* approach, where the same state for the same position in the input is visited exactly once. The problem with this approach is that it takes some serious memory to keep track of where we've been, so **we can only use the backtracking engine on small inputs**. As the input grows, it will eventually reach a point where the backtracker says, \"nope, too big!\" and the Pike VM kicks in and handles it.\r\n\r\nOK, but, but, the pattern is anchored! Should the backtracker quit once it knows it can't find a match? Indeed it should, and it does. The issue here is that the backtracker must spend time initializing (i.e., zeroing) its state table before searching begins. This state table has **size proportional to the input**, which means search times will vary as the input grows, even if the search itself doesn't examine any more input.\r\n\r\nSo I think actual issue here is that the heuristic for picking the backtracking engine, in this case, is simply wrong. There will always be cases where it's wrong, because obviously picking the size limit is a bit of a black art. In any case, it seems like it's probably over extending itself, so I opened #216. With that change, the benchmarks now look like this:\r\n\r\n```\r\ntest bench_001x ... bench:     432,289 ns/iter (+/- 934)\r\ntest bench_002x ... bench:     550,904 ns/iter (+/- 3,360)\r\ntest bench_003x ... bench:     659,164 ns/iter (+/- 2,237)\r\ntest bench_005x ... bench:     889,168 ns/iter (+/- 2,246)\r\ntest bench_010x ... bench:   1,556,030 ns/iter (+/- 13,166)\r\ntest bench_020x ... bench:     908,140 ns/iter (+/- 2,301)\r\ntest bench_100x ... bench:     682,278 ns/iter (+/- 832)\r\ntest bench_200x ... bench:     683,504 ns/iter (+/- 2,103)\r\ntest bench_300x ... bench:     683,351 ns/iter (+/- 1,068)\r\n```\r\n\r\nStill not quite perfect, but better. At least, you would have noticed the plateau in this case I think. :-)"}}