{"thread":{"id":"44042","subject":"[PATCH] checkout: eliminate unnecessary merge for trivial checkout","startedAt":"2016-09-08T20:45:03Z","lastAt":"2016-09-09T13:29:55Z","messageCount":4,"participants":["Ben Peart","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"301445","messageId":"20160908204431.14612-1-benpeart@microsoft.com","threadId":"44042","inReplyTo":null,"subject":"[PATCH] checkout: eliminate unnecessary merge for trivial checkout","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2016-09-08T20:44:31Z","receivedAt":"2016-09-08T20:45:03Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"Teach git to avoid unnecessary merge during trivial checkout.  When\nrunning 'git checkout -b foo' git follows a common code path through\nthe expensive merge_working_tree even when it is unnecessary.  As a\nresult, 95% of the time is spent in merge_working_tree doing the 2-way\nmerge between the new and old commit trees that is unneeded.\n\nThe time breakdown is as follows:\n\n    merge_working_tree <-- 95%\n        unpack_trees <-- 80%\n            traverse_trees <-- 50%\n            cache_tree_update <-- 17%\n            mark_new_skip_worktree <-- 10%\n\nWith a large repo, this cost is pronounced.  Using \"git checkout -b r\"\nto create and switch to a new branch costs 166 seconds (all times worst\ncase with a cold file system cache).\n\ngit.c:406               trace: built-in: git 'checkout' '-b' 'r'\nread-cache.c:1667       performance: 17.442926555 s: read_index_from\nname-hash.c:128         performance: 2.912145231 s: lazy_init_name_hash\nread-cache.c:2208       performance: 4.387713335 s: write_locked_index\ntrace.c:420             performance: 166.458921289 s: git command:\n                                        'c:\\Users\\benpeart\\bin\\git.exe' 'checkout' '-b' 'r'\nSwitched to a new branch 'r'\n\nBy adding a test to skip the unnecessary call to merge_working_tree in\nthis case reduces the cost to 16 seconds.\n\ngit.c:406               trace: built-in: git 'checkout' '-b' 's'\nread-cache.c:1667       performance: 16.100742476 s: read_index_from\ntrace.c:420             performance: 16.461547867 s: git command: 'c:\\Users\\benpeart\\bin\\git.exe' 'checkout' '-b' 's'\nSwitched to a new branch 's'\n\nSigned-off-by: Ben Peart <benpeart@microsoft.com>\n---\n builtin/checkout.c | 23 +++++++++++++++++++----\n 1 file changed, 19 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/checkout.c b/builtin/checkout.c\nindex 8672d07..595d64b 100644\n--- a/builtin/checkout.c\n+++ b/builtin/checkout.c\n@@ -827,10 +827,25 @@ static int switch_branches(const struct checkout_opts *opts,\n \t\tparse_commit_or_die(new->commit);\n \t}\n \n-\tret = merge_working_tree(opts, &old, new, &writeout_error);\n-\tif (ret) {\n-\t\tfree(path_to_free);\n-\t\treturn ret;\n+\t/*\n+\t * Optimize the performance of checkout when the current and\n+\t * new branch have the same OID and avoid the trivial merge.\n+\t * For example, a \"git checkout -b foo\" just needs to create\n+\t * the new ref and report the stats.\n+\t */\n+\tif (!old.commit || !new->commit\n+\t\t|| oidcmp(&old.commit->object.oid, &new->commit->object.oid)\n+\t\t|| !opts->new_branch || opts->new_branch_force || opts->new_orphan_branch\n+\t\t|| opts->patch_mode || opts->merge || opts->force || opts->force_detach\n+\t\t|| opts->writeout_stage || !opts->overwrite_ignore\n+\t\t|| opts->ignore_skipworktree || opts->ignore_other_worktrees\n+\t\t|| opts->new_branch_log || opts->branch_exists || opts->prefix\n+\t\t|| opts->source_tree) {\n+\t\tret = merge_working_tree(opts, &old, new, &writeout_error);\n+\t\tif (ret) {\n+\t\t\tfree(path_to_free);\n+\t\t\treturn ret;\n+\t\t}\n \t}\n \n \tif (!opts->quiet && !old.path && old.commit && new->commit != old.commit)\n-- \n2.10.0.windows.1\n\n"},{"id":"301450","messageId":"xmqqh99qf5o7.fsf@gitster.mtv.corp.google.com","threadId":"44042","inReplyTo":"20160908204431.14612-1-benpeart@microsoft.com","subject":"Re: [PATCH] checkout: eliminate unnecessary merge for trivial checkout","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-09-08T21:22:16Z","receivedAt":"2016-09-08T21:22:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ben Peart <peartben@gmail.com> writes:\n\n> Teach git to avoid unnecessary merge during trivial checkout.  When\n> running 'git checkout -b foo' git follows a common code path through\n> the expensive merge_working_tree even when it is unnecessary.\n\nI would be lying if I said I am not sympathetic to the cause, but...\n\n> +\t/*\n> +\t * Optimize the performance of checkout when the current and\n> +\t * new branch have the same OID and avoid the trivial merge.\n> +\t * For example, a \"git checkout -b foo\" just needs to create\n> +\t * the new ref and report the stats.\n> +\t */\n> +\tif (!old.commit || !new->commit\n> +\t\t|| oidcmp(&old.commit->object.oid, &new->commit->object.oid)\n> +\t\t|| !opts->new_branch || opts->new_branch_force || opts->new_orphan_branch\n> +\t\t|| opts->patch_mode || opts->merge || opts->force || opts->force_detach\n> +\t\t|| opts->writeout_stage || !opts->overwrite_ignore\n> +\t\t|| opts->ignore_skipworktree || opts->ignore_other_worktrees\n> +\t\t|| opts->new_branch_log || opts->branch_exists || opts->prefix\n> +\t\t|| opts->source_tree) {\n\n... this is a maintenance nightmare in that any new option we will\nadd later will need to consider what this \"optimization\" is trying\n(not) to skip.  The first two lines (i.e. we need a real checkout if\nwe cannot positively say that old and new commits are the same\nobject) are clear, but no explanation was given for all the other\nrandom conditions this if condition checks.  What if opts->something\nwas not listed (or \"listed\" for that matter) in the list above--it\nis totally unclear if it was missed by mistake (or \"added by\nmistake\") or deliberately excluded (or \"deliberately added\").\n\nFor example, why is opts->prefix there?  If\n\n\tgit checkout -b new-branch HEAD\n\nshould be able to omit the two-way merge, shouldn't\n\n\tcd t && git checkout -b new-branch HEAD\n\nalso be able to?\n\nEven the main condition is unclear.  It wants to see that old and\nnew have exactly the same commit, but shouldn't the \"the result of\nthe two-way merge is known to be no-op\" logic equally apply if the\nold and two trees are the same?\n\n\n\n\n"},{"id":"301456","messageId":"20160908213738.zgwgfy3nybkam3hk@sigill.intra.peff.net","threadId":"44042","inReplyTo":"xmqqh99qf5o7.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] checkout: eliminate unnecessary merge for trivial checkout","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-09-08T21:37:38Z","receivedAt":"2016-09-08T21:37:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 08, 2016 at 02:22:16PM -0700, Junio C Hamano wrote:\n\n> > +\t/*\n> > +\t * Optimize the performance of checkout when the current and\n> > +\t * new branch have the same OID and avoid the trivial merge.\n> > +\t * For example, a \"git checkout -b foo\" just needs to create\n> > +\t * the new ref and report the stats.\n> > +\t */\n> > +\tif (!old.commit || !new->commit\n> > +\t\t|| oidcmp(&old.commit->object.oid, &new->commit->object.oid)\n> > +\t\t|| !opts->new_branch || opts->new_branch_force || opts->new_orphan_branch\n> > +\t\t|| opts->patch_mode || opts->merge || opts->force || opts->force_detach\n> > +\t\t|| opts->writeout_stage || !opts->overwrite_ignore\n> > +\t\t|| opts->ignore_skipworktree || opts->ignore_other_worktrees\n> > +\t\t|| opts->new_branch_log || opts->branch_exists || opts->prefix\n> > +\t\t|| opts->source_tree) {\n> \n> ... this is a maintenance nightmare in that any new option we will\n> add later will need to consider what this \"optimization\" is trying\n> (not) to skip.  The first two lines (i.e. we need a real checkout if\n> we cannot positively say that old and new commits are the same\n> object) are clear, but no explanation was given for all the other\n> random conditions this if condition checks.  What if opts->something\n> was not listed (or \"listed\" for that matter) in the list above--it\n> is totally unclear if it was missed by mistake (or \"added by\n> mistake\") or deliberately excluded (or \"deliberately added\").\n> \n> For example, why is opts->prefix there?  If\n> \n> \tgit checkout -b new-branch HEAD\n> \n> should be able to omit the two-way merge, shouldn't\n> \n> \tcd t && git checkout -b new-branch HEAD\n> \n> also be able to?\n\nI was just writing another reply, but I think our complaints may have\ndovetailed.\n\nMy issue is that the condition above is an unreadable mass.  It would be\nreally nice to pull it out into a helper function, and then all of the\nitems could be split out and commented independently, like:\n\n  static int needs_working_tree_merge(const struct checkout_opts *opts,\n                                      const struct branch_info *old,\n\t\t\t\t      const struct branch_info *new)\n  {\n\t/*\n\t * We must do the merge if we are actually moving to a new\n\t * commit.\n\t */\n\tif (!old->commit || !new->commit ||\n\t    oidcmp(&old.commit->object.oid, &new->commit->object.oid))\n\t\treturn 1;\n\n\t/* Option \"foo\" is not compatible because of... */\n\tif (opts->foo)\n\t\treturn 1;\n\n\t... etc ...\n  }\n\nThat still leaves your \"what if opts->something is not listed\" question\nopen, but at least it makes it easier to comment on it in the code.\n\n-Peff\n\nPS I didn't think hard on whether the conditions above make _sense_. My\n   first goal would be to get more communication about them individually,\n   and then we can evaluate them.\n\n"},{"id":"301490","messageId":"002501d20a9e$3c7de5c0$b579b140$@gmail.com","threadId":"44042","inReplyTo":"20160908213738.zgwgfy3nybkam3hk@sigill.intra.peff.net","subject":"RE: [PATCH] checkout: eliminate unnecessary merge for trivial checkout","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2016-09-09T13:29:45Z","receivedAt":"2016-09-09T13:29:55Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\n> -----Original Message-----\n> From: Jeff King [mailto:peff@peff.net]\n> Sent: Thursday, September 8, 2016 5:38 PM\n> To: Junio C Hamano <gitster@pobox.com>\n> Cc: Ben Peart <peartben@gmail.com>; git@vger.kernel.org;\n> pclouds@gmail.com; =peartben@gmail.com; Ben Peart\n> <benpeart@microsoft.com>\n> Subject: Re: [PATCH] checkout: eliminate unnecessary merge for trivial\n> checkout\n> \n> On Thu, Sep 08, 2016 at 02:22:16PM -0700, Junio C Hamano wrote:\n> \n> > > +\t/*\n> > > +\t * Optimize the performance of checkout when the current and\n> > > +\t * new branch have the same OID and avoid the trivial merge.\n> > > +\t * For example, a \"git checkout -b foo\" just needs to create\n> > > +\t * the new ref and report the stats.\n> > > +\t */\n> > > +\tif (!old.commit || !new->commit\n> > > +\t\t|| oidcmp(&old.commit->object.oid, &new->commit-\n> >object.oid)\n> > > +\t\t|| !opts->new_branch || opts->new_branch_force || opts-\n> >new_orphan_branch\n> > > +\t\t|| opts->patch_mode || opts->merge || opts->force || opts-\n> >force_detach\n> > > +\t\t|| opts->writeout_stage || !opts->overwrite_ignore\n> > > +\t\t|| opts->ignore_skipworktree || opts-\n> >ignore_other_worktrees\n> > > +\t\t|| opts->new_branch_log || opts->branch_exists || opts-\n> >prefix\n> > > +\t\t|| opts->source_tree) {\n> >\n> > ... this is a maintenance nightmare in that any new option we will add\n> > later will need to consider what this \"optimization\" is trying\n> > (not) to skip.  The first two lines (i.e. we need a real checkout if\n> > we cannot positively say that old and new commits are the same\n> > object) are clear, but no explanation was given for all the other\n> > random conditions this if condition checks.  What if opts->something\n> > was not listed (or \"listed\" for that matter) in the list above--it is\n> > totally unclear if it was missed by mistake (or \"added by\n> > mistake\") or deliberately excluded (or \"deliberately added\").\n> >\n> > For example, why is opts->prefix there?  If\n> >\n> > \tgit checkout -b new-branch HEAD\n> >\n> > should be able to omit the two-way merge, shouldn't\n> >\n> > \tcd t && git checkout -b new-branch HEAD\n> >\n> > also be able to?\n\nBecause this induces a behavior change (the optimized path will no \nlonger do a \"soft reset\" and regenerate the index for example) I was\nattempting to make it as restrictive as possible but still enable the\nfast path in the most common case.  If everyone is OK with the behavior\nchange, I can make the optimization more inclusive by removing those\ntests that are not absolutely required (like opts->prefix).\n\nTo help ensure the optimization is updated when new checkout options are\nadded I could add a comment into the checkout_opts structure and/or put\na pseudo version check into the code so if the size of the structure\nchanges, the fast path fails.  That feels a little hacky and I haven't\nseen that in other areas so I'd rather stick with splitting it out into\na helper function and add comments.\n\n> \n> I was just writing another reply, but I think our complaints may have\n> dovetailed.\n> \n> My issue is that the condition above is an unreadable mass.  It would be\n> really nice to pull it out into a helper function, and then all of the items could\n> be split out and commented independently, like:\n> \n>   static int needs_working_tree_merge(const struct checkout_opts *opts,\n>                                       const struct branch_info *old,\n> \t\t\t\t      const struct branch_info *new)\n>   {\n> \t/*\n> \t * We must do the merge if we are actually moving to a new\n> \t * commit.\n> \t */\n> \tif (!old->commit || !new->commit ||\n> \t    oidcmp(&old.commit->object.oid, &new->commit->object.oid))\n> \t\treturn 1;\n> \n> \t/* Option \"foo\" is not compatible because of... */\n> \tif (opts->foo)\n> \t\treturn 1;\n> \n> \t... etc ...\n>   }\n\nThat is a great suggestion.  Splitting this out into a helper function \nwith comments will definitely make this more readable/maintainable and \nprovide more information on why each test is there.  I'll do that and\nreroll the patch.\n\n> \n> That still leaves your \"what if opts->something is not listed\" question open,\n> but at least it makes it easier to comment on it in the code.\n> \n> -Peff\n> \n> PS I didn't think hard on whether the conditions above make _sense_. My\n>    first goal would be to get more communication about them individually,\n>    and then we can evaluate them.\n\n\n"}]}