{"thread":{"id":"57384","subject":"Optimization for \"git clean -ffdx\"","startedAt":"2022-02-08T22:25:04Z","lastAt":"2022-02-15T22:16:26Z","messageCount":3,"participants":["Patrick Marlier","Elijah Newren"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"447999","messageId":"CAKQMxzSQRL-Q5daxETF+gYhVScmq_n=r2LJAeEuxpM7=jPajZQ@mail.gmail.com","threadId":"57384","inReplyTo":null,"subject":"Optimization for \"git clean -ffdx\"","fromName":"Patrick Marlier","fromEmail":"patrick.marlier@gmail.com","sentAt":"2022-02-08T22:03:49Z","receivedAt":"2022-02-08T22:25:04Z","isPatch":false,"sender":{"key":"patrick.marlier@gmail.com","avatar":null},"body":"Dear git Developers,\n\nIn a big repository with a lot of untracked directories and files\n(build in tree), \"git clean -ffdx\" can be optimized. Indeed, \"git\nclean\" goes recursively into all untracked and nested directories to\nlook for .git files even if \"-ff\" is specified.\nUsing breakpoint on stat or \"strace -e newfstatat\", it is possible to\nsee the recursing search for \".git\" and \".git/HEAD\". Also it seems to\ntraverse the untracked directories a few times, which I am not sure\nwhy.\n\nUsing \"-ff\" should not check for nested .git and no need to recurse if\nthe directory is already untracked.\n\nDoing the following, it seems to avoid looking for nested .git and all\ntests are passing.\n\n@@ -1007,6 +1008,12 @@ int cmd_clean(int argc, const char **argv,\nconst char *prefix)\n                 * the code clearer to exclude it, though.\n                 */\n                dir.flags |= DIR_KEEP_UNTRACKED_CONTENTS;\n+\n+               /*\n+                * No need to go to deeper in directories if already untracked\n+                */\n+               if (rm_flags == 0)\n+                       dir.flags |= DIR_NO_GITLINKS;\n        }\n\n        if (read_cache() < 0)\n\nHowever reading the documentation of DIR_NO_GITLINKS seems to say that\nis not the right fix.\n\nAnother thing to note is that it shows \"Removing XXX\" but it shows it\nwhen the directory is already gone. So we could change to \"Removed\nXXX\" or display the \"Removing XXX\" before starting to remove the\ndirectory.\n\nThanks in advance for any fix or help in getting it right.\n--\nPatrick Marlier\n"},{"id":"448333","messageId":"CABPp-BE2q5_LVVUw=2Wfys0AF350tTMMr43ZLpfsjE4ecb1Tpw@mail.gmail.com","threadId":"57384","inReplyTo":"CAKQMxzSQRL-Q5daxETF+gYhVScmq_n=r2LJAeEuxpM7=jPajZQ@mail.gmail.com","subject":"Re: Optimization for \"git clean -ffdx\"","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-02-13T03:25:18Z","receivedAt":"2022-02-13T03:25:44Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi Patrick,\n\nOn Wed, Feb 9, 2022 at 2:42 AM Patrick Marlier\n<patrick.marlier@gmail.com> wrote:\n>\n> Dear git Developers,\n>\n> In a big repository with a lot of untracked directories and files\n> (build in tree), \"git clean -ffdx\" can be optimized. Indeed, \"git\n> clean\" goes recursively into all untracked and nested directories to\n> look for .git files even if \"-ff\" is specified.\n\nYeah, seems like a waste of work.  Thanks for digging in.\n\n> Using breakpoint on stat or \"strace -e newfstatat\", it is possible to\n> see the recursing search for \".git\" and \".git/HEAD\". Also it seems to\n> traverse the untracked directories a few times, which I am not sure\n> why.\n\nThere are two steps -- collect the list of things that are removable,\nand then a separate step to remove the things that are removable.  It\ncan be the case that we recurse into the same directory twice, once\nfor each step.  For the first step, see the fill_directory() call.  If\nyou left off \"-x\" or only had one \"-f\", or your directories had some\ntracked files, then fill_directory()'s job is finding out which things\nare removable and it'd likely only be a subset of those directories.\nFor the second step, some of those removable things may be entire\ndirectories.  So when it hits one of those and later calls\nremove_dirs() to remove it, it has to recurse again.\n\n> Using \"-ff\" should not check for nested .git and no need to recurse if\n> the directory is already untracked.\n\nNot quite; the -x and lack of -e options is critical here, otherwise\nwe cannot just nuke the whole directory.  (Also, -d is important, but\nthat just kind of goes without saying.)\n\n> Doing the following, it seems to avoid looking for nested .git and all\n> tests are passing.\n>\n> @@ -1007,6 +1008,12 @@ int cmd_clean(int argc, const char **argv,\n> const char *prefix)\n>                  * the code clearer to exclude it, though.\n>                  */\n>                 dir.flags |= DIR_KEEP_UNTRACKED_CONTENTS;\n> +\n> +               /*\n> +                * No need to go to deeper in directories if already untracked\n> +                */\n> +               if (rm_flags == 0)\n> +                       dir.flags |= DIR_NO_GITLINKS;\n>         }\n>\n>         if (read_cache() < 0)\n>\n> However reading the documentation of DIR_NO_GITLINKS seems to say that\n> is not the right fix.\n\nI think DIR_NO_GITLINKS has an unfortunately poor description.  The\nfill_directory() API has many different callers who use it\ndifferently, see commit 8d92fb2927 (\"dir: replace exponential\nalgorithm with a linear one\", 2020-04-01) for some description of\nthis.  I often ran into problems where descriptions of variables and\nitems in the documentation tended to focus on one of those modes in\nsuch a way as to make the other modes that also called in be\nconfusing.  I think the author of the current text was just thinking\nof one of those other callers, probably 'git status'.  Looking at the\ncode, it's intended purpose is just what you're using it for.  (Also,\nI probably should have documented DIR_SKIP_NESTED_GIT when I added it\nin commit 09487f2cba (\"clean: avoid removing untracked files in a\nnested git repository\", 2019-09-17); the fact that it is similar and\nundocumented isn't helping matters, although at the time I didn't know\nthere was documentation for any of the flags given that they were in\nan entirely separate file.)\n\nAnyway, documentation issues aside, I think this is the flag you want\nto use, but this is not the right place to set it.  I think you should\nset it where rm_flags is set to 0 instead.\n\nFurther, setting this flag is only solving part of the performance\nproblem.  We'll still recurse into the directories to look for ignored\nfiles, which should be avoided since we don't need to differentiate.\nThat basically means that we need to avoid all the code in the current\n\n   if (remove_directories && !ignored_only)\n\nblock, whenever (remove_directories && ignored && !exclude_list.nr &&\nforce > 1).\n\n> Another thing to note is that it shows \"Removing XXX\" but it shows it\n> when the directory is already gone. So we could change to \"Removed\n> XXX\" or display the \"Removing XXX\" before starting to remove the\n> directory.\n\nI commented on Bagas' patch, but I think this is minutiae that won't\nbe relevant to the end user, and would rather either ignore it or just\nmove the print statement earlier rather than increasing work for\ntranslators.  That is, unless we tend to use past tense elsewhere in\nthe UI and we want to make a concerted effort to convert to using past\ntense.\n\n> Thanks in advance for any fix or help in getting it right.\n\nYou've clearly taken the time to investigate, and you found the basic\nsolution too.  That's pretty good, especially considering that you're\ndealing with the dragons in dir.[ch].  We could potentially have 1-3\npatches here:\n  * avoiding the unnecessary checks for is_nonbare_repository_dir()\nvia setting DIR_NO_GITLINKS.  This is basically your change, just\nmoved slightly.\n  * avoiding the unnecessary attempts to differentiate untracked and\nignored via avoiding the \"if (remove_directories && !ignored_only)\"\ncode block when appropriate, as highlighted above\n  * fixing up the documentation for DIR_NO_GITLINKS and adding some\nfor DIR_SKIP_NESTED_GIT.\n\nYou've already done most the work for the first one, you'd just need\nto move the line elsewhere and add a commit message (though adding a\ntestcase might be nice too).  Are you up for that?  Would you also\nlike to tackle either of the other two items?  If you combine the\nfirst and the second, you might find be able to generate a good\ntestcase by running\n    GIT_TRACE2_PERF=\"$(pwd)/.git/trace.output\" git clean -ffdx\nand then grepping the trace.output file for \"directories-visited\" and\n\"paths-visited\" and checking that the new flags indeed reduce both of\nthose numbers.  Anyway, I'll be happy to review your patch(es) and\nwill take whichever parts you don't want to tackle.\n\nThanks for digging in, reporting, and helping make Git better!\n"},{"id":"448488","messageId":"CAKQMxzRsq5uHme03a8DqMg1-Tku+0teDv0mDnsbJERfORtTB_w@mail.gmail.com","threadId":"57384","inReplyTo":"CABPp-BE2q5_LVVUw=2Wfys0AF350tTMMr43ZLpfsjE4ecb1Tpw@mail.gmail.com","subject":"Re: Optimization for \"git clean -ffdx\"","fromName":"Patrick Marlier","fromEmail":"patrick.marlier@gmail.com","sentAt":"2022-02-15T22:16:09Z","receivedAt":"2022-02-15T22:16:26Z","isPatch":false,"sender":{"key":"patrick.marlier@gmail.com","avatar":null},"body":"Hi Elijah,\n\nThanks for this nice and very detailed email!\n\nOn Sun, Feb 13, 2022 at 4:25 AM Elijah Newren <newren@gmail.com> wrote:\n> There are two steps -- collect the list of things that are removable,\n> and then a separate step to remove the things that are removable.  It\n> can be the case that we recurse into the same directory twice, once\n> for each step.  For the first step, see the fill_directory() call.  If\n> you left off \"-x\" or only had one \"-f\", or your directories had some\n> tracked files, then fill_directory()'s job is finding out which things\n> are removable and it'd likely only be a subset of those directories.\n> For the second step, some of those removable things may be entire\n> directories.  So when it hits one of those and later calls\n> remove_dirs() to remove it, it has to recurse again.\n\nI am not sure I understand perfectly why there are 2 steps but this is detail.\n\nThe observation I had in the second step for removal, it is this type\nof patterns using strace:\ngetcwd(\"/tmp/repo\", 129) = 46\nnewfstatat(AT_FDCWD, \"/tmp/repo/a\", {st_mode=S_IFDIR|0700,\nst_size=4096, ...}, AT_SYMLINK_NOFOLLOW) = 0\nnewfstatat(AT_FDCWD, \"/tmp/repo/a/a\", {st_mode=S_IFDIR|0700,\nst_size=4096, ...}, AT_SYMLINK_NOFOLLOW) = 0\nnewfstatat(AT_FDCWD, \"/tmp/repo/a/a/a\", {st_mode=S_IFDIR|0700,\nst_size=4096, ...}, AT_SYMLINK_NOFOLLOW) = 0\nnewfstatat(AT_FDCWD, \"/tmp/repo/a/a/a/a\", {st_mode=S_IFDIR|0700,\nst_size=4096, ...}, AT_SYMLINK_NOFOLLOW) = 0\nrmdir(\"a/a/a/a\")                        = 0\nnewfstatat(AT_FDCWD, \"a/a/a/b\", {st_mode=S_IFDIR|0700, st_size=4096,\n...}, AT_SYMLINK_NOFOLLOW) = 0\nopenat(AT_FDCWD, \"a/a/a/b\", O_RDONLY|O_NONBLOCK|O_CLOEXEC|O_DIRECTORY) = 6\nnewfstatat(6, \"\", {st_mode=S_IFDIR|0700, st_size=4096, ...}, AT_EMPTY_PATH) = 0\ngetdents64(6, 0x55b718d8d650 /* 2 entries */, 32768) = 48\ngetdents64(6, 0x55b718d8d650 /* 0 entries */, 32768) = 0\nclose(6)                                = 0\ngetcwd(\"/tmp/repo\", 129) = 46\nnewfstatat(AT_FDCWD, \"/tmp/repo/a\", {st_mode=S_IFDIR|0700,\nst_size=4096, ...}, AT_SYMLINK_NOFOLLOW) = 0\nnewfstatat(AT_FDCWD, \"/tmp/repo/a/a\", {st_mode=S_IFDIR|0700,\nst_size=4096, ...}, AT_SYMLINK_NOFOLLOW) = 0\nnewfstatat(AT_FDCWD, \"/tmp/repo/a/a/a\", {st_mode=S_IFDIR|0700,\nst_size=4096, ...}, AT_SYMLINK_NOFOLLOW) = 0\nnewfstatat(AT_FDCWD, \"/tmp/repo/a/a/a/b\", {st_mode=S_IFDIR|0700,\nst_size=4096, ...}, AT_SYMLINK_NOFOLLOW) = 0\nrmdir(\"a/a/a/b\")                        = 0\n\nHere I have a repository with quite some nested and untracked directories.\nWe can see that many \"newfstatat\" are repeated for the same path. Also\n\"getcwd\" is repeated many times.\nI guess here \"strbuf_realpath\" would benefit from some caching.\n\n\n> > Using \"-ff\" should not check for nested .git and no need to recurse if\n> > the directory is already untracked.\n>\n> Not quite; the -x and lack of -e options is critical here, otherwise\n> we cannot just nuke the whole directory.  (Also, -d is important, but\n> that just kind of goes without saying.)\n\nIndeed, you are right.\n\n\n> Further, setting this flag is only solving part of the performance\n> problem.  We'll still recurse into the directories to look for ignored\n> files, which should be avoided since we don't need to differentiate.\n> That basically means that we need to avoid all the code in the current\n>\n>    if (remove_directories && !ignored_only)\n>\n> block, whenever (remove_directories && ignored && !exclude_list.nr &&\n> force > 1).\n\nGood point!\n\n\n> > Another thfing to note is that it shows \"Removing XXX\" but it shows it\n> > when the directory is already gone. So we could change to \"Removed\n> > XXX\" or display the \"Removing XXX\" before starting to remove the\n> > directory.\n>\n> I commented on Bagas' patch, but I think this is minutiae that won't\n> be relevant to the end user, and would rather either ignore it or just\n> move the print statement earlier rather than increasing work for\n> translators.  That is, unless we tend to use past tense elsewhere in\n> the UI and we want to make a concerted effort to convert to using past\n> tense.\n\nIf we want to be correct, then we should then move the \"Removing\"\nprinting before but then it makes the \"gone\" flag a bit useless.\nI will defer to you if this is something we want to fix.\n\n\n> Anyway, I'll be happy to review your patch(es) and\n> will take whichever parts you don't want to tackle.\n\nIf you don't mind, I will let you adjust the documentation.\nFollowing the patch series for the 2 other changes.\n\nThanks a lot Elijah. Very appreciated!\n--\nPatrick Marlier\n"}]}