commit-graph: avoid unnecessary tag deference when merging

In my testing environment, this improves the time to "merge" a split commit-graph containing all reachable commits in the kernel by re-writing the same commit-graph (effectively measuring the time it takes to check that all of those commits still exist) from:

Attempt 1: 9.614
Attempt 2: 10.984
Attempt 3: 10.39
Attempt 4: 9.14
Attempt 5: 9.439

real 0m9.140s
user 0m8.207s
sys 0m0.602s

to:

Attempt 1: 9.12
Attempt 2: 8.904
Attempt 3: 9.361
Attempt 4: 9.288
Attempt 5: 9.677

real 0m8.904s
user 0m8.208s
sys 0m0.596s

yielding a modest ~2.6% improvement in the best timings from each run, and ~7.4% improvement on average.

Quoted 23 lines · Taylor Blau

In my testing environment, this improves the time to "merge" a split commit-graph containing all reachable commits in the kernel by re-writing the same commit-graph (effectively measuring the time it takes to check that all of those commits still exist) from:

Attempt 1: 9.614
Attempt 2: 10.984
Attempt 3: 10.39
Attempt 4: 9.14
Attempt 5: 9.439

real 0m9.140s
user 0m8.207s
sys 0m0.602s

to:

Attempt 1: 9.12
Attempt 2: 8.904
Attempt 3: 9.361
Attempt 4: 9.288
Attempt 5: 9.677

Quoted 6 lines

real 0m8.904s
user 0m8.208s
sys 0m0.596s

yielding a modest ~2.6% improvement in the best timings from each run, and ~7.4% improvement on average.

That still seems really slow to me. If we were truly eliding the load of most of the commit objects, I'd expect an order of magnitude or so improvement. For example, with a fully constructed commit graph in linux.git, I get:

  $ time git -c core.commitGraph=1 rev-list HEAD | wc -l
  886922

real 0m1.088s
user 0m0.659s
sys 0m1.161s

  $ time git -c core.commitGraph=0 rev-list HEAD | wc -l
  886922

real 0m7.185s
user 0m6.729s
sys 0m1.882s

Obviously not the same operation, but that should give us a rough idea that commit graph lookups are 6-7 times cheaper than loading the actual objects. I don't remember the details of the case that originally led us towards this patch. Can you share more of the setup you used to generate the numbers above (which repo, but more importantly the commands to create the initial state and then time the test).

The patch otherwise still makes sense to me, but I suspect there are other similar optimizations nearby that we'll need to do in tandem.

-Peff

Quoted 51 lines · Jeff King

Quoted 23 lines · Taylor Blau

In my testing environment, this improves the time to "merge" a split commit-graph containing all reachable commits in the kernel by re-writing the same commit-graph (effectively measuring the time it takes to check that all of those commits still exist) from:

Attempt 1: 9.614
Attempt 2: 10.984
Attempt 3: 10.39
Attempt 4: 9.14
Attempt 5: 9.439

real 0m9.140s
user 0m8.207s
sys 0m0.602s

to:

Attempt 1: 9.12
Attempt 2: 8.904
Attempt 3: 9.361
Attempt 4: 9.288
Attempt 5: 9.677

Quoted 6 lines

real 0m8.904s
user 0m8.208s
sys 0m0.596s

yielding a modest ~2.6% improvement in the best timings from each run, and ~7.4% improvement on average.

That still seems really slow to me. If we were truly eliding the load of most of the commit objects, I'd expect an order of magnitude or so improvement. For example, with a fully constructed commit graph in linux.git, I get:

  $ time git -c core.commitGraph=1 rev-list HEAD | wc -l
  886922

real 0m1.088s
user 0m0.659s
sys 0m1.161s

  $ time git -c core.commitGraph=0 rev-list HEAD | wc -l
  886922

real 0m7.185s
user 0m6.729s
sys 0m1.882s

Quoted 6 lines

Obviously not the same operation, but that should give us a rough idea that commit graph lookups are 6-7 times cheaper than loading the actual objects. I don't remember the details of the case that originally led us towards this patch. Can you share more of the setup you used to generate the numbers above (which repo, but more importantly the commands to create the initial state and then time the test).

Sure. I'm running best-of-five on the time it takes to re-generate and merge a commit-graph based on in-pack commits.

The script is (in linux.git):

  $ best-of-five \
      -p 'rm -rf .git/objects/info/commit-graph{,s/}; git commit-graph write --split=no-merge 2>/dev/null' \
      git commit-graph write --split=merge-all

So we're measuring the time it takes to crawl all the packs, decide on the splitting strategy, and then compare all commits in the new merged graph to make sure that they don't already exist in the object store.

But, here's where things get... Bizarre. I was trying to come up with a way to do fewer things and spend proportionally more time in 'merge_commit_graphs', so I did something like:

- Generate a pack containing a single, empty commit.
- Generate a split commit-graph containing commits in the single large pack containing all of history.
- Generate a commit-graph of the small pack, and merge it with the large pack.

That script is:

  $ git --version
  $ git commit -m "empty" --allow-empty
  $ pack="pack-$(git rev-parse HEAD | git pack-objects .git/objects/pack/pack).idx"
  $ best-of-five \
      -p "rm -rf .git/objects/info/commit-graphs && cp -r .git/objects/info/commit-graphs{.bak,}" \
      sh -c "echo $pack | git commit-graph write --split=merge-all"

but things get... slower with this patch? Here are the results before and after:

Attempt 1: 8.444
Attempt 2: 8.453
Attempt 3: 8.391
Attempt 4: 8.376
Attempt 5: 7.859

real 0m7.859s
user 0m7.309s
sys 0m0.511s

vs:

Attempt 1: 8.69
Attempt 2: 8.735
Attempt 3: 8.619
Attempt 4: 8.747
Attempt 5: 8.695

real 0m8.619s
user 0m8.030s
sys 0m0.538s

Without more profiling, I'm puzzled by why this patch seems to make things *worse* under this scenario.

So, I'd appreciate your thoughts: does this set-up seem reasonable? Is it introducing some latency that isn't being accounted for in the original setup?

Quoted 4 lines

The patch otherwise still makes sense to me, but I suspect there are other similar optimizations nearby that we'll need to do in tandem.

-Peff

Thanks,
Taylor

Sure. I'm running best-of-five on the time it takes to re-generate and merge a commit-graph based on in-pack commits.

The script is (in linux.git):

  $ best-of-five \
      -p 'rm -rf .git/objects/info/commit-graph{,s/}; git commit-graph write --split=no-merge 2>/dev/null' \
      git commit-graph write --split=merge-all

But, here's where things get... Bizarre. I was trying to come up with a way to do fewer things and spend proportionally more time in 'merge_commit_graphs', so I did something like:

- Generate a pack containing a single, empty commit.
- Generate a split commit-graph containing commits in the single large pack containing all of history.
- Generate a commit-graph of the small pack, and merge it with the large pack.

That script is:

  $ git --version
  $ git commit -m "empty" --allow-empty
  $ pack="pack-$(git rev-parse HEAD | git pack-objects .git/objects/pack/pack).idx"
  $ best-of-five \
      -p "rm -rf .git/objects/info/commit-graphs && cp -r .git/objects/info/commit-graphs{.bak,}" \
      sh -c "echo $pack | git commit-graph write --split=merge-all"

Quoted 8 lines · Taylor Blau

Sure. I'm running best-of-five on the time it takes to re-generate and merge a commit-graph based on in-pack commits.

The script is (in linux.git):

  $ best-of-five \
      -p 'rm -rf .git/objects/info/commit-graph{,s/}; git commit-graph write --split=no-merge 2>/dev/null' \
      git commit-graph write --split=merge-all

If I build Git without your patch and run the "--split=merge-all" command under a debugger, and then break on parse_object() I find that all of the commits are already parsed. This happens in close_reachable().

So we weren't actually reading all of the commits even under the old code. We were just going into deref_tag(), seeing that the object is already parsed, and then quickly returning when we see that we already have an OBJ_COMMIT. I suspect most of your timing differences are mostly noise.

Perhaps a more interesting case is when you're _not_ adding all of the existing packed commits as input. There we'd feed only a few objects to close_reachable(), and it would stop traversing as soon as it hits a parent that's already in a graph file. So most of the existing objects would remain unparsed.

I'm not sure how to do that, though. Saying "--input=none" still puts all of those existing graphed objects into the list of oids to include. I think you'd need a case where you were legitimately only adding a few commits, but the merge rules say we need to create one big commit-graph file.

