{"thread":{"id":"14721","subject":"q: git-fetch a tad slow?","startedAt":"2008-07-28T16:01:38Z","lastAt":"2008-07-31T21:19:19Z","messageCount":10,"participants":["Ingo Molnar","Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"85300","messageId":"20080728160138.GA12777@elte.hu","threadId":"14721","inReplyTo":null,"subject":"q: git-fetch a tad slow?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-28T16:01:38Z","receivedAt":"2008-07-28T16:01:38Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\nhere's another possibly stupid question.\n\nSetup/background: distributed kernel testing cluster, there's a central \nbox with a git repo of the kernel, and lots of of testboxes that track \nthat repo over ssh transport. In each \"iteration\" a random kernel config \nis generated, built and booted, and the booted up kernel is checked. \nPerformance of each iteration matters to total testing throughput, so i \ntry to optimize the critical path.\n\nProblem: i noticed that git-fetch is a tad slow:\n\n  titan:~/tip> time git-fetch\n \n  real    0m2.372s\n  user    0m0.814s\n  sys     0m0.951s\n\nThere are hundreds of branches, so i thought fetching a single branch \nalone would improve things:\n\n  titan:~/tip> time git-fetch origin master\n\n  real    0m0.942s\n  user    0m0.285s\n  sys     0m0.109s\n\nBut that's still slow - so i use a (lame) ad-hoc script instead:\n\n  titan:~/tip> time tip-fetch\n\n  real    0m0.246s\n  user    0m0.024s\n  sys     0m0.019s\n\n... which ssh's to the repo to check tip/master by hand:\n\n  HEAD=$(git-log -1 --pretty=format:\"%H\" HEAD)\n  RHEAD=$(ssh server \"cd tip; git-log master -1 --pretty=format:'%H'\")\n  [ \"$RHEAD\" != \"$HEAD\" ] && {\n    [...]\n  }\n\n... which script is lame/expensive on multiple levels but still is much \nfaster.\n\nI'm wondering, am i missing something obvious? It seems most of the \noverhead is local CPU overhead, so it's something in Git's domain and \nnot the expense of the ssh protocol. (which expense should be about 200 \nmsecs)\n\n\tIngo\n"},{"id":"85415","messageId":"20080729055014.GE11947@spearce.org","threadId":"14721","inReplyTo":"20080728160138.GA12777@elte.hu","subject":"Re: q: git-fetch a tad slow?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-29T05:50:14Z","receivedAt":"2008-07-29T05:50:14Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ingo Molnar <mingo@elte.hu> wrote:\n> \n> Setup/background: distributed kernel testing cluster, [...]\n> \n> Problem: i noticed that git-fetch is a tad slow:\n> \n>   titan:~/tip> time git-fetch\n>   real    0m2.372s\n> \n> There are hundreds of branches, so i thought fetching a single branch \n> alone would improve things:\n> \n>   titan:~/tip> time git-fetch origin master\n>   real    0m0.942s\n>\n> But that's still slow - so i use a (lame) ad-hoc script instead:\n> \n>   titan:~/tip> time tip-fetch\n>   real    0m0.246s\n\nOK, yes, when there are _many_ branches like that limiting fetch\nto a narrow focus of only the branch(es) you must have can make it\ngo much faster.  Part of the problem is we loop over the branches\nmany times, and those are O(N) loops (N=number of branches).  We\ncould do better, but we don't.\n\nOne reason why your tip-fetch runs so much better is because we don't\nhave to enumerate the hundreds of advertised branches offered up by\nthe remote peer to find the one you want to fetch.  Your tip-fetch\nis reading only that one ref file (.git/refs/heads/master) and\nthat's pretty much it.\n\nIn contrast git-upload-pack on the server side must open and read\n_all_ ref files under .git/refs/ and send them to the client, who\nthen has to loop over them at least twice before it can decide if\na match exists.  That's a lot more data to shove down over SSH.\nGranted its only 42 bytes + refname per ref, but its still more.\n\nThose O(N) loops I referred to earlier can explain why for hundreds\nof branches it gets ugly.  That turns into an O(N^2) matching\nalgorithm.  Not pretty.  A simple hash would solve a lot of that,\nchanging the first time from 0m2.372s to much closer to the scond\ntime of 0m0.942s.\n\nNeither of which can compete with your tip-fetch.\n\nHave you tried using git-pack-refs to pack the branches on the\nremote repository?\n\nIf you update all of the branches, run `git pack-refs --all --prune`,\nthen allow the testing clients to start fetching it may go much\nquicker.  The pack-refs moves all of the individual ref files into\nthe single .git/packed-refs file, reducing the number of files we\nneed to open and read to service a single fetch client.\n\nI wonder if git-pack-refs + fetching only a single branch will get\nyou closer to the tip-fetch time.\n\nAlso, I wonder if you really need to fetch over SSH.  Doing a\nfetch over git:// is much quicker, as there is no SSH session\nsetup overheads.\n\n-- \nShawn.\n"},{"id":"85440","messageId":"20080729090802.GA11373@elte.hu","threadId":"14721","inReplyTo":"20080729055014.GE11947@spearce.org","subject":"Re: q: git-fetch a tad slow?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-29T09:08:02Z","receivedAt":"2008-07-29T09:08:02Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Shawn O. Pearce <spearce@spearce.org> wrote:\n\n> Ingo Molnar <mingo@elte.hu> wrote:\n> > \n> > Setup/background: distributed kernel testing cluster, [...]\n> > \n> > Problem: i noticed that git-fetch is a tad slow:\n> > \n> >   titan:~/tip> time git-fetch\n> >   real    0m2.372s\n\n> Also, I wonder if you really need to fetch over SSH.  Doing a fetch \n> over git:// is much quicker, as there is no SSH session setup \n> overheads.\n\nnote that titan is a very beefy box, almost 3 GHz Core2Duo:\n\n   model name      : Intel(R) Core(TM)2 CPU         E6800  @ 2.93GHz\n   stepping        : 5\n   cpu MHz         : 2933.331\n\nserver is 3 GHz. So if we have a quadratic overhead on number of \nbranches, that's going to be quite a PITA.\n\n> I wonder if git-pack-refs + fetching only a single branch will get you \n> closer to the tip-fetch time.\n\nshould i pack on both repos? I dont explicitly pack anything, but on the \nserver it goes into regular gc runs. (which will pack most stuff, \nright?)\n\n\tIngo\n"},{"id":"85568","messageId":"20080730044855.GA7225@spearce.org","threadId":"14721","inReplyTo":"20080729090802.GA11373@elte.hu","subject":"Re: q: git-fetch a tad slow?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-30T04:48:55Z","receivedAt":"2008-07-30T04:48:55Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ingo Molnar <mingo@elte.hu> wrote:\n> * Shawn O. Pearce <spearce@spearce.org> wrote:\n> > Ingo Molnar <mingo@elte.hu> wrote:\n> > > \n> > > Setup/background: distributed kernel testing cluster, [...]\n> > > \n> > > Problem: i noticed that git-fetch is a tad slow:\n> > > \n> > >   titan:~/tip> time git-fetch\n> > >   real    0m2.372s\n>\n> note that titan is a very beefy box, almost 3 GHz Core2Duo:\n\nThat isn't going to matter if you have a quadratic algorithm and a\nlarge dataset.  Especially when the inner loops are doing multiple\nsystem calls per item in a long list of items.  :-|   Linux is fast,\nbut it isn't magic pixie dust.  It cannot fix broken applications.\n \n> [...] So if we have a quadratic overhead on number of \n> branches, that's going to be quite a PITA.\n\nRight.\n\n> > I wonder if git-pack-refs + fetching only a single branch will get you \n> > closer to the tip-fetch time.\n> \n> should i pack on both repos? I dont explicitly pack anything, but on the \n> server it goes into regular gc runs. (which will pack most stuff, \n> right?)\n\ngit-gc automatically runs `git pack-refs --all --prune` like I\nrecommended, unless you disabled it with config gc.packrefs = false.\nSo its probably already packed.\n\nWhat does `find .git/refs -type f | wc -l` give for the repository\non the central server?  If its more than a handful (~20) I would\nsuggest running git-gc before testing again.\n\nBut I'm really suspecting that this is just our quadratic matching\nalgorithm running up against a large number of branches, causing\nit to suck.\n\njgit at least uses an O(N) algorithm here, but since it is written\nin Java its of course slow compared to C Git.  Takes a while to\nget that JVM running.\n\nI'll try to find some time to reproduce the issue and look at the\nbottleneck here.  I'm two days into a new job so my git time has\nbeen really quite short this week.  :-|\n\n-- \nShawn.\n"},{"id":"85668","messageId":"20080730190657.GC26389@elte.hu","threadId":"14721","inReplyTo":"20080730044855.GA7225@spearce.org","subject":"Re: q: git-fetch a tad slow?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-30T19:06:57Z","receivedAt":"2008-07-30T19:06:57Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Shawn O. Pearce <spearce@spearce.org> wrote:\n\n> > should i pack on both repos? I dont explicitly pack anything, but on \n> > the server it goes into regular gc runs. (which will pack most \n> > stuff, right?)\n> \n> git-gc automatically runs `git pack-refs --all --prune` like I \n> recommended, unless you disabled it with config gc.packrefs = false. \n> So its probably already packed.\n> \n> What does `find .git/refs -type f | wc -l` give for the repository on \n> the central server?  If its more than a handful (~20) I would suggest \n> running git-gc before testing again.\n\nah, you are right, it gave 275, then git-gc brought it down to two:\n\n  earth4:~/tip> find .git/refs -type f | wc -l\n  275\n  earth4:~/tip> git gc\n  earth4:~/tip> find .git/refs -type f | wc -l\n  2\n\ni turned off auto-gc recently (two weeks ago) because it was \nauto-triggering _way_ too frequently. (like on every fifth merge i was \ndoing or so)\n\nalas, fetching still seems to be slow:\n\n  titan:~/tip> time git-fetch origin\n\n  real    0m5.112s\n  user    0m0.972s\n  sys     0m3.380s\n\n(but the gc run has not finished yet on the central repo so this isnt \nfully valid.)\n\n> But I'm really suspecting that this is just our quadratic matching \n> algorithm running up against a large number of branches, causing it to \n> suck.\n> \n> jgit at least uses an O(N) algorithm here, but since it is written in \n> Java its of course slow compared to C Git.  Takes a while to get that \n> JVM running.\n> \n> I'll try to find some time to reproduce the issue and look at the \n> bottleneck here.  I'm two days into a new job so my git time has been \n> really quite short this week.  :-|\n\nfetching the -tip repo:\n\n   http://people.redhat.com/mingo/tip.git/README\n\nand then running 'git remote update' will i think already show this \nproblem for you too. People have been complaining about how slow the \nupdate is.\n\n\tIngo\n"},{"id":"85700","messageId":"20080730223814.GF28503@spearce.org","threadId":"14721","inReplyTo":"20080730190657.GC26389@elte.hu","subject":"Re: q: git-fetch a tad slow?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-30T22:38:14Z","receivedAt":"2008-07-30T22:38:14Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ingo Molnar <mingo@elte.hu> wrote:\n> * Shawn O. Pearce <spearce@spearce.org> wrote:\n> > \n> > What does `find .git/refs -type f | wc -l` give for the repository on \n> > the central server?  If its more than a handful (~20) I would suggest \n> > running git-gc before testing again.\n> \n> ah, you are right, it gave 275, then git-gc brought it down to two:\n> \n>   earth4:~/tip> find .git/refs -type f | wc -l\n>   275\n>   earth4:~/tip> git gc\n>   earth4:~/tip> find .git/refs -type f | wc -l\n>   2\n> \n> alas, fetching still seems to be slow:\n> \n>   titan:~/tip> time git-fetch origin\n> \n>   real    0m5.112s\n>   user    0m0.972s\n>   sys     0m3.380s\n\nYea, OK, there's definately performance problems there.  And it\nshould be fast.  Its too common of a case (fetching small deltas).\n \n> > I'll try to find some time to reproduce the issue and look at the \n> > bottleneck here.  I'm two days into a new job so my git time has been \n> > really quite short this week.  :-|\n> \n> fetching the -tip repo:\n> \n>    http://people.redhat.com/mingo/tip.git/README\n> \n> and then running 'git remote update' will i think already show this \n> problem for you too. People have been complaining about how slow the \n> update is.\n\nThanks.  I'll try to poke at it this evening and see what I find.\ngit-fetch should be running faster than this.\n\n-- \nShawn.\n"},{"id":"85723","messageId":"20080731044531.GB1860@spearce.org","threadId":"14721","inReplyTo":"20080730190657.GC26389@elte.hu","subject":"Re: q: git-fetch a tad slow?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-31T04:45:31Z","receivedAt":"2008-07-31T04:45:31Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ingo Molnar <mingo@elte.hu> wrote:\n> alas, fetching still seems to be slow:\n> \n>   titan:~/tip> time git-fetch origin\n> \n>   real    0m5.112s\n>   user    0m0.972s\n>   sys     0m3.380s\n\nWhat version of git are dealing with on the client side?\n\nI only have a MacBook Pro (2.4 GHz Intel Core 2 Duo) and I'm getting\nfetch times of ~472 ms over git:// to your -tip.git tree and ~128\nms for strictly local fetch.  If your SSH overhead is ~300 ms this\nis only a ~700 ms real time for `git fetch origin`, not 5100 ms.\n\nIs your git-fetch a shell script?  Or a compiled binary?  The port\ninto C made it go _much_ faster, even though it is still a naive\nO(N^2) matching algorithm.  Yea, we still should fix that, but\nI think an upgrade to 1.5.4 or later would make the client side\nimprove consideribly.\n\n-- \nShawn.\n"},{"id":"85824","messageId":"20080731210307.GF25138@elte.hu","threadId":"14721","inReplyTo":"20080731044531.GB1860@spearce.org","subject":"Re: q: git-fetch a tad slow?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-31T21:03:07Z","receivedAt":"2008-07-31T21:03:07Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Shawn O. Pearce <spearce@spearce.org> wrote:\n\n> Ingo Molnar <mingo@elte.hu> wrote:\n> > alas, fetching still seems to be slow:\n> > \n> >   titan:~/tip> time git-fetch origin\n> > \n> >   real    0m5.112s\n> >   user    0m0.972s\n> >   sys     0m3.380s\n> \n> What version of git are dealing with on the client side?\n\nthe client side on titan has:\n\n titan:~> git version\n git version 1.5.2.2\n\noldish but not outrageously old, right?\n\n server side has:\n\n earth4:~> git version\n git version 1.5.6.1.108.g660379\n\n> \n> fetch times of ~472 ms over git:// to your -tip.git tree and ~128 ms \n> for strictly local fetch.  If your SSH overhead is ~300 ms this is \n> only a ~700 ms real time for `git fetch origin`, not 5100 ms.\n> \n> Is your git-fetch a shell script?  Or a compiled binary?  The port \n> into C made it go _much_ faster, even though it is still a naive \n> O(N^2) matching algorithm.  Yea, we still should fix that, but I think \n> an upgrade to 1.5.4 or later would make the client side improve \n> consideribly.\n\nah, it is a shell script indeed! I'll upgrade to latest.\n\n\tIngo\n"},{"id":"85826","messageId":"20080731211141.GA1159@elte.hu","threadId":"14721","inReplyTo":"20080731210307.GF25138@elte.hu","subject":"Re: q: git-fetch a tad slow?","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2008-07-31T21:11:41Z","receivedAt":"2008-07-31T21:11:41Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar <mingo@elte.hu> wrote:\n\n> > for strictly local fetch.  If your SSH overhead is ~300 ms this is \n> > only a ~700 ms real time for `git fetch origin`, not 5100 ms.\n> > \n> > Is your git-fetch a shell script?  Or a compiled binary?  The port \n> > into C made it go _much_ faster, even though it is still a naive \n> > O(N^2) matching algorithm.  Yea, we still should fix that, but I \n> > think an upgrade to 1.5.4 or later would make the client side \n> > improve consideribly.\n> \n> ah, it is a shell script indeed! I'll upgrade to latest.\n\non another box, with 1.5.4, i have:\n\n dione:~/tip> time git fetch origin\n\n real    0m0.481s\n user    0m0.136s\n sys     0m0.060s\n\n dione:~/tip> time ./tip-fetch\n b714d1a257cca93ba6422ca3276ac80a2cde2b59\n b714d1a257cca93ba6422ca3276ac80a2cde2b59\n\n real    0m0.273s\n user    0m0.012s\n sys     0m0.020s\n\nthat's a 2.66 GHz core2 quad, i.e. a pretty fast box too. As you can see \nmost time spent in the tip-fetch case was waiting for the network. So \nthere's about 200 msecs of extra CPU cost on the local side. On a CPU \n1-2 generations older that could be up to 1000 msecs or more.\n\nIn any case, performance has improved significantly with the C version! \n(I'll still use tip-fetch to squeeze out the last bit of performance, \nbut it's quite comparable now.)\n\nSorry that i didnt notice that titan had 1.5.2 - i almost never notice \nit when i switch between stable git versions. (you guys are doing a \nreally good job on compatibility)\n\n\tIngo\n"},{"id":"85828","messageId":"20080731211919.GC24631@spearce.org","threadId":"14721","inReplyTo":"20080731211141.GA1159@elte.hu","subject":"Re: q: git-fetch a tad slow?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-31T21:19:19Z","receivedAt":"2008-07-31T21:19:19Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ingo Molnar <mingo@elte.hu> wrote:\n> \n> on another box, with 1.5.4, i have:\n> \n>  dione:~/tip> time git fetch origin\n> \n>  real    0m0.481s\n>  user    0m0.136s\n>  sys     0m0.060s\n> \n>  dione:~/tip> time ./tip-fetch\n>  b714d1a257cca93ba6422ca3276ac80a2cde2b59\n>  b714d1a257cca93ba6422ca3276ac80a2cde2b59\n> \n>  real    0m0.273s\n>  user    0m0.012s\n>  sys     0m0.020s\n> \n> that's a 2.66 GHz core2 quad, i.e. a pretty fast box too. As you can see \n> most time spent in the tip-fetch case was waiting for the network. So \n> there's about 200 msecs of extra CPU cost on the local side.\n\nYea.  My testing last night was suggesting about 1/2 of that 200\nms is on the client, and the other 200 ms is on the server side\nof the connection.  That matches up somewhat with your test above,\nwhere git-fetch used about 100 ms more user time on the client side\nthan your tip-fetch shell script.\n\nI have no clue where the bottleneck is, I didn't get that far before\nI realized you must have been running a shell script based git-fetch\nto be seeing the performance you were.\n\nMaybe 1.6.1 or .2 we can try to squeeze fetch to run faster.\nIts far too late for 1.6.0.\n\n> Sorry that i didnt notice that titan had 1.5.2 - i almost never notice \n> it when i switch between stable git versions. (you guys are doing a \n> really good job on compatibility)\n\nYea, its easy to not realize your git isn't giving you the latest\nand greatest toys.  ;-)\n\n-- \nShawn.\n"}]}