Homec4science

Fix explosive runtime of detectCopiedCode()

Authored by epriestley <git@epriestley.com> on May 19 2014, 21:39.

Description

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

Maniphest Tasks: T5041

Differential Revision: https://secure.phabricator.com/D9178

Details

Committed
epriestley <git@epriestley.com>May 19 2014, 21:39
Pushed
aubortJan 31 2017, 17:16
Parents
rPHba6a5dae6156: Make "Facts" publicly viewable
Branches
Unknown
Tags
Unknown

Event Timeline

epriestley <git@epriestley.com> committed rPHb64407d47e18: Fix explosive runtime of detectCopiedCode() (authored by epriestley <git@epriestley.com>).May 19 2014, 21:39