I guess --input=stdin-commits is a good way to simulate that. Try this (assuming there's already a split-graph file with all of the commits in it):

  git rev-parse HEAD >input
  time git commit-graph write --input=stdin-commits --split=merge-all <input

Without your patch on linux.git I get:

real 0m11.713s
user 0m11.349s
sys 0m0.341s

but with it I get:

real 0m2.305s
user 0m2.177s
sys 0m0.100s

A more realistic case would probably be feeding a new small pack to --input=stdin-packs.

Quoted 10 lines

But, here's where things get... Bizarre. I was trying to come up with a way to do fewer things and spend proportionally more time in 'merge_commit_graphs', so I did something like:

- Generate a pack containing a single, empty commit.
- Generate a split commit-graph containing commits in the single large pack containing all of history.
- Generate a commit-graph of the small pack, and merge it with the large pack.

Quoted 8 lines

That script is:

  $ git --version
  $ git commit -m "empty" --allow-empty
  $ pack="pack-$(git rev-parse HEAD | git pack-objects .git/objects/pack/pack).idx"
  $ best-of-five \
      -p "rm -rf .git/objects/info/commit-graphs && cp -r .git/objects/info/commit-graphs{.bak,}" \
      sh -c "echo $pack | git commit-graph write --split=merge-all"

I think you'd need --stdin-packs in the actual timed command?

At any rate, I think there is a demonstrable speedup there. But moreover, I'm pretty sure this existing code is not doing what it expects:

/* only add commits if they still exist in the repo */ result = lookup_commit_reference_gently(ctx->r, &oid, 1);

That won't look at the object database at all if the commit is already marked as parsed. And that parsing might have come from the commit graph itself, as our earlier attempts showed. So switching to a real has_object_file() call is an important _correctness_ fix, even leaving aside the speed improvements.

-Peff

Quoted 5 lines

I'm not sure how to do that, though. Saying "--input=none" still puts all of those existing graphed objects into the list of oids to include. I think you'd need a case where you were legitimately only adding a few commits, but the merge rules say we need to create one big commit-graph file.

You have to be careful, since we're taking the reachability closure over any commits that you do give. So, one thing you could do to ensure that you have an actually small graph is to take something from the output of 'git rev-list --max-parents=0 HEAD'.

To try and reproduce your results, I used '1da177e4c3', which is the kernel's first commit in Git. If my interpretation of your setup is faithful, it goes something like:

  $ graphdir=.git/objects/info/commit-graphs
  $ git rev-parse 1da177e4c3 |
    git commit-graph write --split=no-merge --stdin-commits
  $ cp -r "$graphdir{,.bak}"

  $ best-of-five -p "rm -rf $graphdir && cp -r $graphdir{.bak,}" \
    'git commit-graph write --split=merge-all'

Where the last step is taking all commits listed in any pack, which is cheap to iterate.

In the above setup, I get something like:

git version 2.26.0.rc2.221.ge327a58236
Attempt 1: 16.933
Attempt 2: 18.101
Attempt 3: 17.603
Attempt 4: 20.404
Attempt 5: 18.871

real 0m16.933s
user 0m16.440s
sys 0m0.472s

versus:

git version 2.26.0.rc2.222.g295e7905ee
Attempt 1: 5.34
Attempt 2: 4.623
Attempt 3: 5.263
Attempt 4: 5.268
Attempt 5: 5.606

real 0m4.623s
user 0m4.428s
sys 0m0.176s

which is a best-case savings of ~72.7%, and a savings of ~71.5%. That seems much better.

The "--input=none" option
isn't "no input"; it's actually "take all existing graphed objects as input" (i.e., it implies --append). So each of those objects will already have been examined in an earlier stage.

Quoted 2 lines

Where the last step is taking all commits listed in any pack, which is cheap to iterate.

I'm not sure it's all that cheap. It has to find the type of every object in every pack. And finding types involves walking delta chains.

Quoted 5 lines

Quoted 2 lines

Where the last step is taking all commits listed in any pack, which is cheap to iterate.

I'm not sure it's all that cheap. It has to find the type of every object in every pack. And finding types involves walking delta chains.

Indeed, that's just about the most expensive way to find all commits, in my experience it can be well over a magnitude slower than '--reachable'.

3. To find the type of a delta object, we have to walk back to a base object with a concrete type. When we access the actual object contents, we cache intermediate bases to avoid digging down the same chain over and over. But I don't think there's any such cache for the type lookup. So if you have a 50-deep delta chain and want the type of each object, you'll walk down 49 links, then 48 links, and so on. It probably wouldn't be that hard to have a small type cache (or just allow the existing cache to have entries for "I know the type, but don't have the contents").

I suspect (1) would give the biggest speedup, but is more work and requires bitmaps. I think (3) is likely to give a moderate win and probably isn't that big a patch.

Quoted 4 lines · Jeff King

The "--input=none" option
isn't "no input"; it's actually "take all existing graphed objects as input" (i.e., it implies --append). So each of those objects will already have been examined in an earlier stage.

Yeah, we discussed it earlier that '--input=none' doesn't properly describe what it tries to accomplish, and suggested '--input=exists' (or was it 'existing'?) instead.

Quoted 5 lines

Quoted 2 lines

Where the last step is taking all commits listed in any pack, which is cheap to iterate.

I'm not sure it's all that cheap. It has to find the type of every object in every pack. And finding types involves walking delta chains.

Indeed, that's just about the most expensive way to find all commits, in my experience it can be well over a magnitude slower than '--reachable'.

Quoted 10 lines · Taylor Blau

Quoted 5 lines

I'm not sure how to do that, though. Saying "--input=none" still puts all of those existing graphed objects into the list of oids to include. I think you'd need a case where you were legitimately only adding a few commits, but the merge rules say we need to create one big commit-graph file.

You have to be careful, since we're taking the reachability closure over any commits that you do give. So, one thing you could do to ensure that you have an actually small graph is to take something from the output of 'git rev-list --max-parents=0 HEAD'.

I don't think you need to be that careful, though. In split-mode, close_reachable() will stop traversing when it finds a graphed commit. That's why using the tip of HEAD in my previous example worked.

Quoted 11 lines

To try and reproduce your results, I used '1da177e4c3', which is the kernel's first commit in Git. If my interpretation of your setup is faithful, it goes something like:

  $ graphdir=.git/objects/info/commit-graphs
  $ git rev-parse 1da177e4c3 |
    git commit-graph write --split=no-merge --stdin-commits
  $ cp -r "$graphdir{,.bak}"

  $ best-of-five -p "rm -rf $graphdir && cp -r $graphdir{.bak,}" \
    'git commit-graph write --split=merge-all'

My case is the opposite, isn't it? Here it looks like you've made a very _tiny_ commit-graph file (with one commit), and then you're going to end up adding in all of the new objects. I don't think it would be improved much by this patch (which makes me very confused by the numbers you got below).

I also don't think it's that interesting a real-world case.

The more interesting one is where you do already have a big commit-graph, and want to add just a bit more to it. In the real world, that might look something like this:

  # create a fake server repo
  git clone --bare . dst.git

  # imagine the server already has everything in a graph file
  git -C dst.git commit-graph write --split=no-merge --reachable

  # and now do a small push
  git commit --allow-empty -m foo
  git push dst.git

  # the server might do an incremental immediately to cover the new
  # objects; here we'll use --stdin-commits with the new data, but a
  # real server might feed the new packfile. We'd probably just use
  # regular --split here in practice, but let's imagine that we're
  # starting to have a lot of graph files, and that triggers a desire to
  # merge. We'll force that state with --split=merge-all.
  git rev-list HEAD^..HEAD |
  git -C dst.git commit-graph write --split=merge-all --stdin-commits

Without your patch, that takes ~11s for me. With it, it takes ~2s.

Another equally interesting case is if the per-push generation _doesn't_ merge anything, and just creates a new, tiny graph file. And then later we want to do a real maintenance, merging them all done. I think that would be something like:

  git -C dst.git commit-graph write --input=none --split=merge-all

But that _isn't_ improved by your patch. For the simple reason that all of the commits will already have been parsed. The "--input=none" option isn't "no input"; it's actually "take all existing graphed objects as input" (i.e., it implies --append). So each of those objects will already have been examined in an earlier stage.

Quoted 2 lines

Where the last step is taking all commits listed in any pack, which is cheap to iterate.

I'm not sure it's all that cheap. It has to find the type of every object in every pack. And finding types involves walking delta chains. That's something like 7s on my machine for linux.git (compared to the 2s in which I can just merge down the existing graph files).

Quoted 26 lines

In the above setup, I get something like:

git version 2.26.0.rc2.221.ge327a58236
Attempt 1: 16.933
Attempt 2: 18.101
Attempt 3: 17.603
Attempt 4: 20.404
Attempt 5: 18.871

real 0m16.933s
user 0m16.440s
sys 0m0.472s

versus:

git version 2.26.0.rc2.222.g295e7905ee
Attempt 1: 5.34
Attempt 2: 4.623
Attempt 3: 5.263
Attempt 4: 5.268
Attempt 5: 5.606

real 0m4.623s
user 0m4.428s
sys 0m0.176s

Quoted 2 lines

which is a best-case savings of ~72.7%, and a savings of ~71.5%. That seems much better.

I'm still puzzled by this. In the setup you showed, hardly anything is graphed. But the change is only in the graph-merge code.

-Peff

So, I'm not sure what was going on with my original measurements, other than that I took them around midnight, so the chance for error was probably high. I'll go with your measurements, since they are both closer to what we'd see in the real world, and actually representative of the change here.

So we weren't actually reading all of the commits even under the old code. We were just going into deref_tag(), seeing that the object is already parsed, and then quickly returning when we see that we already have an OBJ_COMMIT. I suspect most of your timing differences are mostly noise.

I guess --input=stdin-commits is a good way to simulate that. Try this (assuming there's already a split-graph file with all of the commits in it):

git rev-parse HEAD >input
time git commit-graph write --input=stdin-commits --split=merge-all <input
...
A more realistic case would probably be feeding a new small pack to --input=stdin-packs.

At any rate, I think there is a demonstrable speedup there. But moreover, I'm pretty sure this existing code is not doing what it expects:

/* only add commits if they still exist in the repo */ result = lookup_commit_reference_gently(ctx->r, &oid, 1);

That won't look at the object database at all if the commit is already marked as parsed. And that parsing might have come from the commit graph itself, as our earlier attempts showed. So switching to a real has_object_file() call is an important _correctness_ fix, even leaving aside the speed improvements.

Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this codepath, by the way?

Quoted 2 lines · Junio C Hamano

Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this codepath, by the way?

I was coming back to this thread to bring up these exact flags for consideration. The good news is that in a partial clone with any amount of filtering we will still have all reachable commits, which are necessary for the commit-graph to make sense. The only ones that would fail has_object_file() are ones removed by GC, but they may still exist on the remote. So without SKIP_FETCH_OBJECT, we would generate a network call even if the server has GC'd to remove the commits. This gets particularly bad when the server returns all reachable objects from that commit!

Thanks,
-Stolee

Quoted 4 lines · Derrick Stolee

Quoted 2 lines · Junio C Hamano

Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this codepath, by the way?

Quoted 9 lines

I was coming back to this thread to bring up these exact flags for consideration. The good news is that in a partial clone with any amount of filtering we will still have all reachable commits, which are necessary for the commit-graph to make sense. The only ones that would fail has_object_file() are ones removed by GC, but they may still exist on the remote. So without SKIP_FETCH_OBJECT, we would generate a network call even if the server has GC'd to remove the commits. This gets particularly bad when the server returns all reachable objects from that commit!

That makes sense. Do you think something like this should be applied?

commit-graph.c +2 -1

index c7cfadc786..0097318798 100644
@@ -1594,6 +1594,7 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,
 {
        uint32_t i;
        uint32_t offset = g->num_commits_in_base;
+       int flags = OBJECT_INFO_QUICK | OBJECT_INFO_SKIP_FETCH_OBJECT;
 
        ALLOC_GROW(ctx->commits.list, ctx->commits.nr + g->num_commits, ctx->commits.alloc);
 

@@ -1606,7 +1607,7 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,
                load_oid_from_graph(g, i + offset, &oid);
 
                /* only add commits if they still exist in the repo */
-               if (repo_has_object_file(ctx->r, &oid)) {
+               if (repo_has_object_file_with_flags(ctx->r, &oid, flags)) {
                        result = lookup_commit(ctx->r, &oid);
                        if (repo_parse_commit(ctx->r, result))
                                result = NULL;

Quoted 15 lines · Taylor Blau

Quoted 13 lines · Derrick Stolee

Quoted 2 lines · Junio C Hamano

Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this codepath, by the way?

I was coming back to this thread to bring up these exact flags for consideration. The good news is that in a partial clone with any amount of filtering we will still have all reachable commits, which are necessary for the commit-graph to make sense. The only ones that would fail has_object_file() are ones removed by GC, but they may still exist on the remote. So without SKIP_FETCH_OBJECT, we would generate a network call even if the server has GC'd to remove the commits. This gets particularly bad when the server returns all reachable objects from that commit!

Quoted 2 lines

That makes sense. Do you think something like this should be applied?
+ int flags = OBJECT_INFO_QUICK | OBJECT_INFO_SKIP_FETCH_OBJECT;

[...]

Yes, I think this is the appropriate update. Thanks!

[1] I'm actually not quite sure about correctness here. It should be fine to generate a graph file without any given commit; readers will just have to load that commit the old-fashioned way. But at this phase of "commit-graph write", I think we'll already have done the close_reachable() check. What does it mean to throw away a commit at this stage? If we're the parent of another commit, then it will have trouble referring to us by a uint32_t. Will the actual writing phase barf, or will we generate an invalid graph file?

Quoted 8 lines · Jeff King

[1] I'm actually not quite sure about correctness here. It should be fine to generate a graph file without any given commit; readers will just have to load that commit the old-fashioned way. But at this phase of "commit-graph write", I think we'll already have done the close_reachable() check. What does it mean to throw away a commit at this stage? If we're the parent of another commit, then it will have trouble referring to us by a uint32_t. Will the actual writing phase barf, or will we generate an invalid graph file?

It doesn't seem great. If I instrument Git like this to simulate an object temporarily "missing" (if it were really missing the whole repo would be corrupt; we're trying to see what would happen if a race causes us to momentarily not see it):

commit-graph.c +18 -0

index 3da52847e4..71419c2532 100644
@@ -1596,6 +1596,19 @@ static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)
 	}
 }
 
+static int pretend_commit_is_missing(const struct object_id *oid)
+{
+	static int initialized;
+	static struct object_id missing;
+	if (!initialized) {
+		const char *x = getenv("PRETEND_COMMIT_IS_MISSING");
+		if (x)
+			get_oid_hex(x, &missing);
+		initialized = 1;
+	}
+	return oideq(&missing, oid);
+}
+
 static void merge_commit_graph(struct write_commit_graph_context *ctx,
 			       struct commit_graph *g)
 {

@@ -1612,6 +1625,11 @@ static void merge_commit_graph(struct write_commit_graph_context *ctx,
 
 		load_oid_from_graph(g, i + offset, &oid);
 
+		if (pretend_commit_is_missing(&oid)) {
+			warning("pretending %s is missing", oid_to_hex(&oid));
+			continue;
+		}
+
 		/* only add commits if they still exist in the repo */
 		result = lookup_commit_reference_gently(ctx->r, &oid, 1);
 

and then I make a fully-graphed repo like this:

  git init repo
  cd repo
  for i in $(seq 10); do
    git commit --allow-empty -m $i
  done
  git commit-graph write --input=reachable --split=no-merge

if we pretend a parent is missing, I get a BUG():

  $ git rev-parse HEAD |
    PRETEND_COMMIT_IS_MISSING=$(git rev-parse HEAD^) \
    git commit-graph write --stdin-commits --split=merge-all
  warning: pretending 35e6e15c738cf2bfbe495957b2a941c2efe86dd9 is missing
  BUG: commit-graph.c:879: missing parent 35e6e15c738cf2bfbe495957b2a941c2efe86dd9 for commit d4141fb57a9bbe26b247f23c790d63d078977833
  Aborted

So it seems like just skipping here (either with the new patch or without) isn't really a good strategy.

-Peff

Quoted 9 lines

Quoted 8 lines

[1] I'm actually not quite sure about correctness here. It should be fine to generate a graph file without any given commit; readers will just have to load that commit the old-fashioned way. But at this phase of "commit-graph write", I think we'll already have done the close_reachable() check. What does it mean to throw away a commit at this stage? If we're the parent of another commit, then it will have trouble referring to us by a uint32_t. Will the actual writing phase barf, or will we generate an invalid graph file?

Quoted 4 lines

It doesn't seem great. If I instrument Git like this to simulate an object temporarily "missing" (if it were really missing the whole repo would be corrupt; we're trying to see what would happen if a race causes us to momentarily not see it):

This is definitely a problem on either side of this patch, which is demonstrated by the fact that you applied your changes without my patch on top (and that my patch isn't changing anything substantial in this area like removing the 'continue' statement).

Should we address this before moving on with my patch? I think that we *could*, but I'd rather go forward with what we have for now, since it's only improving the situation, and not introducing a new bug.

Quoted 14 lines · Taylor Blau

Quoted 9 lines

Quoted 8 lines

[1] I'm actually not quite sure about correctness here. It should be fine to generate a graph file without any given commit; readers will just have to load that commit the old-fashioned way. But at this phase of "commit-graph write", I think we'll already have done the close_reachable() check. What does it mean to throw away a commit at this stage? If we're the parent of another commit, then it will have trouble referring to us by a uint32_t. Will the actual writing phase barf, or will we generate an invalid graph file?

Quoted 4 lines

It doesn't seem great. If I instrument Git like this to simulate an object temporarily "missing" (if it were really missing the whole repo would be corrupt; we're trying to see what would happen if a race causes us to momentarily not see it):

Quoted 8 lines

This is definitely a problem on either side of this patch, which is demonstrated by the fact that you applied your changes without my patch on top (and that my patch isn't changing anything substantial in this area like removing the 'continue' statement).

Should we address this before moving on with my patch? I think that we *could*, but I'd rather go forward with what we have for now, since it's only improving the situation, and not introducing a new bug.

I do agree it's a problem before your patch. But I think your patch may make it a lot more common, if only because it means we'd _actually_ be dropping entries for objects that went away, instead of accidentally keeping them due to re-using the graph result. So it probably is worth trying to deal with it now, or at least thinking hard about it.

The trouble is that I'm not sure what _should_ happen. Aborting the whole commit-graph generation seems overboard (and would be annoying for cases where whole swaths of history became unreachable and went away; presumably we'd be dropping _all_ of those objects, and the write phase would be just fine). I have a feeling the correct solution is to do this merging pass earlier, before we check close_reachable(). Or if not a true merging pass, at least a pass to check which existing entries are still valid. But I don't know how painful that reordering would be.

-Peff

Quoted 8 lines

The trouble is that I'm not sure what _should_ happen. Aborting the whole commit-graph generation seems overboard (and would be annoying for cases where whole swaths of history became unreachable and went away; presumably we'd be dropping _all_ of those objects, and the write phase would be just fine). I have a feeling the correct solution is to do this merging pass earlier, before we check close_reachable(). Or if not a true merging pass, at least a pass to check which existing entries are still valid. But I don't know how painful that reordering would be.

Maybe, but I'm not sure that moving 'close_reachable' up would necessarily solve all of our problems. Or, at least, that it wouldn't create a set of new problems :).

