list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: Derrick Stolee <>
Cc:,,,, Derrick Stolee <>
Subject: [PATCH] revision: use generation for A..B --topo-order queries
Date: Tue, 21 May 2019 09:14:38 -0400	[thread overview]
Message-ID: <> (raw)
In-Reply-To: <>

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 <>


If you have the chance, then please apply this patch (on v2.22.0-rc1)
and re-run your test. This will confirm if my thoughts on this matter
are correct.


 revision.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/revision.c b/revision.c
index d4aaf0ef25..be6ccf5786 100644
--- a/revision.c
+++ b/revision.c
@@ -436,7 +436,9 @@ static struct commit *handle_commit(struct rev_info *revs,
 			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);

  parent reply	other threads:[~2019-05-21 13:14 UTC|newest]

Thread overview: 23+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-05-18  0:54 Revision walking, commit dates, slop Mike Hommey
2019-05-18  1:50 ` SZEDER Gábor
2019-05-18  3:58   ` Mike Hommey
2019-05-18  4:17     ` Mike Hommey
2019-05-18 12:01       ` SZEDER Gábor
2019-05-19 22:28         ` Jakub Narebski
2019-05-20  1:33       ` Derrick Stolee
2019-05-20 11:02         ` Jakub Narebski
2019-05-20 11:20           ` Derrick Stolee
2019-05-20 13:42             ` Jakub Narebski
2019-05-20 23:27               ` Jakub Narebski
2019-05-21  1:20                 ` Derrick Stolee
2019-05-22 18:29                   ` Jakub Narebski
2019-05-22 19:06                     ` Derrick Stolee
2019-05-23 21:04                       ` Jakub Narebski
2019-06-25  7:51               ` Jakub Narebski
2019-06-25 10:54                 ` Derrick Stolee
2019-09-18  8:43                   ` [RFC/PATCH] commit-graph: generation v5 (backward compatible date ceiling) Jakub Narebski
2019-09-18 12:26                     ` Derrick Stolee
2019-05-21 13:14         ` Derrick Stolee [this message]
2019-05-21 13:59           ` [PATCH 2/2] revision: keep topo-walk free of unintersting commits Derrick Stolee
2019-05-22  2:19             ` Mike Hommey
2019-05-21  2:00   ` Revision walking, commit dates, slop Jonathan Nieder

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

  List information:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \ \ \ \
    --subject='Re: [PATCH] revision: use generation for A..B --topo-order queries' \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Code repositories for project(s) associated with this inbox:

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).