list-objects: only look at cmdline trees with edge_hintjk/mark-edges-uninteresting

When rev-list is given a command-line like:

  git rev-list --objects $commit --not --all

the most accurate answer is the difference between the set
of objects reachable from $commit and the set reachable from
all of the existing refs. However, we have not historically
provided that answer, because it is very expensive to
calculate. We would have to open every tree of every commit
in the entire history.

Instead, we find the accurate set difference of the
reachable commits, and then mark the trees at the boundaries
as uninteresting. This misses objects which appear in the
trees of both the interesting commits and deep within the
uninteresting history.

Commit fbd4a70 (list-objects: mark more commits as edges in
mark_edges_uninteresting, 2013-08-16) noticed that we miss
those objects during pack-objects, and added code to examine
the trees of all of the "--not" refs given on the
command-line.  Note that this is still not the complete set
difference, because we look only at the tips of the
command-line arguments, not all of their reachable commits.
But it increases the set of boundary objects we consider,
which is especially important for shallow fetches.  So we
are trading extra CPU time for a larger set of boundary
objects, which can improve the resulting pack size for a
--thin pack.

This tradeoff probably makes sense in the context of
pack-objects, where we have set revs->edge_hint to have the
traversal feed us the set of boundary objects.  For a
regular rev-list, though, it is probably not a good
tradeoff. It is true that it makes our list slightly closer
to a true set difference, but it is a rare case where this
is important. And because we do not have revs->edge_hint
set, we do nothing useful with the larger set of boundary
objects.

This patch therefore ties the extra tree examination to the
revs->edge_hint flag; it is the presence of that flag that
makes the tradeoff worthwhile.

Here is output from the p0001-rev-list showing the
improvement in performance:

Test                                             HEAD^             HEAD
-----------------------------------------------------------------------------------------
0001.1: rev-list --all                           0.69(0.65+0.02)   0.69(0.66+0.02) +0.0%
0001.2: rev-list --all --objects                 3.22(3.19+0.03)   3.23(3.20+0.03) +0.3%
0001.4: rev-list $commit --not --all             0.04(0.04+0.00)   0.04(0.04+0.00) +0.0%
0001.5: rev-list --objects $commit --not --all   0.27(0.26+0.01)   0.04(0.04+0.00) -85.2%

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 11 insertions, 9 deletions

diff --git a/list-objects.c b/list-objects.c
index 05c8c5c616..8b39b50c22 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -163,15 +163,17 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)
 		}
 		mark_edge_parents_uninteresting(commit, revs, show_edge);
 	}
-	for (i = 0; i < revs->cmdline.nr; i++) {
-		struct object *obj = revs->cmdline.rev[i].item;
-		struct commit *commit = (struct commit *)obj;
-		if (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))
-			continue;
-		mark_tree_uninteresting(commit->tree);
-		if (revs->edge_hint && !(obj->flags & SHOWN)) {
-			obj->flags |= SHOWN;
-			show_edge(commit);
+	if (revs->edge_hint) {
+		for (i = 0; i < revs->cmdline.nr; i++) {
+			struct object *obj = revs->cmdline.rev[i].item;
+			struct commit *commit = (struct commit *)obj;
+			if (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))
+				continue;
+			mark_tree_uninteresting(commit->tree);
+			if (!(obj->flags & SHOWN)) {
+				obj->flags |= SHOWN;
+				show_edge(commit);
+			}
 		}
 	}
 }