{"thread":{"id":"26125","subject":"[PATCH] unpack_trees(): skip trees that are the same in all input","startedAt":"2010-12-22T22:13:47Z","lastAt":"2010-12-30T12:44:08Z","messageCount":4,"participants":["Junio C Hamano","Nguyen Thai Ngoc Duy"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"158498","messageId":"7vr5d94fs4.fsf@alter.siamese.dyndns.org","threadId":"26125","inReplyTo":null,"subject":"[PATCH] unpack_trees(): skip trees that are the same in all input","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-22T22:13:47Z","receivedAt":"2010-12-22T22:13:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"unpack_trees() merges two trees (the current HEAD and the destination\ncommit) when switching to another branch, checking and updating the index\nentry where the destination differs from the current HEAD.  It merges three\ntrees (the common ancestor, the current HEAD and the other commit) when\nperforming a three-way merge, checking and updating the index entry when\nthe merge result differs from the current HEAD.  It does so by walking the\ninput trees in parallel all the way down to the leaves.\n\nOne common special case is a directory is identical across the trees\ninvolved in the merge.  In such a case, we do not have to descend into the\ndirectory at all---we know that the end result is to keep the entries in\nthe current index.\n\nThis optimization cannot be applied in a few special cases in\nunpack_trees(), though.  We need to descend into the directory and update\nthe index entries from the target tree in the following cases:\n\n - When resetting (e.g. \"git reset --hard\"); and\n\n - When checking out a tree for the first time into an empty working tree\n   (e.g. \"git read-tree -m -u HEAD HEAD\" with missing .git/index).\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n With and without this patch I tried to recreate a handful of recent\n merges in the kernel repository.  The result is somewhat mixed but\n overall in favor.\n\n <resulting merge commit>\n *** CURRENT ***\n /usr/bin/time output from \"git merge\" to reproduce it, without the patch\n *** NEW ***\n /usr/bin/time output from \"git merge\" to reproduce it, with the patch\n\n 6313e3c21743cc88bb5bd8aa72948ee1e83937b6\n *** CURRENT ***\n 3.88user 0.43system 0:04.31elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+47688outputs (0major+205724minor)pagefaults 0swaps\n *** NEW ***\n 3.78user 0.46system 0:04.26elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+47688outputs (0major+185004minor)pagefaults 0swaps\n\n 6dde39be39e636c1d41e73590668d5903b11535b\n *** CURRENT ***\n 0.32user 0.12system 0:00.44elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+15272outputs (0major+23180minor)pagefaults 0swaps\n *** NEW ***\n 0.24user 0.11system 0:00.34elapsed 102%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+15264outputs (0major+18288minor)pagefaults 0swaps\n\n f8f5d4f11dc7d321fb372b09fc8767069a18bf30\n *** CURRENT ***\n 1.37user 0.14system 0:01.52elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+15336outputs (0major+43258minor)pagefaults 0swaps\n *** NEW ***\n 1.40user 0.14system 0:01.54elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+15336outputs (0major+41767minor)pagefaults 0swaps\n\n 2cedcc4f122934c3ad38dfb2a400b98a62703e6d\n *** CURRENT ***\n 0.43user 0.10system 0:00.54elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+13696outputs (0major+24652minor)pagefaults 0swaps\n *** NEW ***\n 0.30user 0.12system 0:00.43elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+13696outputs (0major+22156minor)pagefaults 0swaps\n\n 81e8d2162566379adcf4b3700f03845c62577145\n *** CURRENT ***\n 0.42user 0.12system 0:00.54elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+13544outputs (0major+24128minor)pagefaults 0swaps\n *** NEW ***\n 0.35user 0.11system 0:00.50elapsed 91%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+13536outputs (0major+21667minor)pagefaults 0swaps\n\n unpack-trees.c |   48 ++++++++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 48 insertions(+), 0 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex aa585be..7c0c963 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -436,6 +436,10 @@ static int switch_cache_bottom(struct traverse_info *info)\n \treturn ret;\n }\n \n+static int fast_forward_merge(int n, unsigned long dirmask,\n+\t\t\t      struct name_entry *names,\n+\t\t\t      struct traverse_info *info);\n+\n static int traverse_trees_recursive(int n, unsigned long dirmask,\n \t\t\t\t    unsigned long df_conflicts,\n \t\t\t\t    struct name_entry *names,\n@@ -447,6 +451,11 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n \tstruct traverse_info newinfo;\n \tstruct name_entry *p;\n \n+\tif (!df_conflicts) {\n+\t\tint status = fast_forward_merge(n, dirmask, names, info);\n+\t\tif (status)\n+\t\t\treturn status;\n+\t}\n \tp = names;\n \twhile (!p->mode)\n \t\tp++;\n@@ -694,6 +703,45 @@ static struct cache_entry *find_cache_entry(struct traverse_info *info,\n \t\treturn NULL;\n }\n \n+static int fast_forward_merge(int n, unsigned long dirmask,\n+\t\t\t      struct name_entry *names,\n+\t\t\t      struct traverse_info *info)\n+{\n+\tint i;\n+\tstruct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };\n+\tstruct unpack_trees_options *o = info->data;\n+\n+\t/* merging two or more trees with an identical subdirectory? */\n+\tif ((n < 2) || ((1UL << n) - 1) != dirmask ||\n+\t    !o->merge || o->reset || o->initial_checkout)\n+\t\treturn 0;\n+\tfor (i = 1; i < n; i++)\n+\t\tif (hashcmp(names[i-1].sha1, names[i].sha1))\n+\t\t\treturn 0;\n+\n+\t/*\n+\t * Instead of descending into the directory, keep the contents\n+\t * of the current index.\n+\t */\n+\twhile (1) {\n+\t\tstruct cache_entry *ce;\n+\t\tce = next_cache_entry(o);\n+\t\tif (!ce)\n+\t\t\tbreak;\n+\t\t/* Is the entry still in that directory? */\n+\t\tif (do_compare_entry(ce, info, names))\n+\t\t\tbreak;\n+\t\tfor (i = 0; i < n + 1; i++)\n+\t\t\tsrc[i] = ce;\n+\t\tmark_ce_used(ce, o);\n+\t\tif (call_unpack_fn(src, o) < 0)\n+\t\t\treturn unpack_failed(o, NULL);\n+\t\tif (ce_stage(ce))\n+\t\t\tmark_ce_used_same_name(ce, o);\n+\t}\n+\treturn dirmask;\n+}\n+\n static void debug_path(struct traverse_info *info)\n {\n \tif (info->prev) {\n-- \n1.7.3.4.804.g8883a\n"},{"id":"158712","messageId":"AANLkTinm=k_84Nh4YakbkdNNLO4-yeVxGF+p_rR5TFB=@mail.gmail.com","threadId":"26125","inReplyTo":"7vr5d94fs4.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] unpack_trees(): skip trees that are the same in all input","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2010-12-29T14:43:09Z","receivedAt":"2010-12-29T14:43:09Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Dec 23, 2010 at 5:13 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> @@ -447,6 +451,11 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n>        struct traverse_info newinfo;\n>        struct name_entry *p;\n>\n> +       if (!df_conflicts) {\n> +               int status = fast_forward_merge(n, dirmask, names, info);\n> +               if (status)\n> +                       return status;\n> +       }\n\nAlso skip the optimization when sparse checkout is active\n(info->data->skip_sparse_checkout == 0). People may need to just\nupdate skip-worktree bits and add/remove worktree files along the\nline.\n\nOr you could make another step ahead and make fast_forward_merge aware\nof sparse checkout too ;-)\n-- \nDuy\n"},{"id":"158720","messageId":"7vd3oktmoo.fsf@alter.siamese.dyndns.org","threadId":"26125","inReplyTo":"AANLkTinm=k_84Nh4YakbkdNNLO4-yeVxGF+p_rR5TFB=@mail.gmail.com","subject":"Re: [PATCH] unpack_trees(): skip trees that are the same in all input","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-29T19:15:51Z","receivedAt":"2010-12-29T19:15:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:\n\n> On Thu, Dec 23, 2010 at 5:13 AM, Junio C Hamano <gitster@pobox.com> wrote:\n>> @@ -447,6 +451,11 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n>>        struct traverse_info newinfo;\n>>        struct name_entry *p;\n>>\n>> +       if (!df_conflicts) {\n>> +               int status = fast_forward_merge(n, dirmask, names, info);\n>> +               if (status)\n>> +                       return status;\n>> +       }\n>\n> Also skip the optimization when sparse checkout is active\n> (info->data->skip_sparse_checkout == 0). People may need to just\n> update skip-worktree bits and add/remove worktree files along the\n> line.\n\nSounds sensible and safer to special case that one, I would agree.\n\nBy the way, I think info->data->skip_sparse_checkout should be fixed by\nrenaming it to info->data->sparse_checkout.  The flag controls a special\ncase logic that should not be in effect unless explicitly asked, and\nforcing normal codepath to say \"If skip_sparse_checkout is not false, do\nthis\" in double-negative is unnice than \"If sparse_checkout is in effect,\nplease run this special case\" when reading the code.\n"},{"id":"158756","messageId":"AANLkTinWj7vjQcJVZ732HDj++F8PjUHhne8unoORsVB9@mail.gmail.com","threadId":"26125","inReplyTo":"7vd3oktmoo.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] unpack_trees(): skip trees that are the same in all input","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2010-12-30T12:44:08Z","receivedAt":"2010-12-30T12:44:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Dec 30, 2010 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> By the way, I think info->data->skip_sparse_checkout should be fixed by\n> renaming it to info->data->sparse_checkout.  The flag controls a special\n> case logic that should not be in effect unless explicitly asked, and\n> forcing normal codepath to say \"If skip_sparse_checkout is not false, do\n> this\" in double-negative is unnice than \"If sparse_checkout is in effect,\n> please run this special case\" when reading the code.\n\nIt's something to do with zero value being \"feature set by default\".\nUnless explicitly said otherwise, sparse checkout code should be in\neffect so that skip-checkout bit is preserved in index. No, double\nnegation is not nice. But I don't know how I can set\nunpack_trees_options.sparse_checkout = 1 by default.\n-- \nDuy\n"}]}