Compute and consume generation numbers

Most code paths load commits using lookup_commit() and then parse_commit(). In some cases, including some branch lookups, the commit is parsed using parse_object_buffer() which side-steps parse_commit() in favor of parse_commit_buffer().

Before adding generation numbers to the commit-graph, we need to ensure that any commit that exists in the graph is loaded from the graph, so check parse_commit_in_graph() before calling parse_commit_buffer().

Signed-off-by Derrick Stolee <[email protected]>

Quoted 10 lines · On Tue, 3 Apr 2018 12:51:38 -0400 Derrick Stolee <[email protected]> wrote:

Most code paths load commits using lookup_commit() and then parse_commit(). In some cases, including some branch lookups, the commit is parsed using parse_object_buffer() which side-steps parse_commit() in favor of parse_commit_buffer().

Before adding generation numbers to the commit-graph, we need to ensure that any commit that exists in the graph is loaded from the graph, so check parse_commit_in_graph() before calling parse_commit_buffer().

Signed-off-by Derrick Stolee <[email protected]>

Modifying parse_object_buffer() is the most pragmatic way to accomplish this, but this also means that parse_object_buffer() now potentially reads from the local object store (instead of only relying on what's in memory and what's in the provided buffer). parse_object_buffer() is called by several callers including in builtin/fsck.c. I would feel more comfortable if the relevant [1] caller to parse_object_buffer() was modified instead of parse_object_buffer(), but I'll let others give their opinions too.

Quoted 13 lines · Jonathan Tan

Quoted 10 lines · On Tue, 3 Apr 2018 12:51:38 -0400 Derrick Stolee <[email protected]> wrote:

Most code paths load commits using lookup_commit() and then parse_commit(). In some cases, including some branch lookups, the commit is parsed using parse_object_buffer() which side-steps parse_commit() in favor of parse_commit_buffer().

Before adding generation numbers to the commit-graph, we need to ensure that any commit that exists in the graph is loaded from the graph, so check parse_commit_in_graph() before calling parse_commit_buffer().

Signed-off-by Derrick Stolee <[email protected]>

Quoted 8 lines

Modifying parse_object_buffer() is the most pragmatic way to accomplish this, but this also means that parse_object_buffer() now potentially reads from the local object store (instead of only relying on what's in memory and what's in the provided buffer). parse_object_buffer() is called by several callers including in builtin/fsck.c. I would feel more comfortable if the relevant [1] caller to parse_object_buffer() was modified instead of parse_object_buffer(), but I'll let others give their opinions too.

It's not just you. This seems like a really odd place to put it. Especially because if we have the buffer to pass to this function, then we'd already have incurred the cost to inflate the object.

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Add a uint32_t generation field to struct commit so we can pass this

information to revision walks. We use two special values to signal the generation number is invalid:

GENERATION_NUMBER_UNDEF 0xFFFFFFFF
GENERATION_NUMBER_NONE 0

The first (_UNDEF) means the generation number has not been loaded or computed. The second (_NONE) means the generation number was loaded from a commit graph file that was stored before generation numbers were computed.

Signed-off-by Derrick Stolee <[email protected]>

---
 alloc.c        | 1 +
 commit-graph.c | 2 ++
 commit.h       | 3 +++
 3 files changed, 6 insertions(+)

alloc.c +1 -0

index cf4f8b61e1..1a62e85ac3 100644
@@ -94,6 +94,7 @@ void *alloc_commit_node(void)
 	c->object.type = OBJ_COMMIT;
 	c->index = alloc_commit_index();
 	c->graph_pos = COMMIT_NOT_FROM_GRAPH;
+	c->generation = GENERATION_NUMBER_UNDEF;
 	return c;
 }
 

commit-graph.c +2 -0

index 1fc63d541b..d24b947525 100644
@@ -264,6 +264,8 @@ static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uin
 	date_low = get_be32(commit_data + g->hash_len + 12);
 	item->date = (timestamp_t)((date_high << 32) | date_low);
 
+	item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
+
 	pptr = &item->parents;
 
 	edge_value = get_be32(commit_data + g->hash_len);

commit.h +3 -0

index e57ae4b583..3cadd386f3 100644
@@ -10,6 +10,8 @@
 #include "pretty.h"
 
 #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF
