On 12/29/2019 1:12 AM, Jeff King wrote:

On Fri, Dec 27, 2019 at 09:51:02AM -0500, Derrick Stolee wrote:

quoted

On 12/22/2019 4:32 AM, Jeff King wrote:

quoted

Looking at the diff of commit objects in pack order is much faster than
in sha1 order, as it gives locality to the access of tree deltas
(whereas sha1 order is effectively random). Unfortunately the
commit-graph code sorts the commits (several times, sometimes as an oid
and sometimes a pointer-to-commit), and we ultimately traverse in sha1
order.

Instead, let's remember the position at which we see each commit, and
traverse in that order when looking at bloom filters. This drops my time
for "git commit-graph write --changed-paths" in linux.git from ~4
minutes to ~1.5 minutes.

I'm doing my own perf tests on these patches, and my copy of linux.git
has four packs of varying sizes (corresponding with my rare fetches and
lack of repacks). My time goes from 3m50s to 3m00s. I was confused at
first, but then realized that I used the "--reachable" flag. In that
case, we never run set_commit_pos(), so all positions are equal and the
sort is not helpful.

I thought that inserting some set_commit_pos() calls into close_reachable()
and add_missing_parents() would give some amount of time-order to the
commits as we compute the filters. However, the time did not change at
all.

I've included the patch below for reference, anyway.

Yeah, I expected that would cover it, too. But instrumenting it to dump
the position of each commit (see patch below), and then decorating "git
log" output with the positions (see script below) shows that we're all
over the map:

  *   3
  |\  
  | * 2791
  | * 5476
  | * 8520
  | * 12040
  | * 16036
  * |   2790
  |\ \  
  | * | 5475
  | * | 8519
  | * | 12039
  | * | 16035
  | * | 20517
  | * | 25527
  | |/  
  * |   5474
  |\ \  
  | * | 8518
  | * | 12038
  * | |   8517
  [...]

This makes a lot of sense why the previous approach did not work. Thanks!

I think the root issue is that we never do any date-sorting on the
commits. So:

  - we hit each ref tip in lexical order; with tags, this is quite often
    the opposite of reverse-chronological

  - we traverse breadth-first, but we don't order queue at all. So if we
    see a merge X, then we'll next process X^1 and X^2, and then X^1^,
    and then X^2^, and so forth. So we keep digging equally down
    simultaneous branches, even if one branch is way shorter than the
    other. Whereas a regular Git traversal will order the queue by
    commit timestamp, so it tends to be roughly chronological (of course
    a topo-sort would work too, but that's probably overkill).

I wonder if this would be simpler if "commit-graph --reachable" just
used the regular revision machinery instead of doing its own custom
traversal.

Instead, why not use our already-computed generation numbers? That seems
to improve the time a bit. (6m30s to 4m50s)

-->8--

From: Derrick Stolee <redacted>
Date: Fri, 27 Dec 2019 09:47:49 -0500
Subject: [PATCH] commit-graph: examine commits by generation number

When running 'git commit-graph write --changed-paths', we sort the
commits by pack-order to save time when computing the changed-paths
bloom filters. This does not help when finding the commits via the
--reachable flag.

If not using pack-order, then sort by generation number before
examining the diff. Commits with similar generation are more likely
to have many trees in common, making the diff faster.

On the Linux kernel repository, this change reduced the computation
time for 'git commit-graph write --reachable --changed-paths' from
6m30s to 4m50s.

Helped-by: Jeff King [off-list ref]
Signed-off-by: Derrick Stolee <redacted>
---
 commit-graph.c | 33 ++++++++++++++++++++++++++++++---
 1 file changed, 30 insertions(+), 3 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index bf6c663772..fe4ab545f2 100644
--- a/commit-graph.c
+++ b/commit-graph.c

@@ -72,6 +72,25 @@ static int commit_pos_cmp(const void *va, const void *vb)
 	       commit_pos_at(&commit_pos, b);
 }
 
+static int commit_gen_cmp(const void *va, const void *vb)
+{
+	const struct commit *a = *(const struct commit **)va;
+	const struct commit *b = *(const struct commit **)vb;
+
+	/* lower generation commits first */
+	if (a->generation < b->generation)
+		return -1;
+	else if (a->generation > b->generation)
+		return 1;
+
+	/* use date as a heuristic when generations are equal */
+	if (a->date < b->date)
+		return -1;
+	else if (a->date > b->date)
+		return 1;
+	return 0;
+}
+
 char *get_commit_graph_filename(const char *obj_dir)
 {
 	char *filename = xstrfmt("%s/info/commit-graph", obj_dir);

@@ -849,7 +868,8 @@ struct write_commit_graph_context {
 		 report_progress:1,
 		 split:1,
 		 check_oids:1,
-		 bloom:1;
+		 bloom:1,
+		 order_by_pack:1;
 
 	const struct split_commit_graph_opts *split_opts;
 	uint32_t total_bloom_filter_size;

@@ -1245,7 +1265,11 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)
 
 	ALLOC_ARRAY(sorted_by_pos, ctx->commits.nr);
 	COPY_ARRAY(sorted_by_pos, ctx->commits.list, ctx->commits.nr);
-	QSORT(sorted_by_pos, ctx->commits.nr, commit_pos_cmp);
+
+	if (ctx->order_by_pack)
+		QSORT(sorted_by_pos, ctx->commits.nr, commit_pos_cmp);
+	else
+		QSORT(sorted_by_pos, ctx->commits.nr, commit_gen_cmp);
 
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = sorted_by_pos[i];

@@ -1979,6 +2003,7 @@ int write_commit_graph(const char *obj_dir,
 	}
 
 	if (pack_indexes) {
+		ctx->order_by_pack = 1;
 		if ((res = fill_oids_from_packs(ctx, pack_indexes)))
 			goto cleanup;
 	}

@@ -1988,8 +2013,10 @@ int write_commit_graph(const char *obj_dir,
 			goto cleanup;
 	}
 
-	if (!pack_indexes && !commit_hex)
+	if (!pack_indexes && !commit_hex) {
+		ctx->order_by_pack = 1;
 		fill_oids_from_all_packs(ctx);
+	}
 
 	close_reachable(ctx);
 

-- 
2.25.0.rc0