{"thread":{"id":"26089","subject":"Performance issue exposed by git-filter-branch","startedAt":"2010-12-17T01:07:15Z","lastAt":"2011-02-05T14:21:23Z","messageCount":15,"participants":["Ken Brownfield","Jonathan Nieder","Thomas Rast","Jakub Narebski","Elijah Newren","Nguyen Thai Ngoc Duy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"158250","messageId":"41C1B4AC-8427-4D62-BEB6-689A4BE4EE5B@irridia.com","threadId":"26089","inReplyTo":null,"subject":"Performance issue exposed by git-filter-branch","fromName":"Ken Brownfield","fromEmail":"krb@irridia.com","sentAt":"2010-12-17T01:07:15Z","receivedAt":"2010-12-17T01:07:15Z","isPatch":false,"sender":{"key":"krb@irridia.com","avatar":null},"body":"I have a large git repository (1,757,784 objects, 209,282 commits) from which I have been planning to filter large tree portions (~36,000 of ~132,000 files). When I first ran git-filter-branch on this repository about a year ago:\n\ngit filter-branch --index-filter 'git rm -r --cached --ignore-unmatch -- bigdirtree stuff/a stuff/b stuff/c stuff/dir/{a,b,c}' --prune-empty --tag-name-filter cat -- --all\n\nThe process took around 25 hours for the repository when it was at ~101k commits. This wasn't ideal, but could be completed over a weekend maintenance. There are 50 daily active committers to this repository, so the window has to be short.\n\nHowever, we didn't have time to implement this newly filtered repo (it involves everyone recloning, etc) until now.\n\nNow that the same repository has grown, this same filter-branch process now takes 6.5 *days* at 100% CPU on the same machine (2x4 Xeon, x86_64) on git-1.7.3.2. There's no I/O, memory, or other resource contention.\n\nI tend to doubt there are any multi-processing opportunities with this process, so at this point git-filter-branch is no longer feasible.\n\nThis is an oprofile sample (all samples >1%) at roughly one day into the 6.5 day Rewrite process:\n\n[...]\n11594 1.0208 git git add_index_entry\n11616 1.0228 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server find_lock_page\n12624 1.1115 git git decode_tree_entry\n13065 1.1504 git git refresh_index\n13757 1.2113 git git match_pathspec\n14041 1.2363 git git read_packed_refs\n18309 1.6121 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server unmap_vmas\n20014 1.7622 libc-2.7.so libc-2.7.so _int_malloc\n24248 2.1350 git git find_cache_pos\n24560 2.1625 git git find_pack_entry_one\n29042 2.5571 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server debug\n31202 2.7473 libz.so.1.2.3.3 libz.so.1.2.3.3 inflate\n34941 3.0765 git git df_name_compare\n36749 3.2357 libz.so.1.2.3.3 libz.so.1.2.3.3 inflate_fast\n41704 3.6720 git git index_name_pos\n46908 4.1302 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server clear_page\n92554 8.1493 libc-2.7.so libc-2.7.so memcpy\n127439 11.2208 libcrypto.so.0.9.8 libcrypto.so.0.9.8 sha1_block_data_order\n188373 16.5860 git git cache_name_compare\n\ncache_name_compare (and the presumed follow-ons of memcpy/sha/malloc/etc) is the major consumer.\n\nSampling the filter only 2k commits into the Rewrite stage shows:\n\n[...]\n12058 1.0135 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server do_path_lookup\n13532 1.1374 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server copy_user_generic_string\n13934 1.1712 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server clear_page\n16565 1.3924 git git cache_name_compare\n16948 1.4246 libc-2.7.so libc-2.7.so memcpy\n16969 1.4263 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server system_call\n19189 1.6129 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server debug\n22697 1.9078 git git add_ref\n31112 2.6151 ext3 ext3 (no symbols)\n33925 2.8516 git git sort_ref_list\n34026 2.8600 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server _atomic_dec_and_lock\n39304 3.3037 git git read_packed_refs\n43920 3.6917 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server __link_path_walk\n58504 4.9175 libc-2.7.so libc-2.7.so strcmp\n79957 6.7208 vmlinux-debug-2.6.24-28-server vmlinux-debug-2.6.24-28-server __d_lookup\n168696 14.1797 git git prepare_packed_git_one\n\nThe process is still pretty slow (1-2 commits per second) but cache_name_compare is in the background.\n\nIs there a way to apply the optimizations mentioned in that old thread to the code paths used by git-filter-branch (mainly git-read and git-rm, seemingly), or is there another way to investigate and improve the performance of the filter?\n\nOutside of this specific issue, it might be worth taking a look at the overall performance of git-filter-branch: bash loops iterating over core executables probably isn't ideal, but there are lower-hanging fruits. Running the filter in a single process may allow some better caching and reduce duplication of work (maybe parallelization?), but I'm just guessing.\n\nOur tree is quite large, but the O(n^2) nature of this process is pretty crippling for the larger repositories that are bound to be in the wild. And while filter-branch isn't an everyday thing, when I /do/ need to use it, I won't be able to wait a week. :-)\n\nI'd appreciate any feedback or suggestions anyone might have!\n\nThanks,\nKen\n\nPS: On an unrelated note, I would recommend that the following code in git-filter-branch:\n\n277:rev_args=$(git rev-parse --revs-only \"$@\")\n\nbe changed to write out to a temporary file, then piped into the \"git rev-list\" at line 289 with \"--stdin\". For larger trees, the use of $rev_args on the \"git rev-list\" command-line exceeds the size of some shells' command-line buffers (from direct experience).\n"},{"id":"158251","messageId":"20101217014539.GA6775@burratino","threadId":"26089","inReplyTo":"41C1B4AC-8427-4D62-BEB6-689A4BE4EE5B@irridia.com","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-12-17T01:45:39Z","receivedAt":"2010-12-17T01:45:39Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi Ken,\n\nKen Brownfield wrote:\n\n> Is there a way to apply the optimizations mentioned in that old\n> thread to the code paths used by git-filter-branch (mainly git-read\n> and git-rm, seemingly), or is there another way to investigate and\n> improve the performance of the filter?\n\nWhich old thread?\n\nYou might be able to get faster results using the approach of [1]\n(using \"git cat-file --batch-check\" to collect the trees you want\nand \"git fast-import\" to paste them together), which avoids unpacking\ntrees when not needed.\n\nHope that helps,\nJonathan\n\n[1] http://repo.or.cz/w/git/barrbrain/github.git/commitdiff/db-svn-filter-root\n"},{"id":"158252","messageId":"201012170254.13005.trast@student.ethz.ch","threadId":"26089","inReplyTo":"41C1B4AC-8427-4D62-BEB6-689A4BE4EE5B@irridia.com","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-17T01:54:12Z","receivedAt":"2010-12-17T01:54:12Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Ken Brownfield wrote:\n> git filter-branch --index-filter 'git rm -r --cached --ignore-unmatch -- bigdirtree stuff/a stuff/b stuff/c stuff/dir/{a,b,c}' --prune-empty --tag-name-filter cat -- --all\n[...]\n> Now that the same repository has grown, this same filter-branch\n> process now takes 6.5 *days* at 100% CPU on the same machine (2x4\n> Xeon, x86_64) on git-1.7.3.2. There's no I/O, memory, or other\n> resource contention.\n\nIf all you do is an index-filter for deletion, I think it should be\nrather easy to achieve good results by filtering the fast-export\nstream to remove these files, and then piping that back to\nfast-import.\n\n(It's just that AFAIK nobody has written that code yet.)\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"158254","messageId":"1FBB24BF-6517-4906-99D5-A5DDBEA14D6D@irridia.com","threadId":"26089","inReplyTo":"20101217014539.GA6775@burratino","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Ken Brownfield","fromEmail":"krb@irridia.com","sentAt":"2010-12-17T02:31:52Z","receivedAt":"2010-12-17T02:31:52Z","isPatch":false,"sender":{"key":"krb@irridia.com","avatar":null},"body":"The thread titled \"git and larger trees, not so fast?\". Some of the history is lost, but here's the earliest post I can find:\n\nhttp://lists-archives.org/git/627040-git-and-larger-trees-not-so-fast.html\n\nOn GMANE:\nhttp://article.gmane.org/gmane.comp.version-control.git/55460/match=git+larger+trees+not+so+fast\n\nBut I can't figure out how to show the whole thread.\n\nSorry, that paragraph of my email disappeared. :-(\n\nKen\n\nOn Dec 16, 2010, at 5:45 PM, Jonathan Nieder wrote:\n\n> Hi Ken,\n> \n> Ken Brownfield wrote:\n> \n>> Is there a way to apply the optimizations mentioned in that old\n>> thread to the code paths used by git-filter-branch (mainly git-read\n>> and git-rm, seemingly), or is there another way to investigate and\n>> improve the performance of the filter?\n> \n> Which old thread?\n> \n> You might be able to get faster results using the approach of [1]\n> (using \"git cat-file --batch-check\" to collect the trees you want\n> and \"git fast-import\" to paste them together), which avoids unpacking\n> trees when not needed.\n> \n> Hope that helps,\n> Jonathan\n> \n> [1] http://repo.or.cz/w/git/barrbrain/github.git/commitdiff/db-svn-filter-root\n"},{"id":"158255","messageId":"9A686258-A504-4CBB-9993-048B45B5EE6A@irridia.com","threadId":"26089","inReplyTo":"201012170254.13005.trast@student.ethz.ch","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Ken Brownfield","fromEmail":"krb@irridia.com","sentAt":"2010-12-17T02:36:36Z","receivedAt":"2010-12-17T02:36:36Z","isPatch":false,"sender":{"key":"krb@irridia.com","avatar":null},"body":"I had considered this approach (and the one mentioned by Jonathan) but there are no git tools to actually perform the filter I wanted on the export in this form. I could (and will) parse fast-export and make an attempt a filtering files/directories... my concern is that I won't do it right, and will introduce subtle corruption. But if there's no existing tool, I'll take a crack at it. :-)\n\nThanks for your suggestions so far,\n\nKen\n\nPS: This was my exact first thought, since I was previously used to performing \"svnadmin dump/svndumpfilter/svnadmin load\" on this repository when it was in SVN.\n\nOn Dec 16, 2010, at 5:54 PM, Thomas Rast wrote:\n\n> Ken Brownfield wrote:\n>> git filter-branch --index-filter 'git rm -r --cached --ignore-unmatch -- bigdirtree stuff/a stuff/b stuff/c stuff/dir/{a,b,c}' --prune-empty --tag-name-filter cat -- --all\n> [...]\n>> Now that the same repository has grown, this same filter-branch\n>> process now takes 6.5 *days* at 100% CPU on the same machine (2x4\n>> Xeon, x86_64) on git-1.7.3.2. There's no I/O, memory, or other\n>> resource contention.\n> \n> If all you do is an index-filter for deletion, I think it should be\n> rather easy to achieve good results by filtering the fast-export\n> stream to remove these files, and then piping that back to\n> fast-import.\n> \n> (It's just that AFAIK nobody has written that code yet.)\n> \n> -- \n> Thomas Rast\n> trast@{inf,student}.ethz.ch\n"},{"id":"158256","messageId":"m3lj4sll39.fsf@localhost.localdomain","threadId":"26089","inReplyTo":"9A686258-A504-4CBB-9993-048B45B5EE6A@irridia.com","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2010-12-17T02:51:32Z","receivedAt":"2010-12-17T02:51:32Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Please do not toppost.\n\nKen Brownfield writes:\n\n> I had considered this approach (and the one mentioned by Jonathan)\n> but there are no git tools to actually perform the filter I wanted\n> on the export in this form. I could (and will) parse fast-export\n> and make an attempt a filtering files/directories... my concern is\n> that I won't do it right, and will introduce subtle corruption. But\n> if there's no existing tool, I'll take a crack at it. :-)\n\nYou can try ESR's reposurgeon:\n\n http://www.catb.org/~esr/reposurgeon/\n\nIt's limitation is that it loads structure of DAG of revisions (but\nnot blobs i.e. contents of file) to memory. IIRC. It is not\nstreaming, but \"DOM\" based, otherwise some commands would not work.\n\n\nBy the way, git-filter-branch documentation recomments to use\nindex-filter with git-update-index instead of tree-filter with git-rm,\nand if tree-filter is needed, to use some fast filesystem, e.g. RAM\none.\n\nBut probably you know all that.\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"158257","messageId":"20101217030855.GB7003@burratino","threadId":"26089","inReplyTo":"9A686258-A504-4CBB-9993-048B45B5EE6A@irridia.com","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-12-17T03:08:55Z","receivedAt":"2010-12-17T03:08:55Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Ken Brownfield wrote:\n\n> I had considered this approach (and the one mentioned by Jonathan)\n> but there are no git tools to actually perform the filter I wanted\n> on the export in this form.\n\nKeep in mind that the two suggestions were subtly different from one\nanother.\n\nFor the \"filter fast-import stream\" technique, apparently there is a\ntool called reposurgeon[1] to do that. git_fast_filter[2] has the\nsame purpose, too, if I remember correctly.\n\nFor the unpack-trees avoidance technique, true, the only example I\nknow if is the one I mentioned[3]. The idea would be to sort the\ncommits you want in topological order and replay them, for each one\ngoing like so:\n\n\tM 040000 \"\"\n\tD bad/directory/one\n\tD bad/directory/two\n\nusing fast-import from git.git master. (Older versions of fast-import\ndo not properly handle replacing the root directory, so if that sort\nof compatibility is important, you'd have to use a directory listing\nand fill in all the _good_ directories instead.)\n\nI'd be glad to look at any work in this direction. Something like it\nwould be useful for postprocessing when importing from svn repos.\n\nThanks,\nJonathan\n\n[1] http://esr.ibiblio.org/?p=2718\n[2] http://thread.gmane.org/gmane.comp.version-control.git/116028\nand links therein\n[3] http://thread.gmane.org/gmane.comp.version-control.git/158375\n"},{"id":"158258","messageId":"20101217032232.GC7003@burratino","threadId":"26089","inReplyTo":"1FBB24BF-6517-4906-99D5-A5DDBEA14D6D@irridia.com","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-12-17T03:22:32Z","receivedAt":"2010-12-17T03:22:32Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Ken Brownfield wrote:\n\n> The thread titled \"git and larger trees, not so fast?\".\n\nHere it is[1]. Sorry to say, the improvements discussed there\nwere made right away and indeed had a dramatic effect.\n\nJonathan\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/55458/focus=55643\n"},{"id":"158260","messageId":"20101217033715.GA7302@burratino","threadId":"26089","inReplyTo":"20101217032232.GC7003@burratino","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-12-17T03:37:15Z","receivedAt":"2010-12-17T03:37:15Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jonathan Nieder wrote:\n> Ken Brownfield wrote:\n\n>> The thread titled \"git and larger trees, not so fast?\".\n>\n> Here it is[1]. Sorry to say, the improvements discussed there\n> were made right away and indeed had a dramatic effect.\n\nOf course I missed your point. :)\n\nfilter-branch --index-filter works a little like this: for\neach commit:\n\n. find the underlying tree\n. read-tree: unpack that tree and all of its subtrees into\nthe index file. That is, convert from a recursive structure\n /:\n\tCOPYING\n\tDocumentation/\n\tINSTALL\n\tMakefile\n\t...\n\n Documentation/:\n\tCodingGuidelines\n\tMakefile\n\t...\n\ninto a flat structure\n\n\tCOPYING\n\tDocumentation/CodingGuideLines\n\tDocumentation/Makefile\n\tDocumentation/RelNotes/1.5.0.txt\n\t...\n. rm: find entries matching certain patterns and remove them\nfrom the index file. This takes two passes through the index:\nfirst to find matching entries, second to write the result to\ndisk.\n. write-tree: write new trees for the object store. That is,\nconvert from a flat structure back to a recursive structure.\n\nThis is convenient, but it does not sound to me like the most\nefficient way to eliminate a few subtrees from each commit. That is\nwhy I was suggesting a method that avoids unpacking some trees\naltogether.\n\nThat said, speedups for read-tree, rm, and write-tree would certainly\nbe nice to have. One project of interest to some people is to give\nthe index file a recursive structure, so finding the entries to remove\nin the \"git rm\" example could be faster.\n"},{"id":"158265","messageId":"AANLkTi=-0Sj9c5b778jchn+pgw26xCbioQ2K4tNgtm_G@mail.gmail.com","threadId":"26089","inReplyTo":"20101217030855.GB7003@burratino","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-12-17T05:39:44Z","receivedAt":"2010-12-17T05:39:44Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Dec 16, 2010 at 8:08 PM, Jonathan Nieder wrote:\n> Ken Brownfield wrote:\n>\n>> I had considered this approach (and the one mentioned by Jonathan)\n>> but there are no git tools to actually perform the filter I wanted\n>> on the export in this form.\n>\n> Keep in mind that the two suggestions were subtly different from one\n> another.\n>\n> For the \"filter fast-import stream\" technique, apparently there is a\n> tool called reposurgeon[1] to do that.  git_fast_filter[2] has the\n> same purpose, too, if I remember correctly.\n\nYes, git_fast_filter was written precisely because git-filter-branch\ntook waaaaaay too long. IIRC, git-filter-branch would have taken\nabout 2-3 months for our use case (there's no way we could have shut\ndown the repositories for that long), whereas git_fast_filter (serving\nalong with fast-export and fast-import) allowed us to drop that to\nabout an hour (we couldn't use --index-filter with filter-branch as we\nneeded to do a number of operations on the actual file contents as\nwell).\n\nAll git_fast_filter really does is parse the fast-export output into\nsome basic python data structures, making it easy for you to modify\nthose structures as necessary (assuming basic python skills, though if\nyou only need to do what one of the examples shows then you could even\nget away without that), and then pipes the results back out in the\nformat fast-import expects. It has a few examples with it; removing\nexisting files is one of the simple examples.\n\nI haven't really bothered keeping the public repository up-to-date\nsince there hasn't been any prior external interest in it, but we\nhaven't modified it much internally either, and most of those\nmodifications are likely for niche stuff that you wouldn't need.\n\nElijah\n"},{"id":"158280","messageId":"AANLkTi=eWaaGKGpUptdkVg5iEMiZK5FQ9URjUTgd+LxB@mail.gmail.com","threadId":"26089","inReplyTo":"41C1B4AC-8427-4D62-BEB6-689A4BE4EE5B@irridia.com","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2010-12-17T13:01:41Z","receivedAt":"2010-12-17T13:01:41Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Dec 17, 2010 at 8:07 AM, Ken Brownfield wrote:\n> cache_name_compare (and the presumed follow-ons of memcpy/sha/malloc/etc) is the major consumer.\n\nOther people have given you alternative approaches. I'm just wondering\nif we can improve something here. cache_name_compare() is essentially\nmemcmp() on two full paths. A tree-based index might help. How long\nare your file names on average? Are your trees deep?\n-- \nDuy\n"},{"id":"158427","messageId":"3800FCA0-3894-417D-847D-421693A53E75@irridia.com","threadId":"26089","inReplyTo":"m3lj4sll39.fsf@localhost.localdomain","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Ken Brownfield","fromEmail":"krb@irridia.com","sentAt":"2010-12-21T04:49:11Z","receivedAt":"2010-12-21T04:49:11Z","isPatch":false,"sender":{"key":"krb@irridia.com","avatar":null},"body":"This does pretty much exactly what I want (and a lot more), but reposurgeon is now over three days into reading the fast-export stream at 100% CPU. My guess is that it's about 30% done.\n\nIt does look like a great tool for smaller repositories.\n\nThanks for the suggestion, though! It looks like git_fast_filter is my next stop.\n\nKen\n\nOn Dec 16, 2010, at 6:51 PM, Jakub Narebski wrote:\n\n> Please do not toppost.\n> \n> Ken Brownfield writes:\n> \n>> I had considered this approach (and the one mentioned by Jonathan)\n>> but there are no git tools to actually perform the filter I wanted\n>> on the export in this form. I could (and will) parse fast-export\n>> and make an attempt a filtering files/directories... my concern is\n>> that I won't do it right, and will introduce subtle corruption. But\n>> if there's no existing tool, I'll take a crack at it. :-)\n> \n> You can try ESR's reposurgeon:\n> \n> http://www.catb.org/~esr/reposurgeon/\n> \n> It's limitation is that it loads structure of DAG of revisions (but\n> not blobs i.e. contents of file) to memory. IIRC. It is not\n> streaming, but \"DOM\" based, otherwise some commands would not work.\n> \n> \n> By the way, git-filter-branch documentation recomments to use\n> index-filter with git-update-index instead of tree-filter with git-rm,\n> and if tree-filter is needed, to use some fast filesystem, e.g. RAM\n> one.\n> \n> But probably you know all that.\n> -- \n> Jakub Narebski\n> Poland\n> ShadeHawk on #git\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"158428","messageId":"5ED25D1E-3028-43B7-9EA7-8E94773EA3E1@irridia.com","threadId":"26089","inReplyTo":"AANLkTi=eWaaGKGpUptdkVg5iEMiZK5FQ9URjUTgd+LxB@mail.gmail.com","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Ken Brownfield","fromEmail":"krb@irridia.com","sentAt":"2010-12-21T04:59:27Z","receivedAt":"2010-12-21T04:59:27Z","isPatch":false,"sender":{"key":"krb@irridia.com","avatar":null},"body":"Filename lengths: min 4 avg 50 median 51 max 178\nDirectory depths: min 1 avg 5 median 6 max 13\n\nPretty standard Python naming/hierarchy, really.\n\nThanks!\nKen\n\nOn Dec 17, 2010, at 5:01 AM, Nguyen Thai Ngoc Duy wrote:\n\n> On Fri, Dec 17, 2010 at 8:07 AM, Ken Brownfield wrote:\n>> cache_name_compare (and the presumed follow-ons of memcpy/sha/malloc/etc) is the major consumer.\n> \n> Other people have given you alternative approaches. I'm just wondering\n> if we can improve something here. cache_name_compare() is essentially\n> memcmp() on two full paths. A tree-based index might help. How long\n> are your file names on average? Are your trees deep?\n> -- \n> Duy\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"160408","messageId":"010EA68F-6122-47C7-B761-7D786F37B0C6@irridia.com","threadId":"26089","inReplyTo":"AANLkTi=-0Sj9c5b778jchn+pgw26xCbioQ2K4tNgtm_G@mail.gmail.com","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Ken Brownfield","fromEmail":"krb@irridia.com","sentAt":"2011-02-04T21:17:10Z","receivedAt":"2011-02-04T21:17:10Z","isPatch":false,"sender":{"key":"krb@irridia.com","avatar":null},"body":"Thanks for the feedback on git_fast_filter. It takes 11.5 hours on our repository instead of 6.5 days, so that's a significant improvement. :-) I have a couple of observations:\n\n1) You said that your repo would have taken 2-3 months to filter with git-filter-branch, and the time was reduced to ~1hr. I'm surprised our reduction was not quite as dramatic, although I presume the variability of repo contents are the explanation.\n\n2) The resulting repository pack files are actually much larger. A garbage collection reduces the size below the original, but only slightly. I'm concerned that the recreated repository has redundant or inefficiently stored information, but I'm not sure how to verify what objects are taking up what space.\n\n3) git_fast_filter doesn't currently support remote submodules. When it tries to parse a submodule line, the regex fails and the code aborts:\n\nExpected:\n\tM 100644 :433236 foo/bar/bletch\nReceived, something like:\n\tM 100644 cd821b4c0ea8e9493069ff43712a0b09 foo/bar/bletch\n\nTo correct the issue, I modified git_fast_filter to simply skip these. While we no longer utilize remote submodules, I would prefer not to have them removed.\n\nAny feedback on what the proper behavior would be in the submodule case? Perhaps this is covered in your internal version?\n\nThanks,\n-- \nKen\n\nOn Dec 16, 2010, at 9:39 PM, Elijah Newren wrote:\n\n> On Thu, Dec 16, 2010 at 8:08 PM, Jonathan Nieder wrote:\n>> Ken Brownfield wrote:\n>> \n>>> I had considered this approach (and the one mentioned by Jonathan)\n>>> but there are no git tools to actually perform the filter I wanted\n>>> on the export in this form.\n>> \n>> Keep in mind that the two suggestions were subtly different from one\n>> another.\n>> \n>> For the \"filter fast-import stream\" technique, apparently there is a\n>> tool called reposurgeon[1] to do that. git_fast_filter[2] has the\n>> same purpose, too, if I remember correctly.\n> \n> Yes, git_fast_filter was written precisely because git-filter-branch\n> took waaaaaay too long. IIRC, git-filter-branch would have taken\n> about 2-3 months for our use case (there's no way we could have shut\n> down the repositories for that long), whereas git_fast_filter (serving\n> along with fast-export and fast-import) allowed us to drop that to\n> about an hour (we couldn't use --index-filter with filter-branch as we\n> needed to do a number of operations on the actual file contents as\n> well).\n> \n> All git_fast_filter really does is parse the fast-export output into\n> some basic python data structures, making it easy for you to modify\n> those structures as necessary (assuming basic python skills, though if\n> you only need to do what one of the examples shows then you could even\n> get away without that), and then pipes the results back out in the\n> format fast-import expects. It has a few examples with it; removing\n> existing files is one of the simple examples.\n> \n> I haven't really bothered keeping the public repository up-to-date\n> since there hasn't been any prior external interest in it, but we\n> haven't modified it much internally either, and most of those\n> modifications are likely for niche stuff that you wouldn't need.\n> \n> Elijah\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n"},{"id":"160444","messageId":"AANLkTi=J+oTE6RoVgziGfwNzkqgRe0yNJB0RVqdWegyc@mail.gmail.com","threadId":"26089","inReplyTo":"010EA68F-6122-47C7-B761-7D786F37B0C6@irridia.com","subject":"Re: Performance issue exposed by git-filter-branch","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2011-02-05T14:21:23Z","receivedAt":"2011-02-05T14:21:23Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi,\n\nOn Fri, Feb 4, 2011 at 2:17 PM, Ken Brownfield wrote:\n> Thanks for the feedback on git_fast_filter.  It takes 11.5 hours on our repository instead of 6.5 days, so that's a significant improvement. :-)  I have a couple of observations:\n>\n> 1) You said that your repo would have taken 2-3 months to filter with git-filter-branch, and the time was reduced to ~1hr.  I'm surprised our reduction was not quite as dramatic, although I presume the variability of repo contents are the explanation.\n\nVariability of the repo certainly would account for some differences,\nthough I suspect more of the differences come from what kind of\nfiltering we were doing. For example, the advantage of\ngit_fast_filter over filter-branch's --index-filter will be much less\nthan its advantage over filter-branch's --tree-filter. Further, in my\ncase, I was parsing and potentially editing the contents of all files,\nwhich becomes much more painful with filter-branch as you'll need to\nre-edit the exact same contents in as many revisions of history as the\nfile remains unchanged in (in other words, duplicating the same work\nhundreds or thousands of times). With git_fast_filter, I only needed\nto parse/edit a given version of some file exactly once. That's what\nreally helped in my case.\n\n> 2) The resulting repository pack files are actually much larger.  A garbage collection reduces the size below the original, but only slightly.  I'm concerned that the recreated repository has redundant or inefficiently stored information, but I'm not sure how to verify what objects are taking up what space.\n\nYou may want to use packinfo.pl from under contrib/stats/ in the git\nrepository to find out what objects take up how much space. From my\nnotes on using it for this purpose:\n\n git verify-pack -v .git/objects/pack/pack-.idx |\npackinfo.pl -tree -filenames > tree-info.txt\n sort -k 4 -n tree-info.txt | grep -v ^$ | less\n\n> 3) git_fast_filter doesn't currently support remote submodules.  When it tries to parse a submodule line, the regex fails and the code aborts:\n>\n> Expected:\n>        M 100644 :433236 foo/bar/bletch\n> Received, something like:\n>        M 100644 cd821b4c0ea8e9493069ff43712a0b09 foo/bar/bletch\n>\n> To correct the issue, I modified git_fast_filter to simply skip these.  While we no longer utilize remote submodules, I would prefer not to have them removed.\n>\n> Any feedback on what the proper behavior would be in the submodule case?  Perhaps this is covered in your internal version?\n\ngit_fast_filter would need to be modified to handle this kind of\ninput, create an appropriate object type, and that object type would\nneed to be able to appropriately output itself later. Since\nsubmodules haven't really been relevant for me, I've never bothered\nimplementing this[*]. The assumption that git-fast-export will\nproduce numeric ids (i.e. that submodules are not present) is somewhat\nhardwired in, so it'd take a little bit of refactoring, though\nprobably not to bad.\n\n\nElijah\n\n[*] Well, actually we did hit it once somewhat recently when someone\ncreated a commit containing a submodule...and then also immediately\nreverted it. Since we don't want to use submodules, I simply put in a\nhack that would recognize them and unconditionally strip them out on\nthe input parsing end, which sounds like the same thing you did.\nThat's obviously not what you're asking for.\n"}]}