Mercurial > hg
changeset 39536:bdb177923291
ancestor: optimize _lazyancestorsiter() for contiguous chains
If there's no revision between p1 and current, p1 must be the next revision
to visit. In this case, we can get around the overhead of heappop/push
operations. Note that this is faster than using heapreplace().
'current - p1 == 1' could be generalized as 'all(r not in seen for r in
xrange(p1, current)', but Python is too slow to do such thing.
| author | Yuya Nishihara <yuya@tcha.org> |
|---|---|
| date | Mon, 10 Sep 2018 21:58:59 +0900 |
| parents | b9ee9c2e10dd |
| children | ca9983c35d89 |
| files | mercurial/ancestor.py tests/test-ancestor.py tests/test-ancestor.py.out |
| diffstat | 3 files changed, 17 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/mercurial/ancestor.py Mon Sep 10 21:54:40 2018 +0900 +++ b/mercurial/ancestor.py Mon Sep 10 21:58:59 2018 +0900 @@ -283,14 +283,22 @@ see(p2) while visit: - current = -nextitem(visit) + current = -visit[0] if current < stoprev: break yield current + # optimize out heapq operation if p1 is known to be the next highest + # revision, which is quite common in linear history. p1, p2 = parentrevs(current) if p1 not in seen: - schedule(visit, -p1) + if current - p1 == 1: + visit[0] = -p1 + else: + nextitem(visit) + schedule(visit, -p1) see(p1) + else: + nextitem(visit) if p2 not in seen: schedule(visit, -p2) see(p2)
--- a/tests/test-ancestor.py Mon Sep 10 21:54:40 2018 +0900 +++ b/tests/test-ancestor.py Mon Sep 10 21:58:59 2018 +0900 @@ -221,6 +221,10 @@ s = genlazyancestors([11, 13], stoprev=12, inclusive=True) printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) + # Contiguous chains: 5->4, 2->1 (where 1 is in seen set), 1->0 + s = genlazyancestors([10, 1], inclusive=True) + printlazyancestors(s, [2, 10, 4, 5, -1, 0, 1]) + # The C gca algorithm requires a real repo. These are textual descriptions of # DAGs that have been known to be problematic, and, optionally, known pairs # of revisions and their expected ancestor list.
--- a/tests/test-ancestor.py.out Mon Sep 10 21:54:40 2018 +0900 +++ b/tests/test-ancestor.py.out Mon Sep 10 21:58:59 2018 +0900 @@ -22,3 +22,6 @@ % lazy ancestor set for [11, 13], stoprev = 12, inclusive = True membership: [13] iteration: [13] +% lazy ancestor set for [10, 1], stoprev = 0, inclusive = True +membership: [2, 10, 4, 5, 0, 1] +iteration: [10, 5, 4, 2, 1, 0]