GitLab

In pathological cases, such as those provided in the relevant bug,
Zucchini could exhibit O(n^2) behavior during seed selection. To remedy
this, this CL adds a quota to limit the total number of bytes covered
in seed selection search. However, as demonstrated in CL:
https://chromium-review.googlesource.com/c/chromium/src/+/1115710
this is insufficient. haungs@ determined that if this is the only
limitation then the ExtendEquivalenceBackward method will perform a
linear time extension resulting in O(n) behvior which when applied
over O(n) offsets results in O(n^2) behavior again. To limit this he
proposed limiting the distance ExtendEquivalenceBackward can search
which is also implemented in this CL.

These parameters are tuned such that they have no noticeable impact
when patching chrome.7z for Windows. For the pathological testcases in
the bug the results are significantly better (refer to the bug for
exact improvements).

This solution results in linear time performance on the pathological
cases. We could get these numbers down even smaller by reducing the
limit on backward extension. However, this had a small, but noticeable
~5 kiB increase in patches for chrome.7z.

Bug: 849471
Change-Id: If7e857884b00daeeae7a4a29b1236c749f0b84e4
Reviewed-on: https://chromium-review.googlesource.com/1117273
Commit-Queue: Calder Kitagawa <ckitagawa@chromium.org>
Reviewed-by: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/master@{#571134}