On Thu, Feb 24, 2022 at 08:38:32PM +0000, Derrick Stolee via GitGitGadget wrote:
> From: Derrick Stolee <derrickstolee@xxxxxxxxxx>
>
> 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@xxxxxxxxxx>
> ---
> 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
Attachment:
signature.asc
Description: PGP signature
