{"thread":{"id":"47060","subject":"git rm VERY slow for directories with many files.","startedAt":"2017-10-28T20:43:20Z","lastAt":"2017-10-30T01:36:34Z","messageCount":6,"participants":["Christopher Jefferson","brian m. carlson","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"331243","messageId":"BEEA4A16-5433-4E6C-A7D7-956C85F27DF3@st-andrews.ac.uk","threadId":"47060","inReplyTo":null,"subject":"git rm VERY slow for directories with many files.","fromName":"Christopher Jefferson","fromEmail":"caj21@st-andrews.ac.uk","sentAt":"2017-10-28T17:02:02Z","receivedAt":"2017-10-28T20:43:20Z","isPatch":false,"sender":{"key":"caj21@st-andrews.ac.uk","avatar":null},"body":"I stupidly added a directory with many files ( ~450,000 ) to git, and want to delete them — later I plan to rebase/squash various commits to remove the files from the history altogether.\n\nHowever, ‘git rm’ is VERY slow. For example, in a directory with 10,000 files (on a Mac), git v2.14.2\n\nGit add . : 5.95 secs\nGit commit : 1.29 secs\nGit rm -r : 22 secs\n\n50,000 files\n\nGit add . : 25 secs\nGit commit : 11 secs\nGit rm : After 20 minutes, I killed it.\n\nLooking at an optimized profile, all the time seems to be spent in “get_tree_entry” — I assume there is some huge object representing the directory which is being re-expanded for each file?\n\nIs there any way I can speed up removing this directory?\n\nChris"},{"id":"331244","messageId":"20171028223103.wevq5zf4rjl7ietd@genre.crustytoothpaste.net","threadId":"47060","inReplyTo":"BEEA4A16-5433-4E6C-A7D7-956C85F27DF3@st-andrews.ac.uk","subject":"Re: git rm VERY slow for directories with many files.","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2017-10-28T22:31:04Z","receivedAt":"2017-10-28T22:33:19Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Sat, Oct 28, 2017 at 05:02:02PM +0000, Christopher Jefferson wrote:\n> I stupidly added a directory with many files ( ~450,000 ) to git, and want to delete them — later I plan to rebase/squash various commits to remove the files from the history altogether.\n> \n> However, ‘git rm’ is VERY slow. For example, in a directory with 10,000 files (on a Mac), git v2.14.2\n> \n> Git add . : 5.95 secs\n> Git commit : 1.29 secs\n> Git rm -r : 22 secs\n> \n> 50,000 files\n> \n> Git add . : 25 secs\n> Git commit : 11 secs\n> Git rm : After 20 minutes, I killed it.\n> \n> Looking at an optimized profile, all the time seems to be spent in “get_tree_entry” — I assume there is some huge object representing the directory which is being re-expanded for each file?\n\nYes, there's a tree object that represents each directory.\n\n> Is there any way I can speed up removing this directory?\n\nFirst, make sure your working directory is clean with no changes. Then,\nremove the directory (by hand) or move it somewhere else. Then, run\n\"git add -u\".\n\nThat should allow you to commit the removal of those files quickly.\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\nhttps://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: https://keybase.io/bk2204\n"},{"id":"331250","messageId":"xmqqbmkqbwt0.fsf@gitster.mtv.corp.google.com","threadId":"47060","inReplyTo":"20171028223103.wevq5zf4rjl7ietd@genre.crustytoothpaste.net","subject":"Re: git rm VERY slow for directories with many files.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-29T00:51:55Z","receivedAt":"2017-10-29T00:52:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"brian m. carlson\" writes:\n\n>> Looking at an optimized profile, all the time seems to be spent in “get_tree_entry” — I assume there is some huge object representing the directory which is being re-expanded for each file?\n>\n> Yes, there's a tree object that represents each directory.\n>\n>> Is there any way I can speed up removing this directory?\n>\n> First, make sure your working directory is clean with no changes. Then,\n> remove the directory (by hand) or move it somewhere else. Then, run\n> \"git add -u\".\n>\n> That should allow you to commit the removal of those files quickly.\n\nIf get_tree_entry() shows up a lot in the profile, it would indicate\nthat a lot of cycles are spent in check_local_mod(). Bypassing it\nwith \"-f\" may be the first thing to try ;-)\n\nThe way \"git rm\" makes repeated calls to get_tree_entry() with deep\npathnames would be an easy recipe to get quadratic behaviour like\nthe one reported in the first message on this thread, as it always\ngoes from the root level, grabs an tree object and scans it to get\nthe entry for the next level, and (worse yet) a look-up of a path\ncomponent in each of these tree object must be done as a linear\nscan.\n\nI wonder how fast \"git diff-index --cached -r HEAD --\", with the\nsame pathspec used for the problematic \"git rm\", runs in this same\n50,000 path project. \n\nIf it runs in a reasonable time, one easy way out may be to revamp\nthe codepath to call check_local_mod() to:\n\n - first before making the call, do the \"diff-index --cached\" thing\n internally with the same pathspec to grab the list of paths that\n have local modifications; save the set of paths in a hashmap or\n something.\n\n - pass that hashmap to check_local_mod(), and where the function\n does the \"staged_changes\" check, consult the hashmap to see the\n path in question is different between the HEAD and the index.\n\n"},{"id":"331262","messageId":"xmqqbmkqa9vj.fsf@gitster.mtv.corp.google.com","threadId":"47060","inReplyTo":"xmqqbmkqbwt0.fsf@gitster.mtv.corp.google.com","subject":"Re: git rm VERY slow for directories with many files.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-29T03:52:32Z","receivedAt":"2017-10-29T03:52:39Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> I wonder how fast \"git diff-index --cached -r HEAD --\", with the\n> same pathspec used for the problematic \"git rm\", runs in this same\n> 50,000 path project. \n>\n> If it runs in a reasonable time, one easy way out may be to revamp\n> the codepath to call check_local_mod() to:\n>\n> - first before making the call, do the \"diff-index --cached\" thing\n> internally with the same pathspec to grab the list of paths that\n> have local modifications; save the set of paths in a hashmap or\n> something.\n>\n> - pass that hashmap to check_local_mod(), and where the function\n> does the \"staged_changes\" check, consult the hashmap to see the\n> path in question is different between the HEAD and the index.\n\nAnd if we want to try a more localized band-aid, another approach\nmay be to add a caching version of get_tree_entry() where we keep\ntrack of (stack of) tree, the path component we found during the\nlast call to the helper and the tree_desc. That way, when we get\nthe next call, we descend that stack as long as the leading path\ncomponents are still the same, and when we see that the path\ncomponent we are looking for is different from what we used in the\nlast call, we either (1) reuse the tree_desc and keep going forward\nif the name we looked for the last sorts before what we are looking\nfor, or (2) discard and reopen the tree, rewinding the tree_desc to\nthe beginning and do the scan.\n\nThat way, the caller of the check_local_mod() does not have to know\nthe trick, and because the loop in check_local_mod() iterates over\nthe list that is already sorted in the index order, we'd not just\nreduce the number of times we open the trees but also reduce the\nnumber of times we scan and skip the entries in trees to find the\nentries we are after.\n"},{"id":"331280","messageId":"20171029165244.si4a5furgf6trqe3@genre.crustytoothpaste.net","threadId":"47060","inReplyTo":"xmqqbmkqbwt0.fsf@gitster.mtv.corp.google.com","subject":"Re: git rm VERY slow for directories with many files.","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2017-10-29T16:52:44Z","receivedAt":"2017-10-29T16:52:55Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Sun, Oct 29, 2017 at 09:51:55AM +0900, Junio C Hamano wrote:\n> \"brian m. carlson\" writes:\n> > First, make sure your working directory is clean with no changes. Then,\n> > remove the directory (by hand) or move it somewhere else. Then, run\n> > \"git add -u\".\n> >\n> > That should allow you to commit the removal of those files quickly.\n> \n> If get_tree_entry() shows up a lot in the profile, it would indicate\n> that a lot of cycles are spent in check_local_mod(). Bypassing it\n> with \"-f\" may be the first thing to try ;-)\n\nThat is indeed faster. I tested my solution by creating a directory\nwith 20,000 files in a temporary repo. git rm -r took 17.96s, and git\nrm -rf took .12s. (This is on an SSD.)\n\nThat's also a nicer and more intuitive solution than mine.\n\n> I wonder how fast \"git diff-index --cached -r HEAD --\", with the\n> same pathspec used for the problematic \"git rm\", runs in this same\n> 50,000 path project.\n\nI'll let the original poster answer this one as well, but it was very\nfast in my test repo. I'm not very familiar with the code path in\nquestion, but it definitely looks like we're avoiding the quadratic\nbehavior in this case.\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\nhttps://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: https://keybase.io/bk2204\n"},{"id":"331304","messageId":"xmqqbmkp8lic.fsf@gitster.mtv.corp.google.com","threadId":"47060","inReplyTo":"20171029165244.si4a5furgf6trqe3@genre.crustytoothpaste.net","subject":"Re: git rm VERY slow for directories with many files.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-30T01:36:27Z","receivedAt":"2017-10-30T01:36:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"brian m. carlson\" writes:\n\n> On Sun, Oct 29, 2017 at 09:51:55AM +0900, Junio C Hamano wrote:\n>> \"brian m. carlson\" writes:\n>> > First, make sure your working directory is clean with no changes. Then,\n>> > remove the directory (by hand) or move it somewhere else. Then, run\n>> > \"git add -u\".\n>> >\n>> > That should allow you to commit the removal of those files quickly.\n>> \n>> If get_tree_entry() shows up a lot in the profile, it would indicate\n>> that a lot of cycles are spent in check_local_mod(). Bypassing it\n>> with \"-f\" may be the first thing to try ;-)\n>\n> That is indeed faster. I tested my solution by creating a directory\n> with 20,000 files in a temporary repo. git rm -r took 17.96s, and git\n> rm -rf took .12s. (This is on an SSD.)\n>\n> That's also a nicer and more intuitive solution than mine.\n\nHeh, the above was meant as a joke, though. \"-f\" is bypassing an\nimportant safety valve. In fact in my early draft of the message,\nthe paragraph that followed started with \"Jokes aside, ...\" ;-)\n\n>> I wonder how fast \"git diff-index --cached -r HEAD --\", with the\n>> same pathspec used for the problematic \"git rm\", runs in this same\n>> 50,000 path project.\n>\n> I'll let the original poster answer this one as well, but it was very\n> fast in my test repo. I'm not very familiar with the code path in\n> question, but it definitely looks like we're avoiding the quadratic\n> behavior in this case.\n\nBecause of the way \"diff-index --cached\" iterates over the index and\nthe tree in parallel, it should be a lot faster than doing\nget_tree_entry() for each and every path you care about. In\naddition, the \"--cached\" form is further optimized to take advantage\nof the cached-tree index extension, so you often can tell \"all index\nentries in this directory are untouched\" without descending into\ndeep subdirectories.\n"}]}