Re: [PATCH v3 10/11] commit-reach: use corrected commit dates in paint_down_to_common()

[Abhishek Kumar <abhishekkumar8222@gmail.com>]

On Sat, Aug 22, 2020 at 09:09:21PM +0200, Jakub Narębski wrote:
> Hello Abhishek,
> 
> "Abhishek Kumar via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
> > From: Abhishek Kumar <abhishekkumar8222@gmail.com>
> >
> > With corrected commit dates implemented, we no longer have to rely on
> > commit date as a heuristic in paint_down_to_common().
> 
> All right, but it would be nice to have some benchmark data: what were
> performance when using topological levels, what was performance when
> using commit date heuristics (before this patch), what is performace now
> when using corrected commit date.
> 
> >
> > t6024-recursive-merge setups a unique repository where all commits have
> > the same committer date without well-defined merge-base. As this has
> > already caused problems (as noted in 859fdc0 (commit-graph: define
> > GIT_TEST_COMMIT_GRAPH, 2018-08-29)), we disable commit graph within the
> > test script.
> 
> OK?

In hindsight, that is a terrible explanation. Here's what I have revised
this to:

  With corrected commit dates implemented, we no longer have to rely on
  commit date as a heuristic in paint_down_to_common().

  While using corrected commit dates Git walks nearly the same number of
  commits as commit date, the process is slower as for each comparision we
  have to access the commit-slab (for corrected committer date) instead of
  accessing struct member (for committer date).

  For example, the command `git merge-base v4.8 v4.9` on the linux
  repository walks 167468 commits, taking 0.135s for committer date and
  167496 commits, taking 0.157s for corrected committer date respectively.

  t6404-recursive-merge setups a unique repository where all commits have
  the same committer date without well-defined merge-base. As this has
  already caused problems (as noted in 859fdc0 (commit-graph: define
  GIT_TEST_COMMIT_GRAPH, 2018-08-29)).

  While running tests with GIT_TEST_COMMIT_GRAPH unset, we use committer
  date as a heuristic in paint_down_to_common(). 6404.1 'combined merge
  conflicts' merges commits in the order:
  - Merge C with B to form a intermediate commit.
  - Merge the intermediate commit with A.

  With GIT_TEST_COMMIT_GRAPH=1, we write a commit-graph and subsequently
  use the corrected committer date, which changes the order in which
  commits are merged:
  - Merge A with B to form a intermediate commit.
  - Merge the intermediate commit with C.

  While resulting repositories are equivalent, 6404.4 'virtual trees were
  processed' fails with GIT_TEST_COMMIT_GRAPH=1 as we are selecting
  different merge-bases and thus have different object ids for the
  intermediate commits.

  As this has already causes problems (as noted in 859fdc0 (commit-graph:
  define GIT_TEST_COMMIT_GRAPH, 2018-08-29)), we disable commit graph
  within t6404-recursive-merge.
> 
> >
> > Signed-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com>
> > ---
> >  commit-graph.c             | 14 ++++++++++++++
> >  commit-graph.h             |  6 ++++++
> >  commit-reach.c             |  2 +-
> >  t/t6024-recursive-merge.sh |  4 +++-
> >  4 files changed, 24 insertions(+), 2 deletions(-)
> >
> 
> I have reorderd files for easier review.
> 
> > diff --git a/commit-graph.h b/commit-graph.h
> > index 3cf89d895d..e22ec1e626 100644
> > --- a/commit-graph.h
> > +++ b/commit-graph.h
> > @@ -91,6 +91,12 @@ struct commit_graph *parse_commit_graph(void *graph_map, size_t graph_size);
> >   */
> >  int generation_numbers_enabled(struct repository *r);
> >
> > +/*
> > + * Return 1 if and only if the repository has a commit-graph
> > + * file and generation data chunk has been written for the file.
> > + */
> > +int corrected_commit_dates_enabled(struct repository *r);
> > +
> >  enum commit_graph_write_flags {
> >  	COMMIT_GRAPH_WRITE_APPEND     = (1 << 0),
> >  	COMMIT_GRAPH_WRITE_PROGRESS   = (1 << 1),
> 
> All right.
> 
> > diff --git a/commit-graph.c b/commit-graph.c
> > index c1292f8e08..6411068411 100644
> > --- a/commit-graph.c
> > +++ b/commit-graph.c
> > @@ -703,6 +703,20 @@ int generation_numbers_enabled(struct repository *r)
> >  	return !!first_generation;
> >  }
> >
> > +int corrected_commit_dates_enabled(struct repository *r)
> > +{
> > +	struct commit_graph *g;
> > +	if (!prepare_commit_graph(r))
> > +		return 0;
> > +
> > +	g = r->objects->commit_graph;
> > +
> > +	if (!g->num_commits)
> > +		return 0;
> > +
> > +	return !!g->chunk_generation_data;
> > +}
> 
> The previous commit introduced validate_mixed_generation_chain(), which
> walked whole split commit-graph chain, and set `read_generation_data`
> field in `struct commit_graph` for all layers in the chain.
> 
> This function examines only the top layer, so it follows the assumption
> that Git would behave in such way that oly topmost layers in the chai
> can be GDAT-less.
> 
> Why the difference?  Couldn't validate_mixed_generation_chain() simply
> call corrected_commit_dates_enabled()?

The previous commit didn't need to walk the whole split commit-graph
chain. Because of how we are handling writing in a mixed generation data
chunk, if a layer has generation data chunk, all layers below it have a
generation data chunk as well.

So, there are two cases at hand:

- Topmost layer has generation data chunk, so we know all layers below
  it has generation data chunk and we can read values from it.
- Topmost layer does not have generation data chunk, so we know we can't
  read from generation data chunk.

Just checking the topmost layer suffices - modified the previous commit.

Then, this function is more or less the same as
`g->read_generation_data` that is, if we are reading from generation
data chunk, we are using corrected commit dates.

> 
> > +
> >  static void close_commit_graph_one(struct commit_graph *g)
> >  {
> >  	if (!g)
> > diff --git a/commit-reach.c b/commit-reach.c
> > index 470bc80139..3a1b925274 100644
> > --- a/commit-reach.c
> > +++ b/commit-reach.c
> > @@ -39,7 +39,7 @@ static struct commit_list *paint_down_to_common(struct repository *r,
> >  	int i;
> >  	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
> >
> > -	if (!min_generation)
> 
> This check was added in 091f4cf (commit: don't use generation numbers if
> not needed, 2018-08-30) by Derrick Stolee, and its commit message
> includes benchmark results for running 'git merge-base v4.8 v4.9' in
> Linux kernel repository:
> 
>       v2.18.0: 0.122s    167,468 walked
>   v2.19.0-rc1: 0.547s    635,579 walked
>          HEAD: 0.127s
> 
> > +	if (!min_generation && !corrected_commit_dates_enabled(r))
> >  		queue.compare = compare_commits_by_commit_date;
> 
> It would be nice to have similar benchmark for this change... unless of
> course there is no change in performance, but I think then it needs to
> be stated explicitly.  I think.
> 

Mentioned in the commit message - we walk (nearly) the same number of
commits but take somewhat longer.

> >
> >  	one->object.flags |= PARENT1;
> > diff --git a/t/t6024-recursive-merge.sh b/t/t6024-recursive-merge.sh
> > index 332cfc53fd..d3def66e7d 100755
> > --- a/t/t6024-recursive-merge.sh
> > +++ b/t/t6024-recursive-merge.sh
> > @@ -15,6 +15,8 @@ GIT_COMMITTER_DATE="2006-12-12 23:28:00 +0100"
> >  export GIT_COMMITTER_DATE
> >
> >  test_expect_success 'setup tests' '
> > +	GIT_TEST_COMMIT_GRAPH=0 &&
> > +	export GIT_TEST_COMMIT_GRAPH &&
> >  	echo 1 >a1 &&
> >  	git add a1 &&
> >  	GIT_AUTHOR_DATE="2006-12-12 23:00:00" git commit -m 1 a1 &&
> > @@ -66,7 +68,7 @@ test_expect_success 'setup tests' '
> >  '
> >
> >  test_expect_success 'combined merge conflicts' '
> > -	test_must_fail env GIT_TEST_COMMIT_GRAPH=0 git merge -m final G
> > +	test_must_fail git merge -m final G
> >  '
> >
> >  test_expect_success 'result contains a conflict' '
> 
> OK, so instead of disabling commit-graph for this test, now we disable
> it for the whole script.
> 
> Maybe this change should be in a separate patch?

With the explanation in commit message, it's clear to see how using
corrected commit dates leads to an (incorrectly) failing test. Does it
still make sense to seperate them?

> 
> Best,
> -- 
> Jakub Narębski

Thanks
- Abhishek