Page MenuHomePhabricator

Make PhutilProseDifferenceEngine degrade on large inputs instead of consuming all RAM in the entire world
ClosedPublic

Authored by epriestley on Oct 6 2016, 11:09 PM.
Tags
None
Referenced Files
Unknown Object (File)
Tue, Mar 19, 9:09 PM
Unknown Object (File)
Feb 19 2024, 4:15 PM
Unknown Object (File)
Feb 19 2024, 2:02 PM
Unknown Object (File)
Feb 3 2024, 12:25 PM
Unknown Object (File)
Jan 23 2024, 5:29 PM
Unknown Object (File)
Jan 23 2024, 3:50 PM
Unknown Object (File)
Jan 22 2024, 7:50 PM
Unknown Object (File)
Jan 18 2024, 8:08 PM

Details

Summary

Fixes T11743. For very large inputs which can't be simplified (e.g., dissimilar text at the beginning and end across a very large number of paragraphs) we currently try to build an edit distance matrix, but this is exponential in space and time and slowness and how PHP-ish it is.

Instead, just give up for very large inputs. This will still prose-diff any corpuses with fewer than 128 paragraphs, which is the vast majority of documents.

Test Plan
  • Created a degnerate Paste similar to the one in T11743.
  • Viewed change details and ran bin/worker execute --id <id> --trace before and after patch.
    • Before: everything hung forever.
    • After: everything worked great, although the diff wasn't perfect.

Diff Detail

Repository
rPHU libphutil
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

epriestley retitled this revision from to Make PhutilProseDifferenceEngine degrade on large inputs instead of consuming all RAM in the entire world.
epriestley updated this object.
epriestley edited the test plan for this revision. (Show Details)
epriestley added a reviewer: chad.

Deployed this on our install, and it worked -- resolved all symptoms of T11743. Thanks again for the swift fix!

chad edited edge metadata.
This revision is now accepted and ready to land.Oct 7 2016, 6:02 AM
wizsrk added inline comments.
src/utils/PhutilProseDifferenceEngine.php
28

please ignore this, just a test

src/utils/PhutilProseDifferenceEngine.php
21–23

this is also test

This revision was automatically updated to reflect the committed changes.