Patchwork ancestors: prefetch method outside of the loop

login
register
mail settings
Submitter Pierre-Yves David
Date June 20, 2015, 10:29 p.m.
Message ID <a005a978678ae5bbfdf4.1434839355@marginatus.alto.octopoid.net>
Download mbox | patch
Permalink /patch/9731/
State Accepted
Headers show

Comments

Pierre-Yves David - June 20, 2015, 10:29 p.m.
# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@fb.com>
# Date 1434766800 25200
#      Fri Jun 19 19:20:00 2015 -0700
# Node ID a005a978678ae5bbfdf4cf298af5449db5d7d369
# Parent  2748bf78a5bf610da4f2d90fd1eea19a3b360c04
ancestors: prefetch method outside of the loop

15412bba5a68 is yet another example than this is worthwhile when it comes to
performance, we blindly do in for all 'lazyancestors' method.
Yuya Nishihara - June 21, 2015, 6:15 a.m.
On Sat, 20 Jun 2015 15:29:15 -0700, Pierre-Yves David wrote:
> # HG changeset patch
> # User Pierre-Yves David <pierre-yves.david@fb.com>
> # Date 1434766800 25200
> #      Fri Jun 19 19:20:00 2015 -0700
> # Node ID a005a978678ae5bbfdf4cf298af5449db5d7d369
> # Parent  2748bf78a5bf610da4f2d90fd1eea19a3b360c04
> ancestors: prefetch method outside of the loop
> 
> 15412bba5a68 is yet another example than this is worthwhile when it comes to
> performance, we blindly do in for all 'lazyancestors' method.
> 
> diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
> --- a/mercurial/ancestor.py
> +++ b/mercurial/ancestor.py
> @@ -310,19 +310,23 @@ class lazyancestors(object):
>          if self._inclusive:
>              for rev in revs:
>                  yield rev
>              seen.update(revs)
>  
> +

Nitpick, double empty lines.
It appears check-commit fails to catch this pattern.
Augie Fackler - June 22, 2015, 2:18 p.m.
On Sat, Jun 20, 2015 at 03:29:15PM -0700, Pierre-Yves David wrote:
> # HG changeset patch
> # User Pierre-Yves David <pierre-yves.david@fb.com>
> # Date 1434766800 25200
> #      Fri Jun 19 19:20:00 2015 -0700
> # Node ID a005a978678ae5bbfdf4cf298af5449db5d7d369
> # Parent  2748bf78a5bf610da4f2d90fd1eea19a3b360c04
> ancestors: prefetch method outside of the loop

Queued with a spurious double-blank-line dropped. Thanks!

>
> 15412bba5a68 is yet another example than this is worthwhile when it comes to
> performance, we blindly do in for all 'lazyancestors' method.
>
> diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
> --- a/mercurial/ancestor.py
> +++ b/mercurial/ancestor.py
> @@ -310,19 +310,23 @@ class lazyancestors(object):
>          if self._inclusive:
>              for rev in revs:
>                  yield rev
>              seen.update(revs)
>
> +
>          parentrevs = self._parentrevs
>          stoprev = self._stoprev
>          visit = collections.deque(revs)
>
> +        see = seen.add
> +        schedule = visit.append
> +
>          while visit:
>              for parent in parentrevs(visit.popleft()):
>                  if parent >= stoprev and parent not in seen:
> -                    visit.append(parent)
> -                    seen.add(parent)
> +                    schedule(parent)
> +                    see(parent)
>                      yield parent
>
>      def __contains__(self, target):
>          """Test whether target is an ancestor of self._initrevs."""
>          # Trying to do both __iter__ and __contains__ using the same visit
> @@ -335,20 +339,21 @@ class lazyancestors(object):
>          parentrevs = self._parentrevs
>          visit = self._containsvisit
>          stoprev = self._stoprev
>          heappop = heapq.heappop
>          heappush = heapq.heappush
> +        see = seen.add
>
>          targetseen = False
>
>          while visit and -visit[0] > target and not targetseen:
>              for parent in parentrevs(-heappop(visit)):
>                  if parent < stoprev or parent in seen:
>                      continue
>                  # We need to make sure we push all parents into the heap so
>                  # that we leave it in a consistent state for future calls.
>                  heappush(visit, -parent)
> -                seen.add(parent)
> +                see(parent)
>                  if parent == target:
>                      targetseen = True
>
>          return targetseen
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> https://selenic.com/mailman/listinfo/mercurial-devel

Patch

diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
--- a/mercurial/ancestor.py
+++ b/mercurial/ancestor.py
@@ -310,19 +310,23 @@  class lazyancestors(object):
         if self._inclusive:
             for rev in revs:
                 yield rev
             seen.update(revs)
 
+
         parentrevs = self._parentrevs
         stoprev = self._stoprev
         visit = collections.deque(revs)
 
+        see = seen.add
+        schedule = visit.append
+
         while visit:
             for parent in parentrevs(visit.popleft()):
                 if parent >= stoprev and parent not in seen:
-                    visit.append(parent)
-                    seen.add(parent)
+                    schedule(parent)
+                    see(parent)
                     yield parent
 
     def __contains__(self, target):
         """Test whether target is an ancestor of self._initrevs."""
         # Trying to do both __iter__ and __contains__ using the same visit
@@ -335,20 +339,21 @@  class lazyancestors(object):
         parentrevs = self._parentrevs
         visit = self._containsvisit
         stoprev = self._stoprev
         heappop = heapq.heappop
         heappush = heapq.heappush
+        see = seen.add
 
         targetseen = False
 
         while visit and -visit[0] > target and not targetseen:
             for parent in parentrevs(-heappop(visit)):
                 if parent < stoprev or parent in seen:
                     continue
                 # We need to make sure we push all parents into the heap so
                 # that we leave it in a consistent state for future calls.
                 heappush(visit, -parent)
-                seen.add(parent)
+                see(parent)
                 if parent == target:
                     targetseen = True
 
         return targetseen