"git fetch" is extremely slow on large repos

[TamsynUlthara]

After cloning a large Mercurial repository (16K+ commits, 820 heads) using git-remote-hg, running git fetch is extremely slow. This is the case even when the source repository is local (i.e., on the same machine).

The following two lines are output almost immediately:

searching for changes
no changes found

It then takes between 3-4 minutes before the command finishes.

Cloning the repository takes about 7 minutes. A push to the same repository completes very quickly (under 1 second).

[fingolfin]

Do you know a public repository where one can reproduce this?

[artkat]

You can try fetch https://github.com/xamarin/monodroid-samples.git which takes ages.

[TamsynUlthara]

A public repo example:

Running "git fetch" against http://hg.mozilla.org/mozilla-central/ takes over a minute, even when there are no upstream changes:

$ time git fetch
searching for changes
no changes found
git fetch  25.44s user 3.27s system 41% cpu 1:09.45 total

As with my initial report, searching for changes and no changes found are output very quickly.

[felipec]

Unfortunately I don't think there's anything that can be done. Mercurial's internal repository format is not very efficient and that means git-remote-hg needs to do very expensive extra steps, and there's no way around that (unless Mercurial fixes their format).

[mnauw]

There may very well be an inefficient Mercurial repository format and obviously an initial clone/fetch on a large repo will take some time. However, the problem here is about what happens when doing another fetch when there are no changes on the hg side at all. And that is something that is being tracked by git-remote-hg (such as in marks-hg).

In particular, the gitrange function calculates the hg revisions that need to be fetched (based on last import and current remote state). it turns out there is a bug there when calculating the range a..a (so when there has been no change on the remote) that results in coming up with all revisions.

Of course, it takes some time to come up with all revisions and moreover to deal with them (which will lead to no changes), and in case of a full fetch this is done for every remote head.

Above commit fixes this issue and also simplifies gitrange a bit along the way.

[mnauw]

While most of the operations during fetch are linear in the amount of (new) revisions to fetch, there is a fixed overhead due to the reading (and writing) of the marks files, which depends mostly on their size and that in turn on the size of the repo (i.e. number of revisions).

Since git-fast-import will also place non-commit objects in the marks file (as opposed to git-fast-export) the marks-git file in particular can be large and so manipulating that one can take a few seconds (or more depending on your system hw). If you also push to the remote repo, then marks-git should shrink anyway. But if you do not, then mnauw/git-remote-hg@38741e0 adds a helper script that can (a.o.) shrink that also a bit (fwiw, it may not be unique in that respect, but anyway ...)

[felipec]

Above commit fixes this issue and also simplifies gitrange a bit along the way.

@mnauw That is true, but this a much simpler fix 510441b. Also, I don't think that above code is correct.

I found out a couple more of optimizations, like storing the parent function (fe8b8c1) makes the code significantly faster.

With those two changes the code of gitrange() is significantly faster than revwalk(), actually 40% faster.

I wrote a script to test the different revision walking algorithms, and yes, the original gitrange() is 30% slower, but the modified one is 40% faster than yours.

gitrange: 5.61
revwalk: 9.92
gitrange_orig: 12.62
internal: 6.44

I believe checking the marks for each and every revision is significantly more expensive.

I tested this with mozilla-central. If there are no changes, the code should be much faster now. Please check with the latest version in master.