Let's say that you have (1) some connected component of your history that is written to a commit-graph, where (2) part of that cluster has been dropped (e.g., due to corruption, a rogue 'git gc', etc), and (3) you're writing a new graph with '--input=graphed'.

What is 'close_reachable' supposed to do? If some of the now-missing commits are in the reachability closure of the commits that still exist in the repository, then we're back to where we started. We *could* have 'close_reachable' take all missing commits and drop their ancestors and descendants, but this creates quite the headache for 'close_reachable', which now needs to keep track of such things.

I'm hopeful that this isn't so common in practice, but I'm also not entirely sure one way or another. I can plan to deploy this patch to GitHub's servers for a ~month and see if we experience it. If it turns out to be common, I'll assume that others have this problem, too, in which case we can go back and think more about it.

I can plan to deploy this patch to GitHub's servers for a ~month and see if we experience it.

Quoted 2 lines · Taylor Blau

I can plan to deploy this patch to GitHub's servers for a ~month and see if we experience it.

...I don't think we'll actually generate good data here. We're probably going to end up doing our "big maintenance" commit-graph roll-ups by just feeding --reachable as input, and dropping all of the existing graphs.

-Peff

Quoted 16 lines · Derrick Stolee

Quoted 15 lines · Taylor Blau

Quoted 13 lines · Derrick Stolee

Quoted 2 lines · Junio C Hamano

Do we need to worry about INFO_QUICK and SKIP_FETCH_OBJECT in this codepath, by the way?

I was coming back to this thread to bring up these exact flags for consideration. The good news is that in a partial clone with any amount of filtering we will still have all reachable commits, which are necessary for the commit-graph to make sense. The only ones that would fail has_object_file() are ones removed by GC, but they may still exist on the remote. So without SKIP_FETCH_OBJECT, we would generate a network call even if the server has GC'd to remove the commits. This gets particularly bad when the server returns all reachable objects from that commit!

Quoted 5 lines

Quoted 2 lines

That makes sense. Do you think something like this should be applied?
+ int flags = OBJECT_INFO_QUICK | OBJECT_INFO_SKIP_FETCH_OBJECT;

[...]

Yes, I think this is the appropriate update. Thanks!

I'm not so sure.

In a non-partial clone, when would expect QUICK to matter? If we find the object is missing, then either:

- we are racing with repack, and we would benefit from double-checking that the object really is gone

- we used to have it (since it was mentioned in the graph file) but it went away

Using QUICK means we won't waste time double-checking in the second case. But it means we won't catch the first case, and we may generate a new graph file that omits the object. They're both optimizations, and I don't think we're impacting correctness[1], but it's not clear to me whether one is a win over the other. We don't generally expect objects we have to go away often.

Skipping fetching seems a little more straight-forward to me. If we had it in a graph file, presumably we had the actual object before, too. And either we're in the first case above (we really do have it and just need to double-check) in which case not saying QUICK would be enough. Or we intentionally got rid of it. In which case downloading it just to generate a cache is quite silly.

So it seems like SKIP_FETCH_OBJECT but _not_ QUICK might be reasonable here.

-Peff

[1] I'm actually not quite sure about correctness here. It should be fine to generate a graph file without any given commit; readers will just have to load that commit the old-fashioned way. But at this phase of "commit-graph write", I think we'll already have done the close_reachable() check. What does it mean to throw away a commit at this stage? If we're the parent of another commit, then it will have trouble referring to us by a uint32_t. Will the actual writing phase barf, or will we generate an invalid graph file?

Quoted 7 lines

Using QUICK means we won't waste time double-checking in the second case. But it means we won't catch the first case, and we may generate a new graph file that omits the object. They're both optimizations, and I don't think we're impacting correctness[1], but it's not clear to me whether one is a win over the other. We don't generally expect objects we have to go away often.

Quoted 6 lines

Skipping fetching seems a little more straight-forward to me. If we had it in a graph file, presumably we had the actual object before, too. And either we're in the first case above (we really do have it and just need to double-check) in which case not saying QUICK would be enough. Or we intentionally got rid of it. In which case downloading it just to generate a cache is quite silly.

