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
F14028638: D16682.diff
Fri, Nov 8, 2:54 PM
F14027745: D16682.diff
Fri, Nov 8, 9:03 AM
F14006620: D16682.id40163.diff
Mon, Oct 28, 2:22 PM
F13980106: D16682.id40165.diff
Sat, Oct 19, 8:29 AM
F13967962: D16682.id40163.diff
Wed, Oct 16, 5:27 PM
F13967873: D16682.diff
Wed, Oct 16, 4:44 PM
Unknown Object (File)
Oct 7 2024, 6:51 PM
Unknown Object (File)
Sep 21 2024, 11:56 AM

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
Branch
degrade1
Lint
Lint Passed
Unit
Tests Passed
Build Status
Buildable 14054
Build 18231: Run Core Tests
Build 18230: arc lint + arc unit

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.