Page MenuHomePhabricator

Fix explosive runtime of detectCopiedCode()

Authored by epriestley on May 18 2014, 4:37 AM.



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

Diff Detail

rP Phabricator
Lint Skipped
Unit Tests Skipped

Event Timeline

epriestley updated this revision to Diff 21797.May 18 2014, 4:37 AM
epriestley retitled this revision from to Fix explosive runtime of detectCopiedCode().
epriestley updated this object.
epriestley edited the test plan for this revision. (Show Details)
epriestley added a reviewer: btrahan.
btrahan accepted this revision.May 19 2014, 6:22 PM
btrahan edited edge metadata.


This revision is now accepted and ready to land.May 19 2014, 6:22 PM
chad awarded a token.May 19 2014, 6:30 PM
epriestley closed this revision.May 19 2014, 7:39 PM
epriestley updated this revision to Diff 21854.

Closed by commit rPb64407d47e18 (authored by @epriestley).