{"thread":{"id":"33872","subject":"[RFC/PATCH] patch-ids: check modified paths before calculating diff","startedAt":"2013-05-19T13:17:35Z","lastAt":"2013-05-29T21:30:37Z","messageCount":13,"participants":["John Keeping","Jonathan Nieder","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"217908","messageId":"a7088a74742b71a01423f3ddc1a6c7fd89474ed8.1368969438.git.john@keeping.me.uk","threadId":"33872","inReplyTo":null,"subject":"[RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-19T13:17:35Z","receivedAt":"2013-05-19T13:17:35Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"When using \"git cherry\" or \"git log --cherry-pick\" we often have a small\nnumber of commits on one side and a large number on the other.  In\nrevision.c::cherry_pick_list we store the patch IDs for the small side\nbefore comparing the large side to this.\n\nIn this case, it is likely that only a small number of paths are touched\nby the commits on the smaller side of the range and by storing these we\ncan ignore many commits on the other side before unpacking blobs and\ndiffing them.\n\nThis improves performance in every example I have tried (times are best\nof three, using git.git):\n\nBefore:\n$ time git log --cherry master...jk/submodule-subdirectory-ok >/dev/null\n\nreal    0m0.373s\nuser    0m0.341s\nsys     0m0.031s\n\nAfter:\n$ time git log --cherry master...jk/submodule-subdirectory-ok >/dev/null\n\nreal    0m0.060s\nuser    0m0.055s\nsys     0m0.005s\n\nBefore:\n$ time git log --cherry next...pu >/dev/null\n\nreal    0m0.661s\nuser    0m0.617s\nsys     0m0.044s\n\nAfter:\n$ time git log --cherry next...pu >/dev/null\n\nreal    0m0.509s\nuser    0m0.478s\nsys     0m0.030s\n\nSigned-off-by: John Keeping <john@keeping.me.uk>\n---\n patch-ids.c | 142 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n patch-ids.h |   3 ++\n 2 files changed, 145 insertions(+)\n\ndiff --git a/patch-ids.c b/patch-ids.c\nindex bc8a28f..912f40c 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -1,5 +1,6 @@\n #include \"cache.h\"\n #include \"diff.h\"\n+#include \"diffcore.h\"\n #include \"commit.h\"\n #include \"sha1-lookup.h\"\n #include \"patch-ids.h\"\n@@ -16,6 +17,137 @@ static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \treturn diff_flush_patch_id(options, sha1);\n }\n \n+struct collect_paths_info {\n+\tstruct string_list *paths;\n+\tint searching;\n+};\n+\n+static int collect_paths_recursive(int n, struct tree_desc *t,\n+\tconst char *base, struct pathspec *pathspec,\n+\tstruct collect_paths_info *data);\n+\n+static int same_entry(struct name_entry *a, struct name_entry *b)\n+{\n+\tif (!a->sha1 || !b->sha1)\n+\t\treturn a->sha1 == b->sha1;\n+\treturn\t!hashcmp(a->sha1, b->sha1) &&\n+\t\ta->mode == b->mode;\n+}\n+\n+static char *traverse_path(const struct traverse_info *info,\n+\t\tconst struct name_entry *n)\n+{\n+\tchar *path = xmalloc(traverse_path_len(info, n) + 1);\n+\treturn make_traverse_path(path, info, n);\n+}\n+\n+static int add_touched_path(struct collect_paths_info *info, const char *path)\n+{\n+\tif (info->searching) {\n+\t\tif (!string_list_has_string(info->paths, path))\n+\t\t\treturn -1;\n+\t}\n+\tstring_list_insert(info->paths, path);\n+\treturn 0;\n+}\n+\n+static inline const unsigned char *dir_sha1(struct name_entry *e)\n+{\n+\tif (S_ISDIR(e->mode))\n+\t\treturn e->sha1;\n+\treturn NULL;\n+}\n+\n+static int collect_touched_paths_cb(int n, unsigned long mask,\n+\t\tunsigned long dirmask, struct name_entry *entry,\n+\t\tstruct traverse_info *info)\n+{\n+\tstruct collect_paths_info *collect_info = info->data;\n+\tif (n == 1) {\n+\t\t/* We're handling a root commit - add all the paths. */\n+\t\tif (entry[0].sha1 && !S_ISDIR(entry[0].mode)) {\n+\t\t\tif (add_touched_path(collect_info, entry[0].path))\n+\t\t\t\treturn -1;\n+\t\t} else if (S_ISDIR(entry[0].mode)) {\n+\t\t\tchar *newbase = traverse_path(info, entry);\n+\t\t\tstruct tree_desc t[1];\n+\t\t\tvoid *buf0 = fill_tree_descriptor(t, entry[0].sha1);\n+\t\t\tint error = collect_paths_recursive(1, t, newbase,\n+\t\t\t\t\tinfo->pathspec, collect_info);\n+\t\t\tfree(buf0);\n+\t\t\tfree(newbase);\n+\t\t\tif (error < 0)\n+\t\t\t\treturn error;\n+\t\t}\n+\t\treturn mask;\n+\t}\n+\n+\tif (same_entry(entry+0, entry+1))\n+\t\treturn mask;\n+\n+\tif (entry[0].mode && !S_ISDIR(entry[0].mode))\n+\t\tif (add_touched_path(collect_info, entry[0].path))\n+\t\t\treturn -1;\n+\tif (entry[1].mode && !S_ISDIR(entry[1].mode))\n+\t\tif (add_touched_path(collect_info, entry[1].path))\n+\t\t\treturn -1;\n+\n+\tif ((entry[0].sha1 && S_ISDIR(entry[0].mode)) ||\n+\t    (entry[1].sha1 && S_ISDIR(entry[1].mode))) {\n+\t\tchar *newbase = traverse_path(info,\n+\t\t\t\tS_ISDIR(entry[0].mode) ? entry+0 : entry+1);\n+\t\tstruct tree_desc t[2];\n+\t\tvoid *buf0 = fill_tree_descriptor(t+0, dir_sha1(entry+0));\n+\t\tvoid *buf1 = fill_tree_descriptor(t+1, dir_sha1(entry+1));\n+\t\tint error = collect_paths_recursive(2, t, newbase,\n+\t\t\t\tinfo->pathspec, collect_info);\n+\t\tfree(buf0);\n+\t\tfree(buf1);\n+\t\tfree(newbase);\n+\t\tif (error < 0)\n+\t\t\treturn error;\n+\t}\n+\n+\treturn mask;\n+}\n+\n+static int collect_paths_recursive(int n, struct tree_desc *t,\n+\t\tconst char *base, struct pathspec *pathspec,\n+\t\tstruct collect_paths_info *data)\n+{\n+\tstruct traverse_info info;\n+\n+\tsetup_traverse_info(&info, base);\n+\tinfo.data = data;\n+\tinfo.fn = collect_touched_paths_cb;\n+\tinfo.pathspec = pathspec;\n+\n+\treturn traverse_trees(n, t, &info);\n+}\n+\n+static int collect_touched_paths(struct commit *commit, struct patch_ids *ids,\n+\t\tint searching)\n+{\n+\tstruct tree_desc trees[2];\n+\tstruct collect_paths_info info = { &ids->touched_paths, searching };\n+\tvoid *commitbuf;\n+\tint result;\n+\n+\tcommitbuf = fill_tree_descriptor(trees + 1, commit->object.sha1);\n+\tif (commit->parents) {\n+\t\tvoid *parentbuf = fill_tree_descriptor(trees + 0,\n+\t\t\t\t\tcommit->parents->item->object.sha1);\n+\t\tresult = collect_paths_recursive(2, trees, \"\",\n+\t\t\t\t&ids->diffopts.pathspec, &info);\n+\t\tfree(parentbuf);\n+\t} else {\n+\t\tresult = collect_paths_recursive(1, trees + 1, \"\",\n+\t\t\t\t&ids->diffopts.pathspec, &info);\n+\t}\n+\tfree(commitbuf);\n+\treturn result;\n+}\n+\n static const unsigned char *patch_id_access(size_t index, void *table)\n {\n \tstruct patch_id **id_table = table;\n@@ -40,6 +172,7 @@ int init_patch_ids(struct patch_ids *ids)\n \tdiff_setup(&ids->diffopts);\n \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n \tdiff_setup_done(&ids->diffopts);\n+\tids->touched_paths.strdup_strings = 1;\n \treturn 0;\n }\n \n@@ -52,6 +185,8 @@ int free_patch_ids(struct patch_ids *ids)\n \t\tnext = patches->next;\n \t\tfree(patches);\n \t}\n+\n+\tstring_list_clear(&ids->touched_paths, 0);\n \treturn 0;\n }\n \n@@ -64,6 +199,13 @@ static struct patch_id *add_commit(struct commit *commit,\n \tunsigned char sha1[20];\n \tint pos;\n \n+\tif (no_add) {\n+\t\tif (collect_touched_paths(commit, ids, 1) < 0)\n+\t\t\treturn NULL;\n+\t} else {\n+\t\tcollect_touched_paths(commit, ids, 0);\n+\t}\n+\n \tif (commit_patch_id(commit, &ids->diffopts, sha1))\n \t\treturn NULL;\n \tpos = patch_pos(ids->table, ids->nr, sha1);\ndiff --git a/patch-ids.h b/patch-ids.h\nindex c8c7ca1..c90bec5 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -1,6 +1,8 @@\n #ifndef PATCH_IDS_H\n #define PATCH_IDS_H\n \n+#include \"string-list.h\"\n+\n struct patch_id {\n \tunsigned char patch_id[20];\n \tchar seen;\n@@ -8,6 +10,7 @@ struct patch_id {\n \n struct patch_ids {\n \tstruct diff_options diffopts;\n+\tstruct string_list touched_paths;\n \tint nr, alloc;\n \tstruct patch_id **table;\n \tstruct patch_id_bucket *patches;\n-- \n1.8.3.rc3.372.g721bad8\n"},{"id":"217926","messageId":"20130519193612.GH3362@elie.Belkin","threadId":"33872","inReplyTo":"a7088a74742b71a01423f3ddc1a6c7fd89474ed8.1368969438.git.john@keeping.me.uk","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2013-05-19T19:36:12Z","receivedAt":"2013-05-19T19:36:12Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"John Keeping wrote:\n\n> In this case, it is likely that only a small number of paths are touched\n> by the commits on the smaller side of the range and by storing these we\n> can ignore many commits on the other side before unpacking blobs and\n> diffing them.\n\nI like this idea a lot.\n\n> --- a/patch-ids.c\n> +++ b/patch-ids.c\n> @@ -1,5 +1,6 @@\n>  #include \"cache.h\"\n>  #include \"diff.h\"\n> +#include \"diffcore.h\"\n>  #include \"commit.h\"\n>  #include \"sha1-lookup.h\"\n>  #include \"patch-ids.h\"\n> @@ -16,6 +17,137 @@ static int commit_patch_id(struct commit *commit, struct diff_options *options,\n>  \treturn diff_flush_patch_id(options, sha1);\n>  }\n>  \n> +struct collect_paths_info {\n> +\tstruct string_list *paths;\n> +\tint searching;\n> +};\n> +\n> +static int collect_paths_recursive(int n, struct tree_desc *t,\n> +\tconst char *base, struct pathspec *pathspec,\n> +\tstruct collect_paths_info *data);\n\nCan you say a little about how this function works (e.g., in a\ncomment)?  What are the preconditions and postconditions?  How does\nthe state evolve (e.g, when is \"searching\" set)?\n\n> +\n> +static int same_entry(struct name_entry *a, struct name_entry *b)\n> +{\n> +\tif (!a->sha1 || !b->sha1)\n> +\t\treturn a->sha1 == b->sha1;\n> +\treturn\t!hashcmp(a->sha1, b->sha1) &&\n> +\t\ta->mode == b->mode;\n\nStyle: unusual whitespace (the tab after \"return\").  I'd just do\n\n\tif (!a->sha1 || ...)\n\t\treturn ...\n\treturn !hashcmp(a->sha1, b->sha1) && a->mode == b->mode;\n\nsince it is not too long.\n\n[...]\n> +static char *traverse_path(const struct traverse_info *info,\n> +\t\tconst struct name_entry *n)\n> +{\n> +\tchar *path = xmalloc(traverse_path_len(info, n) + 1);\n> +\treturn make_traverse_path(path, info, n);\n> +}\n\nThis function seems to be the same as one of the same name in\nbuiltin/merge-tree.c.  Should it be put somewhere more public, for\nexample as part of the tree-walk API?  Who is responsible for freeing\n\"path\"?  Would it make sense to use a strbuf here?\n\n\tstrbuf_setlen(&buf, traverse_path_len(info, n));\n\tmake_traverse_path(&buf.buf, info, n);\n\n> +\n> +static int add_touched_path(struct collect_paths_info *info, const char *path)\n> +{\n> +\tif (info->searching) {\n> +\t\tif (!string_list_has_string(info->paths, path))\n> +\t\t\treturn -1;\n> +\t}\n> +\tstring_list_insert(info->paths, path);\n> +\treturn 0;\n> +}\n\nSame question about internal API: when I see\n\n\tadd_touched_path(info, path)\n\nwhat should I expect it to do?\n\nIn the info->searching case, \"string_list_insert(info->paths, path)\"\nwill always be a no-op, right?  What does it mean that this is adding\na touched path in that case?\n\n[...]\n> +static int collect_touched_paths_cb(int n, unsigned long mask,\n> +\t\tunsigned long dirmask, struct name_entry *entry,\n> +\t\tstruct traverse_info *info)\n> +{\n\nSame question about contracts.  Ideally a reader in a rush should be\nable to read an opening comment about what the function does and\nthen return to the caller without delving into the details of how\nit does its work.\n\n> +\tstruct collect_paths_info *collect_info = info->data;\n> +\tif (n == 1) {\n> +\t\t/* We're handling a root commit - add all the paths. */\n[...]\n> +\tif ((entry[0].sha1 && S_ISDIR(entry[0].mode)) ||\n> +\t    (entry[1].sha1 && S_ISDIR(entry[1].mode))) {\n\nAt this point I'm not sure what two trees are being traversed in\nparallel, so it's not obvious to me what the code's about.  Are\nthey the \"before\" and \"after\" trees for commits being rebased?\n\n[...]\n> +static int collect_touched_paths(struct commit *commit, struct patch_ids *ids,\n> +\t\tint searching)\n> +{\n> +\tstruct tree_desc trees[2];\n> +\tstruct collect_paths_info info = { &ids->touched_paths, searching };\n> +\tvoid *commitbuf;\n> +\tint result;\n> +\n> +\tcommitbuf = fill_tree_descriptor(trees + 1, commit->object.sha1);\n> +\tif (commit->parents) {\n> +\t\tvoid *parentbuf = fill_tree_descriptor(trees + 0,\n> +\t\t\t\t\tcommit->parents->item->object.sha1);\n\nLooks like yes.\n\nWhat should happen for commits with more than 1 parent?  If they're\nsupposed to not enter this codepath because of a previous check, a\ndie(\"BUG: ...\") could be a good way to make reading easier.\n\n[...]\n> @@ -40,6 +172,7 @@ int init_patch_ids(struct patch_ids *ids)\n>  \tdiff_setup(&ids->diffopts);\n>  \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n>  \tdiff_setup_done(&ids->diffopts);\n> +\tids->touched_paths.strdup_strings = 1;\n\nGood.\n\n[...]\n> @@ -64,6 +199,13 @@ static struct patch_id *add_commit(struct commit *commit,\n>  \tunsigned char sha1[20];\n>  \tint pos;\n>  \n> +\tif (no_add) {\n> +\t\tif (collect_touched_paths(commit, ids, 1) < 0)\n> +\t\t\treturn NULL;\n\nAh, so this is what the \"searching\" does.\n\nThe existing \"no_add\" argument is very confusing (what does it mean to\nadd a commit without adding?), but at least the confusion is\nself-contained in a small, simple set of functions:\n\n\tstatic struct patch_id *add_commit(struct commit *commit,\n\t\t\t\t\t   struct patch_ids *ids,\n\t\t\t\t\t   int no_add)\n\t{\n\t\t...\n\t}\n\n\tstruct patch_id *has_commit_patch_id(struct commit *commit,\n\t\t\t\t\t     struct patch_ids *ids)\n\t{\n\t\treturn add_commit(commit, ids, 1);\n\t}\n\n\tstruct patch_id *add_commit_patch_id(struct commit *commit,\n\t\t\t\t\t     struct patch_ids *ids)\n\t{\n\t\treturn add_commit(commit, ids, 0);\n\t}\n\nIn fact the \"no_add\" makes *some* sense because add_commit() needs\nto search for a patch-id before adding it, so calling with no_add\nmeans to do all the work except for actually adding.\n\nThis new call propagates the mysterious boolean argument beyond\nthere and uses it in different ways.  Would it make sense to do\nthe following?\n\n (1) rename the \"no_add\" parameter to \"search_instead\" or something\n (2) avoid passing on \"no_add\" as a boolean.  Instead, use the\n     same trick elsewhere so this can use appropriately named\n     functions like:\n\n\tif (!searching)\n\t\tcollect_touched_paths(commit, ids);\n\telse if (!only_touches_touched_paths(commit, ids))\n\t\treturn NULL;\n\nHope that helps,\nJonathan\n"},{"id":"217948","messageId":"20130519220206.GK27005@serenity.lan","threadId":"33872","inReplyTo":"20130519193612.GH3362@elie.Belkin","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-19T22:02:06Z","receivedAt":"2013-05-19T22:02:06Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Sun, May 19, 2013 at 12:36:12PM -0700, Jonathan Nieder wrote:\n> John Keeping wrote:\n> \n> > In this case, it is likely that only a small number of paths are touched\n> > by the commits on the smaller side of the range and by storing these we\n> > can ignore many commits on the other side before unpacking blobs and\n> > diffing them.\n> \n> I like this idea a lot.\n> \n> > --- a/patch-ids.c\n> > +++ b/patch-ids.c\n> > @@ -1,5 +1,6 @@\n> >  #include \"cache.h\"\n> >  #include \"diff.h\"\n> > +#include \"diffcore.h\"\n> >  #include \"commit.h\"\n> >  #include \"sha1-lookup.h\"\n> >  #include \"patch-ids.h\"\n> > @@ -16,6 +17,137 @@ static int commit_patch_id(struct commit *commit, struct diff_options *options,\n> >  \treturn diff_flush_patch_id(options, sha1);\n> >  }\n> >  \n> > +struct collect_paths_info {\n> > +\tstruct string_list *paths;\n> > +\tint searching;\n> > +};\n> > +\n> > +static int collect_paths_recursive(int n, struct tree_desc *t,\n> > +\tconst char *base, struct pathspec *pathspec,\n> > +\tstruct collect_paths_info *data);\n> \n> Can you say a little about how this function works (e.g., in a\n> comment)?  What are the preconditions and postconditions?  How does\n> the state evolve (e.g, when is \"searching\" set)?\n\nAs you figure out below, the patch ID API has two modes, \"compute and\nstore\" and \"have we seen before\".  The \"searching\" flag passes this\ninformation down as we recursively compare the before and after trees\nfor a commit.  So when we hit a file that is changed by the commit we\neither add it to the list of touched paths or tests if it is in the list\nand stops comparing the trees if it isn't.\n\n> > +\n> > +static int same_entry(struct name_entry *a, struct name_entry *b)\n> > +{\n> > +\tif (!a->sha1 || !b->sha1)\n> > +\t\treturn a->sha1 == b->sha1;\n> > +\treturn\t!hashcmp(a->sha1, b->sha1) &&\n> > +\t\ta->mode == b->mode;\n> \n> Style: unusual whitespace (the tab after \"return\").  I'd just do\n> \n> \tif (!a->sha1 || ...)\n> \t\treturn ...\n> \treturn !hashcmp(a->sha1, b->sha1) && a->mode == b->mode;\n> \n> since it is not too long.\n\nMakes sense, I copied from the function of the same name in\nbuiltin/merge-tree.c, although I then changed the semantics for\nnon-existent entries.\n\n> [...]\n> > +static char *traverse_path(const struct traverse_info *info,\n> > +\t\tconst struct name_entry *n)\n> > +{\n> > +\tchar *path = xmalloc(traverse_path_len(info, n) + 1);\n> > +\treturn make_traverse_path(path, info, n);\n> > +}\n> \n> This function seems to be the same as one of the same name in\n> builtin/merge-tree.c.  Should it be put somewhere more public, for\n> example as part of the tree-walk API?  Who is responsible for freeing\n> \"path\"?  Would it make sense to use a strbuf here?\n> \n> \tstrbuf_setlen(&buf, traverse_path_len(info, n));\n> \tmake_traverse_path(&buf.buf, info, n);\n\nPerhaps alloc_traverse_path?  I'm not sure the strbuf buys us much for\nthis case, since we only use the result for a few lines before freeing\nit.\n\n> > +\n> > +static int add_touched_path(struct collect_paths_info *info, const char *path)\n> > +{\n> > +\tif (info->searching) {\n> > +\t\tif (!string_list_has_string(info->paths, path))\n> > +\t\t\treturn -1;\n> > +\t}\n> > +\tstring_list_insert(info->paths, path);\n> > +\treturn 0;\n> > +}\n> \n> Same question about internal API: when I see\n> \n> \tadd_touched_path(info, path)\n> \n> what should I expect it to do?\n\nYeah, this patch suffers a lot from writing separate \"collect\" and\n\"check\" codepaths and refactoring out common functionality later.\n\nPerhaps all of the collect_* functions should be changed_paths_* and\nthen this is \"process_changed_path\".\n\n> In the info->searching case, \"string_list_insert(info->paths, path)\"\n> will always be a no-op, right?  What does it mean that this is adding\n> a touched path in that case?\n> \n> [...]\n> > +static int collect_touched_paths_cb(int n, unsigned long mask,\n> > +\t\tunsigned long dirmask, struct name_entry *entry,\n> > +\t\tstruct traverse_info *info)\n> > +{\n> \n> Same question about contracts.  Ideally a reader in a rush should be\n> able to read an opening comment about what the function does and\n> then return to the caller without delving into the details of how\n> it does its work.\n> \n> > +\tstruct collect_paths_info *collect_info = info->data;\n> > +\tif (n == 1) {\n> > +\t\t/* We're handling a root commit - add all the paths. */\n> [...]\n> > +\tif ((entry[0].sha1 && S_ISDIR(entry[0].mode)) ||\n> > +\t    (entry[1].sha1 && S_ISDIR(entry[1].mode))) {\n> \n> At this point I'm not sure what two trees are being traversed in\n> parallel, so it's not obvious to me what the code's about.  Are\n> they the \"before\" and \"after\" trees for commits being rebased?\n> \n> [...]\n> > +static int collect_touched_paths(struct commit *commit, struct patch_ids *ids,\n> > +\t\tint searching)\n> > +{\n> > +\tstruct tree_desc trees[2];\n> > +\tstruct collect_paths_info info = { &ids->touched_paths, searching };\n> > +\tvoid *commitbuf;\n> > +\tint result;\n> > +\n> > +\tcommitbuf = fill_tree_descriptor(trees + 1, commit->object.sha1);\n> > +\tif (commit->parents) {\n> > +\t\tvoid *parentbuf = fill_tree_descriptor(trees + 0,\n> > +\t\t\t\t\tcommit->parents->item->object.sha1);\n> \n> Looks like yes.\n> \n> What should happen for commits with more than 1 parent?  If they're\n> supposed to not enter this codepath because of a previous check, a\n> die(\"BUG: ...\") could be a good way to make reading easier.\n\nCurrently the patch ID code compares the commit with its first parent,\nso I think this should do the same.  I posted about this in relation to\nrevision.c earlier [1].\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/224884\n\n> [...]\n> > @@ -40,6 +172,7 @@ int init_patch_ids(struct patch_ids *ids)\n> >  \tdiff_setup(&ids->diffopts);\n> >  \tDIFF_OPT_SET(&ids->diffopts, RECURSIVE);\n> >  \tdiff_setup_done(&ids->diffopts);\n> > +\tids->touched_paths.strdup_strings = 1;\n> \n> Good.\n> \n> [...]\n> > @@ -64,6 +199,13 @@ static struct patch_id *add_commit(struct commit *commit,\n> >  \tunsigned char sha1[20];\n> >  \tint pos;\n> >  \n> > +\tif (no_add) {\n> > +\t\tif (collect_touched_paths(commit, ids, 1) < 0)\n> > +\t\t\treturn NULL;\n> \n> Ah, so this is what the \"searching\" does.\n> \n> The existing \"no_add\" argument is very confusing (what does it mean to\n> add a commit without adding?), but at least the confusion is\n> self-contained in a small, simple set of functions:\n> \n> \tstatic struct patch_id *add_commit(struct commit *commit,\n> \t\t\t\t\t   struct patch_ids *ids,\n> \t\t\t\t\t   int no_add)\n> \t{\n> \t\t...\n> \t}\n> \n> \tstruct patch_id *has_commit_patch_id(struct commit *commit,\n> \t\t\t\t\t     struct patch_ids *ids)\n> \t{\n> \t\treturn add_commit(commit, ids, 1);\n> \t}\n> \n> \tstruct patch_id *add_commit_patch_id(struct commit *commit,\n> \t\t\t\t\t     struct patch_ids *ids)\n> \t{\n> \t\treturn add_commit(commit, ids, 0);\n> \t}\n> \n> In fact the \"no_add\" makes *some* sense because add_commit() needs\n> to search for a patch-id before adding it, so calling with no_add\n> means to do all the work except for actually adding.\n> \n> This new call propagates the mysterious boolean argument beyond\n> there and uses it in different ways.  Would it make sense to do\n> the following?\n> \n>  (1) rename the \"no_add\" parameter to \"search_instead\" or something\n>  (2) avoid passing on \"no_add\" as a boolean.  Instead, use the\n>      same trick elsewhere so this can use appropriately named\n>      functions like:\n> \n> \tif (!searching)\n> \t\tcollect_touched_paths(commit, ids);\n> \telse if (!only_touches_touched_paths(commit, ids))\n> \t\treturn NULL;\n\nSeems reasonable.\n\nThanks for the review.\n"},{"id":"217956","messageId":"7vwqquw958.fsf@alter.siamese.dyndns.org","threadId":"33872","inReplyTo":"20130519193612.GH3362@elie.Belkin","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-20T04:46:43Z","receivedAt":"2013-05-20T04:46:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Nieder <jrnieder@gmail.com> writes:\n\n>> @@ -64,6 +199,13 @@ static struct patch_id *add_commit(struct commit *commit,\n>>  \tunsigned char sha1[20];\n>>  \tint pos;\n>>  \n>> +\tif (no_add) {\n>> +\t\tif (collect_touched_paths(commit, ids, 1) < 0)\n>> +\t\t\treturn NULL;\n>\n> Ah, so this is what the \"searching\" does.\n>\n> The existing \"no_add\" argument is very confusing (what does it mean to\n> add a commit without adding?),\n\nSuch a mode of operation is usually called \"dry-run\", no?\n"},{"id":"217961","messageId":"20130520063623.GB2919@elie.Belkin","threadId":"33872","inReplyTo":"20130519220206.GK27005@serenity.lan","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2013-05-20T06:36:23Z","receivedAt":"2013-05-20T06:36:23Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"John Keeping wrote:\n> On Sun, May 19, 2013 at 12:36:12PM -0700, Jonathan Nieder wrote:\n\n>>                                        Who is responsible for freeing\n>> \"path\"?  Would it make sense to use a strbuf here?\n>>\n>> \tstrbuf_setlen(&buf, traverse_path_len(info, n));\n>> \tmake_traverse_path(&buf.buf, info, n);\n>\n> Perhaps alloc_traverse_path?  I'm not sure the strbuf buys us much for\n> this case, since we only use the result for a few lines before freeing\n> it.\n\nGood idea.  Generally strbufs are nice for this kind of thing because\nthey make it easy to reuse buffers, but in this case there's no\nopportunity for that.\n\n[...]\n> then this is \"process_changed_path\".\n\nSounds good.\n\n[...]\n>> What should happen for commits with more than 1 parent?  If they're\n>> supposed to not enter this codepath because of a previous check, a\n>> die(\"BUG: ...\") could be a good way to make reading easier.\n>\n> Currently the patch ID code compares the commit with its first parent,\n> so I think this should do the same.\n\nOk.  I guess a comment nearby would help future readers avoid the same\nquestion.\n\nI don't know what it should mean to try to use --cherry without\n--no-merges or --first-parent, so I guess this is harmless.\n\n[...]\n> Thanks for the review.\n\nNo problem.  Thanks for a pleasant read.\n\nCiao,\nJonathan\n"},{"id":"217964","messageId":"20130520081638.GL27005@serenity.lan","threadId":"33872","inReplyTo":"20130520063623.GB2919@elie.Belkin","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-20T08:16:38Z","receivedAt":"2013-05-20T08:16:38Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Sun, May 19, 2013 at 11:36:23PM -0700, Jonathan Nieder wrote:\n> I don't know what it should mean to try to use --cherry without\n> --no-merges or --first-parent, so I guess this is harmless.\n\nCurrently --no-merges doesn't actually get passed down this far.  We do\nthe patch ID calculations without taking that into account.\n"},{"id":"218763","messageId":"20130529062007.GA11955@sigill.intra.peff.net","threadId":"33872","inReplyTo":"a7088a74742b71a01423f3ddc1a6c7fd89474ed8.1368969438.git.john@keeping.me.uk","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-29T06:20:07Z","receivedAt":"2013-05-29T06:20:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, May 19, 2013 at 02:17:35PM +0100, John Keeping wrote:\n\n> When using \"git cherry\" or \"git log --cherry-pick\" we often have a small\n> number of commits on one side and a large number on the other.  In\n> revision.c::cherry_pick_list we store the patch IDs for the small side\n> before comparing the large side to this.\n> \n> In this case, it is likely that only a small number of paths are touched\n> by the commits on the smaller side of the range and by storing these we\n> can ignore many commits on the other side before unpacking blobs and\n> diffing them.\n\nThere are two observations that make your scheme work:\n\n  1. For something like --cherry-pick, we do not even care about the\n     actual patch-ids, only whether there are matches from the left and\n     right sides.\n\n  2. Comparing the sets of paths touched by two commits is often\n     sufficient to realize they do not have the same patch-ids.\n\nBut I think those observations mean we can do even better than\ncalculating the real patch-id for the small side at all.\n\nImagine we have both \"loose\" and \"strict\" patch-ids, where the loose one\nis much faster to compute, and has that property that a match _might_\nmean we have the same strict patch-id, but a non-match means we\ndefinitely do not have the same strict patch-id.\n\nI think such a loose patch-id could just be a hash of the filenames that\nwere changed by the patch (e.g., the first 32-bits of the sha1 of the\nconcatenated filenames). Computing that should be about as expensive as\na tree-diff. Per observation 2 above, if two commits do not have the\nsame loose id, we know that they cannot possibly have the same strict\nid.\n\nThen we can forget about the smaller-side and bigger-side entirely, and\njust do something like:\n\n  1. Make a sorted list (or hash table) of loose ids for one side.\n\n  2. For each commit on the other side, calculate its loose id and look\n     that up in the sorted list. If no hits, we know that there is no\n     match. For any hits, lazily calculate (and cache) the strict patch\n     id for both sides and compare as usual.\n\nIn the best case, we compute no patch-ids at all. And even for the\naverage case, I'd expect our lazy calculation to only have to compute a\nhandful of ids.\n\n-Peff\n"},{"id":"218777","messageId":"20130529072225.GB11955@sigill.intra.peff.net","threadId":"33872","inReplyTo":"20130529062007.GA11955@sigill.intra.peff.net","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-29T07:22:25Z","receivedAt":"2013-05-29T07:22:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 29, 2013 at 02:20:07AM -0400, Jeff King wrote:\n\n> In the best case, we compute no patch-ids at all. And even for the\n> average case, I'd expect our lazy calculation to only have to compute a\n> handful of ids.\n\nHere is a not-well-tested version of the idea. I tried to contain the\nchanges to patch-ids.c, though we may also be able to simplify the\n--cherry code, too.\n\nHere are my timings compared to stock git and to yours\n(all are best-of-five, \"git log --cherry $revs\"):\n\n  revs=origin/master...origin/jk/submodule-subdirectory-ok\n        stock    |    you   |    me\n        -------------------------------\n  real  0m0.501s | 0m0.078s | 0m0.098s\n  user  0m0.480s | 0m0.056s | 0m0.084s\n  sys   0m0.016s | 0m0.020s | 0m0.012s\n\n  revs=origin/next...origin/pu\n        stock    |    you   |    me\n        -------------------------------\n  real  0m0.857s | 0m0.847s | 0m0.519s\n  user  0m0.828s | 0m0.812s | 0m0.488s\n  sys   0m0.024s | 0m0.028s | 0m0.024s\n\nSo it performs slightly less well on the small case, and a bit better on\nthe large case. I think part of the problem is that when we do have a\n\"loose\" hit, we end up re-doing the tree diff to find the strict, which\ninvolves re-inflating the trees. It's unavoidable for the lazy entries\nunless we want to cache the whole diff_queued_diff, but for the non-lazy\nentries we should be able to do the strict patch-id incrementally. We\njust need to improve the function interfaces.\n\n---\n diff.c      |  15 ++++-\n diff.h      |   2 +-\n patch-ids.c | 117 +++++++++++++++++++----------------\n patch-ids.h |  11 ++--\n 4 files changed, 82 insertions(+), 63 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex f0b3e7c..3b55788 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4233,7 +4233,8 @@ static void patch_id_consume(void *priv, char *line, unsigned long len)\n }\n \n /* returns 0 upon success, and writes result into sha1 */\n-static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n+static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1,\n+\t\t\t     int loose)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tint i;\n@@ -4266,6 +4267,12 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n \t\tif (DIFF_PAIR_UNMERGED(p))\n \t\t\tcontinue;\n \n+\t\tif (loose) {\n+\t\t\tgit_SHA1_Update(&ctx, p->one->path, strlen(p->one->path));\n+\t\t\tgit_SHA1_Update(&ctx, p->two->path, strlen(p->two->path));\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\tdiff_fill_sha1_info(p->one);\n \t\tdiff_fill_sha1_info(p->two);\n \t\tif (fill_mmfile(&mf1, p->one) < 0 ||\n@@ -4323,11 +4330,13 @@ int diff_flush_patch_id(struct diff_options *options, unsigned char *sha1)\n \treturn 0;\n }\n \n-int diff_flush_patch_id(struct diff_options *options, unsigned char *sha1)\n+int diff_flush_patch_id(struct diff_options *options,\n+\t\t\tunsigned char *sha1,\n+\t\t\tint loose)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tint i;\n-\tint result = diff_get_patch_id(options, sha1);\n+\tint result = diff_get_patch_id(options, sha1, loose);\n \n \tfor (i = 0; i < q->nr; i++)\n \t\tdiff_free_filepair(q->queue[i]);\ndiff --git a/diff.h b/diff.h\nindex 78b4091..b018aaf 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -320,7 +320,7 @@ extern int do_diff_cache(const unsigned char *, struct diff_options *);\n extern int run_diff_index(struct rev_info *revs, int cached);\n \n extern int do_diff_cache(const unsigned char *, struct diff_options *);\n-extern int diff_flush_patch_id(struct diff_options *, unsigned char *);\n+extern int diff_flush_patch_id(struct diff_options *, unsigned char *, int loose);\n \n extern int diff_result_code(struct diff_options *, int);\n \ndiff --git a/patch-ids.c b/patch-ids.c\nindex bc8a28f..3a83ee6 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -5,7 +5,7 @@ static int commit_patch_id(struct commit *commit, struct diff_options *options,\n #include \"patch-ids.h\"\n \n static int commit_patch_id(struct commit *commit, struct diff_options *options,\n-\t\t    unsigned char *sha1)\n+\t\t\t   unsigned char *sha1, int loose)\n {\n \tif (commit->parents)\n \t\tdiff_tree_sha1(commit->parents->item->object.sha1,\n@@ -13,27 +13,9 @@ static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \telse\n \t\tdiff_root_tree_sha1(commit->object.sha1, \"\", options);\n \tdiffcore_std(options);\n-\treturn diff_flush_patch_id(options, sha1);\n+\treturn diff_flush_patch_id(options, sha1, loose);\n }\n \n-static const unsigned char *patch_id_access(size_t index, void *table)\n-{\n-\tstruct patch_id **id_table = table;\n-\treturn id_table[index]->patch_id;\n-}\n-\n-static int patch_pos(struct patch_id **table, int nr, const unsigned char *id)\n-{\n-\treturn sha1_pos(id, table, nr, patch_id_access);\n-}\n-\n-#define BUCKET_SIZE 190 /* 190 * 21 = 3990, with slop close enough to 4K */\n-struct patch_id_bucket {\n-\tstruct patch_id_bucket *next;\n-\tint nr;\n-\tstruct patch_id bucket[BUCKET_SIZE];\n-};\n-\n int init_patch_ids(struct patch_ids *ids)\n {\n \tmemset(ids, 0, sizeof(*ids));\n@@ -43,56 +25,83 @@ static struct patch_id *add_commit(struct commit *commit,\n \treturn 0;\n }\n \n+static int free_each_patch_id(void *patch_id, void *data)\n+{\n+\tfree(patch_id);\n+\treturn 0;\n+}\n+\n int free_patch_ids(struct patch_ids *ids)\n {\n-\tstruct patch_id_bucket *next, *patches;\n-\n-\tfree(ids->table);\n-\tfor (patches = ids->patches; patches; patches = next) {\n-\t\tnext = patches->next;\n-\t\tfree(patches);\n-\t}\n+\tfor_each_hash(&ids->table, free_each_patch_id, NULL);\n+\tfree_hash(&ids->table);\n \treturn 0;\n }\n \n+static inline unsigned long hash_sha1(const unsigned char *sha1)\n+{\n+\tunsigned int hash;\n+\tmemcpy(&hash, sha1, sizeof(hash));\n+\treturn hash;\n+}\n+\n static struct patch_id *add_commit(struct commit *commit,\n \t\t\t\t   struct patch_ids *ids,\n \t\t\t\t   int no_add)\n {\n-\tstruct patch_id_bucket *bucket;\n-\tstruct patch_id *ent;\n-\tunsigned char sha1[20];\n-\tint pos;\n+\tstruct patch_id *p;\n+\tunsigned char loose[20], strict[20];\n+\tunsigned long hash;\n+\tvoid **pos;\n \n-\tif (commit_patch_id(commit, &ids->diffopts, sha1))\n+\tif (commit_patch_id(commit, &ids->diffopts, loose, 1))\n \t\treturn NULL;\n-\tpos = patch_pos(ids->table, ids->nr, sha1);\n-\tif (0 <= pos)\n-\t\treturn ids->table[pos];\n+\thash = hash_sha1(loose);\n+\n+\tp = lookup_hash(hash, &ids->table);\n+\tfor (; p; p = p->next) {\n+\t\t/* Skip collisions from our reduced hash. */\n+\t\tif (hashcmp(loose, p->loose))\n+\t\t    continue;\n+\n+\t\t/*\n+\t\t * We have a real loose match; lazily load and cache the strict\n+\t\t * id to compare.\n+\t\t */\n+\t\tif (is_null_sha1(p->strict)) {\n+\t\t\tif (commit_patch_id(p->commit, &ids->diffopts,\n+\t\t\t\t\t    p->strict, 0))\n+\t\t\t\treturn NULL;\n+\t\t}\n+\t\tif (commit_patch_id(commit, &ids->diffopts, strict, 0))\n+\t\t\treturn NULL;\n+\n+\t\t/*\n+\t\t * If the strict ones match, we do not need to look farther;\n+\t\t * the patch-id is here.\n+\t\t */\n+\t\tif (!hashcmp(strict, p->strict))\n+\t\t\treturn p;\n+\t}\n+\n+\t/*\n+\t * Otherwise, we may have a loose but not strict match, or even no\n+\t * loose match at all. Now we can add the new entry (or return failure\n+\t * to look it up).\n+\t */\n \tif (no_add)\n \t\treturn NULL;\n \n-\tpos = -1 - pos;\n+\tp = xcalloc(1, sizeof(*p));\n+\tp->commit = commit;\n+\thashcpy(p->loose, loose);\n \n-\tbucket = ids->patches;\n-\tif (!bucket || (BUCKET_SIZE <= bucket->nr)) {\n-\t\tbucket = xcalloc(1, sizeof(*bucket));\n-\t\tbucket->next = ids->patches;\n-\t\tids->patches = bucket;\n+\tpos = insert_hash(hash, p, &ids->table);\n+\tif (pos) {\n+\t\tp->next = *pos;\n+\t\t*pos = p;\n \t}\n-\tent = &bucket->bucket[bucket->nr++];\n-\thashcpy(ent->patch_id, sha1);\n-\n-\tif (ids->alloc <= ids->nr) {\n-\t\tids->alloc = alloc_nr(ids->nr);\n-\t\tids->table = xrealloc(ids->table, sizeof(ent) * ids->alloc);\n-\t}\n-\tif (pos < ids->nr)\n-\t\tmemmove(ids->table + pos + 1, ids->table + pos,\n-\t\t\tsizeof(ent) * (ids->nr - pos));\n-\tids->nr++;\n-\tids->table[pos] = ent;\n-\treturn ids->table[pos];\n+\treturn p;\n }\n \n struct patch_id *has_commit_patch_id(struct commit *commit,\ndiff --git a/patch-ids.h b/patch-ids.h\nindex c8c7ca1..c40ff39 100644\n--- a/patch-ids.h\n+++ b/patch-ids.h\n@@ -2,15 +2,16 @@ struct patch_ids {\n #define PATCH_IDS_H\n \n struct patch_id {\n-\tunsigned char patch_id[20];\n-\tchar seen;\n+\tstruct commit *commit;\n+\tunsigned char loose[20];\n+\tunsigned char strict[20];\n+\tunsigned seen:1;\n+\tstruct patch_id *next;\n };\n \n struct patch_ids {\n \tstruct diff_options diffopts;\n-\tint nr, alloc;\n-\tstruct patch_id **table;\n-\tstruct patch_id_bucket *patches;\n+\tstruct hash_table table;\n };\n \n int init_patch_ids(struct patch_ids *);\n"},{"id":"218781","messageId":"20130529075020.GC11955@sigill.intra.peff.net","threadId":"33872","inReplyTo":"20130529072225.GB11955@sigill.intra.peff.net","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-29T07:50:20Z","receivedAt":"2013-05-29T07:50:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 29, 2013 at 03:22:25AM -0400, Jeff King wrote:\n\n>   revs=origin/master...origin/jk/submodule-subdirectory-ok\n>         stock    |    you   |    me\n>         -------------------------------\n>   real  0m0.501s | 0m0.078s | 0m0.098s\n>   user  0m0.480s | 0m0.056s | 0m0.084s\n>   sys   0m0.016s | 0m0.020s | 0m0.012s\n> \n>   revs=origin/next...origin/pu\n>         stock    |    you   |    me\n>         -------------------------------\n>   real  0m0.857s | 0m0.847s | 0m0.519s\n>   user  0m0.828s | 0m0.812s | 0m0.488s\n>   sys   0m0.024s | 0m0.028s | 0m0.024s\n> \n> So it performs slightly less well on the small case, and a bit better on\n> the large case. I think part of the problem is that when we do have a\n> \"loose\" hit, we end up re-doing the tree diff to find the strict, which\n> involves re-inflating the trees. It's unavoidable for the lazy entries\n> unless we want to cache the whole diff_queued_diff, but for the non-lazy\n> entries we should be able to do the strict patch-id incrementally. We\n> just need to improve the function interfaces.\n\nThe (somewhat hacky) patch below, on top of my previous one, does that\noptimization.  But the timings aren't improved by much. My best-of-five\nfor the second case went down to:\n\n  real    0m0.495s\n  user    0m0.488s\n  sys     0m0.004s\n\nHowever, the actual time to just do \"git log --raw $revs\" is:\n\n  real    0m0.333s\n  user    0m0.292s\n  sys     0m0.032s\n\nwhich provides a lower-bound for how well we can do, as it is just doing\na single tree diff for each commit. So I think we have reaped most of\nthe benefits of this approach already (and we will generally have to do\n_some_ true patch-id calculations, so we can never meet that lower\nbound).\n\n---\n diff.c      | 11 +++-------\n diff.h      |  3 ++-\n patch-ids.c | 39 ++++++++++++++++++++++++++---------\n 3 files changed, 34 insertions(+), 19 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 3b55788..161c5bf 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4233,8 +4233,8 @@ static void patch_id_consume(void *priv, char *line, unsigned long len)\n }\n \n /* returns 0 upon success, and writes result into sha1 */\n-static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1,\n-\t\t\t     int loose)\n+int diff_get_patch_id(struct diff_options *options, unsigned char *sha1,\n+\t\t      int loose)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tint i;\n@@ -4330,21 +4330,16 @@ int diff_flush_patch_id(struct diff_options *options,\n \treturn 0;\n }\n \n-int diff_flush_patch_id(struct diff_options *options,\n-\t\t\tunsigned char *sha1,\n-\t\t\tint loose)\n+void diff_queue_clear(void)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tint i;\n-\tint result = diff_get_patch_id(options, sha1, loose);\n \n \tfor (i = 0; i < q->nr; i++)\n \t\tdiff_free_filepair(q->queue[i]);\n \n \tfree(q->queue);\n \tDIFF_QUEUE_CLEAR(q);\n-\n-\treturn result;\n }\n \n static int is_summary_empty(const struct diff_queue_struct *q)\ndiff --git a/diff.h b/diff.h\nindex b018aaf..7207d4b 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -320,7 +320,8 @@ extern int do_diff_cache(const unsigned char *, struct diff_options *);\n extern int run_diff_index(struct rev_info *revs, int cached);\n \n extern int do_diff_cache(const unsigned char *, struct diff_options *);\n-extern int diff_flush_patch_id(struct diff_options *, unsigned char *, int loose);\n+extern int diff_get_patch_id(struct diff_options *, unsigned char *, int loose);\n+extern void diff_queue_clear(void);\n \n extern int diff_result_code(struct diff_options *, int);\n \ndiff --git a/patch-ids.c b/patch-ids.c\nindex 3a83ee6..83cda92 100644\n--- a/patch-ids.c\n+++ b/patch-ids.c\n@@ -4,8 +4,7 @@\n #include \"sha1-lookup.h\"\n #include \"patch-ids.h\"\n \n-static int commit_patch_id(struct commit *commit, struct diff_options *options,\n-\t\t\t   unsigned char *sha1, int loose)\n+static void start_patch_id(struct commit *commit, struct diff_options *options)\n {\n \tif (commit->parents)\n \t\tdiff_tree_sha1(commit->parents->item->object.sha1,\n@@ -13,7 +12,6 @@ static int commit_patch_id(struct commit *commit, struct diff_options *options,\n \telse\n \t\tdiff_root_tree_sha1(commit->object.sha1, \"\", options);\n \tdiffcore_std(options);\n-\treturn diff_flush_patch_id(options, sha1, loose);\n }\n \n int init_patch_ids(struct patch_ids *ids)\n@@ -50,12 +48,16 @@ static struct patch_id *add_commit(struct commit *commit,\n \t\t\t\t   int no_add)\n {\n \tstruct patch_id *p;\n-\tunsigned char loose[20], strict[20];\n+\tunsigned char loose[20], strict[20] = {0};\n \tunsigned long hash;\n \tvoid **pos;\n \n-\tif (commit_patch_id(commit, &ids->diffopts, loose, 1))\n+\tstart_patch_id(commit, &ids->diffopts);\n+\tif (diff_get_patch_id(&ids->diffopts, loose, 1)) {\n+\t\tdiff_queue_clear();\n \t\treturn NULL;\n+\t}\n+\n \thash = hash_sha1(loose);\n \n \tp = lookup_hash(hash, &ids->table);\n@@ -66,15 +68,24 @@ static struct patch_id *add_commit(struct commit *commit,\n \n \t\t/*\n \t\t * We have a real loose match; lazily load and cache the strict\n-\t\t * id to compare.\n+\t\t * id to compare. We must do the \"current\" commit first, as its\n+\t\t * incremental state is waiting in the diff machinery.\n \t\t */\n+\t\tif (is_null_sha1(strict)) {\n+\t\t\tint result = diff_get_patch_id(&ids->diffopts, strict, 0);\n+\t\t\tdiff_queue_clear();\n+\t\t\tif (result)\n+\t\t\t\treturn NULL;\n+\t\t}\n+\n \t\tif (is_null_sha1(p->strict)) {\n-\t\t\tif (commit_patch_id(p->commit, &ids->diffopts,\n-\t\t\t\t\t    p->strict, 0))\n+\t\t\tint result;\n+\t\t\tstart_patch_id(p->commit, &ids->diffopts);\n+\t\t\tresult = diff_get_patch_id(&ids->diffopts, p->strict, 0);\n+\t\t\tdiff_queue_clear();\n+\t\t\tif (result)\n \t\t\t\treturn NULL;\n \t\t}\n-\t\tif (commit_patch_id(commit, &ids->diffopts, strict, 0))\n-\t\t\treturn NULL;\n \n \t\t/*\n \t\t * If the strict ones match, we do not need to look farther;\n@@ -85,6 +96,14 @@ static struct patch_id *add_commit(struct commit *commit,\n \t}\n \n \t/*\n+\t * If we get here and have not filled in strict, then we do not need\n+\t * to compute it (for now), but we must clean up the leftover diff\n+\t * state.\n+\t */\n+\tif (is_null_sha1(strict))\n+\t\tdiff_queue_clear();\n+\n+\t/*\n \t * Otherwise, we may have a loose but not strict match, or even no\n \t * loose match at all. Now we can add the new entry (or return failure\n \t * to look it up).\n"},{"id":"218868","messageId":"7vip21u09d.fsf@alter.siamese.dyndns.org","threadId":"33872","inReplyTo":"20130529062007.GA11955@sigill.intra.peff.net","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-29T18:08:46Z","receivedAt":"2013-05-29T18:08:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> I think such a loose patch-id could just be a hash of the filenames that\n> were changed by the patch (e.g., the first 32-bits of the sha1 of the\n> concatenated filenames). Computing that should be about as expensive as\n> a tree-diff. Per observation 2 above, if two commits do not have the\n> same loose id, we know that they cannot possibly have the same strict\n> id.\n\nBecause the \"strict\" one already hashes the filenames, if files that\nare touched by a patch is different from that of another patch, we\njudge them being different.\n\n> Then we can forget about the smaller-side and bigger-side entirely, and\n> just do something like:\n>\n>   1. Make a sorted list (or hash table) of loose ids for one side.\n>\n>   2. For each commit on the other side, calculate its loose id and look\n>      that up in the sorted list. If no hits, we know that there is no\n>      match. For any hits, lazily calculate (and cache) the strict patch\n>      id for both sides and compare as usual.\n>\n> In the best case, we compute no patch-ids at all. And even for the\n> average case, I'd expect our lazy calculation to only have to compute a\n> handful of ids.\n\nCorrect.\n\nThis has rather interesting ramifications on cherry-pick and rebase,\nthough.  Both command can handle changes that come from an old tree\nbefore some paths were renamed, but strict patch-id would not spot\nequivalent changes we already have in our history if our change\nhappened after a rename, i.e.\n\n   Z\n  /\n O---R---X---Y\n\nwhere Z updates path F, R moves F to G and X changes G the same way\nas Z changes F, and we are trying to cherry-pick Z on top of Y.  The\ncherry-pick filter will see different patch-id for Z and X.\n\nWe will likely to notice that \"patch already applied\" (if using am-3\nmachinery) or \"already up-to-date\" (if using merge machinery) even\nwhen we missed this equivalency and drop the duplicate from the\nresult, so it is not a big loss, but we might want to consider\nremoving the filename from patch-id computation, at least for the\nones we internally use and discard for revs->cherry_pick filtering.\n"},{"id":"218873","messageId":"20130529183658.GA15616@sigill.intra.peff.net","threadId":"33872","inReplyTo":"7vip21u09d.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-29T18:36:58Z","receivedAt":"2013-05-29T18:36:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 29, 2013 at 11:08:46AM -0700, Junio C Hamano wrote:\n\n> This has rather interesting ramifications on cherry-pick and rebase,\n> though.  Both command can handle changes that come from an old tree\n> before some paths were renamed, but strict patch-id would not spot\n> equivalent changes we already have in our history if our change\n> happened after a rename, i.e.\n> \n>    Z\n>   /\n>  O---R---X---Y\n> \n> where Z updates path F, R moves F to G and X changes G the same way\n> as Z changes F, and we are trying to cherry-pick Z on top of Y.  The\n> cherry-pick filter will see different patch-id for Z and X.\n\nTrue. That is a problem with the current patch-id system, no? Though my\nproposal would make it harder to change it in the future (as does\nJohn's).\n\nWith mine, I wonder if you could use a different \"loose\" definition that\ndoes not take the filenames into account.  Using something like the\nchanges in file sizes would be unique, but would not properly map to\nstrict cases (a patch-id that adds 5 lines to the end of a 100-byte file\nmay match one that adds the same five lines to the end of a 200-byte\nfile).\n\n-Peff\n"},{"id":"218876","messageId":"7vy5axsju2.fsf@alter.siamese.dyndns.org","threadId":"33872","inReplyTo":"20130529183658.GA15616@sigill.intra.peff.net","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-29T18:48:53Z","receivedAt":"2013-05-29T18:48:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Wed, May 29, 2013 at 11:08:46AM -0700, Junio C Hamano wrote:\n>\n>> This has rather interesting ramifications on cherry-pick and rebase,\n>> though.  Both command can handle changes that come from an old tree\n>> before some paths were renamed, but strict patch-id would not spot\n>> equivalent changes we already have in our history if our change\n>> happened after a rename, i.e.\n>> \n>>    Z\n>>   /\n>>  O---R---X---Y\n>> \n>> where Z updates path F, R moves F to G and X changes G the same way\n>> as Z changes F, and we are trying to cherry-pick Z on top of Y.  The\n>> cherry-pick filter will see different patch-id for Z and X.\n>\n> True. That is a problem with the current patch-id system, no?\n\nCorrect.  That is why I suggested not to change the external\ninterface (i.e. what is shown from patch-id command) as people may\nhave kept them, but wondered if a possible improvement may be to\nexclude the name from ids when we internally generate two sets of\nIds and intersect them, i.e. log --cherry.\n"},{"id":"218903","messageId":"20130529213037.GC17475@serenity.lan","threadId":"33872","inReplyTo":"7vy5axsju2.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH] patch-ids: check modified paths before calculating diff","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-05-29T21:30:37Z","receivedAt":"2013-05-29T21:30:37Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Wed, May 29, 2013 at 11:48:53AM -0700, Junio C Hamano wrote:\n> Jeff King <peff@peff.net> writes:\n> \n> > On Wed, May 29, 2013 at 11:08:46AM -0700, Junio C Hamano wrote:\n> >\n> >> This has rather interesting ramifications on cherry-pick and rebase,\n> >> though.  Both command can handle changes that come from an old tree\n> >> before some paths were renamed, but strict patch-id would not spot\n> >> equivalent changes we already have in our history if our change\n> >> happened after a rename, i.e.\n> >> \n> >>    Z\n> >>   /\n> >>  O---R---X---Y\n> >> \n> >> where Z updates path F, R moves F to G and X changes G the same way\n> >> as Z changes F, and we are trying to cherry-pick Z on top of Y.  The\n> >> cherry-pick filter will see different patch-id for Z and X.\n> >\n> > True. That is a problem with the current patch-id system, no?\n> \n> Correct.  That is why I suggested not to change the external\n> interface (i.e. what is shown from patch-id command) as people may\n> have kept them, but wondered if a possible improvement may be to\n> exclude the name from ids when we internally generate two sets of\n> Ids and intersect them, i.e. log --cherry.\n\nWould that not rely on the files still being in the same order?  Since\nwe essentially hash the content of the patch, it will presumably be\nquite different if the order of the files in the patch changes.\n\nI expect it's possible to work around that by being a bit more clever\nthough.  Perhaps hash each file individually and then sort those and\nhash the concatenated result?\n"}]}