revision: use generation for A..B --topo-order queries
authorDerrick Stolee <>
Tue, 21 May 2019 13:14:38 +0000 (09:14 -0400)
committerJunio C Hamano <>
Tue, 28 May 2019 17:39:47 +0000 (10:39 -0700)
If a commit-graph exists with computed generation numbers, then a
'git rev-list --topo-order -n <N> <rev>' query will use those generation
numbers to reduce the number of commits walked before writing N commits.

One caveat put in b454241 (revision.c: generation-based topo-order
algorithm, 2018-11-01) was to not enable the new algorithm for queries
with a revision range "A..B". The logic was placed to walk from "A" and
mark those commits as uninteresting, but the performance was actually
worse than the existing logic in some cases.

The root cause of this performance degradation is that generation
numbers _increase_ the number of commits we walk relative to the
existing heuristic of walking by commit date. While generation numbers
actually guarantee that the algorithm is correct, the existing logic
is very rarely wrong and that added requirement is not worth the cost.

This motivates the planned "corrected commit date" to replace
generation numbers in a future version of Git.

The current change enables the logic to use whatever reachability
index is currently in the commit-graph (generation numbers or
corrected commit date).

The limited flag in struct rev_info forces a full walk of the
commit history (after discovering the A..B range). Previosuly, it
is enabled whenever we see an uninteresting commit. We prevent
enabling the parameter when we are planning to use the reachability
index for a topo-order.

Signed-off-by: Derrick Stolee <>
Signed-off-by: Junio C Hamano <>

index d4aaf0e..be6ccf5 100644 (file)
@@ -436,7 +436,9 @@ static struct commit *handle_commit(struct rev_info *revs,
                        die("unable to parse commit %s", name);
                if (flags & UNINTERESTING) {
                        die("unable to parse commit %s", name);
                if (flags & UNINTERESTING) {
-                       revs->limited = 1;
+                       if (!revs->topo_order || !generation_numbers_enabled(the_repository))
+                               revs->limited = 1;
                if (revs->sources) {
                        char **slot = revision_sources_at(revs->sources, commit);
                if (revs->sources) {
                        char **slot = revision_sources_at(revs->sources, commit);