From: Derrick Stolee <stolee@gmail.com>
To: Elijah Newren <newren@gmail.com>, Derrick Stolee <dstolee@microsoft.com>
Cc: Git Mailing List <git@vger.kernel.org>
Subject: Re: commit-graph is cool (overcoming add_missing_tags() perf issues)
Date: Wed, 17 Oct 2018 14:19:40 -0400 [thread overview]
Message-ID: <1d52a566-e7f5-9b7f-4bb1-cac5a50ebcb6@gmail.com> (raw)
In-Reply-To: <CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com>
On 10/17/2018 2:00 PM, Elijah Newren wrote:
> 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.
> 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
next prev parent reply other threads:[~2018-10-17 18:19 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-10-17 18:00 commit-graph is cool (overcoming add_missing_tags() perf issues) Elijah Newren
2018-10-17 18:19 ` Derrick Stolee [this message]
2018-10-17 18:31 ` Jeff King
2018-10-30 14:22 ` Derrick Stolee
2018-10-31 5:45 ` Elijah Newren
2018-10-30 16:22 ` Ævar Arnfjörð Bjarmason
2018-10-31 5:46 ` Elijah Newren
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1d52a566-e7f5-9b7f-4bb1-cac5a50ebcb6@gmail.com \
--to=stolee@gmail.com \
--cc=dstolee@microsoft.com \
--cc=git@vger.kernel.org \
--cc=newren@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).