git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / Atom feed
From: Elijah Newren <newren@gmail.com>
To: Derrick Stolee <dstolee@microsoft.com>
Cc: Git Mailing List <git@vger.kernel.org>
Subject: commit-graph is cool (overcoming add_missing_tags() perf issues)
Date: Wed, 17 Oct 2018 11:00:03 -0700
Message-ID: <CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com> (raw)

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.

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.

(And in the mean time I gave the user a one-liner to nuke his
local-only tags that I suspect he doesn't need.)

Thanks,
Elijah


[1] lerna seems to scale horribly, especially when you suddenly
transition dozens of web developers and even more independent
repositories into a single large monorepo.  Usage of lerna was
thankfully ripped out at some point, but the crazy number of
historical tags remain.  Also, this user did a bunch of the
filter-branch'ing to suck extra repos into the monorepo, likely
involved somehow in the many extra tags he had.

[2] In fact, I still had timings of over a minute when adjusting the command to:
  git push --follow-tags --dry-run /PATH/TO/LOCAL-MIRROR $BRANCH

             reply index

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-10-17 18:00 Elijah Newren [this message]
2018-10-17 18:19 ` Derrick Stolee
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 publically 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=CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com \
    --to=newren@gmail.com \
    --cc=dstolee@microsoft.com \
    --cc=git@vger.kernel.org \
    /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

git@vger.kernel.org list mirror (unofficial, one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Example config snippet for mirrors

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox