[StGIT PATCH 0/4] Optimizations for the DAG appliedness stuff

[StGIT PATCH 0/4] Optimizations for the DAG appliedness stuff

[Karl Hasselström]

The DAG appliedness series incurred a serious slowdown when it had to
recompute the set of uninteresting commits from scratch. (This is the
set of commits that are parents of patch commits, but not ancestors of
any patch commit. They are used to make DAG appliedness operations
fast.)

The patches in this series fall into two categories:

  * Making the recomputation-from-scratch (slightly) faster.

  * Reducing the number of situations where the
    recomputation-from-scratch has to be done.

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

[StGIT PATCH 1/4] Speed up the discovery of uninteresting commits

[Karl Hasselström]

The operation of discovering uninteresting commits (that is, all the
commits that immediately precede a patch but don't have any patch
among their ancestors) is expensive. Make it less so, by using the
fact that we're done as soon as we've seen all patch commits.

This is probably less of a win than might be naively expected, since
we give the --topo-order flag to git-rev-list, which causes it to have
to read the full DAG to even start producing the output; but at least
we skip quite a bit of looping and set manipulation in Python, which
ought to be worth _something_.

Signed-off-by: Karl Hasselström <kha@treskal.com>

---

 stgit/stack.py |   10 ++++++++--
 1 files changed, 8 insertions(+), 2 deletions(-)

diff --git a/stgit/stack.py b/stgit/stack.py
index 1b6808e..d3756d0 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -472,11 +472,17 @@ class UninterestingCache:
                 for p in parents:
                     if not p in interesting:
                         uninteresting.add(p)
-                continue
+
+                # If this is the last patch commit, there is no way we
+                # can encounter any more uninteresting commits.
+                patches.remove(commit)
+                if not patches:
+                    break
 
             # Commits with interesting parents are interesting.
-            if interesting.intersection(parents):
+            elif interesting.intersection(parents):
                 interesting.add(commit)
+
         self.__uninteresting = uninteresting
         out.done()
     def create_patch(self, name, top, bottom):

[StGIT PATCH 2/4] Speed up appliedness check during patch creation

[Karl Hasselström]

When we create a new patch commit that isn't next to an existing patch
commit (which occurs e.g. every time we push the first patch onto a
stack), we do a full recalculation of the set of uninteresting
commits. However, if we know that the new patch refers to a new
commit, we only have to see if this new commit can reach any existing
patch, which is a much cheaper operation.

Signed-off-by: Karl Hasselström <kha@treskal.com>

---

 stgit/stack.py |   54 ++++++++++++++++++++++++++++++++++++++++++------------
 1 files changed, 42 insertions(+), 12 deletions(-)

diff --git a/stgit/stack.py b/stgit/stack.py
index d3756d0..8f1c0ee 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -485,9 +485,13 @@ class UninterestingCache:
 
         self.__uninteresting = uninteresting
         out.done()
