q: git-fetch a tad slow?

here's another possibly stupid question.

Setup/background: distributed kernel testing cluster, there's a central box with a git repo of the kernel, and lots of of testboxes that track that repo over ssh transport. In each "iteration" a random kernel config is generated, built and booted, and the booted up kernel is checked. Performance of each iteration matters to total testing throughput, so i try to optimize the critical path.

Problem: i noticed that git-fetch is a tad slow:

  titan:~/tip> time git-fetch
 
  real    0m2.372s
  user    0m0.814s
  sys     0m0.951s

There are hundreds of branches, so i thought fetching a single branch alone would improve things:

  titan:~/tip> time git-fetch origin master

  real    0m0.942s
  user    0m0.285s
  sys     0m0.109s

But that's still slow - so i use a (lame) ad-hoc script instead:

  titan:~/tip> time tip-fetch

  real    0m0.246s
  user    0m0.024s
  sys     0m0.019s

... which ssh's to the repo to check tip/master by hand:

  HEAD=$(git-log -1 --pretty=format:"%H" HEAD)
  RHEAD=$(ssh server "cd tip; git-log master -1 --pretty=format:'%H'")
  [ "$RHEAD" != "$HEAD" ] && {
    [...]
  }

... which script is lame/expensive on multiple levels but still is much faster.

I'm wondering, am i missing something obvious? It seems most of the overhead is local CPU overhead, so it's something in Git's domain and not the expense of the ssh protocol. (which expense should be about 200 msecs)

	Ingo

Ingo Molnar <mingo@elte.hu> wrote:

OK, yes, when there are _many_ branches like that limiting fetch to a narrow focus of only the branch(es) you must have can make it go much faster. Part of the problem is we loop over the branches many times, and those are O(N) loops (N=number of branches). We could do better, but we don't.

One reason why your tip-fetch runs so much better is because we don't have to enumerate the hundreds of advertised branches offered up by the remote peer to find the one you want to fetch. Your tip-fetch is reading only that one ref file (.git/refs/heads/master) and that's pretty much it.

In contrast git-upload-pack on the server side must open and read _all_ ref files under .git/refs/ and send them to the client, who then has to loop over them at least twice before it can decide if a match exists. That's a lot more data to shove down over SSH. Granted its only 42 bytes + refname per ref, but its still more.

Those O(N) loops I referred to earlier can explain why for hundreds of branches it gets ugly. That turns into an O(N^2) matching algorithm. Not pretty. A simple hash would solve a lot of that, changing the first time from 0m2.372s to much closer to the scond time of 0m0.942s.

Neither of which can compete with your tip-fetch.

Have you tried using git-pack-refs to pack the branches on the remote repository?

If you update all of the branches, run `git pack-refs --all --prune`, then allow the testing clients to start fetching it may go much quicker. The pack-refs moves all of the individual ref files into the single .git/packed-refs file, reducing the number of files we need to open and read to service a single fetch client.

I wonder if git-pack-refs + fetching only a single branch will get you closer to the tip-fetch time.

Also, I wonder if you really need to fetch over SSH. Doing a fetch over git:// is much quicker, as there is no SSH session setup overheads.

* Shawn O. Pearce <spearce@spearce.org> wrote:

note that titan is a very beefy box, almost 3 GHz Core2Duo:

   model name      : Intel(R) Core(TM)2 CPU         E6800  @ 2.93GHz
   stepping        : 5
   cpu MHz         : 2933.331

server is 3 GHz. So if we have a quadratic overhead on number of branches, that's going to be quite a PITA.

should i pack on both repos? I dont explicitly pack anything, but on the server it goes into regular gc runs. (which will pack most stuff, right?)

	Ingo

Ingo Molnar <mingo@elte.hu> wrote:

That isn't going to matter if you have a quadratic algorithm and a
large dataset.  Especially when the inner loops are doing multiple
system calls per item in a long list of items.  :-|   Linux is fast,
but it isn't magic pixie dust.  It cannot fix broken applications.
 

Right.

git-gc automatically runs `git pack-refs --all --prune` like I recommended, unless you disabled it with config gc.packrefs = false. So its probably already packed.

What does `find .git/refs -type f | wc -l` give for the repository on the central server? If its more than a handful (~20) I would suggest running git-gc before testing again.

