This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4508

lazyancestors: reuse __iter__ implementation in __contains__
ClosedPublic

Authored by martinvonz on Sep 8 2018, 3:38 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG77a2f6d805f2: lazyancestors: reuse __iter__ implementation in __contains__
Summary

There was a comment in the code that said "Trying to do both iter
and contains using the same visit heap and seen set is complex
enough that it slows down both. Keep them separate.". However, it
seems easy and efficient to make contains keep an iterator across
calls.

I couldn't measure any slowdown from hg bundle --all (which seem to
call lazyancestors.contains frequently).

1HG: --

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

martinvonz created this revision.Sep 8 2018, 3:38 AM
yuja added a subscriber: yuja.Sep 8 2018, 4:33 AM

+ self._containsseen = set()
+ self._containsiter = iter(self)

Perhaps iter() needs to be extracted to a free function to avoid
reference cycle.

martinvonz added a comment.Sep 10 2018, 2:50 AM
In D4508#68864, @yuja wrote:

+ self._containsseen = set()
+ self._containsiter = iter(self)

Perhaps iter() needs to be extracted to a free function to avoid
reference cycle.

Good point. I'll send a patch before this one to extract a free function.

Why do we care about reference cycles again? Because some runtimes don't have GC?

martinvonz updated this revision to Diff 10852.Sep 10 2018, 3:06 AM
Closed by commit rHG77a2f6d805f2: lazyancestors: reuse __iter__ implementation in __contains__ (authored by martinvonz). · Explain WhySep 10 2018, 7:43 AM
This revision was automatically updated to reflect the committed changes.
yuja added a comment.Sep 10 2018, 7:54 AM

Queued, thanks.

Revision Contents
Changeset List

PathPackages
Mmercurial/ancestor.py (57 lines)

Diff 10856

mercurial/ancestor.py

than stoprev will not be generated. than stoprev will not be generated.
Result does not include the null revision.""" Result does not include the null revision."""
self._parentrevs = pfunc self._parentrevs = pfunc
self._initrevs = revs = [r for r in revs if r >= stoprev] self._initrevs = revs = [r for r in revs if r >= stoprev]
self._stoprev = stoprev self._stoprev = stoprev
self._inclusive = inclusive self._inclusive = inclusive
# Initialize data structures for __contains__.
# For __contains__, we use a heap rather than a deque because
# (a) it minimizes the number of parentrevs calls made
# (b) it makes the loop termination condition obvious
# Python's heap is a min-heap. Multiply all values by -1 to convert it
# into a max-heap.
self._containsvisit = [-rev for rev in revs]
heapq.heapify(self._containsvisit)
if inclusive:
self._containsseen = set(revs)
else:
self._containsseen = set() self._containsseen = set()
self._containsiter = _lazyancestorsiter(self._parentrevs,
self._initrevs,
self._stoprev,
self._inclusive)
def __nonzero__(self): def __nonzero__(self):
"""False if the set is empty, True otherwise.""" """False if the set is empty, True otherwise."""
try: try:
next(iter(self)) next(iter(self))
return True return True
except StopIteration: except StopIteration:
return False return False
If inclusive is True, the source revisions are also yielded. The If inclusive is True, the source revisions are also yielded. The
reverse revision number order is still enforced.""" reverse revision number order is still enforced."""
for rev in _lazyancestorsiter(self._parentrevs, self._initrevs, for rev in _lazyancestorsiter(self._parentrevs, self._initrevs,
self._stoprev, self._inclusive): self._stoprev, self._inclusive):
yield rev yield rev
def __contains__(self, target): def __contains__(self, target):
"""Test whether target is an ancestor of self._initrevs.""" """Test whether target is an ancestor of self._initrevs."""
# Trying to do both __iter__ and __contains__ using the same visit
# heap and seen set is complex enough that it slows down both. Keep
# them separate.
seen = self._containsseen seen = self._containsseen
if target in seen: if target in seen:
return True return True
iter = self._containsiter
if iter is None:
# Iterator exhausted
return False
# Only integer target is valid, but some callers expect 'None in self' # Only integer target is valid, but some callers expect 'None in self'
# to be False. So we explicitly allow it. # to be False. So we explicitly allow it.
if target is None: if target is None:
return False return False
parentrevs = self._parentrevs
visit = self._containsvisit
stoprev = self._stoprev
heappop = heapq.heappop
heappush = heapq.heappush
see = seen.add see = seen.add
try:
targetseen = False while True:
rev = next(iter)
while visit and -visit[0] > target and not targetseen: see(rev)
for parent in parentrevs(-heappop(visit)): if rev == target:
if parent < stoprev or parent in seen: return True
continue if rev < target:
# We need to make sure we push all parents into the heap so return False
# that we leave it in a consistent state for future calls. except StopIteration:
heappush(visit, -parent) # Set to None to indicate fast-path can be used next time, and to
see(parent) # free up memory.
if parent == target: self._containsiter = None
targetseen = True return False
return targetseen