| Message ID | 20191222093206.GA3460818@coredump.intra.peff.net (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | [1/3] commit-graph: examine changed-path objects in pack order | expand |
On 12/22/2019 4:32 AM, Jeff King wrote: > 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. Thanks, -Stolee -->8-- From e7c63d8db09be81ce213ba7f112bb3d2f537bf4a Mon Sep 17 00:00:00 2001 From: Derrick Stolee <dstolee@microsoft.com> Date: Fri, 27 Dec 2019 09:47:49 -0500 Subject: [PATCH] commit-graph: set commit positions for --reachable 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. Add calls to set_commit_pos() when walking the reachable commits, which provides an ordering similar to a topological ordering. Unfortunately, the performance did not improve with this change. Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- commit-graph.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/commit-graph.c b/commit-graph.c index bf6c663772..a6c4ab401e 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -1126,6 +1126,8 @@ static void add_missing_parents(struct write_commit_graph_context *ctx, struct c oidcpy(&ctx->oids.list[ctx->oids.nr], &(parent->item->object.oid)); ctx->oids.nr++; parent->item->object.flags |= REACHABLE; + + set_commit_pos(ctx->r, &parent->item->object.oid); } } } @@ -1142,8 +1144,10 @@ static void close_reachable(struct write_commit_graph_context *ctx) for (i = 0; i < ctx->oids.nr; i++) { display_progress(ctx->progress, i + 1); commit = lookup_commit(ctx->r, &ctx->oids.list[i]); - if (commit) + if (commit) { commit->object.flags |= REACHABLE; + set_commit_pos(ctx->r, &commit->object.oid); + } } stop_progress(&ctx->progress);
On Fri, Dec 27, 2019 at 09:51:02AM -0500, Derrick Stolee wrote: > On 12/22/2019 4:32 AM, Jeff King wrote: > > 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 [...] 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. -Peff
On Sun, Dec 29, 2019 at 01:12:46AM -0500, Jeff King wrote: > 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: I forgot the patch, of course. :) I just dumped this trace: --- diff --git a/commit-graph.c b/commit-graph.c index a6c4ab401e..1cb77be45f 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -61,6 +61,7 @@ static void set_commit_pos(struct repository *r, const struct object_id *oid) if (!commit) return; /* should never happen, but be lenient */ + trace_printf("pos %s = %d", oid_to_hex(oid), max_pos); *commit_pos_at(&commit_pos, commit) = max_pos++; } with: rm -f .git/objects/info/commit-graph GIT_TRACE=$PWD/trace.out git commit-graph write --changed-paths --reachable and then used: cat >foo.pl <<\EOF #!/usr/bin/perl my %deco = do { open(my $fh, '<', 'trace.out'); map { /pos (\S+) = (\d+)/ ? ($1 => $2) : () } <$fh> }; while (<>) { s/([0-9a-f]{40})/$deco{$1}/; print; } EOF like so: git log --graph --format=%H | perl foo.pl | less -Peff
On 12/29/2019 1:12 AM, Jeff King wrote: > On Fri, Dec 27, 2019 at 09:51:02AM -0500, Derrick Stolee wrote: > >> On 12/22/2019 4:32 AM, Jeff King wrote: >>> 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 <dstolee@microsoft.com> 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 <peff@peff.net> Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- 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);
On 12/30/2019 9:37 AM, Derrick Stolee wrote: > On the Linux kernel repository, this change reduced the computation > time for 'git commit-graph write --reachable --changed-paths' from > 6m30s to 4m50s. I apologize, these numbers are based on the AzureDevOps repo, not the Linux kernel repo. After re-running with the Linux kernel repo my times improve from 3m00s to 1m37s. -Stolee
diff --git a/commit-graph.c b/commit-graph.c index 0580ce75d5..bf6c663772 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -17,6 +17,7 @@ #include "replace-object.h" #include "progress.h" #include "bloom.h" +#include "commit-slab.h" #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */ #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */ @@ -48,6 +49,29 @@ /* Remember to update object flag allocation in object.h */ #define REACHABLE (1u<<15) +/* Keep track of the order in which commits are added to our list. */ +define_commit_slab(commit_pos, int); +static struct commit_pos commit_pos = COMMIT_SLAB_INIT(1, commit_pos); + +static void set_commit_pos(struct repository *r, const struct object_id *oid) +{ + static int32_t max_pos; + struct commit *commit = lookup_commit(r, oid); + + if (!commit) + return; /* should never happen, but be lenient */ + + *commit_pos_at(&commit_pos, commit) = max_pos++; +} + +static int commit_pos_cmp(const void *va, const void *vb) +{ + const struct commit *a = *(const struct commit **)va; + const struct commit *b = *(const struct commit **)vb; + return commit_pos_at(&commit_pos, a) - + commit_pos_at(&commit_pos, b); +} + char *get_commit_graph_filename(const char *obj_dir) { char *filename = xstrfmt("%s/info/commit-graph", obj_dir); @@ -1088,6 +1112,8 @@ static int add_packed_commits(const struct object_id *oid, oidcpy(&(ctx->oids.list[ctx->oids.nr]), oid); ctx->oids.nr++; + set_commit_pos(ctx->r, oid); + return 0; } @@ -1208,6 +1234,7 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) { int i; struct progress *progress = NULL; + struct commit **sorted_by_pos; load_bloom_filters(); @@ -1216,13 +1243,18 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) _("Computing commit diff Bloom filters"), ctx->commits.nr); + 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); + for (i = 0; i < ctx->commits.nr; i++) { - struct commit *c = ctx->commits.list[i]; + struct commit *c = sorted_by_pos[i]; struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1); ctx->total_bloom_filter_size += sizeof(uint64_t) * filter->len; display_progress(progress, i + 1); } + free(sorted_by_pos); stop_progress(&progress); }
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. Probably the "--reachable" code path would want something similar. Or alternatively, we could use a different data structure (either a hash, or maybe even just a bit in "struct commit") to keep track of which oids we've seen, etc instead of sorting. And then we could keep the original order. Signed-off-by: Jeff King <peff@peff.net> --- commit-graph.c | 34 +++++++++++++++++++++++++++++++++- 1 file changed, 33 insertions(+), 1 deletion(-)