On Thu, Feb 24, 2022 at 08:38:32PM +0000, Derrick Stolee via GitGitGadget wrote:
> From: Derrick Stolee <derrickstolee@github.com>
> 
> The 'read_generation_data' member of 'struct commit_graph' was
> introduced by 1fdc383c5 (commit-graph: use generation v2 only if entire
> chain does, 2021-01-16). The intention was to avoid using corrected
> commit dates if not all layers of a commit-graph had that data stored.
> The logic in validate_mixed_generation_chain() at that point incorrectly
> initialized read_generation_data to 1 if and only if the tip
> commit-graph contained the Corrected Commit Date chunk.
> 
> This was "fixed" in 448a39e65 (commit-graph: validate layers for
> generation data, 2021-02-02) to validate that read_generation_data was
> either non-zero for all layers, or it would set read_generation_data to
> zero for all layers.
> 
> The problem here is that read_generation_data is not initialized to be
> non-zero anywhere!
> 
> This change initializes read_generation_data immediately after the chunk
> is parsed, so each layer will have its value present as soon as
> possible.
> 
> The read_generation_data member is used in fill_commit_graph_info() to
> determine if we should use the corrected commit date or the topological
> levels stored in the Commit Data chunk. Due to this bug, all previous
> versions of Git were defaulting to topological levels in all cases!
> 
> This can be measured with some performance tests. Using the Linux kernel
> as a testbed, I generated a complete commit-graph containing corrected
> commit dates and tested the 'new' version against the previous, 'old'
> version.
> 
> First, rev-list with --topo-order demonstrates a 26% improvement using
> corrected commit dates:
> 
> hyperfine \
> 	-n "old" "$OLD_GIT rev-list --topo-order -1000 v3.6" \
> 	-n "new" "$NEW_GIT rev-list --topo-order -1000 v3.6" \
> 	--warmup=10
> 
> Benchmark 1: old
>   Time (mean ± σ):      57.1 ms ±   3.1 ms
>   Range (min … max):    52.9 ms …  62.0 ms    55 runs
> 
> Benchmark 2: new
>   Time (mean ± σ):      45.5 ms ±   3.3 ms
>   Range (min … max):    39.9 ms …  51.7 ms    59 runs
> 
> Summary
>   'new' ran
>     1.26 ± 0.11 times faster than 'old'
> 
> These performance improvements are due to the algorithmic improvements
> given by walking fewer commits due to the higher cutoffs from corrected
> commit dates.
> 
> However, this comes at a cost. The additional I/O cost of parsing the
> corrected commit dates is visible in case of merge-base commands that do
> not reduce the overall number of walked commits.
> 
> hyperfine \
>         -n "old" "$OLD_GIT merge-base v4.8 v4.9" \
>         -n "new" "$NEW_GIT merge-base v4.8 v4.9" \
>         --warmup=10
> 
> Benchmark 1: old
>   Time (mean ± σ):     110.4 ms ±   6.4 ms
>   Range (min … max):    96.0 ms … 118.3 ms    25 runs
> 
> Benchmark 2: new
>   Time (mean ± σ):     150.7 ms ±   1.1 ms
>   Range (min … max):   149.3 ms … 153.4 ms    19 runs
> 
> Summary
>   'old' ran
>     1.36 ± 0.08 times faster than 'new'
> 
> Performance issues like this are what motivated 702110aac (commit-graph:
> use config to specify generation type, 2021-02-25).
> 
> In the future, we could fix this performance problem by inserting the
> corrected commit date offsets into the Commit Date chunk instead of
> having that data in an extra chunk.
> 
> Signed-off-by: Derrick Stolee <derrickstolee@github.com>
> ---
>  commit-graph.c                |  3 +++
>  t/t4216-log-bloom.sh          |  2 +-
>  t/t5318-commit-graph.sh       | 14 ++++++++++++--
>  t/t5324-split-commit-graph.sh |  9 +++++++--
>  4 files changed, 23 insertions(+), 5 deletions(-)
> 
> diff --git a/commit-graph.c b/commit-graph.c
> index a19bd96c2ee..8e52bb09552 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -407,6 +407,9 @@ struct commit_graph *parse_commit_graph(struct repository *r,
>  			&graph->chunk_generation_data);
>  		pair_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,
>  			&graph->chunk_generation_data_overflow);
> +
> +		if (graph->chunk_generation_data)
> +			graph->read_generation_data = 1;
>  	}
>  
>  	if (r->settings.commit_graph_read_changed_paths) {

I wanted to test your changes because they seem quite exciting in the
context of my work as well, but this commit seems to uncover a bug with
how we handle overflows. I originally triggered the bug when trying to
do a mirror-fetch, but as it turns it seems to trigger now whenever the
commit-graph is being read:

    $ git commit-graph verify
    fatal: commit-graph requires overflow generation data but has none

    $ git commit-graph write --split
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    fatal: commit-graph requires overflow generation data but has none

    $ git commit-graph write --split=replace
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    fatal: commit-graph requires overflow generation data but has none

I initially assumed this may be a bug with how we previously wrote the
commit-graph, but removing all chains still reliably triggers it:

    $ rm -f objects/info/commit-graphs/*
    $ git commit-graph write --split
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    fatal: commit-graph requires overflow generation data but has none

I haven't yet found the time to dig deeper into why this is happening.
While the repository is publicly accessible at [1], unfortunately the
bug seems to be triggered by a commit that's only kept alive by an
internal reference.

Patrick

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git