Page MenuHomePhabricator

Fix explosive runtime of detectCopiedCode()
ClosedPublic

Authored by epriestley on May 18 2014, 4:37 AM.
Tags
None
Referenced Files
Unknown Object (File)
Wed, Mar 20, 6:50 PM
Unknown Object (File)
Feb 7 2024, 4:23 PM
Unknown Object (File)
Feb 5 2024, 7:22 PM
Unknown Object (File)
Feb 4 2024, 3:41 AM
Unknown Object (File)
Jan 29 2024, 9:03 PM
Unknown Object (File)
Jan 29 2024, 8:39 PM
Unknown Object (File)
Jan 20 2024, 12:54 AM
Unknown Object (File)
Jan 20 2024, 12:54 AM
Subscribers
Tokens
"Mountain of Wealth" token, awarded by chad.

Details

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

Diff Detail

Repository
rP Phabricator
Lint
Lint Skipped
Unit
Tests Skipped

Event Timeline

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 edited edge metadata.

Hazzah!

This revision is now accepted and ready to land.May 19 2014, 6:22 PM
epriestley updated this revision to Diff 21854.

Closed by commit rPb64407d47e18 (authored by @epriestley).