Reduce complexity of "possible_ancestors" from quadratic to linear.
"Possible ancestors" are all the leaf revisions with a position less than any
of the missing revisions. Previously, for every leaf revision we potentially
checked every missing revision. And with missing revisions list being sorted
from smallest to largest, that meant often traversing most of the missing
revisions list. In general, it meant performing O(R * M) operations, where R is
the number of leaf revision, and M is the number of missing revisions.
The optimization is instead of comparing against every single missing revision
we can compare only against the highest one. If a leaf revision is less than
highest missing revison, then it is already a possible ancestor, so we can stop
checking. Thus, we can go from a quadratic O(R * M) to an O(R) + O(M)
complexity, which, when merging large conflicting documents could give us a
nice performance boost.
2 files changed
