• Benedikt Meurer's avatar
    [liveedit] Reduce peak memory usage of text diffing. · 3fa681db
    Benedikt Meurer authored
    The algorithm used to compute the textual differences uses requires
    quadratic space (in the size of the input scripts). Previously the
    implementation was naively allocating a single matrix, which is commonly
    very sparse, since the expectation for LiveEdit is that only a small
    portion of the script is actually altered. So we can use a std::map here
    instead to reduce the cost.
    
    We can also significantly reduce the cost (especially of the stack grow
    due to the recursion) by precomputing the common prefix, and pre-filling
    the table for the common suffix, both of which are also assumed to make
    up for the majority of the script in case of LiveEdit.
    
    This is still only ducktape, but should mitigate the crashes in the wild
    significantly. Ideally we'd eventually replace this with an
    implementation of the Myers algorithm that runs in linear space.
    
    Fixed: chromium:1199807
    Change-Id: Ib5fa0b1aa63c67631f919dc3b6641dfc0b20ae74
    Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2867470Reviewed-by: 's avatarYang Guo <yangguo@chromium.org>
    Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#74344}
    3fa681db
liveedit.cc 43.7 KB