tree de5a38c442b4c968f34ae1404a06a5b5bc79ba58
parent adde37ab813b2ae39c25d891b646191498b35872
author Nick Vatamaniuc <vatamane@gmail.com> 1654893184 -0400
committer Nick Vatamaniuc <nickva@users.noreply.github.com> 1654970545 -0400

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.