I was going to write that I'm not entirely sure of this, but I tried to talk myself through it below, and I think that the right flag is *only* OBJECT_INFO_SKIP_FETCH_OBJECT.

When performing a 'git commit-graph write' with '--split', the commit-graph machinery calls 'merge_commit_graph()' after deciding on a split strategy to optionally clean up any existing commit-graph layers that were made obsolete by the split strategy [1].

At this time, 'merge_commit_graph()' checks each commit that it writes into the merged graph to make sure that it still exists in the object store.

To do this, it uses 'lookup_commit_reference_gently()', which accepts either a commit object, or a tag that refers to a commit. However, since all 'oid' arguments passed to this function are from within the commit-graphs being merged, we never pass a commit reference, and so any time we spend in 'deref_tag()' is wasted.

commit-graph.c +6 -2

 	for (i = 0; i < g->num_commits; i++) {
 		struct object_id oid;
-		struct commit *result;
+		struct commit *result = NULL;
 
 		display_progress(ctx->progress, i + 1);
 
 		load_oid_from_graph(g, i + offset, &oid);
 
 		/* only add commits if they still exist in the repo */
-		result = lookup_commit_reference_gently(ctx->r, &oid, 1);
+		if (repo_has_object_file(ctx->r, &oid)) {
+			result = lookup_commit(ctx->r, &oid);
+			if (repo_parse_commit(ctx->r, result))
+				result = NULL;
+		}
 
 		if (result) {
 			ctx->commits.list[ctx->commits.nr] = result;

This patch avoids an unnecessary tag dereference in 'merge_commit_graph()', which can improve the running time of a commit-graph write by around ~7.4% on average.

Quoted 3 lines · Taylor Blau

This patch avoids an unnecessary tag dereference in 'merge_commit_graph()', which can improve the running time of a commit-graph write by around ~7.4% on average.

That I suspect depends heavily on what portion of your total committishes consist of tags, no (in an absurdly extreme case, if there is no tag in the repository, there won't be any improvement)?

What tag-vs-commit ratio is the above "average" number based on?

Quoted 10 lines · Junio C Hamano

Quoted 3 lines · Taylor Blau

This patch avoids an unnecessary tag dereference in 'merge_commit_graph()', which can improve the running time of a commit-graph write by around ~7.4% on average.

That I suspect depends heavily on what portion of your total committishes consist of tags, no (in an absurdly extreme case, if there is no tag in the repository, there won't be any improvement)?

Quoted 1 line

What tag-vs-commit ratio is the above "average" number based on?

I think the point is that in this code path we've already identified the candidates as commits (because they were in an existing commit-graph file), so treating the items as a committishes in the first place is unnecessary. If an object isn't itself a commit, we should be dropping it from the proposed output (possibly we ought to give a warning in such a case, too, as it indicates the previous writer did something wrong).

-Peff