Mercurial > hg
comparison mercurial/ancestor.py @ 39482:77a2f6d805f2
lazyancestors: reuse __iter__ implementation in __contains__
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).
Differential Revision: https://phab.mercurial-scm.org/D4508
author | Martin von Zweigbergk <martinvonz@google.com> |
---|---|
date | Fri, 07 Sep 2018 23:36:09 -0700 |
parents | b6a0e06b0f7d |
children | f6bcb4f9cd3c |
comparison
equal
deleted
inserted
replaced
39481:b6a0e06b0f7d | 39482:77a2f6d805f2 |
---|---|
306 self._parentrevs = pfunc | 306 self._parentrevs = pfunc |
307 self._initrevs = revs = [r for r in revs if r >= stoprev] | 307 self._initrevs = revs = [r for r in revs if r >= stoprev] |
308 self._stoprev = stoprev | 308 self._stoprev = stoprev |
309 self._inclusive = inclusive | 309 self._inclusive = inclusive |
310 | 310 |
311 # Initialize data structures for __contains__. | 311 self._containsseen = set() |
312 # For __contains__, we use a heap rather than a deque because | 312 self._containsiter = _lazyancestorsiter(self._parentrevs, |
313 # (a) it minimizes the number of parentrevs calls made | 313 self._initrevs, |
314 # (b) it makes the loop termination condition obvious | 314 self._stoprev, |
315 # Python's heap is a min-heap. Multiply all values by -1 to convert it | 315 self._inclusive) |
316 # into a max-heap. | |
317 self._containsvisit = [-rev for rev in revs] | |
318 heapq.heapify(self._containsvisit) | |
319 if inclusive: | |
320 self._containsseen = set(revs) | |
321 else: | |
322 self._containsseen = set() | |
323 | 316 |
324 def __nonzero__(self): | 317 def __nonzero__(self): |
325 """False if the set is empty, True otherwise.""" | 318 """False if the set is empty, True otherwise.""" |
326 try: | 319 try: |
327 next(iter(self)) | 320 next(iter(self)) |
346 self._stoprev, self._inclusive): | 339 self._stoprev, self._inclusive): |
347 yield rev | 340 yield rev |
348 | 341 |
349 def __contains__(self, target): | 342 def __contains__(self, target): |
350 """Test whether target is an ancestor of self._initrevs.""" | 343 """Test whether target is an ancestor of self._initrevs.""" |
351 # Trying to do both __iter__ and __contains__ using the same visit | |
352 # heap and seen set is complex enough that it slows down both. Keep | |
353 # them separate. | |
354 seen = self._containsseen | 344 seen = self._containsseen |
355 if target in seen: | 345 if target in seen: |
356 return True | 346 return True |
347 iter = self._containsiter | |
348 if iter is None: | |
349 # Iterator exhausted | |
350 return False | |
357 # Only integer target is valid, but some callers expect 'None in self' | 351 # Only integer target is valid, but some callers expect 'None in self' |
358 # to be False. So we explicitly allow it. | 352 # to be False. So we explicitly allow it. |
359 if target is None: | 353 if target is None: |
360 return False | 354 return False |
361 | 355 |
362 parentrevs = self._parentrevs | |
363 visit = self._containsvisit | |
364 stoprev = self._stoprev | |
365 heappop = heapq.heappop | |
366 heappush = heapq.heappush | |
367 see = seen.add | 356 see = seen.add |
368 | 357 try: |
369 targetseen = False | 358 while True: |
370 | 359 rev = next(iter) |
371 while visit and -visit[0] > target and not targetseen: | 360 see(rev) |
372 for parent in parentrevs(-heappop(visit)): | 361 if rev == target: |
373 if parent < stoprev or parent in seen: | 362 return True |
374 continue | 363 if rev < target: |
375 # We need to make sure we push all parents into the heap so | 364 return False |
376 # that we leave it in a consistent state for future calls. | 365 except StopIteration: |
377 heappush(visit, -parent) | 366 # Set to None to indicate fast-path can be used next time, and to |
378 see(parent) | 367 # free up memory. |
379 if parent == target: | 368 self._containsiter = None |
380 targetseen = True | 369 return False |
381 | |
382 return targetseen |