But I'm really suspecting that this is just our quadratic matching algorithm running up against a large number of branches, causing it to suck.

jgit at least uses an O(N) algorithm here, but since it is written in Java its of course slow compared to C Git. Takes a while to get that JVM running.

I'll try to find some time to reproduce the issue and look at the bottleneck here. I'm two days into a new job so my git time has been really quite short this week. :-|

* Shawn O. Pearce <spearce@spearce.org> wrote:

ah, you are right, it gave 275, then git-gc brought it down to two:

  earth4:~/tip> find .git/refs -type f | wc -l
  275
  earth4:~/tip> git gc
  earth4:~/tip> find .git/refs -type f | wc -l
  2

i turned off auto-gc recently (two weeks ago) because it was auto-triggering _way_ too frequently. (like on every fifth merge i was doing or so)

alas, fetching still seems to be slow:

  titan:~/tip> time git-fetch origin

  real    0m5.112s
  user    0m0.972s
  sys     0m3.380s

(but the gc run has not finished yet on the central repo so this isnt fully valid.)

fetching the -tip repo:

   http://people.redhat.com/mingo/tip.git/README

and then running 'git remote update' will i think already show this problem for you too. People have been complaining about how slow the update is.

	Ingo

Ingo Molnar <mingo@elte.hu> wrote:

Yea, OK, there's definately performance problems there.  And it
should be fast.  Its too common of a case (fetching small deltas).
 

Thanks. I'll try to poke at it this evening and see what I find. git-fetch should be running faster than this.

Ingo Molnar <mingo@elte.hu> wrote:

What version of git are dealing with on the client side?

I only have a MacBook Pro (2.4 GHz Intel Core 2 Duo) and I'm getting fetch times of ~472 ms over git:// to your -tip.git tree and ~128 ms for strictly local fetch. If your SSH overhead is ~300 ms this is only a ~700 ms real time for `git fetch origin`, not 5100 ms.

Is your git-fetch a shell script? Or a compiled binary? The port into C made it go _much_ faster, even though it is still a naive O(N^2) matching algorithm. Yea, we still should fix that, but I think an upgrade to 1.5.4 or later would make the client side improve consideribly.

* Shawn O. Pearce <spearce@spearce.org> wrote:

the client side on titan has:

 titan:~> git version
 git version 1.5.2.2

oldish but not outrageously old, right?

 server side has:

 earth4:~> git version
 git version 1.5.6.1.108.g660379

ah, it is a shell script indeed! I'll upgrade to latest.

	Ingo

* Ingo Molnar <mingo@elte.hu> wrote:

on another box, with 1.5.4, i have:

 dione:~/tip> time git fetch origin

 real    0m0.481s
 user    0m0.136s
 sys     0m0.060s

 dione:~/tip> time ./tip-fetch
 b714d1a257cca93ba6422ca3276ac80a2cde2b59
 b714d1a257cca93ba6422ca3276ac80a2cde2b59

 real    0m0.273s
 user    0m0.012s
 sys     0m0.020s

that's a 2.66 GHz core2 quad, i.e. a pretty fast box too. As you can see most time spent in the tip-fetch case was waiting for the network. So there's about 200 msecs of extra CPU cost on the local side. On a CPU 1-2 generations older that could be up to 1000 msecs or more.

In any case, performance has improved significantly with the C version! (I'll still use tip-fetch to squeeze out the last bit of performance, but it's quite comparable now.)

Sorry that i didnt notice that titan had 1.5.2 - i almost never notice it when i switch between stable git versions. (you guys are doing a really good job on compatibility)

	Ingo

Ingo Molnar <mingo@elte.hu> wrote:

Yea. My testing last night was suggesting about 1/2 of that 200 ms is on the client, and the other 200 ms is on the server side of the connection. That matches up somewhat with your test above, where git-fetch used about 100 ms more user time on the client side than your tip-fetch shell script.

I have no clue where the bottleneck is, I didn't get that far before I realized you must have been running a shell script based git-fetch to be seeing the performance you were.

Maybe 1.6.1 or .2 we can try to squeeze fetch to run faster. Its far too late for 1.6.0.

Yea, its easy to not realize your git isn't giving you the latest and greatest toys. ;-)