{"thread":{"id":"39003","subject":"git clean performance issues","startedAt":"2015-04-04T18:32:45Z","lastAt":"2015-11-13T23:53:34Z","messageCount":6,"participants":["erik elfström","Jeff King","Andreas Krey"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"258993","messageId":"CAMpP7NY++BwV+UygRj1C6Zsf=jE-z1AQuN3On0HeEqQpKGQtqw@mail.gmail.com","threadId":"39003","inReplyTo":null,"subject":"git clean performance issues","fromName":"erik elfström","fromEmail":"erik.elfstrom@gmail.com","sentAt":"2015-04-04T18:32:45Z","receivedAt":"2015-04-04T18:32:45Z","isPatch":false,"sender":{"key":"erik.elfstrom@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13905184?v=4"},"body":"Hi,\n\nI'm having a performance issue with \"git clean -qxfd\" (note, not using\n\"-ff\").\n\nThe performance issue shows up when trying to clean untracked\ndirectories that themselves contain many sub directories. The\nperformance is highly non linear with the number of sub\ndirectories. Some test numbers:\n\nDirs Time\n10000 0m0.754s\n50000 0m16.606s\n100000 1m31.418s\n\nWhen running \"git clean -qxffd\" (note, using \"-ff\") the performance is\nfast and linear:\n\nDirs Time\n10000 0m0.158s\n50000 0m0.918s\n100000 0m1.639s\n\nAfter checking the source of git-clean my understanding of the problem\nis as follows:\n\nWhen clean.c:cmd_clean finds a directory and the \"-d\" flag is given it\nwill call clean.c:remove_dirs to potentially remove the directory and\nall sub directories.\n\nUnless \"-ff\" is given remove_dirs tries to be nice and not remove\ndirectories containing other git repositories. To do this it does the\nfollowing check:\n\n ...\n if ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) &&\n !resolve_gitlink_ref(path->buf, \"HEAD\", submodule_head)) {\n ...\n\nThe problem is that refs.c:resolve_gitlink_ref will call\nrefs.c:get_ref_cache that will linearly search a linked list of cache\nentries and create and insert a new ref_cache entry in the list for\neach path it is given if it fails to find an existing entry:\n\n for (refs = submodule_ref_caches; refs; refs = refs->next)\n if (!strcmp(submodule, refs->name))\n return refs;\n\n refs = create_ref_cache(submodule);\n refs->next = submodule_ref_caches;\n submodule_ref_caches = refs;\n return refs;\n\nIn my scenario get_ref_cache will be called 10000+ times, each time\nwith a new path. The final few calls will need to search through and\ncompare 10000+ entries before realizing that there is no existing\nentry. This quickly ads up to 100 million+ calls to strcmp().\n\n>From what I can understand, the calls to get_ref_cache in this\nscenario will never do any useful work. Is this correct? If so, would\nit be possible to bypass it, maybe by calling\nresolve_gitlink_ref_recursive directly or by using some other way of\nchecking for the presence of a git repo in clean.c:remove_dirs?\n\n/Erik\n"},{"id":"258998","messageId":"20150404195507.GA31763@peff.net","threadId":"39003","inReplyTo":"CAMpP7NY++BwV+UygRj1C6Zsf=jE-z1AQuN3On0HeEqQpKGQtqw@mail.gmail.com","subject":"Re: git clean performance issues","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-04T19:55:07Z","receivedAt":"2015-04-04T19:55:07Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Apr 04, 2015 at 08:32:45PM +0200, erik elfström wrote:\n\n> In my scenario get_ref_cache will be called 10000+ times, each time\n> with a new path. The final few calls will need to search through and\n> compare 10000+ entries before realizing that there is no existing\n> entry. This quickly ads up to 100 million+ calls to strcmp().\n> \n> From what I can understand, the calls to get_ref_cache in this\n> scenario will never do any useful work. Is this correct? If so, would\n> it be possible to bypass it, maybe by calling\n> resolve_gitlink_ref_recursive directly or by using some other way of\n> checking for the presence of a git repo in clean.c:remove_dirs?\n\nI think this is the same issue that was discussed here:\n\n http://thread.gmane.org/gmane.comp.version-control.git/265560/focus=265585\n\nThere is some discussion of a possible fix in that thread. I was hoping\nthat Andreas was going to look further and produce a patch, but I\nimagine he got busy with other things. Do you want to try picking it up?\n\n-Peff\n"},{"id":"259002","messageId":"CAMpP7NZ8OD5or8H11OvuH1nq+qe-btKCsQnhas6+7SRYE1M1Tw@mail.gmail.com","threadId":"39003","inReplyTo":"20150404195507.GA31763@peff.net","subject":"Re: git clean performance issues","fromName":"erik elfström","fromEmail":"erik.elfstrom@gmail.com","sentAt":"2015-04-04T20:39:47Z","receivedAt":"2015-04-04T20:39:47Z","isPatch":false,"sender":{"key":"erik.elfstrom@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13905184?v=4"},"body":"That looks like the same issue. The \"use is_git_directory\" approach\nsounds good to me, is that the direction you would prefer? I can try\nto cobble something together although I must warn you I have zero\nprevious experience with this code base so a few iterations will\nprobably be needed.\n\n/Erik\n\nOn Sat, Apr 4, 2015 at 9:55 PM, Jeff King wrote:\n> On Sat, Apr 04, 2015 at 08:32:45PM +0200, erik elfström wrote:\n>\n>> In my scenario get_ref_cache will be called 10000+ times, each time\n>> with a new path. The final few calls will need to search through and\n>> compare 10000+ entries before realizing that there is no existing\n>> entry. This quickly ads up to 100 million+ calls to strcmp().\n>>\n>> From what I can understand, the calls to get_ref_cache in this\n>> scenario will never do any useful work. Is this correct? If so, would\n>> it be possible to bypass it, maybe by calling\n>> resolve_gitlink_ref_recursive directly or by using some other way of\n>> checking for the presence of a git repo in clean.c:remove_dirs?\n>\n> I think this is the same issue that was discussed here:\n>\n> http://thread.gmane.org/gmane.comp.version-control.git/265560/focus=265585\n>\n> There is some discussion of a possible fix in that thread. I was hoping\n> that Andreas was going to look further and produce a patch, but I\n> imagine he got busy with other things. Do you want to try picking it up?\n>\n> -Peff\n"},{"id":"259003","messageId":"20150404204802.GA558@peff.net","threadId":"39003","inReplyTo":"CAMpP7NZ8OD5or8H11OvuH1nq+qe-btKCsQnhas6+7SRYE1M1Tw@mail.gmail.com","subject":"Re: git clean performance issues","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-04T20:48:02Z","receivedAt":"2015-04-04T20:48:02Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Apr 04, 2015 at 10:39:47PM +0200, erik elfström wrote:\n\n> That looks like the same issue. The \"use is_git_directory\" approach\n> sounds good to me, is that the direction you would prefer? I can try\n> to cobble something together although I must warn you I have zero\n> previous experience with this code base so a few iterations will\n> probably be needed.\n\nYeah, I think the preferred direction is building a solution in\nis_git_directory. Multiple iterations are fine. That's what review is\nfor. :) See SubmittingPatches for tips, though.\n\n-Peff\n"},{"id":"273277","messageId":"20151113141907.GB16219@inner.h.apk.li","threadId":"39003","inReplyTo":"20150404195507.GA31763@peff.net","subject":"Re: git clean performance issues","fromName":"Andreas Krey","fromEmail":"a.krey@gmx.de","sentAt":"2015-11-13T14:19:07Z","receivedAt":"2015-11-13T14:19:07Z","isPatch":false,"sender":{"key":"a.krey@gmx.de","avatar":"https://avatars.githubusercontent.com/u/37810?v=4"},"body":"On Sat, 04 Apr 2015 15:55:07 +0000, Jeff King wrote:\n...\n> I think this is the same issue that was discussed here:\n> \n> http://thread.gmane.org/gmane.comp.version-control.git/265560/focus&5585\n> \n> There is some discussion of a possible fix in that thread. I was hoping\n> that Andreas was going to look further and produce a patch, but I\n> imagine he got busy with other things.\n\nThat about sums it up. However I now have a similar issue;\ngit ls-files shows the same behaviour (takes relatively\nforever at 100% CPU), and runs instantly with my patch\nfrom back then. Nothing seems to have changed, so I\nmay have another chance to look into this.\n\nAndreas\n\n-- \n\"Totally trivial. Famous last words.\"\nFrom: Linus Torvalds \nDate: Fri, 22 Jan 2010 07:29:21 -0800\n"},{"id":"273303","messageId":"20151113235334.GA18260@sigill.intra.peff.net","threadId":"39003","inReplyTo":"20151113141907.GB16219@inner.h.apk.li","subject":"Re: git clean performance issues","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-13T23:53:34Z","receivedAt":"2015-11-13T23:53:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 13, 2015 at 03:19:07PM +0100, Andreas Krey wrote:\n\n> On Sat, 04 Apr 2015 15:55:07 +0000, Jeff King wrote:\n> ...\n> > I think this is the same issue that was discussed here:\n> > \n> > http://thread.gmane.org/gmane.comp.version-control.git/265560/focus&5585\n> > \n> > There is some discussion of a possible fix in that thread. I was hoping\n> > that Andreas was going to look further and produce a patch, but I\n> > imagine he got busy with other things.\n> \n> That about sums it up. However I now have a similar issue;\n> git ls-files shows the same behaviour (takes relatively\n> forever at 100% CPU), and runs instantly with my patch\n> from back then. Nothing seems to have changed, so I\n> may have another chance to look into this.\n\nYeah, I think Erik's patch in 0179ca7 (clean: improve performance when\nremoving lots of directories, 2015-06-15) handles the git-clean case the\nway we want to, but all of the other calls to resolve_gitlink_ref need\nto be inspected and fixed similarly.\n\nThe one your are hitting with ls-files is probably in dir.c:treat_directory.\n\n-Peff\n"}]}