R1:b64407d47e18
R1:b64407d47e18
Fix explosive runtime of detectCopiedCode()
Summary:
Fixes T5041. Pretty sure this is the issue: if a diff contains a large number of identical lines longer than 30 characters, we end up paying O(N^2) for each set.
Instead, when N > 16, opt to pay 0.
Test Plan: Added a test which dropped from ~100s to ~0 after changes (this diff includes a reduced-strenght version of the test, since parsing a 4,000 line diff is a little bit pricey).
Reviewers: btrahan
Reviewed By: btrahan
Subscribers: epriestley…
Summary:
Fixes T5041. Pretty sure this is the issue: if a diff contains a large number of identical lines longer than 30 characters, we end up paying O(N^2) for each set.
Instead, when N > 16, opt to pay 0.
Test Plan: Added a test which dropped from ~100s to ~0 after changes (this diff includes a reduced-strenght version of the test, since parsing a 4,000 line diff is a little bit pricey).
Reviewers: btrahan
Reviewed By: btrahan
Subscribers: epriestley…
Repository: R1 hydra
Commit Date: May 19 2014