{"thread":{"id":"33269","subject":"[PATCH] checkout: avoid unncessary match_pathspec calls","startedAt":"2013-03-23T10:55:42Z","lastAt":"2013-03-28T22:32:27Z","messageCount":7,"participants":["Nguyễn Thái Ngọc Duy","Eric Sunshine","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"212044","messageId":"1364036142-3031-1-git-send-email-pclouds@gmail.com","threadId":"33269","inReplyTo":null,"subject":"[PATCH] checkout: avoid unncessary match_pathspec calls","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-23T10:55:42Z","receivedAt":"2013-03-23T10:55:42Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"In checkout_paths() we do this\n\n - for i = 0..active_nr, if not updated, call match_pathspec\n - for ..., call match_pathspec (inside unmerge_cache)\n - for ..., call match_pathspec (for showing \"path .. is unmerged)\n - for ..., if not updated, call match_pathspec and update paths\n\nThat's a lot of duplicate match_pathspec(s) and the function is not\nexactly cheap to be called so many times, especially on large indexes.\nThis patch makes it call match_pathspec once per index entry, save the\nresult in ce_flags and reuse the results in the following loops.\n\nThis command is used on webkit, 215k entries. The pattern is chosen\nmainly to make match_pathspec sweat:\n\ngit checkout -- \"*[a-zA-Z]*[a-zA-Z]*[a-zA-Z]*\"\n\n        before      after\nreal    0m3.493s    0m2.737s\nuser    0m2.239s    0m1.586s\nsys     0m1.252s    0m1.151s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n Junio, this patch clearly conflicts wih nd/magic-pathspecs. Do you\n want me to:\n\n  - hold it off until nd/magic-pathspecs graduates\n  - rebase on top of nd/magic-pathspecs and repost\n  - leave it to you to handle conflicts\n\n ?\n\n builtin/checkout.c | 23 +++++++++++++++++++----\n cache.h            |  1 +\n resolve-undo.c     | 19 ++++++++++++++++++-\n resolve-undo.h     |  1 +\n 4 files changed, 39 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/checkout.c b/builtin/checkout.c\nindex a9c1b5a..fadc11b 100644\n--- a/builtin/checkout.c\n+++ b/builtin/checkout.c\n@@ -273,22 +273,37 @@ static int checkout_paths(const struct checkout_opts *opts,\n \n \tfor (pos = 0; pos < active_nr; pos++) {\n \t\tstruct cache_entry *ce = active_cache[pos];\n+\t\tce->ce_flags &= ~CE_MATCHED;\n \t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n \t\t\tcontinue;\n-\t\tmatch_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, ps_matched);\n+\t\tif (match_pathspec(opts->pathspec, ce->name,\n+\t\t\t\t   ce_namelen(ce), 0, ps_matched))\n+\t\t\tce->ce_flags |= CE_MATCHED;\n \t}\n \n \tif (report_path_error(ps_matched, opts->pathspec, opts->prefix))\n \t\treturn 1;\n \n+\t/*\n+\t * call match_pathspec on the remaining entries that have not\n+\t * been done in the previous loop\n+\t */\n+\tfor (pos = 0; pos < active_nr; pos++) {\n+\t\tstruct cache_entry *ce = active_cache[pos];\n+\t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE) &&\n+\t\t    match_pathspec(opts->pathspec, ce->name,\n+\t\t\t\t   ce_namelen(ce), 0, ps_matched))\n+\t\t\tce->ce_flags |= CE_MATCHED;\n+\t}\n+\n \t/* \"checkout -m path\" to recreate conflicted state */\n \tif (opts->merge)\n-\t\tunmerge_cache(opts->pathspec);\n+\t\tunmerge_marked_index(&the_index);\n \n \t/* Any unmerged paths? */\n \tfor (pos = 0; pos < active_nr; pos++) {\n \t\tstruct cache_entry *ce = active_cache[pos];\n-\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, NULL)) {\n+\t\tif (ce->ce_flags & CE_MATCHED) {\n \t\t\tif (!ce_stage(ce))\n \t\t\t\tcontinue;\n \t\t\tif (opts->force) {\n@@ -315,7 +330,7 @@ static int checkout_paths(const struct checkout_opts *opts,\n \t\tstruct cache_entry *ce = active_cache[pos];\n \t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n \t\t\tcontinue;\n-\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, NULL)) {\n+\t\tif (ce->ce_flags & CE_MATCHED) {\n \t\t\tif (!ce_stage(ce)) {\n \t\t\t\terrs |= checkout_entry(ce, &state, NULL);\n \t\t\t\tcontinue;\ndiff --git a/cache.h b/cache.h\nindex c56315c..04e6090 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -161,6 +161,7 @@ struct cache_entry {\n \n #define CE_UNPACKED          (1 << 24)\n #define CE_NEW_SKIP_WORKTREE (1 << 25)\n+#define CE_MATCHED           (1 << 26)\n \n /*\n  * Extended on-disk flags\ndiff --git a/resolve-undo.c b/resolve-undo.c\nindex 72b4612..639eb9c 100644\n--- a/resolve-undo.c\n+++ b/resolve-undo.c\n@@ -118,7 +118,7 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \tstruct cache_entry *ce;\n \tstruct string_list_item *item;\n \tstruct resolve_undo_info *ru;\n-\tint i, err = 0;\n+\tint i, err = 0, matched;\n \n \tif (!istate->resolve_undo)\n \t\treturn pos;\n@@ -137,6 +137,7 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \tru = item->util;\n \tif (!ru)\n \t\treturn pos;\n+\tmatched = ce->ce_flags & CE_MATCHED;\n \tremove_index_entry_at(istate, pos);\n \tfor (i = 0; i < 3; i++) {\n \t\tstruct cache_entry *nce;\n@@ -144,6 +145,8 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \t\t\tcontinue;\n \t\tnce = make_cache_entry(ru->mode[i], ru->sha1[i],\n \t\t\t\t       ce->name, i + 1, 0);\n+\t\tif (matched)\n+\t\t\tnce->ce_flags |= CE_MATCHED;\n \t\tif (add_index_entry(istate, nce, ADD_CACHE_OK_TO_ADD)) {\n \t\t\terr = 1;\n \t\t\terror(\"cannot unmerge '%s'\", ce->name);\n@@ -156,6 +159,20 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \treturn unmerge_index_entry_at(istate, pos);\n }\n \n+void unmerge_marked_index(struct index_state *istate)\n+{\n+\tint i;\n+\n+\tif (!istate->resolve_undo)\n+\t\treturn;\n+\n+\tfor (i = 0; i < istate->cache_nr; i++) {\n+\t\tstruct cache_entry *ce = istate->cache[i];\n+\t\tif (ce->ce_flags & CE_MATCHED)\n+\t\t\ti = unmerge_index_entry_at(istate, i);\n+\t}\n+}\n+\n void unmerge_index(struct index_state *istate, const char **pathspec)\n {\n \tint i;\ndiff --git a/resolve-undo.h b/resolve-undo.h\nindex 8458769..7a30206 100644\n--- a/resolve-undo.h\n+++ b/resolve-undo.h\n@@ -12,5 +12,6 @@ extern struct string_list *resolve_undo_read(const char *, unsigned long);\n extern void resolve_undo_clear_index(struct index_state *);\n extern int unmerge_index_entry_at(struct index_state *, int);\n extern void unmerge_index(struct index_state *, const char **);\n+extern void unmerge_marked_index(struct index_state *);\n \n #endif\n-- \n1.8.2.83.gc99314b\n"},{"id":"212066","messageId":"CAPig+cR3=h6gCTC223mOrS3dQWt8dv49BDHj52W27ZoV6HvJkA@mail.gmail.com","threadId":"33269","inReplyTo":"1364036142-3031-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] checkout: avoid unncessary match_pathspec calls","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-03-24T02:45:05Z","receivedAt":"2013-03-24T02:45:05Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sat, Mar 23, 2013 at 6:55 AM, Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:\n> checkout: avoid unncessary match_pathspec calls\n\ns/unncessary/unnecessary/\n\n> In checkout_paths() we do this\n> ...\n"},{"id":"212077","messageId":"7vr4j52t0z.fsf@alter.siamese.dyndns.org","threadId":"33269","inReplyTo":"1364036142-3031-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] checkout: avoid unncessary match_pathspec calls","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-24T06:47:40Z","receivedAt":"2013-03-24T06:47:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:\n\n> ---\n>  Junio, this patch clearly conflicts wih nd/magic-pathspecs. Do you\n>  want me to:\n>\n>   - hold it off until nd/magic-pathspecs graduates\n>   - rebase on top of nd/magic-pathspecs and repost\n>   - leave it to you to handle conflicts\n>  ?\n\nI'd prefer to take small, independent and clear improvements first\nand worry about larger ones later, so if there were another choice,\ni.e.\n\n - eject nd/magic-pathspecs for now, cook this (and other small\n   independent and clear improvements you may come up with, some of\n   which might come out of nd/magic-pathspecs itself) and let it\n   graduate first, and later revisit rerolld nd/magic-pathspecs\n\nthat would be the ideal among the given choices ;-).\n\n>  \tfor (pos = 0; pos < active_nr; pos++) {\n>  \t\tstruct cache_entry *ce = active_cache[pos];\n> +\t\tce->ce_flags &= ~CE_MATCHED;\n>  \t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n>  \t\t\tcontinue;\n> -\t\tmatch_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, ps_matched);\n> +\t\tif (match_pathspec(opts->pathspec, ce->name,\n> +\t\t\t\t   ce_namelen(ce), 0, ps_matched))\n> +\t\t\tce->ce_flags |= CE_MATCHED;\n>  \t}\n>  \n>  \tif (report_path_error(ps_matched, opts->pathspec, opts->prefix))\n>  \t\treturn 1;\n>  \n> +\t/*\n> +\t * call match_pathspec on the remaining entries that have not\n> +\t * been done in the previous loop\n> +\t */\n> +\tfor (pos = 0; pos < active_nr; pos++) {\n> +\t\tstruct cache_entry *ce = active_cache[pos];\n> +\t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE) &&\n> +\t\t    match_pathspec(opts->pathspec, ce->name,\n> +\t\t\t\t   ce_namelen(ce), 0, ps_matched))\n> +\t\t\tce->ce_flags |= CE_MATCHED;\n> +\t}\n> +\n\nThe above is a faithful rewrite, but I have to wonder why you need\ntwo separate loops.\n\nDo you understand what the original loop is doing with ps_matched,\nand why the code excludes certain paths while doing so?  I didn't\nwhen I read your patch for the first time, as I forgot, until I\nchecked with 0a1283bc3955 (checkout $tree $path: do not clobber\nlocal changes in $path not in $tree, 2011-09-30)\n\nYou don't use ps_matched after report_path_error(); the new loop\nshouldn't have to record which pathspec matched.\n\nAlso I notice that I forgot to free ps_matched.  Perhaps doing it\nthis way is easier to maintain?\n\n\t/*\n         * Make sure all pathspecs participated in locating the\n\t * paths to be checked out.\n         */\n\tfor (pos = 0; pos < active_nr; pos++) {\n\t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n\t\t\t/*\n                         * \"git checkout tree-ish -- path\", but this entry\n                         * is in the original index; it will not be checked\n                         * out to the working tree and it does not matter\n\t\t\t * if pathspec matched this entry.  We will not do\n\t\t\t * anything to this entry at all.\n                \t */\n\t\t\tverify_psmatch = NULL;\n\t\telse\n\t\t\t/*\n                         * Either this entry came from the tree-ish\n                         * we are checking the paths out of, or we\n\t\t\t * are checking out of the index.\n                \t */\n                        verify_psmatch = ps_matched;\n\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce),\n\t\t\t\t   0, verify_psmatch))\n\t\t\tce->ce_flags |= CE_MATCHED;\n\t}\n\n\tif (report_path_error(ps_matched, opts->pathspec, opts->prefix))\n\t\treturn 1;\n\tfree(ps_matched);\n\nAfter commenting on the above, it makes me wonder if we even need to\nbother marking entries that were in the index that did not come from\nthe tree-ish we are checking paths out of, though.  What breaks if\nyou did not do the rewrite above and dropped the second loop in your\npatch?\n"},{"id":"212092","messageId":"1364129725-29597-1-git-send-email-pclouds@gmail.com","threadId":"33269","inReplyTo":"7vr4j52t0z.fsf@alter.siamese.dyndns.org","subject":"[PATCH v2] checkout: avoid unnecessary match_pathspec calls","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-24T12:55:25Z","receivedAt":"2013-03-24T12:55:25Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"In checkout_paths() we do this\n\n - for all updated items, call match_pathspec\n - for all items, call match_pathspec (inside unmerge_cache)\n - for all items, call match_pathspec (for showing \"path .. is unmerged)\n - for updated items, call match_pathspec and update paths\n\nThat's a lot of duplicate match_pathspec(s) and the function is not\nexactly cheap to be called so many times, especially on large indexes.\nThis patch makes it call match_pathspec once per updated index entry,\nsave the result in ce_flags and reuse the results in the following\nloops.\n\nThe changes in 0a1283b (checkout $tree $path: do not clobber local\nchanges in $path not in $tree - 2011-09-30) limit the affected paths\nto ones we read from $tree. We do not do anything to other modified\nentries in this case, so the \"for all items\" above could be modified\nto \"for all updated items\". But..\n\nThe command's behavior now is modified slightly: unmerged entries that\nmatch $path, but not updated by $tree, are now NOT touched.  Although\nthis should be considered a bug fix, not a regression.\n\nAnd while at there, free ps_matched after use.\n\nThe following command is tested on webkit, 215k entries. The pattern\nis chosen mainly to make match_pathspec sweat:\n\ngit checkout -- \"*[a-zA-Z]*[a-zA-Z]*[a-zA-Z]*\"\n\n        before      after\nreal    0m3.493s    0m2.737s\nuser    0m2.239s    0m1.586s\nsys     0m1.252s    0m1.151s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n > and worry about larger ones later, so if there were another choice,\n > i.e.\n >\n >  - eject nd/magic-pathspecs for now, cook this (and other small\n >    independent and clear improvements you may come up with, some of\n >    which might come out of nd/magic-pathspecs itself) and let it\n >    graduate first, and later revisit rerolld nd/magic-pathspecs\n >\n > that would be the ideal among the given choices ;-).\n\n Whichever is easier for you.\n\n > The above is a faithful rewrite, but I have to wonder why you need\n > two separate loops.\n >\n > Do you understand what the original loop is doing with ps_matched,\n > and why the code excludes certain paths while doing so?\n\n Nope, I did not dig that deep. I expected you to do it ;-) j/k\n\n > After commenting on the above, it makes me wonder if we even need to\n > bother marking entries that were in the index that did not come from\n > the tree-ish we are checking paths out of, though.  What breaks if\n > you did not do the rewrite above and dropped the second loop in your\n > patch?\n\n The test suite says none. There is a behavior change regarding\n unmerged entries as mentioned in the commit message. But I think it's\n a good change.\n\n builtin/checkout.c | 34 +++++++++++++++++++++++++++-------\n cache.h            |  1 +\n resolve-undo.c     | 19 ++++++++++++++++++-\n resolve-undo.h     |  1 +\n 4 files changed, 47 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/checkout.c b/builtin/checkout.c\nindex a9c1b5a..359b983 100644\n--- a/builtin/checkout.c\n+++ b/builtin/checkout.c\n@@ -271,24 +271,46 @@ static int checkout_paths(const struct checkout_opts *opts,\n \t\t;\n \tps_matched = xcalloc(1, pos);\n \n+\t/*\n+\t * Make sure all pathspecs participated in locating the paths\n+\t * to be checked out.\n+\t */\n \tfor (pos = 0; pos < active_nr; pos++) {\n \t\tstruct cache_entry *ce = active_cache[pos];\n+\t\tce->ce_flags &= ~CE_MATCHED;\n \t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n+\t\t\t/*\n+\t\t\t * \"git checkout tree-ish -- path\", but this entry\n+\t\t\t * is in the original index; it will not be checked\n+\t\t\t * out to the working tree and it does not matter\n+\t\t\t * if pathspec matched this entry.  We will not do\n+\t\t\t * anything to this entry at all.\n+\t\t\t */\n \t\t\tcontinue;\n-\t\tmatch_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, ps_matched);\n+\t\t/*\n+\t\t * Either this entry came from the tree-ish we are\n+\t\t * checking the paths out of, or we are checking out\n+\t\t * of the index.\n+\t\t */\n+\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce),\n+\t\t\t\t   0, ps_matched))\n+\t\t\tce->ce_flags |= CE_MATCHED;\n \t}\n \n-\tif (report_path_error(ps_matched, opts->pathspec, opts->prefix))\n+\tif (report_path_error(ps_matched, opts->pathspec, opts->prefix)) {\n+\t\tfree(ps_matched);\n \t\treturn 1;\n+\t}\n+\tfree(ps_matched);\n \n \t/* \"checkout -m path\" to recreate conflicted state */\n \tif (opts->merge)\n-\t\tunmerge_cache(opts->pathspec);\n+\t\tunmerge_marked_index(&the_index);\n \n \t/* Any unmerged paths? */\n \tfor (pos = 0; pos < active_nr; pos++) {\n \t\tstruct cache_entry *ce = active_cache[pos];\n-\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, NULL)) {\n+\t\tif (ce->ce_flags & CE_MATCHED) {\n \t\t\tif (!ce_stage(ce))\n \t\t\t\tcontinue;\n \t\t\tif (opts->force) {\n@@ -313,9 +335,7 @@ static int checkout_paths(const struct checkout_opts *opts,\n \tstate.refresh_cache = 1;\n \tfor (pos = 0; pos < active_nr; pos++) {\n \t\tstruct cache_entry *ce = active_cache[pos];\n-\t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n-\t\t\tcontinue;\n-\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, NULL)) {\n+\t\tif (ce->ce_flags & CE_MATCHED) {\n \t\t\tif (!ce_stage(ce)) {\n \t\t\t\terrs |= checkout_entry(ce, &state, NULL);\n \t\t\t\tcontinue;\ndiff --git a/cache.h b/cache.h\nindex c56315c..04e6090 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -161,6 +161,7 @@ struct cache_entry {\n \n #define CE_UNPACKED          (1 << 24)\n #define CE_NEW_SKIP_WORKTREE (1 << 25)\n+#define CE_MATCHED           (1 << 26)\n \n /*\n  * Extended on-disk flags\ndiff --git a/resolve-undo.c b/resolve-undo.c\nindex 72b4612..639eb9c 100644\n--- a/resolve-undo.c\n+++ b/resolve-undo.c\n@@ -118,7 +118,7 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \tstruct cache_entry *ce;\n \tstruct string_list_item *item;\n \tstruct resolve_undo_info *ru;\n-\tint i, err = 0;\n+\tint i, err = 0, matched;\n \n \tif (!istate->resolve_undo)\n \t\treturn pos;\n@@ -137,6 +137,7 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \tru = item->util;\n \tif (!ru)\n \t\treturn pos;\n+\tmatched = ce->ce_flags & CE_MATCHED;\n \tremove_index_entry_at(istate, pos);\n \tfor (i = 0; i < 3; i++) {\n \t\tstruct cache_entry *nce;\n@@ -144,6 +145,8 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \t\t\tcontinue;\n \t\tnce = make_cache_entry(ru->mode[i], ru->sha1[i],\n \t\t\t\t       ce->name, i + 1, 0);\n+\t\tif (matched)\n+\t\t\tnce->ce_flags |= CE_MATCHED;\n \t\tif (add_index_entry(istate, nce, ADD_CACHE_OK_TO_ADD)) {\n \t\t\terr = 1;\n \t\t\terror(\"cannot unmerge '%s'\", ce->name);\n@@ -156,6 +159,20 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \treturn unmerge_index_entry_at(istate, pos);\n }\n \n+void unmerge_marked_index(struct index_state *istate)\n+{\n+\tint i;\n+\n+\tif (!istate->resolve_undo)\n+\t\treturn;\n+\n+\tfor (i = 0; i < istate->cache_nr; i++) {\n+\t\tstruct cache_entry *ce = istate->cache[i];\n+\t\tif (ce->ce_flags & CE_MATCHED)\n+\t\t\ti = unmerge_index_entry_at(istate, i);\n+\t}\n+}\n+\n void unmerge_index(struct index_state *istate, const char **pathspec)\n {\n \tint i;\ndiff --git a/resolve-undo.h b/resolve-undo.h\nindex 8458769..7a30206 100644\n--- a/resolve-undo.h\n+++ b/resolve-undo.h\n@@ -12,5 +12,6 @@ extern struct string_list *resolve_undo_read(const char *, unsigned long);\n extern void resolve_undo_clear_index(struct index_state *);\n extern int unmerge_index_entry_at(struct index_state *, int);\n extern void unmerge_index(struct index_state *, const char **);\n+extern void unmerge_marked_index(struct index_state *);\n \n #endif\n-- \n1.8.2.83.gc99314b\n"},{"id":"212177","messageId":"7vr4j3zbrz.fsf@alter.siamese.dyndns.org","threadId":"33269","inReplyTo":"1364129725-29597-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v2] checkout: avoid unnecessary match_pathspec calls","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-25T16:26:08Z","receivedAt":"2013-03-25T16:26:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> In checkout_paths() we do this\n>\n>  - for all updated items, call match_pathspec\n>  - for all items, call match_pathspec (inside unmerge_cache)\n>  - for all items, call match_pathspec (for showing \"path .. is unmerged)\n>  - for updated items, call match_pathspec and update paths\n>\n> That's a lot of duplicate match_pathspec(s) and the function is not\n> exactly cheap to be called so many times, especially on large indexes.\n> This patch makes it call match_pathspec once per updated index entry,\n> save the result in ce_flags and reuse the results in the following\n> loops.\n>\n> The changes in 0a1283b (checkout $tree $path: do not clobber local\n> changes in $path not in $tree - 2011-09-30) limit the affected paths\n> to ones we read from $tree. We do not do anything to other modified\n> entries in this case, so the \"for all items\" above could be modified\n> to \"for all updated items\". But..\n>\n> The command's behavior now is modified slightly: unmerged entries that\n> match $path, but not updated by $tree, are now NOT touched.  Although\n> this should be considered a bug fix, not a regression.\n\nCould we have a test to show the difference please, especially if we\nare going to sell this as a fix?\n\nThe change itself looks quite sane to me (I didn't apply or test it,\nthough---just eyeballing).\n\nThanks.\n\n>\n> And while at there, free ps_matched after use.\n>\n> The following command is tested on webkit, 215k entries. The pattern\n> is chosen mainly to make match_pathspec sweat:\n>\n> git checkout -- \"*[a-zA-Z]*[a-zA-Z]*[a-zA-Z]*\"\n>\n>         before      after\n> real    0m3.493s    0m2.737s\n> user    0m2.239s    0m1.586s\n> sys     0m1.252s    0m1.151s\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n> ---\n>  > and worry about larger ones later, so if there were another choice,\n>  > i.e.\n>  >\n>  >  - eject nd/magic-pathspecs for now, cook this (and other small\n>  >    independent and clear improvements you may come up with, some of\n>  >    which might come out of nd/magic-pathspecs itself) and let it\n>  >    graduate first, and later revisit rerolld nd/magic-pathspecs\n>  >\n>  > that would be the ideal among the given choices ;-).\n>\n>  Whichever is easier for you.\n>\n>  > The above is a faithful rewrite, but I have to wonder why you need\n>  > two separate loops.\n>  >\n>  > Do you understand what the original loop is doing with ps_matched,\n>  > and why the code excludes certain paths while doing so?\n>\n>  Nope, I did not dig that deep. I expected you to do it ;-) j/k\n>\n>  > After commenting on the above, it makes me wonder if we even need to\n>  > bother marking entries that were in the index that did not come from\n>  > the tree-ish we are checking paths out of, though.  What breaks if\n>  > you did not do the rewrite above and dropped the second loop in your\n>  > patch?\n>\n>  The test suite says none. There is a behavior change regarding\n>  unmerged entries as mentioned in the commit message. But I think it's\n>  a good change.\n>\n>  builtin/checkout.c | 34 +++++++++++++++++++++++++++-------\n>  cache.h            |  1 +\n>  resolve-undo.c     | 19 ++++++++++++++++++-\n>  resolve-undo.h     |  1 +\n>  4 files changed, 47 insertions(+), 8 deletions(-)\n>\n> diff --git a/builtin/checkout.c b/builtin/checkout.c\n> index a9c1b5a..359b983 100644\n> --- a/builtin/checkout.c\n> +++ b/builtin/checkout.c\n> @@ -271,24 +271,46 @@ static int checkout_paths(const struct checkout_opts *opts,\n>  \t\t;\n>  \tps_matched = xcalloc(1, pos);\n>  \n> +\t/*\n> +\t * Make sure all pathspecs participated in locating the paths\n> +\t * to be checked out.\n> +\t */\n>  \tfor (pos = 0; pos < active_nr; pos++) {\n>  \t\tstruct cache_entry *ce = active_cache[pos];\n> +\t\tce->ce_flags &= ~CE_MATCHED;\n>  \t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n> +\t\t\t/*\n> +\t\t\t * \"git checkout tree-ish -- path\", but this entry\n> +\t\t\t * is in the original index; it will not be checked\n> +\t\t\t * out to the working tree and it does not matter\n> +\t\t\t * if pathspec matched this entry.  We will not do\n> +\t\t\t * anything to this entry at all.\n> +\t\t\t */\n>  \t\t\tcontinue;\n> -\t\tmatch_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, ps_matched);\n> +\t\t/*\n> +\t\t * Either this entry came from the tree-ish we are\n> +\t\t * checking the paths out of, or we are checking out\n> +\t\t * of the index.\n> +\t\t */\n> +\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce),\n> +\t\t\t\t   0, ps_matched))\n> +\t\t\tce->ce_flags |= CE_MATCHED;\n>  \t}\n>  \n> -\tif (report_path_error(ps_matched, opts->pathspec, opts->prefix))\n> +\tif (report_path_error(ps_matched, opts->pathspec, opts->prefix)) {\n> +\t\tfree(ps_matched);\n>  \t\treturn 1;\n> +\t}\n> +\tfree(ps_matched);\n>  \n>  \t/* \"checkout -m path\" to recreate conflicted state */\n>  \tif (opts->merge)\n> -\t\tunmerge_cache(opts->pathspec);\n> +\t\tunmerge_marked_index(&the_index);\n>  \n>  \t/* Any unmerged paths? */\n>  \tfor (pos = 0; pos < active_nr; pos++) {\n>  \t\tstruct cache_entry *ce = active_cache[pos];\n> -\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, NULL)) {\n> +\t\tif (ce->ce_flags & CE_MATCHED) {\n>  \t\t\tif (!ce_stage(ce))\n>  \t\t\t\tcontinue;\n>  \t\t\tif (opts->force) {\n> @@ -313,9 +335,7 @@ static int checkout_paths(const struct checkout_opts *opts,\n>  \tstate.refresh_cache = 1;\n>  \tfor (pos = 0; pos < active_nr; pos++) {\n>  \t\tstruct cache_entry *ce = active_cache[pos];\n> -\t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n> -\t\t\tcontinue;\n> -\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, NULL)) {\n> +\t\tif (ce->ce_flags & CE_MATCHED) {\n>  \t\t\tif (!ce_stage(ce)) {\n>  \t\t\t\terrs |= checkout_entry(ce, &state, NULL);\n>  \t\t\t\tcontinue;\n> diff --git a/cache.h b/cache.h\n> index c56315c..04e6090 100644\n> --- a/cache.h\n> +++ b/cache.h\n> @@ -161,6 +161,7 @@ struct cache_entry {\n>  \n>  #define CE_UNPACKED          (1 << 24)\n>  #define CE_NEW_SKIP_WORKTREE (1 << 25)\n> +#define CE_MATCHED           (1 << 26)\n>  \n>  /*\n>   * Extended on-disk flags\n> diff --git a/resolve-undo.c b/resolve-undo.c\n> index 72b4612..639eb9c 100644\n> --- a/resolve-undo.c\n> +++ b/resolve-undo.c\n> @@ -118,7 +118,7 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n>  \tstruct cache_entry *ce;\n>  \tstruct string_list_item *item;\n>  \tstruct resolve_undo_info *ru;\n> -\tint i, err = 0;\n> +\tint i, err = 0, matched;\n>  \n>  \tif (!istate->resolve_undo)\n>  \t\treturn pos;\n> @@ -137,6 +137,7 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n>  \tru = item->util;\n>  \tif (!ru)\n>  \t\treturn pos;\n> +\tmatched = ce->ce_flags & CE_MATCHED;\n>  \tremove_index_entry_at(istate, pos);\n>  \tfor (i = 0; i < 3; i++) {\n>  \t\tstruct cache_entry *nce;\n> @@ -144,6 +145,8 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n>  \t\t\tcontinue;\n>  \t\tnce = make_cache_entry(ru->mode[i], ru->sha1[i],\n>  \t\t\t\t       ce->name, i + 1, 0);\n> +\t\tif (matched)\n> +\t\t\tnce->ce_flags |= CE_MATCHED;\n>  \t\tif (add_index_entry(istate, nce, ADD_CACHE_OK_TO_ADD)) {\n>  \t\t\terr = 1;\n>  \t\t\terror(\"cannot unmerge '%s'\", ce->name);\n> @@ -156,6 +159,20 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n>  \treturn unmerge_index_entry_at(istate, pos);\n>  }\n>  \n> +void unmerge_marked_index(struct index_state *istate)\n> +{\n> +\tint i;\n> +\n> +\tif (!istate->resolve_undo)\n> +\t\treturn;\n> +\n> +\tfor (i = 0; i < istate->cache_nr; i++) {\n> +\t\tstruct cache_entry *ce = istate->cache[i];\n> +\t\tif (ce->ce_flags & CE_MATCHED)\n> +\t\t\ti = unmerge_index_entry_at(istate, i);\n> +\t}\n> +}\n> +\n>  void unmerge_index(struct index_state *istate, const char **pathspec)\n>  {\n>  \tint i;\n> diff --git a/resolve-undo.h b/resolve-undo.h\n> index 8458769..7a30206 100644\n> --- a/resolve-undo.h\n> +++ b/resolve-undo.h\n> @@ -12,5 +12,6 @@ extern struct string_list *resolve_undo_read(const char *, unsigned long);\n>  extern void resolve_undo_clear_index(struct index_state *);\n>  extern int unmerge_index_entry_at(struct index_state *, int);\n>  extern void unmerge_index(struct index_state *, const char **);\n> +extern void unmerge_marked_index(struct index_state *);\n>  \n>  #endif\n"},{"id":"212367","messageId":"1364363901-17815-1-git-send-email-pclouds@gmail.com","threadId":"33269","inReplyTo":"7vr4j3zbrz.fsf@alter.siamese.dyndns.org","subject":"[PATCH v3] checkout: avoid unnecessary match_pathspec calls","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-27T05:58:21Z","receivedAt":"2013-03-27T05:58:21Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"In checkout_paths() we do this\n\n - for all updated items, call match_pathspec\n - for all items, call match_pathspec (inside unmerge_cache)\n - for all items, call match_pathspec (for showing \"path .. is unmerged)\n - for updated items, call match_pathspec and update paths\n\nThat's a lot of duplicate match_pathspec(s) and the function is not\nexactly cheap to be called so many times, especially on large indexes.\nThis patch makes it call match_pathspec once per updated index entry,\nsave the result in ce_flags and reuse the results in the following\nloops.\n\nThe changes in 0a1283b (checkout $tree $path: do not clobber local\nchanges in $path not in $tree - 2011-09-30) limit the affected paths\nto ones we read from $tree. We do not do anything to other modified\nentries in this case, so the \"for all items\" above could be modified\nto \"for all updated items\". But..\n\nThe command's behavior now is modified slightly: unmerged entries that\nmatch $path, but not updated by $tree, are now NOT touched.  Although\nthis should be considered a bug fix, not a regression. A new test is\nadded for this change.\n\nAnd while at there, free ps_matched after use.\n\nThe following command is tested on webkit, 215k entries. The pattern\nis chosen mainly to make match_pathspec sweat:\n\ngit checkout -- \"*[a-zA-Z]*[a-zA-Z]*[a-zA-Z]*\"\n\n        before      after\nreal    0m3.493s    0m2.737s\nuser    0m2.239s    0m1.586s\nsys     0m1.252s    0m1.151s\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n Changes from v2: a new test and some note about matching twice in\n \"checkout $tree $path\", once in read_tree_some and once checkout_paths.\n We may be able avoid match_pathspec entirely in this case when\n tree_entry_interesting learns to fill ps_matched.\n\n builtin/checkout.c        | 43 ++++++++++++++++++++++++++++++++++++-------\n cache.h                   |  1 +\n resolve-undo.c            | 19 ++++++++++++++++++-\n resolve-undo.h            |  1 +\n t/t2022-checkout-paths.sh | 21 +++++++++++++++++++++\n 5 files changed, 77 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/checkout.c b/builtin/checkout.c\nindex a9c1b5a..f8033f4 100644\n--- a/builtin/checkout.c\n+++ b/builtin/checkout.c\n@@ -271,24 +271,55 @@ static int checkout_paths(const struct checkout_opts *opts,\n \t\t;\n \tps_matched = xcalloc(1, pos);\n \n+\t/*\n+\t * Make sure all pathspecs participated in locating the paths\n+\t * to be checked out.\n+\t */\n \tfor (pos = 0; pos < active_nr; pos++) {\n \t\tstruct cache_entry *ce = active_cache[pos];\n+\t\tce->ce_flags &= ~CE_MATCHED;\n \t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n+\t\t\t/*\n+\t\t\t * \"git checkout tree-ish -- path\", but this entry\n+\t\t\t * is in the original index; it will not be checked\n+\t\t\t * out to the working tree and it does not matter\n+\t\t\t * if pathspec matched this entry.  We will not do\n+\t\t\t * anything to this entry at all.\n+\t\t\t */\n \t\t\tcontinue;\n-\t\tmatch_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, ps_matched);\n+\t\t/*\n+\t\t * Either this entry came from the tree-ish we are\n+\t\t * checking the paths out of, or we are checking out\n+\t\t * of the index.\n+\t\t *\n+\t\t * If it comes from the tree-ish, we already know it\n+\t\t * matches the pathspec and could just stamp\n+\t\t * CE_MATCHED to it from update_some(). But we still\n+\t\t * need ps_matched and read_tree_recursive (and\n+\t\t * eventually tree_entry_interesting) cannot fill\n+\t\t * ps_matched yet. Once it can, we can avoid calling\n+\t\t * match_pathspec() for _all_ entries when\n+\t\t * opts->source_tree != NULL.\n+\t\t */\n+\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce),\n+\t\t\t\t   0, ps_matched))\n+\t\t\tce->ce_flags |= CE_MATCHED;\n \t}\n \n-\tif (report_path_error(ps_matched, opts->pathspec, opts->prefix))\n+\tif (report_path_error(ps_matched, opts->pathspec, opts->prefix)) {\n+\t\tfree(ps_matched);\n \t\treturn 1;\n+\t}\n+\tfree(ps_matched);\n \n \t/* \"checkout -m path\" to recreate conflicted state */\n \tif (opts->merge)\n-\t\tunmerge_cache(opts->pathspec);\n+\t\tunmerge_marked_index(&the_index);\n \n \t/* Any unmerged paths? */\n \tfor (pos = 0; pos < active_nr; pos++) {\n \t\tstruct cache_entry *ce = active_cache[pos];\n-\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, NULL)) {\n+\t\tif (ce->ce_flags & CE_MATCHED) {\n \t\t\tif (!ce_stage(ce))\n \t\t\t\tcontinue;\n \t\t\tif (opts->force) {\n@@ -313,9 +344,7 @@ static int checkout_paths(const struct checkout_opts *opts,\n \tstate.refresh_cache = 1;\n \tfor (pos = 0; pos < active_nr; pos++) {\n \t\tstruct cache_entry *ce = active_cache[pos];\n-\t\tif (opts->source_tree && !(ce->ce_flags & CE_UPDATE))\n-\t\t\tcontinue;\n-\t\tif (match_pathspec(opts->pathspec, ce->name, ce_namelen(ce), 0, NULL)) {\n+\t\tif (ce->ce_flags & CE_MATCHED) {\n \t\t\tif (!ce_stage(ce)) {\n \t\t\t\terrs |= checkout_entry(ce, &state, NULL);\n \t\t\t\tcontinue;\ndiff --git a/cache.h b/cache.h\nindex c56315c..04e6090 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -161,6 +161,7 @@ struct cache_entry {\n \n #define CE_UNPACKED          (1 << 24)\n #define CE_NEW_SKIP_WORKTREE (1 << 25)\n+#define CE_MATCHED           (1 << 26)\n \n /*\n  * Extended on-disk flags\ndiff --git a/resolve-undo.c b/resolve-undo.c\nindex 72b4612..639eb9c 100644\n--- a/resolve-undo.c\n+++ b/resolve-undo.c\n@@ -118,7 +118,7 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \tstruct cache_entry *ce;\n \tstruct string_list_item *item;\n \tstruct resolve_undo_info *ru;\n-\tint i, err = 0;\n+\tint i, err = 0, matched;\n \n \tif (!istate->resolve_undo)\n \t\treturn pos;\n@@ -137,6 +137,7 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \tru = item->util;\n \tif (!ru)\n \t\treturn pos;\n+\tmatched = ce->ce_flags & CE_MATCHED;\n \tremove_index_entry_at(istate, pos);\n \tfor (i = 0; i < 3; i++) {\n \t\tstruct cache_entry *nce;\n@@ -144,6 +145,8 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \t\t\tcontinue;\n \t\tnce = make_cache_entry(ru->mode[i], ru->sha1[i],\n \t\t\t\t       ce->name, i + 1, 0);\n+\t\tif (matched)\n+\t\t\tnce->ce_flags |= CE_MATCHED;\n \t\tif (add_index_entry(istate, nce, ADD_CACHE_OK_TO_ADD)) {\n \t\t\terr = 1;\n \t\t\terror(\"cannot unmerge '%s'\", ce->name);\n@@ -156,6 +159,20 @@ int unmerge_index_entry_at(struct index_state *istate, int pos)\n \treturn unmerge_index_entry_at(istate, pos);\n }\n \n+void unmerge_marked_index(struct index_state *istate)\n+{\n+\tint i;\n+\n+\tif (!istate->resolve_undo)\n+\t\treturn;\n+\n+\tfor (i = 0; i < istate->cache_nr; i++) {\n+\t\tstruct cache_entry *ce = istate->cache[i];\n+\t\tif (ce->ce_flags & CE_MATCHED)\n+\t\t\ti = unmerge_index_entry_at(istate, i);\n+\t}\n+}\n+\n void unmerge_index(struct index_state *istate, const char **pathspec)\n {\n \tint i;\ndiff --git a/resolve-undo.h b/resolve-undo.h\nindex 8458769..7a30206 100644\n--- a/resolve-undo.h\n+++ b/resolve-undo.h\n@@ -12,5 +12,6 @@ extern struct string_list *resolve_undo_read(const char *, unsigned long);\n extern void resolve_undo_clear_index(struct index_state *);\n extern int unmerge_index_entry_at(struct index_state *, int);\n extern void unmerge_index(struct index_state *, const char **);\n+extern void unmerge_marked_index(struct index_state *);\n \n #endif\ndiff --git a/t/t2022-checkout-paths.sh b/t/t2022-checkout-paths.sh\nindex 56090d2..5e01d58 100755\n--- a/t/t2022-checkout-paths.sh\n+++ b/t/t2022-checkout-paths.sh\n@@ -39,4 +39,25 @@ test_expect_success 'checking out paths out of a tree does not clobber unrelated\n \ttest_cmp expect.next2 dir/next2\n '\n \n+test_expect_success 'do not touch unmerged entries matching $path but not in $tree' '\n+\tgit checkout next &&\n+\tgit reset --hard &&\n+\n+\tcat dir/common >expect.common &&\n+\tEMPTY_SHA1=e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 &&\n+\tgit rm dir/next0 &&\n+\tcat >expect.next0<<EOF &&\n+100644 $EMPTY_SHA1 1\tdir/next0\n+100644 $EMPTY_SHA1 2\tdir/next0\n+EOF\n+\tgit update-index --index-info < expect.next0 &&\n+\n+\tgit checkout master dir &&\n+\n+\ttest_cmp expect.common dir/common &&\n+\ttest_path_is_file dir/master &&\n+\tgit diff --exit-code master dir/master &&\n+\tgit ls-files -s dir/next0 >actual.next0\n+'\n+\n test_done\n-- \n1.8.2.82.gc24b958\n"},{"id":"212592","messageId":"7vd2ujrw90.fsf@alter.siamese.dyndns.org","threadId":"33269","inReplyTo":"1364363901-17815-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH v3] checkout: avoid unnecessary match_pathspec calls","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-28T22:32:27Z","receivedAt":"2013-03-28T22:32:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:\n\n> diff --git a/t/t2022-checkout-paths.sh b/t/t2022-checkout-paths.sh\n> index 56090d2..5e01d58 100755\n> --- a/t/t2022-checkout-paths.sh\n> +++ b/t/t2022-checkout-paths.sh\n> @@ -39,4 +39,25 @@ test_expect_success 'checking out paths out of a tree does not clobber unrelated\n>  \ttest_cmp expect.next2 dir/next2\n>  '\n>  \n> +test_expect_success 'do not touch unmerged entries matching $path but not in $tree' '\n> +\tgit checkout next &&\n> +\tgit reset --hard &&\n> +\n> +\tcat dir/common >expect.common &&\n> +\tEMPTY_SHA1=e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 &&\n\n\tEMPTY_SHA1=$(git hash-object -w --stdin </dev/null)\n\n> +\tgit rm dir/next0 &&\n> +\tcat >expect.next0<<EOF &&\n> +100644 $EMPTY_SHA1 1\tdir/next0\n> +100644 $EMPTY_SHA1 2\tdir/next0\n> +EOF\n> +\tgit update-index --index-info < expect.next0 &&\n\n\tcat >expect.next0 <<-EOF &&\n        100644 $EMPTY_SHA1 1 dir/next0\n        100644 $EMPTY_SHA1 2 dir/next0\n\tEOF\n\tgit update-index --index-info <expect.next0 &&\n\n> +\n> +\tgit checkout master dir &&\n> +\n> +\ttest_cmp expect.common dir/common &&\n> +\ttest_path_is_file dir/master &&\n> +\tgit diff --exit-code master dir/master &&\n> +\tgit ls-files -s dir/next0 >actual.next0\n> +'\n\n... and actual.next0 is checked against what?\n\nEnding this test with\n\n\tgit ls-files -s dir/next0 >actual.next0 &&\n\ttest_cmp expect.next0 actual.next0\n\nwould be sufficient, methinks.\n\nWill replace v2 with the above fixups.  Thanks.\n\n> +\n>  test_done\n"}]}