-    def create_patch(self, name, top, bottom):
+    def create_patch(self, name, top, bottom, new_commit):
         """The given patch has been created. Update the uninterested
-        state to maintain the invariant."""
+        state to maintain the invariant.
+
+        If new_commit is true, the caller is promising that top is a
+        new commit that isn't reachable from any of the previously
+        existing uninteresting commits."""
         if not self.__cache_file():
             return # not cached
 
@@ -507,6 +511,28 @@ class UninterestingCache:
         if bottom in bottoms or bottom in tops or top in bottoms:
             return
 
+        if new_commit:
+            # The caller has promised us that no existing
+            # uninteresting commit reaches the new patch, which means
+            # that they are all still valid. Now all we have to do is
+            # decide whether to add the new patch's bottom to the set
+            # of uninteresting commits.
+            ref2hash = read_refs(self.__series.get_name())
+            patches = Set([sha1 for ref, sha1 in ref2hash.iteritems() if ref])
+            for commit in git._output_lines('git-rev-list --stdin %s' % bottom,
+                                          ['^%s\n' % u for u in
+                                           self.__uninteresting]):
+                if commit in patches:
+                    # The bottom of the new patch reaches another
+                    # patch, and so isn't uninteresting.
+                    return
+
+            # The bottom of the new patch doesn't reach any other
+            # patch, so it must be uninteresting.
+            self.__uninteresting.add(bottom)
+            self.__write_file()
+            return
+
         # The new patch is not adjacent to an existing patch. We'd
         # need to first get rid of any uninteresting commit that
         # reaches this patch, and then mark the patch's bottom
@@ -619,16 +645,17 @@ class AppliedCache:
                 self.__write_patchorder()
                 return
         raise StackException, 'Unknown patch "%s"' % oldname
-    def new(self, name, top, bottom):
+    def new(self, name, top, bottom, new_commit):
         """Create new patch."""
-        self.__uninteresting.create_patch(name, top, bottom)
+        self.__uninteresting.create_patch(name, top, bottom, new_commit)
     def delete(self, name, top, bottom):
         """Delete a patch."""
         self.__uninteresting.delete_patch(name, top, bottom)
-    def change(self, name, old_top, old_bottom, new_top, new_bottom):
+    def change(self, name, old_top, old_bottom, new_top, new_bottom,
+               new_commit):
         """Change a patch."""
         if (new_top, new_bottom) != (old_top, old_bottom):
-            self.new(name, new_top, new_bottom)
+            self.new(name, new_top, new_bottom, new_commit)
             self.delete(name, old_top, old_bottom)
     def __write_patchorder(self):
         self.__order.set_patchorder(self.get_applied() + self.get_unapplied())
@@ -1128,7 +1155,7 @@ class Series(PatchSet):
         if patch.restore_old_boundaries():
             self.log_patch(patch, 'undo')
         self.__applied_cache.change(name, curr_top, curr_bottom,
-                                    old_top, old_bottom)
+                                    old_top, old_bottom, new_commit = False)
 
     def new_patch(self, name, message = None, can_edit = True,
                   unapplied = False, show_patch = False,
@@ -1163,7 +1190,6 @@ class Series(PatchSet):
 
         bottom = bottom or head
         top = top or head
-        self.__applied_cache.new(name, top, bottom)
 
         patch.set_bottom(bottom)
         patch.set_top(top)
@@ -1197,10 +1223,12 @@ class Series(PatchSet):
                                    committer_name = committer_name,
                                    committer_email = committer_email)
             # set the patch top to the new commit
+            top = commit_id
             patch.set_top(commit_id)
 
         self.log_patch(patch, 'new')
 
+        self.__applied_cache.new(name, top, bottom, new_commit = commit)
         self.__applied_cache.set_patchorder(order)
         return patch
 
@@ -1291,7 +1319,7 @@ class Series(PatchSet):
 
                     self.__applied_cache.change(
                         name, old_top = old_top, old_bottom = bottom,
-                        new_top = top, new_bottom = head)
+                        new_top = top, new_bottom = head, new_commit = True)
                     self.log_patch(patch, 'push(f)')
                 else:
                     top = head
@@ -1349,7 +1377,8 @@ class Series(PatchSet):
             # need an empty commit
             patch.set_bottom(head, backup = True)
             patch.set_top(head, backup = True)
-            self.__applied_cache.change(name, top, bottom, head, head)
+            self.__applied_cache.change(name, top, bottom, head, head,
+                                        new_commit = False)
             modified = True
         elif head == bottom:
             # reset the backup information. No need for logging
@@ -1362,7 +1391,8 @@ class Series(PatchSet):
             # The current patch is empty after merge.
             patch.set_bottom(head, backup = True)
             patch.set_top(head, backup = True)
-            self.__applied_cache.change(name, top, bottom, head, head)
+            self.__applied_cache.change(name, top, bottom, head, head,
+                                        new_commit = False)
 
             # Try the fast applying first. If this fails, fall back to the
             # three-way merge
@@ -1422,7 +1452,7 @@ class Series(PatchSet):
         self.pop_patch(name)
         ret = patch.restore_old_boundaries()
         self.__applied_cache.change(name, curr_top, curr_bottom,
-                                    old_top, old_bottom)
+                                    old_top, old_bottom, new_commit = False)
         if ret:
             self.log_patch(patch, 'undo')
 

[StGIT PATCH 3/4] Don't traverse the whole DAG when looking for uninteresting commits

[Karl Hasselström]

It's sufficient to look at the part of the DAG that's reachable from
the patches. This might be a large subset, of course, but it could
still be a significant improvement in some cases, especially when
there is only one patch.

Signed-off-by: Karl Hasselström <kha@treskal.com>

---

 stgit/stack.py |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/stgit/stack.py b/stgit/stack.py
index 8f1c0ee..dbb27eb 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -459,7 +459,8 @@ class UninterestingCache:
         # Iterate over all commits. We are guaranteed to see each
         # commit before any of its children.
         for line in git._output_lines(
-            'git-rev-list --topo-order --reverse --parents --all'):
+            'git-rev-list --topo-order --reverse --parents --stdin',
+            ['%s\n' % p for p in patches]):
             commits = line.split()
             commit, parents = commits[0], Set(commits[1:])
 

[StGIT PATCH 4/4] Find uninteresting commits faster for special cases

[Karl Hasselström]

For the special cases of zero or one patch, the set of uninteresting
commits is very cheap to find.

Signed-off-by: Karl Hasselström <kha@treskal.com>

---

 stgit/stack.py |   28 +++++++++++++++++++++++-----
 1 files changed, 23 insertions(+), 5 deletions(-)

diff --git a/stgit/stack.py b/stgit/stack.py
index dbb27eb..b00a024 100644
--- a/stgit/stack.py
+++ b/stgit/stack.py
@@ -449,15 +449,27 @@ class UninterestingCache:
         self.__compute_uninteresting()
         self.__write_file()
     def __compute_uninteresting(self):
-        """Compute a reasonable set of uninteresting commits from
-        scratch. This is expensive."""
-        out.start('Finding uninteresting commits')
+        """Compute the set of uninteresting commits from scratch. This
+        is expensive in the general case; therefore, we print a
+        message to the user."""
         ref2hash = read_refs(self.__series.get_name())
         patches = Set([sha1 for ref, sha1 in ref2hash.iteritems() if ref])
-        interesting, uninteresting = Set(), Set()
+
+        # Optimize some important special cases.
+        if len(patches) == 0:
+            self.__uninteresting = Set()
+            return
+        elif len(patches) == 1:
+            patch = iter(patches).next()
+            commit, parent = git._output_one_line(
+                'git-rev-list --parents %s' % patch).split()
+            self.__uninteresting = Set([parent])
+            return
 
         # Iterate over all commits. We are guaranteed to see each
         # commit before any of its children.
+        out.start('Finding uninteresting commits')
+        interesting, uninteresting = Set(), Set()
         for line in git._output_lines(
             'git-rev-list --topo-order --reverse --parents --stdin',
             ['%s\n' % p for p in patches]):
@@ -483,7 +495,6 @@ class UninterestingCache:
             # Commits with interesting parents are interesting.
             elif interesting.intersection(parents):
                 interesting.add(commit)
-
         self.__uninteresting = uninteresting
         out.done()
     def create_patch(self, name, top, bottom, new_commit):
@@ -496,6 +507,13 @@ class UninterestingCache:
         if not self.__cache_file():
             return # not cached
 
+        # If there are no existing uninteresting commits, this is the
+        # first patch, so its bottom has to be uninteresting.
+        if not self.__uninteresting:
+            self.__uninteresting.add(bottom)
+            self.__write_file()
+            return
+
         # New patch inserted just below an existing bottommost patch:
         # need to move the uninteresting commit down one step.
         if top in self.__uninteresting: