Re: commit-graph is cool (overcoming add_missing_tags() perf issues)

From: Derrick Stolee <stolee@gmail.com>
Date: Oct 17, 2018, 18:19 UTC
Message-ID: <1d52a566-e7f5-9b7f-4bb1-cac5a50ebcb6@gmail.com>
In-Reply-To: <CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com>

On 10/17/2018 2:00 PM, Elijah Newren wrote:

Show 18 quoted lines

> Hi,
>
> Just wanted to give a shout-out for the commit-graph work and how
> impressive it is.  I had an internal report from a user that git
> pushes containing only one new tiny commit were taking over a minute
> (in a moderate size repo with good network connectivity). After
> digging for a while, I noticed three unusual things about the repo[1]:
>    * he had push.followTags set to true
>    * upstream repo had about 20k tags (despite only 55k commits)
>    * his repo had an additional 2.5k tags, but none of these were in
>      the history of the branches he was pushing and thus would not be
>      included in any pushes.
>
> Digging in, almost all the time was CPU-bound and spent in
> add_missing_tags()[2].  If I'm reading the code correctly, it appears
> that function loops over each tag, calling in_merge_bases_many() once
> per tag.  Thus, for his case, we were potentially walking all of
> history of the main branch 2.5k times.  That seemed rather suboptimal.

Thanks for the report. I made a note to inspect add_missing_tags() for more improvement in the future.

Show 9 quoted lines

> Before attempting to optimize, I decided to try out the commit-graph
> with a version of git from pu.  While I expected a speed-up, I was a
> bit suprised that it was a factor of over 100; dropping the time for
> local dry-run push[2] to sub-second.  A quick look suggests that
> commit-graph doesn't fix the fact that we call in_merge_bases_many() N
> times from add_missing_tags() and thus likely need to do N merge base
> computations, it just makes each of the N much faster.  So, perhaps
> there's still another scaling issue we'll eventually need to address,
> but for now, I'm pretty excited about commit-graph.

Without the commit-graph, you are getting a quadratic problem (N commits 
* T tags), but with the commit-graph you are also getting the benefit of 
generation numbers, so the "N commits" is actually likely _zero_ for 
most tags, because the tags have strictly lower generation number. In 
those cases, we can terminate without any walk at all.

Thanks! -Stolee