{"thread":{"id":"25343","subject":"Trac+Git: rev-list with pathspec performance?","startedAt":"2010-10-04T20:21:50Z","lastAt":"2010-10-07T20:33:59Z","messageCount":6,"participants":["Stephen Bash","Jonathan Nieder","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"152586","messageId":"27777603.436995.1286223710787.JavaMail.root@mail.hq.genarts.com","threadId":"25343","inReplyTo":"13399611.436896.1286218134223.JavaMail.root@mail.hq.genarts.com","subject":"Trac+Git: rev-list with pathspec performance?","fromName":"Stephen Bash","fromEmail":"bash@genarts.com","sentAt":"2010-10-04T20:21:50Z","receivedAt":"2010-10-04T20:21:50Z","isPatch":false,"sender":{"key":"bash@genarts.com","avatar":null},"body":"Hi all-\n\nI'm trying to improve the performance of Trac [1], the GitPlugin for Trac[2], and Git. Trac is being extremely sluggish while browsing source, and profiling revealed the majority of the time was the GitPlugin calling git rev-list. When I directly entered the rev-list calls from the shell, I found Git itself was performing slower than I would expect...\n\nThe bottleneck is while Trac is populating the \"last change to file\" column in the source browser (see the \"rev\" column of [3] for an *cough* SVN *cough* example). This concept of \"find the last change to a file\" was discussed a few weeks ago [4], but unlike that thread, the GitPlugin is simply calling\n git rev-list --max-count=1 branchName -- fileName\nfor each file in the current directory. For files modified recently this is very fast (thousandths of a second), but for older files rev-list takes a long time to come up with an answer (~2-3 seconds on our server). \n\nI created a script [5] that reproduces the rev-list behavior with 10k commits (ours is about 17k) and 500 files (we peaked at just under 600 in the root of our repo -- that's been cleaned up in the current version, but the history is still there). On our system the test script fast case is:\n real 0m0.003s, user 0m0.000s, sys 0m0.010s\nThe slow case is\n real 0m1.072s, user 0m1.050s, sys 0m0.000s\n\nIf I naively profile Git I find the worst time offender is tree_entry_interesting with over 10 million calls in the slow case. That seems high (even every commit, every file would be 500*10000=5 million), but I don't know anything about the actual search algorithm.\n\nIs there anything obvious I can do about this performance bottleneck or is it just the nature of our repository? Is there potentially a bug in how rev-list works with a pathspec? Is there a more efficient way to obtain the last commit that changed each file in a directory? (A hack I'm currently testing is just always return the current commit when Trac asks for the last change... that speeds things up but changes the user experience)\n\nThanks,\nStephen\n\nReferences:\n[1] http://trac.edgewall.org\n[2] http://trac-hacks.org/wiki/GitPlugin\n[3] http://trac.edgewall.org/browser/trunk\n[4] http://article.gmane.org/gmane.comp.version-control.git/150183/\n[5]\n#!/bin/bash\n\ngit init big-repo\ncd big-repo\ntouch foo\ntouch bar\nfor ii in {1..500}\ndo\n # create some files for background noise\n touch $ii\ndone\ngit add .\ngit commit -qm \"initial import\"\n\nfor ii in {1..10000}\ndo\n echo \"Creating commit $ii\"\n echo $ii >> foo\n git add foo\n git commit -qm \"simple change $ii\"\n\n if [ $(( $ii % 250 )) == 0 ]\n then\n echo \"Running git gc ($ii)\"\n git gc --quiet\n fi\ndone\n\n# Fast case (last change is close to HEAD)\necho \"git rev-list --max-count=1 HEAD -- foo ...\"\ntime git rev-list --max-count=1 HEAD -- foo\n\n# Slow case (last change is long before HEAD)\necho \"git rev-list --max-count=1 HEAD -- bar ...\"\ntime git rev-list --max-count=1 HEAD -- bar\n\ncd ..\n\n#rm -rf big-repo\n"},{"id":"152588","messageId":"20101004203845.GG6466@burratino","threadId":"25343","inReplyTo":"27777603.436995.1286223710787.JavaMail.root@mail.hq.genarts.com","subject":"Re: Trac+Git: rev-list with pathspec performance?","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-10-04T20:38:45Z","receivedAt":"2010-10-04T20:38:45Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Stephen Bash wrote:\n> Is there a more efficient way to obtain the last commit that changed\n> each file in a directory?\n\nYes.\n\nhttp://yhbt.net/git-set-file-times\n"},{"id":"152629","messageId":"m3r5g5fnth.fsf@localhost.localdomain","threadId":"25343","inReplyTo":"27777603.436995.1286223710787.JavaMail.root@mail.hq.genarts.com","subject":"Re: Trac+Git: rev-list with pathspec performance?","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2010-10-05T01:09:40Z","receivedAt":"2010-10-05T01:09:40Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Stephen Bash writes:\n\n> I'm trying to improve the performance of Trac [1], the GitPlugin for\n> Trac[2], and Git. Trac is being extremely sluggish while browsing\n> source, and profiling revealed the majority of the time was the\n> GitPlugin calling git rev-list. When I directly entered the\n> rev-list calls from the shell, I found Git itself was performing\n> slower than I would expect...\n> \n> The bottleneck is while Trac is populating the \"last change to file\"\n> column in the source browser (see the \"rev\" column of [3] for an\n> *cough* SVN *cough* example). This concept of \"find the last change\n> to a file\" was discussed a few weeks ago [4], but unlike that\n> thread, the GitPlugin is simply calling git rev-list --max-count=1\n> branchName -- fileName for each file in the current directory. For\n> files modified recently this is very fast (thousandths of a second),\n> but for older files rev-list takes a long time to come up with an\n> answer (~2-3 seconds on our server).\n[...]\n\n> References:\n> [1] http://trac.edgewall.org\n> [2] http://trac-hacks.org/wiki/GitPlugin\n> [3] http://trac.edgewall.org/browser/trunk\n> [4] http://article.gmane.org/gmane.comp.version-control.git/150183/\n\nNote that later[5] in mentioned thread[4] there is proof of concept\n\"tree blame\" (in Perl) which generates such 'last change to file'\ninformation, I think faster than running 'git rev-list -1 ' for\neach file. Even better would be to encode used algorithm in C.\n\n[5] http://thread.gmane.org/gmane.comp.version-control.git/150063/focus=150183\n\nP.S. Alternate solution would be to simply get rid of SVN-inspired\nview. Git tracks history of a *project* as a whole, not set of\nhistories for individual files (like CVS).\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"152766","messageId":"17750617.441668.1286378804923.JavaMail.root@mail.hq.genarts.com","threadId":"25343","inReplyTo":"m3r5g5fnth.fsf@localhost.localdomain","subject":"Re: Trac+Git: rev-list with pathspec performance?","fromName":"Stephen Bash","fromEmail":"bash@genarts.com","sentAt":"2010-10-06T15:26:44Z","receivedAt":"2010-10-06T15:26:44Z","isPatch":false,"sender":{"key":"bash@genarts.com","avatar":null},"body":"> Note that there is proof of concept\n> \"tree blame\" (in Perl) which generates such 'last change to file'\n> information, I think faster than running 'git rev-list -1 ' for\n> each file. Even better would be to encode used algorithm in C.\n> \n> http://thread.gmane.org/gmane.comp.version-control.git/150063/focus=150183\n\nMy early experiments with your script are good for speed, but for some reason I'm always getting the first commit for a file rather than the most recent. I'll do some experimenting to see if I can uncover the issue.\n\n(I had seen the script earlier, but I didn't realize the fix for diff-tree had made it into a release already) \n\nThanks,\nStephen\n"},{"id":"152890","messageId":"2595121.446745.1286473792827.JavaMail.root@mail.hq.genarts.com","threadId":"25343","inReplyTo":"17750617.441668.1286378804923.JavaMail.root@mail.hq.genarts.com","subject":"Re: Trac+Git: rev-list with pathspec performance?","fromName":"Stephen Bash","fromEmail":"bash@genarts.com","sentAt":"2010-10-07T17:49:52Z","receivedAt":"2010-10-07T17:49:52Z","isPatch":false,"sender":{"key":"bash@genarts.com","avatar":null},"body":"> > Note that there is proof of concept\n> > \"tree blame\" (in Perl) which generates such 'last change to file'\n> > information, I think faster than running 'git rev-list -1 '\n> > for\n> > each file. Even better would be to encode used algorithm in C.\n> >\n> > http://thread.gmane.org/gmane.comp.version-control.git/150063/focus=150183\n> \n> My early experiments with your script are good for speed, but for some\n> reason I'm always getting the first commit for a file rather than the\n> most recent. I'll do some experimenting to see if I can uncover the\n> issue.\n\nFollowing up, I had to add -r to the diff-tree command line when requesting a subdirectory to work around the problem (script always returned the first commit).\n\nI'm curious if it's faster to get the SHA of the sub-tree and compare that before actually running diff-tree? And for that matter, just run diff-tree on the sub-tree that we care about rather than a recursive sub-tree on the root? These may be early optimizations, but they're ideas that occurred to me while debugging the code...\n\n> > P.S. Alternate solution would be to simply get rid of SVN-inspired\n> > view. Git tracks history of a *project* as a whole, not set of\n> > histories for individual files (like CVS).\n\nAfter a lot of experimentation, this is basically what we did. I modified the Trac templates to not list the last change SHA or log message in the directory view. After all my testing, I just don't think there's a fast way to get this information from Git. This blame-dir script is the fastest alternative I've tried (about 5x faster than rev-list'ing each file), but it's still ~30 seconds on my machine (which is faster than our web server), and IMHO that's too long to ask a user to wait for a page to load.\n\nThanks,\nStephen\n"},{"id":"152929","messageId":"201010072234.00994.jnareb@gmail.com","threadId":"25343","inReplyTo":"2595121.446745.1286473792827.JavaMail.root@mail.hq.genarts.com","subject":"Re: Trac+Git: rev-list with pathspec performance?","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2010-10-07T20:33:59Z","receivedAt":"2010-10-07T20:33:59Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Thu, 7 Oct 2010, Stephen Bash wrote:\n\n>>> Note that there is proof of concept\n>>> \"tree blame\" (in Perl) which generates such 'last change to file'\n>>> information, I think faster than running 'git rev-list -1 '\n>>> for\n>>> each file. Even better would be to encode used algorithm in C.\n>>>\n>>> http://thread.gmane.org/gmane.comp.version-control.git/150063/focus=150183\n>> \n>> My early experiments with your script are good for speed, but for some\n>> reason I'm always getting the first commit for a file rather than the\n>> most recent. I'll do some experimenting to see if I can uncover the\n>> issue.\n> \n> Following up, I had to add -r to the diff-tree command line when\n> requesting a subdirectory to work around the problem (script always\n> returned the first commit). \n\nHmmm... I thought that I have added '-r' if there is path provided,\ni.e. we don't run tree blame on root commit.\n\n> I'm curious if it's faster to get the SHA of the sub-tree and compare\n> that before actually running diff-tree? And for that matter, just run\n> diff-tree on the sub-tree that we care about rather than a recursive\n> sub-tree on the root? These may be early optimizations, but they're\n> ideas that occurred to me while debugging the code... \n\nThere are many possible optimizations (see also below); for the time\nbeing I was concerned with getting the fast tree blame algorithm right\n(and as you can see didn't get it, not completely).\n\n>>> P.S. Alternate solution would be to simply get rid of SVN-inspired\n>>> view. Git tracks history of a *project* as a whole, not set of\n>>> histories for individual files (like CVS).\n> \n> After a lot of experimentation, this is basically what we did.\n> I modified the Trac templates to not list the last change SHA or log\n> message in the directory view. After all my testing, I just don't\n> think there's a fast way to get this information from Git. This\n> blame-dir script is the fastest alternative I've tried (about 5x\n> faster than rev-list'ing each file), but it's still ~30 seconds on my\n> machine (which is faster than our web server), and IMHO that's too\n> long to ask a user to wait for a page to load. \n\nFirst, there is lot of room for optimization of tree blame script, some\nof which I have noted as comments, some which you have found. During\ndeveloping this script I noticed that current plumbing doesn't completly\nfit the tree blame algorithm; for example we need '-r' for blaming \nsubtree (subdirectory), while we need paths only up to depth of blamed\ndirectory, no more.\n\nRewriting tree-blame in C, using in-core revision and tree traversal\nshould be faster, though I'm not sure how much would that be. \nUnfortunately I don't know enough git API; I thought that writing\nPerl script would be easier.\n\nBut you are right in that such view would always be expensive in Git,\nbecause Git tracks history of porject *as a whole*. If file was \ncreated in root commit (first commit) and left unchanged, it would be\neasy to find in VCS that stored history on per-file basis at least to\nsome extent; in git you have to go through comit up till the root \ncommit in this case. If history is long, it might take some time.\n\n\nSecond, you can use the trick that GitHub web interface uses to display\nsimilar view, namely in displaying first just a tree of files, and then\nincrmentally filling in 'last changed' info. Gitweb does something \nsimilar in 'blame_incremental' view; that is why the idea was to have\ntree blame (\"git blame \") to have support for incremental \nformat, similar to an ordinary blame.\n\nThis might take some effort to develop, though...\n-- \nJakub Narebski\nPoland\n"}]}