+#define GENERATION_NUMBER_UNDEF 0xFFFFFFFF
+#define GENERATION_NUMBER_NONE 0
 
 struct commit_list {
 	struct commit *item;

@@ -24,6 +26,7 @@ struct commit {
 	struct commit_list *parents;
 	struct tree *tree;
 	uint32_t graph_pos;
+	uint32_t generation;
 };
 
 extern int save_commit_buffer;

Signature · 1 line

2.17.0.rc0

Quoted 7 lines · Derrick Stolee

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Add a uint32_t generation field to struct commit so we can pass this

Is there any reason to believe this would be too small of a value in the future? Or is a 32 bit unsigned good enough?

Quoted 7 lines · Brandon Williams

Quoted 6 lines · Derrick Stolee

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Quoted 3 lines

Quoted 1 line

Add a uint32_t generation field to struct commit so we can pass this

Is there any reason to believe this would be too small of a value in the future? Or is a 32 bit unsigned good enough?

The linux kernel took ~10 years to produce 500k commits. Even assuming those were all linear (and they're not), that gives us ~80,000 years of leeway. So even if the pace of development speeds up or we have a quicker project, it still seems we have a pretty reasonable safety margin.

Quoted 11 lines · Brandon Williams

Quoted 7 lines · Derrick Stolee

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Add a uint32_t generation field to struct commit so we can pass this

Is there any reason to believe this would be too small of a value in the future? Or is a 32 bit unsigned good enough?

The linux kernel took ~10 years to produce 500k commits. Even assuming those were all linear (and they're not), that gives us ~80,000 years of leeway. So even if the pace of development speeds up or we have a quicker project, it still seems we have a pretty reasonable safety margin.

-Peff

Quoted 7 lines · Brandon Williams

Quoted 6 lines · Derrick Stolee

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Quoted 4 lines

Quoted 1 line

Add a uint32_t generation field to struct commit so we can pass this

Is there any reason to believe this would be too small of a value in the future? Or is a 32 bit unsigned good enough?

The linux kernel took ~10 years to produce 500k commits. Even assuming those were all linear (and they're not),

that gives us ~80,000 years of
leeway. So even if the pace of development speeds up or we have a quicker project, it still seems we have a pretty reasonable safety margin.

Quoted 9 lines · Brandon Williams

Quoted 7 lines · Derrick Stolee

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Add a uint32_t generation field to struct commit so we can pass this

Quoted 2 lines

Is there any reason to believe this would be too small of a value in the future? Or is a 32 bit unsigned good enough?

The linux kernel took ~10 years to produce 500k commits. Even assuming those were all linear (and they're not), that gives us ~80,000 years of leeway. So even if the pace of development speeds up or we have a quicker project, it still seems we have a pretty reasonable safety margin.

Quoted 8 lines

Quoted 2 lines

Is there any reason to believe this would be too small of a value in the future? Or is a 32 bit unsigned good enough?

The linux kernel took ~10 years to produce 500k commits. Even assuming those were all linear (and they're not), that gives us ~80,000 years of leeway. So even if the pace of development speeds up or we have a quicker project, it still seems we have a pretty reasonable safety margin.

I didn't read the patches closely, but isn't it ~20,000 years?

Given that '#define GENERATION_NUMBER_MAX 0x3FFFFFFF', that is. ;-)

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Add a uint32_t generation field to struct commit so we can pass this information to revision walks. We use two special values to signal the generation number is invalid:

GENERATION_NUMBER_UNDEF 0xFFFFFFFF
GENERATION_NUMBER_NONE 0

The first (_UNDEF) means the generation number has not been loaded or computed. The second (_NONE) means the generation number was loaded from a commit graph file that was stored before generation numbers were computed.

Signed-off-by Derrick Stolee <[email protected]>

commit-graph.c static void write_graph_chunk_data(struct hashfile *f, int hash_len, · line 427

Quoted 6 lines · On Tue, 3 Apr 2018 12:51:40 -0400 Derrick Stolee <[email protected]> wrote:

commit-graph.c +6 -0

+             if ((*list)->generation != GENERATION_NUMBER_UNDEF) {
+                     if ((*list)->generation > GENERATION_NUMBER_MAX)
+                             die("generation number %u is too large to store in commit-graph",
+                                 (*list)->generation);
+                     packedDate[0] |= htonl((*list)->generation << 2);
+             }

The die() should have "BUG:" if you agree with my comment below.

commit-graph.c static void close_reachable(struct packed_oid_list *oids) · line 562

Quoted 3 lines

commit-graph.c +2 -0

+static void compute_generation_numbers(struct commit** commits,
+                                    int nr_commits)

Style: space before **, not after.

commit-graph.c static void close_reachable(struct packed_oid_list *oids) · line 593

Quoted 4 lines

commit-graph.c +4 -0

+                     if (all_parents_computed) {
+                             current->generation = max_generation + 1;
+                             pop_commit(&list);
+                     }

I think the current->generation should be clamped to _MAX here. If we do, then the die() I mentioned in my first comment will have "BUG:", since we are never meant to write any number larger than _MAX in ->generation.

Define compare_commits_by_gen_then_commit_date(), which uses generation numbers as a primary comparison and commit date to break ties (or as a comparison when both commits do not have computed generation numbers).

Since the commit-graph file is closed under reachability, we know that all commits in the file have generation at most GENERATION_NUMBER_MAX which is less than GENERATION_NUMBER_UNDEF.

This change does not affect the number of commits that are walked during the execution of paint_down_to_common(), only the order that those commits are inspected. In the case that commit dates violate topological order (i.e. a parent is "newer" than a child), the previous code could walk a commit twice: if a commit is reached with the PARENT1 bit, but later is re-visited with the PARENT2 bit, then that PARENT2 bit must be propagated to its parents. Using generation numbers avoids this extra effort, even if it is somewhat rare.

commit.c +6 -0

+int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)
+{
+	const struct commit *a = a_, *b = b_;
+
+	if (a->generation < b->generation)
+		return 1;

We now calculate generation numbers in the commit-graph file and use them in paint_down_to_common().

This is the first of several "small" patches that follow the serialized Git commit graph patch (ds/commit-graph).

As described in Documentation/technical/commit-graph.txt, the generation number of a commit is one more than the maximum generation number among its parents (trivially, a commit with no parents has generation number one).

This series makes the computation of generation numbers part of the commit-graph write process.

Finally, generation numbers are used to order commits in the priority queue in paint_down_to_common(). This allows a constant-time check in queue_has_nonstale() instead of the previous linear-time check.

This does not have a significant performance benefit in repositories of normal size, but in the Windows repository, some merge-base calculations improve from 3.1s to 2.9s. A modest speedup, but provides an actual consumer of generation numbers as a starting point.

A more substantial refactoring of revision.c is required before making 'git log --graph' use generation numbers effectively.

This patch series depends on v7 of ds/commit-graph.

Derrick Stolee (6):
object.c: parse commit in graph first
commit: add generation number to struct commmit
commit-graph: compute generation numbers
commit: sort by generation number in paint_down_to_common() commit.c: use generation number to stop merge-base walks commit-graph.txt: update design doc with generation numbers

This is the first of several "small" patches that follow the serialized Git commit graph patch (ds/commit-graph).

As described in Documentation/technical/commit-graph.txt, the generation number of a commit is one more than the maximum generation number among its parents (trivially, a commit with no parents has generation number one).

This series makes the computation of generation numbers part of the commit-graph write process.

Finally, generation numbers are used to order commits in the priority queue in paint_down_to_common(). This allows a constant-time check in queue_has_nonstale() instead of the previous linear-time check.

This does not have a significant performance benefit in repositories of normal size, but in the Windows repository, some merge-base calculations improve from 3.1s to 2.9s. A modest speedup, but provides an actual consumer of generation numbers as a starting point.

A more substantial refactoring of revision.c is required before making 'git log --graph' use generation numbers effectively.

This patch series depends on v7 of ds/commit-graph.

Derrick Stolee (6):
object.c: parse commit in graph first
commit: add generation number to struct commmit
commit-graph: compute generation numbers
commit: sort by generation number in paint_down_to_common() commit.c: use generation number to stop merge-base walks commit-graph.txt: update design doc with generation numbers

 Documentation/technical/commit-graph.txt |  7 +---
 alloc.c                                  |  1 +
 commit-graph.c                           | 48 +++++++++++++++++++++
 commit.c                                 | 53 ++++++++++++++++++++----
 commit.h                                 |  7 +++-
 object.c                                 |  4 +-
 6 files changed, 104 insertions(+), 16 deletions(-)

Signature · 1 line

2.17.0.20.g9f30ba16e1

Quoted 7 lines · Derrick Stolee

This is the first of several "small" patches that follow the serialized Git commit graph patch (ds/commit-graph).

As described in Documentation/technical/commit-graph.txt, the generation number of a commit is one more than the maximum generation number among its parents (trivially, a commit with no parents has generation number one).

Thanks for ensuring that this is defined and documented somewhere :)

Quoted 12 lines

This series makes the computation of generation numbers part of the commit-graph write process.

Finally, generation numbers are used to order commits in the priority queue in paint_down_to_common(). This allows a constant-time check in queue_has_nonstale() instead of the previous linear-time check.

This does not have a significant performance benefit in repositories of normal size, but in the Windows repository, some merge-base calculations improve from 3.1s to 2.9s. A modest speedup, but provides an actual consumer of generation numbers as a starting point.

Quoted 2 lines

A more substantial refactoring of revision.c is required before making 'git log --graph' use generation numbers effectively.

log --graph should benefit a lot more from this correct? I know we've talked a bit about negotiation and I wonder if these generation numbers should be able to help out a little bit with that some day.

If we have generic "can X reach Y?" queries, then we can also use generation numbers there to great effect (by not walking commits Z with gen(Z) <= gen(Y)). Perhaps I should look at that "git branch --contains" thread for ideas.

Quoted 4 lines · Derrick Stolee

If we have generic "can X reach Y?" queries, then we can also use generation numbers there to great effect (by not walking commits Z with gen(Z) <= gen(Y)). Perhaps I should look at that "git branch --contains" thread for ideas.

I think the gist of it is the patch below. Which I hastily adapted from the patch we run at GitHub that uses timestamps as a proxy. So it's possible I completely flubbed the logic. I'm assuming unavailable generation numbers are set to 0; the logic is actually a bit simpler if they end up as (uint32_t)-1.

The containment algorithm for 'git branch --contains' is different from that for 'git tag --contains' in that it uses is_descendant_of() instead of contains_tag_algo(). The expensive portion of the branch algorithm is computing merge bases.

When a commit-graph file exists with generation numbers computed, we can avoid this merge-base calculation when the target commit has a larger generation number than the target commits.

Performance tests were run on a copy of the Linux repository where HEAD is contained in v4.13 but no earlier tag. Also, all tags were copied to branches and 'git branch --contains' was tested:

Before: 60.0s
After: 0.4s
Rel %: -99.3%

Reported-by Jeff King <[email protected]>

Signed-off-by Derrick Stolee <[email protected]>

---
  commit.c | 9 ++++++++-
  1 file changed, 8 insertions(+), 1 deletion(-)

commit.c +2 -1

index 858f4fdbc9..2566cba79f 100644
@@ -1059,12 +1059,19 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *
  {
  	struct commit_list *bases;
  	int ret = 0, i;
+	uint32_t min_generation = GENERATION_NUMBER_UNDEF;
 
  	if (parse_commit(commit))
  		return ret;
-	for (i = 0; i < nr_reference; i++)
+	for (i = 0; i < nr_reference; i++) {
  		if (parse_commit(reference[i]))

Quoted 9 lines · Derrick Stolee

The containment algorithm for 'git branch --contains' is different from that for 'git tag --contains' in that it uses is_descendant_of() instead of contains_tag_algo(). The expensive portion of the branch algorithm is computing merge bases.

When a commit-graph file exists with generation numbers computed, we can avoid this merge-base calculation when the target commit has a larger generation number than the target commits.

Quoted 7 lines

Performance tests were run on a copy of the Linux repository where HEAD is contained in v4.13 but no earlier tag. Also, all tags were copied to branches and 'git branch --contains' was tested:

Before: 60.0s
After: 0.4s
Rel %: -99.3%

Quoted 19 lines

commit.c +6 -1

index 858f4fdbc9..2566cba79f 100644
@@ -1059,12 +1059,19 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *
  {
  	struct commit_list *bases;
  	int ret = 0, i;
+	uint32_t min_generation = GENERATION_NUMBER_UNDEF;
  	if (parse_commit(commit))
  		return ret;
-	for (i = 0; i < nr_reference; i++)
+	for (i = 0; i < nr_reference; i++) {
  		if (parse_commit(reference[i]))
  			return ret;
+		if (min_generation > reference[i]->generation)
+			min_generation = reference[i]->generation;
+	}
+

commit.c int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit * · line 1077

Quoted 4 lines

commit.c +2 -0

+	if (commit->generation > min_generation)
+		return 0;
  	bases = paint_down_to_common(commit, nr_reference, reference);
  	if (commit->object.flags & PARENT2)

This patch may suffice to speed up 'git branch --contains' instead of needing to always use the 'git tag --contains' algorithm as considered in [1].

Quoted 18 lines · Derrick Stolee

Quoted 18 lines

commit.c +5 -1

index 858f4fdbc9..2566cba79f 100644
@@ -1059,12 +1059,19 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *
   {
   	struct commit_list *bases;
   	int ret = 0, i;
+	uint32_t min_generation = GENERATION_NUMBER_UNDEF;
   	if (parse_commit(commit))
   		return ret;
-	for (i = 0; i < nr_reference; i++)
+	for (i = 0; i < nr_reference; i++) {
   		if (parse_commit(reference[i]))
   			return ret;
+		if (min_generation > reference[i]->generation)
+			min_generation = reference[i]->generation;
+	}

Quoted 8 lines

commit.c int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit * · line 1077

Quoted 5 lines

commit.c +3 -0

+
+	if (commit->generation > min_generation)
+		return 0;
   	bases = paint_down_to_common(commit, nr_reference, reference);
   	if (commit->object.flags & PARENT2)

This patch may suffice to speed up 'git branch --contains' instead of needing to always use the 'git tag --contains' algorithm as considered in [1].

I'd have to do some timings, but I suspect we may want to switch to the "tag --contains" algorithm anyway. This still does N independent merge-base operations, one per ref. So with enough refs, you're still better off throwing it all into one big traversal.

Quoted 4 lines

I'd have to do some timings, but I suspect we may want to switch to the "tag --contains" algorithm anyway. This still does N independent merge-base operations, one per ref. So with enough refs, you're still better off throwing it all into one big traversal.

...and I suppose your timings are to find out if there are data shapes where the branch algorithm is faster. Perhaps that is impossible now that we have the generation number cutoff for the tag algorithm.

Patches 7 and 8 seem to me like simple changes with no downside UNLESS we are deciding instead to delete the code I'm changing.

ref-filter.c +2 -1

@@ -1615,8 +1619,20 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 					      struct contains_cache *cache)
 {
 	struct contains_stack contains_stack = { 0, 0, NULL };
-	enum contains_result result = contains_test(candidate, want, cache);
+	enum contains_result result;
+	uint32_t cutoff = GENERATION_NUMBER_UNDEF;

Quoted 5 lines · Derrick Stolee

ref-filter.c +0 -1

@@ -1615,8 +1619,20 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
  					      struct contains_cache *cache)
  {
  	struct contains_stack contains_stack = { 0, 0, NULL };
-	enum contains_result result = contains_test(candidate, want, cache);

ref-filter.c static enum contains_result contains_tag_algo(struct commit *candidate, · line 1631

Quoted 10 lines

ref-filter.c +10 -0

+	enum contains_result result;
+	uint32_t cutoff = GENERATION_NUMBER_UNDEF;
+	const struct commit_list *p;
+
+	for (p = want; p; p = p->next) {
+		struct commit *c = p->item;
+		parse_commit_or_die(c);
+		if (c->generation < cutoff)
+			cutoff = c->generation;
+	}

ref-filter.c static enum contains_result contains_tag_algo(struct commit *candidate, · line 1633

Quoted 2 lines

ref-filter.c +2 -0

+	if (cutoff == GENERATION_NUMBER_UNDEF)
+		cutoff = GENERATION_NUMBER_NONE;

Hmm, on reflection, I'm not sure if this is right in the face of multiple "want" commits, only some of which have generation numbers. We probably want to disable the cutoff if _any_ "want" commit doesn't have a number.

There's also an obvious corner case where this won't kick in, and you'd really like it to: recently added commits. E.g,. if I do this:

git gc ;# imagine this writes generation numbers git pull
git tag --contains HEAD

then HEAD isn't going to have a generation number. But this is the case where we have the most to gain, since we could throw away all of the ancient tags immediately upon seeing that their generation numbers are way less than that of HEAD.

I wonder to what degree it's worth traversing to come up with a generation number for the "want" commits. If we walked, say, 50 commits to do it, you'd probably save a lot of work (since the alternative is walking thousands of commits until you realize that some ancient "v1.0" tag is not useful).

I'd actually go so far as to say that any amount of traversal is generally going to be worth it to come up with the correct generation cutoff here. You can come up with pathological cases where you only have one really recent tag or something, but in practice every repository where performance is a concern is going to end up with refs much further back than it would take to reach the cutoff condition.

Quoted 7 lines

Quoted 7 lines

ref-filter.c +2 -1

@@ -1615,8 +1619,20 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
  					      struct contains_cache *cache)
  {
  	struct contains_stack contains_stack = { 0, 0, NULL };
-	enum contains_result result = contains_test(candidate, want, cache);
+	enum contains_result result;
+	uint32_t cutoff = GENERATION_NUMBER_UNDEF;

Quoted 8 lines

ref-filter.c static enum contains_result contains_tag_algo(struct commit *candidate, · line 1631

Quoted 8 lines

ref-filter.c +8 -0

+	const struct commit_list *p;
+
+	for (p = want; p; p = p->next) {
+		struct commit *c = p->item;
+		parse_commit_or_die(c);
+		if (c->generation < cutoff)
+			cutoff = c->generation;
+	}

Now that you mention it, let me split out the portion you are probably talking about as incorrect:

Quoted 2 lines

ref-filter.c static enum contains_result contains_tag_algo(struct commit *candidate, · line 1633

Quoted 2 lines

ref-filter.c +2 -0

+	if (cutoff == GENERATION_NUMBER_UNDEF)
+		cutoff = GENERATION_NUMBER_NONE;

You're right, we don't want this. Since GENERATION_NUMBER_NONE == 0, we get no benefit from this. If we keep it GENERATION_NUMBER_UNDEF, then our walk will be limited to commits NOT in the commit-graph (which we hope is small if proper hygiene is followed).

Quoted 6 lines

I wonder to what degree it's worth traversing to come up with a generation number for the "want" commits. If we walked, say, 50 commits to do it, you'd probably save a lot of work (since the alternative is walking thousands of commits until you realize that some ancient "v1.0" tag is not useful).

Quoted 6 lines

I'd actually go so far as to say that any amount of traversal is generally going to be worth it to come up with the correct generation cutoff here. You can come up with pathological cases where you only have one really recent tag or something, but in practice every repository where performance is a concern is going to end up with refs much further back than it would take to reach the cutoff condition.

Perhaps there is some value in walking to find the correct cutoff value, but it is difficult to determine how far we are from commits with correct generation numbers _a priori_. I'd rather rely on the commit-graph being in a good state, not too far behind the refs. An added complexity of computing generation numbers dynamically is that we would need to add a dependence on the commit-graph file's existence at all.

Quoted 18 lines · Derrick Stolee

Quoted 7 lines

Quoted 7 lines

ref-filter.c +2 -1

@@ -1615,8 +1619,20 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
   					      struct contains_cache *cache)
   {
   	struct contains_stack contains_stack = { 0, 0, NULL };
-	enum contains_result result = contains_test(candidate, want, cache);
+	enum contains_result result;
+	uint32_t cutoff = GENERATION_NUMBER_UNDEF;

Quoted 8 lines

ref-filter.c static enum contains_result contains_tag_algo(struct commit *candidate, · line 1631

Quoted 8 lines

ref-filter.c +8 -0

+	const struct commit_list *p;
+
+	for (p = want; p; p = p->next) {
+		struct commit *c = p->item;
+		parse_commit_or_die(c);
+		if (c->generation < cutoff)
+			cutoff = c->generation;
+	}

Now that you mention it, let me split out the portion you are probably talking about as incorrect:

Quoted 6 lines

Quoted 2 lines

ref-filter.c static enum contains_result contains_tag_algo(struct commit *candidate, · line 1633

Quoted 2 lines

ref-filter.c +2 -0

+	if (cutoff == GENERATION_NUMBER_UNDEF)
+		cutoff = GENERATION_NUMBER_NONE;

You're right, we don't want this. Since GENERATION_NUMBER_NONE == 0, we get no benefit from this. If we keep it GENERATION_NUMBER_UNDEF, then our walk will be limited to commits NOT in the commit-graph (which we hope is small if proper hygiene is followed).

I think it's more than that. If we leave it at UNDEF, that's wrong, because contains_test() compares:

   candidate->generation < cutoff

which would _always_ be true. In other words, we're saying that our "want" has an insanely high generation number, and traversing can never find it. Which is clearly wrong.

So we have to put it at "0", to say "you should always traverse, we can't tell you that this is a dead end". So that part of the logic is currently correct.

But what I was getting at is that the loop behavior can't just pick the min cutoff. The min is effectively "0" if there's even a single ref for which we don't have a generation number, because we cannot ever stop traversing (we might get to that commit if we kept going).

(It's also possible I'm confused about how UNDEF and NONE are used; I'm assuming commits for which we don't have a generation number available would get UNDEF in their commit->generation field).

If you could make the assumption that when we have a generation for commit X, then we have a generation for all of its ancestors, things get easier. Because then if you hit commit X with a generation number and want to compare it to a cutoff, you know that either:

1. The cutoff is defined, in which case you can stop traversing if we've gone past the cutoff.

2. The cutoff is undefined, in which case we cannot possibly reach our "want" by traversing. Even if it has a smaller generation number than us, it's on an unrelated line of development.

I don't know that the reachability property is explicitly promised by your work, but it seems like it would be a natural fallout (after all, you have to know the generation of each ancestor in order to compute the later ones, so you're really just promising that you've actually stored all the ones you've computed).

Quoted 13 lines

Quoted 7 lines

I wonder to what degree it's worth traversing to come up with a generation number for the "want" commits. If we walked, say, 50 commits to do it, you'd probably save a lot of work (since the alternative is walking thousands of commits until you realize that some ancient "v1.0" tag is not useful).

Quoted 6 lines

I'd actually go so far as to say that any amount of traversal is generally going to be worth it to come up with the correct generation cutoff here. You can come up with pathological cases where you only have one really recent tag or something, but in practice every repository where performance is a concern is going to end up with refs much further back than it would take to reach the cutoff condition.

Quoted 6 lines

Perhaps there is some value in walking to find the correct cutoff value, but it is difficult to determine how far we are from commits with correct generation numbers _a priori_. I'd rather rely on the commit-graph being in a good state, not too far behind the refs. An added complexity of computing generation numbers dynamically is that we would need to add a dependence on the commit-graph file's existence at all.

If you could make the reachability assumption, I think this question just goes away. As soon as you hit a commit with _any_ generation number, you could quit traversing down that path.

Quoted 5 lines

I don't know that the reachability property is explicitly promised by your work, but it seems like it would be a natural fallout (after all, you have to know the generation of each ancestor in order to compute the later ones, so you're really just promising that you've actually stored all the ones you've computed).

The commit-graph is closed under reachability, so if a commit has a generation number then it is in the graph and so are all its ancestors.

The reason for GENERATION_NUMBER_NONE is that the commit-graph file stores "0" for generation number until this patch. It still satisfies the condition that gen(A) < gen(B) if B can reach A, but also gives us a condition for "this commit still needs its generation number computed".

Quoted 3 lines

If you could make the reachability assumption, I think this question just goes away. As soon as you hit a commit with _any_ generation number, you could quit traversing down that path.

That is the idea. I should make this clearer in all of my commit messages.

Quoted 1 line · Derrick Stolee

That is the idea. I should make this clearer in all of my commit messages.

Yes, please. :) And maybe in the documentation of the file format, if it's not there (I didn't check). It's a very useful property, and we want to make sure people making use of the graph know they can depend on it.

Quoted 3 lines · Jeff King

Quoted 1 line · Derrick Stolee

That is the idea. I should make this clearer in all of my commit messages.

Quoted 4 lines

Yes, please. :) And maybe in the documentation of the file format, if it's not there (I didn't check). It's a very useful property, and we want to make sure people making use of the graph know they can depend on it.

For v2, I'll expand on the roles of _UNDEF and _NONE in the discussion of generation numbers in Documentation/technical/commit-graph.txt (the design doc instead of the file format).

Quoted 8 lines · Brandon Williams

Quoted 7 lines · Derrick Stolee

This is the first of several "small" patches that follow the serialized Git commit graph patch (ds/commit-graph).

As described in Documentation/technical/commit-graph.txt, the generation number of a commit is one more than the maximum generation number among its parents (trivially, a commit with no parents has generation number one).

Quoted 6 lines

Quoted 2 lines

A more substantial refactoring of revision.c is required before making 'git log --graph' use generation numbers effectively.

log --graph should benefit a lot more from this correct? I know we've talked a bit about negotiation and I wonder if these generation numbers should be able to help out a little bit with that some day.

'log --graph' should be a HUGE speedup, when it is refactored. Since the topo-order can "stream" commits to the pager, it can be very responsive to return the graph in almost all conditions. (The case where generation numbers are not enough is when filters reduce the set of displayed commits to be very sparse, so many commits are walked anyway.)

If we have generic "can X reach Y?" queries, then we can also use generation numbers there to great effect (by not walking commits Z with gen(Z) <= gen(Y)). Perhaps I should look at that "git branch --contains" thread for ideas.

For negotiation, there are some things we can do here. VSTS uses generation numbers as a heuristic for determining "all wants connected to haves" which is a condition for halting negotiation. The idea is very simple, and I'd be happy to discuss it on a separate thread.

This is the first of several "small" patches that follow the serialized Git commit graph patch (ds/commit-graph).

As described in Documentation/technical/commit-graph.txt, the generation number of a commit is one more than the maximum generation number among its parents (trivially, a commit with no parents has generation number one).

This series makes the computation of generation numbers part of the commit-graph write process.

Finally, generation numbers are used [...].

This does not have a significant performance benefit in repositories of normal size, but in the Windows repository, some merge-base calculations improve from 3.1s to 2.9s. A modest speedup, but provides an actual consumer of generation numbers as a starting point.

A more substantial refactoring of revision.c is required before making 'git log --graph' use generation numbers effectively.

Currently I am at the stage of reproducing results in FELINE paper:
"Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach" by Renê R. Veloso, Loïc Cerf, Wagner Meira Jr and Mohammed J. Zaki (2014). This paper is available in the PDF form at
https://openproceedings.org/EDBT/2014/paper_166.pdf

The Jupyter Notebook (which runs on Google cloud, but can be also run locally) uses Python kernel, NetworkX librabry for graph manipulation, and matplotlib (via NetworkX) for display.

Available at:
https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg
https://drive.google.com/file/d/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg/view?usp=sharing

I hope that could be of help, or at least interesting

Quoted 14 lines · Jakub Narebski

Currently I am at the stage of reproducing results in FELINE paper:
"Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach" by Renê R. Veloso, Loïc Cerf, Wagner Meira Jr and Mohammed J. Zaki (2014). This paper is available in the PDF form at
https://openproceedings.org/EDBT/2014/paper_166.pdf

The Jupyter Notebook (which runs on Google cloud, but can be also run locally) uses Python kernel, NetworkX librabry for graph manipulation, and matplotlib (via NetworkX) for display.

Available at:
https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg
https://drive.google.com/file/d/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg/view?usp=sharing

Quoted 1 line

I hope that could be of help, or at least interesting

Let me know when you can give numbers (either raw performance or # of commits walked) for real-world Git commit graphs. The Linux repo is a good example to use for benchmarking, but I also use the Kotlin repo sometimes as it has over a million objects and over 250K commits.

Of course, the only important statistic at the end of the day is the end-to-end time of a 'git ...' command. Your investigations should inform whether it is worth prototyping the feature in the git codebase.

What would you suggest as a good test that could imply performance? The Google Colab notebook linked to above includes a function to count number of commits (nodes / vertices in the commit graph) walked, currently in the worst case scenario.

I have tried finding number of false positives for level (generation number) filter and for FELINE index, and number of false negatives for min-post intervals in the spanning tree (for DFS tree) for 10000 randomly selected pairs of commits... but I don't think this is a good benchmark.

I Linux kernel sources (https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git)
that has 750832 nodes and 811733 edges, and 563747941392 possible
directed pairs, we have for 10000 randomly selected pairs of commits:

   level-filter has    91 =  0.91% [all] false positives
   FELINE index has    78 =  0.78% [all] false positives

FELINE index has 1.16667 less false positives than level filter

min-post spanning-tree intervals has 3641 = 36.41% [all] false negatives

For git.git repository (https://github.com/git/git.git) that has 52950 nodes and 65887 edges the numbers are slighly more in FELINE index favor (also out of 10000 random pairs):

   level-filter has   504 =  9.11% false positives
   FELINE index has   125 =  2.26% false positives

FELINE index has 4.032 less false positives than level filter

This is for FELINE which does not use level / generatio-numbers filter.

Quoted 4 lines · Jakub Narebski

What would you suggest as a good test that could imply performance? The Google Colab notebook linked to above includes a function to count number of commits (nodes / vertices in the commit graph) walked, currently in the worst case scenario.

The two main questions to consider are:

1. Can X reach Y?

2. What is the set of merge-bases between X and Y?

And the thing to measure is a commit count. If possible, it would be good to count commits walked (commits whose parent list is enumerated) and commits inspected (commits that were listed as a parent of some walked commit). Walked commits require a commit parse -- albeit from the commit-graph instead of the ODB now -- while inspected commits only check the in-memory cache.

For git.git and Linux, I like to use the release tags as tests. They provide a realistic view of the linear history, and maintenance releases have their own history from the major releases.

Quoted 5 lines

I have tried finding number of false positives for level (generation number) filter and for FELINE index, and number of false negatives for min-post intervals in the spanning tree (for DFS tree) for 10000 randomly selected pairs of commits... but I don't think this is a good benchmark.

What is a false-positive? A case where gen(X) < gen(Y) but Y cannot reach X?

I do not think that is a great benchmark, but I guess it is something to measure.

Quoted 10 lines

I Linux kernel sources (https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git)
that has 750832 nodes and 811733 edges, and 563747941392 possible
directed pairs, we have for 10000 randomly selected pairs of commits:

   level-filter has    91 =  0.91% [all] false positives
   FELINE index has    78 =  0.78% [all] false positives

FELINE index has 1.16667 less false positives than level filter

min-post spanning-tree intervals has 3641 = 36.41% [all] false negatives

Perhaps something you can do instead of sampling from N^2 commits in total is to select a pair of generations (say, G = 20000, G' = 20100) or regions of generations ( 20000 <= G <= 20050, 20100 <= G' <= 20150) and see how many false positives you see by testing all pairs (one from each level). The delta between the generations may need to be smaller to actually have a large proportion of unreachable pairs. Try different levels, since major version releases tend to "pinch" the commit graph to a common history.

Quoted 9 lines

For git.git repository (https://github.com/git/git.git) that has 52950 nodes and 65887 edges the numbers are slighly more in FELINE index favor (also out of 10000 random pairs):

   level-filter has   504 =  9.11% false positives
   FELINE index has   125 =  2.26% false positives

FELINE index has 4.032 less false positives than level filter

This is for FELINE which does not use level / generatio-numbers filter.

Quoted 10 lines · Derrick Stolee

Quoted 4 lines · Jakub Narebski

What would you suggest as a good test that could imply performance? The Google Colab notebook linked to above includes a function to count number of commits (nodes / vertices in the commit graph) walked, currently in the worst case scenario.

The two main questions to consider are:

1. Can X reach Y?

That is easy to do. The function generic_is_reachable() does that... though using direct translation of the pseudocode for "Algorithm 3: Reachable" from FELINE paper, which is recursive and doesn't check if vertex was already visited was not good idea for large graphs such as Linux kernel commit graph, oops. That is why generic_is_reachable_large() was created.

Quoted 6 lines

And the thing to measure is a commit count. If possible, it would be good to count commits walked (commits whose parent list is enumerated) and commits inspected (commits that were listed as a parent of some walked commit). Walked commits require a commit parse -- albeit from the commit-graph instead of the ODB now -- while inspected commits only check the in-memory cache.

Quoted 4 lines

For git.git and Linux, I like to use the release tags as tests. They provide a realistic view of the linear history, and maintenance releases have their own history from the major releases.

Hmmm... testing for v4.9-rc5..v4.9 in Linux kernel commit graphs, the FELINE index does not bring any improvements over using just level (generation number) filter. But that may be caused by narrowing od commit DAG around releases.

I try do do the same between commits in wide part, with many commits with the same level (same generation number) both for source and for target commit. Though this may be unfair to level filter, though...

Note however that FELINE index is not unabiguous, like generation numbers are (modulo decision whether to start at 0 or at 1); it depends on the topological ordering chosen for the X elements.

Quoted 15 lines · Jakub Narebski

Quoted 8 lines · Derrick Stolee

Quoted 4 lines · Jakub Narebski

What would you suggest as a good test that could imply performance? The Google Colab notebook linked to above includes a function to count number of commits (nodes / vertices in the commit graph) walked, currently in the worst case scenario.

The two main questions to consider are:

1. Can X reach Y?

That is easy to do. The function generic_is_reachable() does that... though using direct translation of the pseudocode for "Algorithm 3: Reachable" from FELINE paper, which is recursive and doesn't check if vertex was already visited was not good idea for large graphs such as Linux kernel commit graph, oops. That is why generic_is_reachable_large() was created.

[...]

Quoted 6 lines

Quoted 6 lines

And the thing to measure is a commit count. If possible, it would be good to count commits walked (commits whose parent list is enumerated) and commits inspected (commits that were listed as a parent of some walked commit). Walked commits require a commit parse -- albeit from the commit-graph instead of the ODB now -- while inspected commits only check the in-memory cache.

[...]

Quoted 8 lines

Quoted 3 lines

For git.git and Linux, I like to use the release tags as tests. They provide a realistic view of the linear history, and maintenance releases have their own history from the major releases.

Hmmm... testing for v4.9-rc5..v4.9 in Linux kernel commit graphs, the FELINE index does not bring any improvements over using just level (generation number) filter. But that may be caused by narrowing od commit DAG around releases.

Quoted 8 lines

I try do do the same between commits in wide part, with many commits with the same level (same generation number) both for source and for target commit. Though this may be unfair to level filter, though...

Note however that FELINE index is not unabiguous, like generation numbers are (modulo decision whether to start at 0 or at 1); it depends on the topological ordering chosen for the X elements.

One can now test reachability on git.git repository; there is a form where one can plug source and destination revisions at
https://colab.research.google.com/drive/1V-U7_slu5Z3s5iEEMFKhLXtaxSu5xyzg#scrollTo=svNUnSA9O_NK&line=2&uniqifier=1

I have tried the case that is quite unfair to the generation numbers filter, namely the check between one of recent tags, and one commit that shares generation number among largest number of other commits.

Here level = generation number-1 (as it starts at 0 for root commit, not 1).

The results are:
* src = 468165c1d = v2.17.0
* dst = 66d2e04ec = v2.0.5-5-g66d2e04ec

* 468165c1d has level 18418 which it shares with 6 commits
* 66d2e04ec has level 14776 which it shares with 93 commits
* gen(468165c1d) - gen(66d2e04ec) = 3642

algorithm | access | walk | maxdepth | visited | level-f | FELINE-f |
-----------+---------+--------+----------+---------+----------+-----------+

  naive      | 48865   | 39599  | 244      | 9200    |          |           |
  level      |  3086   |  2492  | 113      |  528    | 285      |           |
  FELINE     |   283   |   216  |  68      |    0    |          |  25       |
  lev+FELINE |   282   |   215  |  68      |    0    |   5      |  24       |

-----------+---------+--------+----------+---------+----------+-----------+
lev+FEL+mpi| 79 | 59 | 21 | 0 | 0 | 0 |

Here we have:
* 'naive' implementation means simple DFS walk, without any filters (cut-offs)
* 'level' means using levels / generation numbers based negative-cut filter
* 'FELINE' means using FELINE index based negative-cut filter
* 'lev+FELINE' means combining generation numbers filter with FELINE filter
* 'mpi' means min-post [smanning-tree] intervals for positive-cut filter; note that the code does not walk the path after cut, but it is easy to do

The stats have the following meaning:
* 'access' means accessing the node
* 'walk' is actual walking the node
* 'maxdepth' is maximum depth of the stack used for DFS
* 'level-f' and 'FELINE-f' is number of times levels filter or FELINE filter were used for negative-cut; note that those are not disjoint; node can be rejected by both level filter and FELINE filter

For v2.17.0 and v2.17.0-rc2 the numbers are much less in FELINE favor:
the results are the same, with 5 commits accessed and 6 walked compared to 61574 accessed in naive algorithm.

The git.git commit graph has 53128 nodes and 66124 edges, 4 tips / heads (different child-less commits) and 9 roots, and has average clustering coefficient 0.000409217.

P.S. Would it be better to move the discussion about possible extensions to the commit-graph in the form of new chunks (topological order, FELINE index, min-post intervals, bloom filter for changed files, etc.) be moved into separate thread?

builtin/merge.c +0 -0

index ee050a47f3..20897f8223 100644
@@ -1183,13 +1183,14 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	branch = branch_to_free = resolve_refdup("HEAD", 0, &head_oid, NULL);
 	if (branch)
 		skip_prefix(branch, "refs/heads/", &branch);

Move the config load to be between the initialization of 'branch' and the commit lookup. Also add a test to t5318-commit-graph.sh that exercises this code path to prevent a regression.

t/t5318-commit-graph.sh +9 -0

index a380419b65..77d85aefe7 100755
@@ -221,4 +221,13 @@ test_expect_success 'write graph in bare repo' '
 graph_git_behavior 'bare repo with graph, commit 8 vs merge 1' bare commits/8 merge/1
 graph_git_behavior 'bare repo with graph, commit 8 vs merge 2' bare commits/8 merge/2
 
+test_expect_success 'perform fast-forward merge in full repo' '
+	cd "$TRASH_DIRECTORY/full" &&
+	git checkout -b merge-5-to-8 commits/5 &&
+	git merge commits/8 &&
+	git show-ref -s merge-5-to-8 >output &&
+	git show-ref -s commits/8 >expect &&
+	test_cmp expect output
+'
+
 test_done

Quoted 16 lines · Derrick Stolee

builtin/merge.c +3 -0

index ee050a47f3..20897f8223 100644
@@ -1183,13 +1183,14 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
  	branch = branch_to_free = resolve_refdup("HEAD", 0, &head_oid, NULL);
  	if (branch)
  		skip_prefix(branch, "refs/heads/", &branch);
+	init_diff_ui_defaults();
+	git_config(git_merge_config, NULL);
+
  	if (!branch || is_null_oid(&head_oid))
  		head_commit = NULL;
  	else
  		head_commit = lookup_commit_or_die(&head_oid, "HEAD");
 

builtin/merge.c int cmd_merge(int argc, const char **argv, const char *prefix) · line 1192

Quoted 2 lines

builtin/merge.c +0 -2

-	init_diff_ui_defaults();
-	git_config(git_merge_config, NULL);

Wow, that's tricky. git_merge_config() wants to know which "branch" we are on, and this place is as early as we can move the call to without breaking things. Is this to allow parse_object() called in lookup_commit_reference_gently() to know if we can rely on the data cached in the commit-graph data?

Quoted 4 lines

Move the config load to be between the initialization of 'branch' and the commit lookup. Also add a test to t5318-commit-graph.sh that exercises this code path to prevent a regression.

It is not clear to me how a successful merge of commits/8 demonstrates that reading the config earlier than before is regression free.

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Add a uint32_t generation field to struct commit so we can pass this information to revision walks. We use two special values to signal the generation number is invalid:

GENERATION_NUMBER_ININITY 0xFFFFFFFF

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Add a uint32_t generation field to struct commit so we can pass this information to revision walks. We use two special values to signal the generation number is invalid:

GENERATION_NUMBER_ININITY 0xFFFFFFFF
GENERATION_NUMBER_ZERO 0

The first (_INFINITY) means the generation number has not been loaded or computed. The second (_ZERO) means the generation number was loaded from a commit graph file that was stored before generation numbers were computed.

Quoted 10 lines · Derrick Stolee

The generation number of a commit is defined recursively as follows:

* If a commit A has no parents, then the generation number of A is one.
* If a commit A has parents, then the generation number of A is one more than the maximum generation number among the parents of A.

Add a uint32_t generation field to struct commit so we can pass this information to revision walks. We use two special values to signal the generation number is invalid:

Quoted 7 lines

GENERATION_NUMBER_ININITY 0xFFFFFFFF
GENERATION_NUMBER_ZERO 0

The first (_INFINITY) means the generation number has not been loaded or computed. The second (_ZERO) means the generation number was loaded from a commit graph file that was stored before generation numbers were computed.

Should it also be possible for a caller to tell if a given commit has too deep a history, i.e. we do not know its generation number exactly, but we know it is larger than 1<<30?

It seems that we only have a 30-bit field in the file, so wouldn't we need a special value defined in (e.g. "0") so that we can tell that the commit has such a large generation number? E.g.

commit-graph.c static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uin · line 267

Quoted 1 line

commit-graph.c +1 -0

+	item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;

	if (!item->generation)
		item->generation = GENERATION_NUMBER_OVERFLOW;

when we read it from the file?

We obviously need to do something similar when assigning a generation number to a child commit, perhaps like

	#define GENERATION_NUMBER_OVERFLOW (GENERATION_NUMBER_MAX + 1)

	commit->generation = 1; /* assume no parent */
	for (p = commit->parents; p; p++) {
		uint32_t gen = p->item->generation + 1;

		if (gen >= GENERATION_NUMBER_OVERFLOW) {
			commit->generation = GENERATION_NUMBER_OVERFLOW;
			break;
		} else if (commit->generation < gen)
			commit->generation = gen;
	}

or something? And then on the writing side you'd encode too large a generation as '0'.

How about we do a slightly different
arrangement for these overflow commits?

Instead of storing the commits in the commit-graph file as "0" (which currently means "written by a version of git that did not compute generation numbers") we could let GENERATION_NUMBER_MAX be the maximum generation of a commit in the commit-graph, and if a commit would have larger generation, we collapse it down to that value.

commit-graph.c static void write_graph_chunk_data(struct hashfile *f, int hash_len, · line 427

Quoted 6 lines · Derrick Stolee

commit-graph.c +6 -0

+		if ((*list)->generation != GENERATION_NUMBER_INFINITY) {
+			if ((*list)->generation > GENERATION_NUMBER_MAX)
+				die("generation number %u is too large to store in commit-graph",
+				    (*list)->generation);
+			packedDate[0] |= htonl((*list)->generation << 2);
+		}

How serious do we want this feature to be? On one extreme, we could be irresponsible and say it will be a problem for our descendants in the future if their repositories have more than billion pearls on a single strand, and the above certainly is a reasonable way to punt. Those who actually encounter the problem will notice by Git dying somewhere rather deep in the callchain.

Or we could say Git actually does support a history that is arbitrarily long, even though such a deep portion of history will not benefit from having generation numbers in commit-graph.

I've been assuming that our stance is the latter and that is why I made noises about overflowing 30-bit generation field in my review of the previous step.

In case we want to do the "we know this is very large, but we do not know the exact value", we may actually want a mode where we can pretend that GENERATION_NUMBER_MAX is set to quite low (say 256) and make sure that the code to handle overflow behaves sensibly.

commit-graph.c static void close_reachable(struct packed_oid_list *oids) · line 588

Quoted 11 lines

commit-graph.c +10 -0

+	for (i = 0; i < nr_commits; i++) {
+		if (commits[i]->generation != GENERATION_NUMBER_INFINITY &&
+		    commits[i]->generation != GENERATION_NUMBER_ZERO)
+			continue;
+
+		commit_list_insert(commits[i], &list);
+		while (list) {
+...
+		}
+	}

So we go over the list of commits just _once_ and make sure each of them gets the generation assigned correctly by (conceptually recursively but iteratively in implementation by using a commit list) making sure that all its parents have generation assigned and compute the generation for the commit, before moving to the next one. Which sounds correct.

Quoted 4 lines · Junio C Hamano

In case we want to do the "we know this is very large, but we do not know the exact value", we may actually want a mode where we can pretend that GENERATION_NUMBER_MAX is set to quite low (say 256) and make sure that the code to handle overflow behaves sensibly.

I agree. I wonder how we can effectively expose this value into a test. It's probably not sufficient to manually test using compiler flags ("-D GENERATION_NUMBER_MAX=8").

Quoted 23 lines · Junio C Hamano

commit-graph.c static void write_graph_chunk_data(struct hashfile *f, int hash_len, · line 427

Quoted 7 lines · Derrick Stolee

commit-graph.c +3 -0

+               if ((*list)->generation != GENERATION_NUMBER_INFINITY) {
+                       if ((*list)->generation > GENERATION_NUMBER_MAX)
+                               die("generation number %u is too large to

store in commit-graph",

commit-graph.c +3 -0

+                                   (*list)->generation);
+                       packedDate[0] |= htonl((*list)->generation << 2);
+               }

How serious do we want this feature to be? On one extreme, we could be irresponsible and say it will be a problem for our descendants in the future if their repositories have more than billion pearls on a single strand, and the above certainly is a reasonable way to punt. Those who actually encounter the problem will notice by Git dying somewhere rather deep in the callchain.

Or we could say Git actually does support a history that is arbitrarily long, even though such a deep portion of history will not benefit from having generation numbers in commit-graph.

Quoted 8 lines

I've been assuming that our stance is the latter and that is why I made noises about overflowing 30-bit generation field in my review of the previous step.

In case we want to do the "we know this is very large, but we do not know the exact value", we may actually want a mode where we can pretend that GENERATION_NUMBER_MAX is set to quite low (say 256) and make sure that the code to handle overflow behaves sensibly.

I agree. I wonder how we can effectively expose this value into a test. It's probably not sufficient to manually test using compiler flags ("-D GENERATION_NUMBER_MAX=8").

commit.c +10 -1

@@ -800,17 +810,26 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc
 		return result;
 	}
 	prio_queue_put(&queue, one);
+	if (one->generation < min_nonstale_gen)
+		min_nonstale_gen = one->generation;
 
 	for (i = 0; i < n; i++) {
 		twos[i]->object.flags |= PARENT2;
 		prio_queue_put(&queue, twos[i]);
+		if (twos[i]->generation < min_nonstale_gen)
+			min_nonstale_gen = twos[i]->generation;
 	}
 
-	while (queue_has_nonstale(&queue)) {
+	while (queue_has_nonstale(&queue, min_nonstale_gen)) {
 		struct commit *commit = prio_queue_get(&queue);
 		struct commit_list *parents;
 		int flags;
 
+		if (commit->generation > last_gen)
+			BUG("bad generation skip");
+
+		last_gen = commit->generation;
+
 		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
 		if (flags == (PARENT1 | PARENT2)) {
 			if (!(commit->object.flags & RESULT)) {

commit.c +4 -0

 			prio_queue_put(&queue, p);
+
+			if (!(flags & STALE) &&
+			    p->generation < min_nonstale_gen)
+				min_nonstale_gen = p->generation;
 		}
 	}

Quoted 20 lines · Derrick Stolee

commit.c +5 -1

@@ -800,17 +810,26 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc
  		return result;
  	}
  	prio_queue_put(&queue, one);
+	if (one->generation < min_nonstale_gen)
+		min_nonstale_gen = one->generation;
 
  	for (i = 0; i < n; i++) {
  		twos[i]->object.flags |= PARENT2;
  		prio_queue_put(&queue, twos[i]);
+		if (twos[i]->generation < min_nonstale_gen)
+			min_nonstale_gen = twos[i]->generation;
  	}
 
-	while (queue_has_nonstale(&queue)) {
+	while (queue_has_nonstale(&queue, min_nonstale_gen)) {
  		struct commit *commit = prio_queue_get(&queue);
  		struct commit_list *parents;
  		int flags;
 

commit.c static struct commit_list *paint_down_to_common(struct commit *one, int n, struc · line 850

Quoted 11 lines

commit.c +5 -0

+		if (commit->generation > last_gen)
+			BUG("bad generation skip");
+
+		last_gen = commit->generation;
+
  		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
  		if (flags == (PARENT1 | PARENT2)) {
  			if (!(commit->object.flags & RESULT)) {

@@ -830,6 +849,10 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc
  				return NULL;
  			p->object.flags |= flags;

Hmph. Can a commit that used to be not stale (and contributed to the current value of min_nonstale_gen) become stale here by getting visited twice, invalidating the value in min_nonstale_gen?

Documentation/technical/commit-graph.txt +16 -0

+Here is a diagram to visualize the shape of the full commit graph, and
+how different generation numbers relate:
+
+    +-----------------------------------------+
+    | GENERATION_NUMBER_INFINITY = 0xFFFFFFFF |
+    +-----------------------------------------+
+	    |            |      ^
+	    |            |      |
+	    |            +------+
+	    |         [gen(A) = gen(B)]
+	    V
+    +-------------------------------------+
+    | 0 < commit->generation < 0x40000000 |
+    +-------------------------------------+
+	    |            |      ^
+	    |            |      |

Design Details
--------------

Documentation/technical/commit-graph.txt +0 -0

@@ -98,17 +141,12 @@ Future Work
 - The 'commit-graph' subcommand does not have a "verify" mode that is
   necessary for integration with fsck.
 

Quoted 16 lines · Derrick Stolee

Documentation/technical/commit-graph.txt +16 -0

+Here is a diagram to visualize the shape of the full commit graph, and
+how different generation numbers relate:
+
+    +-----------------------------------------+
+    | GENERATION_NUMBER_INFINITY = 0xFFFFFFFF |
+    +-----------------------------------------+
+	    |            |      ^
+	    |            |      |
+	    |            +------+
+	    |         [gen(A) = gen(B)]
+	    V
+    +-------------------------------------+
+    | 0 < commit->generation < 0x40000000 |
+    +-------------------------------------+
+	    |            |      ^
+	    |            |      |

Documentation/technical/commit-graph.txt in the commit graph. We can treat these commits as having "infinite" · line 121

Quoted 10 lines

Documentation/technical/commit-graph.txt +10 -0

+	    |            +------+
+	    |        [gen(A) > gen(B)]
+	    V
+    +-------------------------------------+
+    | GENERATION_NUMBER_ZERO = 0          |
+    +-------------------------------------+
+			 |      ^
+			 |      |
+			 +------+
+		     [gen(A) = gen(B)]

It may be just me but all I can read out of the above is that commit->generation may store 0xFFFFFFFF, a value between 0 and 0x40000000, or 0. I cannot quite tell what the notation [gen(A)

<cmp> gen(B)] is trying to say. I am guessing "Two generation numbers within the 'valid' range can be compared" is what the second one is trying to say, but it is much less interesting to know that two infinities compare equal than how generation numbers from different classes compare, which cannot be depicted in the above notation, I am afraid. For example, don't we want to say that a commit with INF can never be reached by a commit with a valid generation number, or something like that?

Quoted 8 lines

Design Details
--------------

Documentation/technical/commit-graph.txt +0 -0

@@ -98,17 +141,12 @@ Future Work
  - The 'commit-graph' subcommand does not have a "verify" mode that is
    necessary for integration with fsck.
 

Documentation/technical/commit-graph.txt Future Work · line 148

Quoted 10 lines

Documentation/technical/commit-graph.txt +1 -5

-- The file format includes room for precomputed generation numbers. These
-  are not currently computed, so all generation numbers will be marked as
-  0 (or "uncomputed"). A later patch will include this calculation.
-
  - After computing and storing generation numbers, we must make graph
    walks aware of generation numbers to gain the performance benefits they
    enable. This will mostly be accomplished by swapping a commit-date-ordered
    priority queue with one ordered by generation number. The following
-  operations are important candidates:
+  operation is an important candidate:

Good.

Quoted 22 lines · Junio C Hamano

Quoted 20 lines · Derrick Stolee

Documentation/technical/commit-graph.txt +20 -0

+Here is a diagram to visualize the shape of the full commit graph, and
+how different generation numbers relate:
+
+    +-----------------------------------------+
+    | GENERATION_NUMBER_INFINITY = 0xFFFFFFFF |
+    +-----------------------------------------+
+	    |            |      ^
+	    |            |      |
+	    |            +------+
+	    |         [gen(A) = gen(B)]
+	    V
+    +-------------------------------------+
+    | 0 < commit->generation < 0x40000000 |
+    +-------------------------------------+
+	    |            |      ^
+	    |            |      |
+	    |            +------+
+	    |        [gen(A) > gen(B)]
+	    V
+    +-------------------------------------+

Quoted 8 lines

Documentation/technical/commit-graph.txt in the commit graph. We can treat these commits as having "infinite" · line 121

Quoted 6 lines

Documentation/technical/commit-graph.txt +6 -0

+    | GENERATION_NUMBER_ZERO = 0          |
+    +-------------------------------------+
+			 |      ^
+			 |      |
+			 +------+
+		     [gen(A) = gen(B)]

It may be just me but all I can read out of the above is that

Quoted 10 lines

commit->generation may store 0xFFFFFFFF, a value between 0 and 0x40000000, or 0. I cannot quite tell what the notation [gen(A) <cmp> gen(B)] is trying to say. I am guessing "Two generation numbers within the 'valid' range can be compared" is what the second one is trying to say, but it is much less interesting to know that two infinities compare equal than how generation numbers from different classes compare, which cannot be depicted in the above notation, I am afraid. For example, don't we want to say that a commit with INF can never be reached by a commit with a valid generation number, or something like that?

My intention with the arrows was to demonstrate where parent relationships can go, and the generation-number relation between a commit A with parent B. Clearly, this diagram is less than helpful.

Define compare_commits_by_gen_then_commit_date(), which uses generation numbers as a primary comparison and commit date to break ties (or as a comparison when both commits do not have computed generation numbers).

Since the commit-graph file is closed under reachability, we know that all commits in the file have generation at most GENERATION_NUMBER_MAX which is less than GENERATION_NUMBER_INFINITY.

This change does not affect the number of commits that are walked during the execution of paint_down_to_common(), only the order that those commits are inspected. In the case that commit dates violate topological order (i.e. a parent is "newer" than a child), the previous code could walk a commit twice: if a commit is reached with the PARENT1 bit, but later is re-visited with the PARENT2 bit, then that PARENT2 bit must be propagated to its parents. Using generation numbers avoids this extra effort, even if it is somewhat rare.

Signed-off-by Derrick Stolee <[email protected]>

---
 commit.c | 20 +++++++++++++++++++-
 commit.h |  1 +
 2 files changed, 20 insertions(+), 1 deletion(-)

commit.c +1 -0

index 711f674c18..a44899c733 100644
@@ -640,6 +640,24 @@ static int compare_commits_by_author_date(const void *a_, const void *b_,
 	return 0;
 }
 
+int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)

commit.c +8 -1

+	if (a->date < b->date)
+		return 1;
+	else if (a->date > b->date)
+		return -1;
+	return 0;
+}
+
 int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused)
 {
 	const struct commit *a = a_, *b = b_;

@@ -789,7 +807,7 @@ static int queue_has_nonstale(struct prio_queue *queue)
 /* all input commits in one and twos[] must have been parsed! */
 static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
 {
-	struct prio_queue queue = { compare_commits_by_commit_date };
+	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 	struct commit_list *result = NULL;
 	int i;
 

commit.h +1 -0

index aac3b8c56f..64436ff44e 100644
@@ -341,6 +341,7 @@ extern int remove_signature(struct strbuf *buf);
 extern int check_commit_signature(const struct commit *commit, struct signature_check *sigc);
 
 int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused);
+int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused);
 
 LAST_ARG_MUST_BE_NULL
 extern int run_commit_hook(int editor_is_used, const char *index_file, const char *name, ...);

Quoted 8 lines · Derrick Stolee

Define compare_commits_by_gen_then_commit_date(), which uses generation numbers as a primary comparison and commit date to break ties (or as a comparison when both commits do not have computed generation numbers).

Since the commit-graph file is closed under reachability, we know that all commits in the file have generation at most GENERATION_NUMBER_MAX which is less than GENERATION_NUMBER_INFINITY.

Quoted 8 lines

This change does not affect the number of commits that are walked during the execution of paint_down_to_common(), only the order that those commits are inspected. In the case that commit dates violate topological order (i.e. a parent is "newer" than a child), the previous code could walk a commit twice: if a commit is reached with the PARENT1 bit, but later is re-visited with the PARENT2 bit, then that PARENT2 bit must be propagated to its parents. Using generation numbers avoids this extra effort, even if it is somewhat rare.

Does it mean that it gives no measureable performance improvements for typical test cases?

Quoted 16 lines

Signed-off-by Derrick Stolee <[email protected]>

---
  commit.c | 20 +++++++++++++++++++-
  commit.h |  1 +
  2 files changed, 20 insertions(+), 1 deletion(-)

commit.c +1 -0

index 711f674c18..a44899c733 100644
@@ -640,6 +640,24 @@ static int compare_commits_by_author_date(const void *a_, const void *b_,
  	return 0;
  }
 
+int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)

commit.c static int compare_commits_by_author_date(const void *a_, const void *b_, · line 653

Quoted 10 lines

commit.c +10 -0

+{
+	const struct commit *a = a_, *b = b_;
+
+	/* newer commits first */
+	if (a->generation < b->generation)
+		return 1;
+	else if (a->generation > b->generation)
+		return -1;
+
+	/* use date as a heuristic when generataions are equal */

Very minor typo in above comment: