{"thread":{"id":"35860","subject":"[PATCH 0/2] Multiparent diff tree-walker + combine-diff speedup","startedAt":"2014-02-13T14:02:53Z","lastAt":"2014-02-18T21:29:30Z","messageCount":10,"participants":["Kirill Smelkov","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"234728","messageId":"cover.1392299516.git.kirr@mns.spb.ru","threadId":"35860","inReplyTo":null,"subject":"[PATCH 0/2] Multiparent diff tree-walker + combine-diff speedup","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-13T14:02:53Z","receivedAt":"2014-02-13T14:02:53Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"Here go combine-diff speedup patches in form of first reworking diff\ntree-walker to work in general case - when a commit have several parents, not\nonly one - we are traversing all 1+nparent trees in parallel.\n\nThen we are taking advantage of the new diff tree-walker for speeding up\ncombine-diff, which for linux.git results in ~14 times speedup.\n\nI understand v1.9.0 is going to be released first, but wanted to finally send\nthe patches, so that people could start reviewing them.\n\nPlease apply on top of ks/tree-diff-more and thanks beforehand,\n\nKirill\n\n\n\nKirill Smelkov (2):\n tree-diff: rework diff_tree() to generate diffs for multiparent cases as well\n combine-diff: speed it up, by using multiparent diff tree-walker directly\n\n combine-diff.c | 85 +++++++++-\n diff.c | 2 +\n diff.h | 10 ++\n tree-diff.c | 501 +++++++++++++++++++++++++++++++++++++++++++++++++--------\n 4 files changed, 529 insertions(+), 69 deletions(-)\n\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234730","messageId":"1dd9ca564e00ef235875aae4944675f53dcd25a3.1392299516.git.kirr@mns.spb.ru","threadId":"35860","inReplyTo":"cover.1392299516.git.kirr@mns.spb.ru","subject":"[PATCH 1/2] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-13T14:02:54Z","receivedAt":"2014-02-13T14:02:54Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"Previously diff_tree(), which is now named __diff_tree_sha1(), was\ngenerating diff_filepair(s) for two trees t1 and t2, and that was\nusually used for a commit as t1=HEAD~, and t2=HEAD - i.e. to see changes\na commit introduces.\n\nIn Git, however, we have fundamentally built flexibility in that a\ncommit can have many parents - 1 for a plain commit, 2 for a simple merge,\nbut also more than 2 for merging several heads at once.\n\nFor merges there is a so called combine-diff, which shows diff, a merge\nintroduces by itself, omitting changes done by any parent. That works\nthrough first finding paths, that are different to all parents, and then\nshowing generalized diff, with separate columns for +/- for each parent.\nThe code lives in combine-diff.c .\n\nThere is an impedance mismatch, however, in that a commit could\ngenerally have any number of parents, and that while diffing trees, we\ndivide cases for 2-tree diffs and more-than-2-tree diffs. I mean there\nis no special casing for multiple parents commits in e.g.\nrevision-walker .\n\nThat impedance mismatch *hurts* *performance* *badly* for generating\ncombined diffs - in c839f1bd (combine-diff: optimize combine_diff_path\nsets intersection) I've already removed some slowness from it, but from\nthe timings provided there, it could be seen, that combined diffs still\ncost more than an order of magnitude more cpu time, compared to diff for\nusual commits, and that would only be an optimistic estimate, if we take\ninto account that for e.g. linux.git there is only one merge for several\ndozens of plain commits.\n\nThat slowness comes from the fact that currently, while generating\ncombined diff, a lot of time is spent computing diff(commit,commit^2)\njust to only then intersect that huge diff to almost small set of files\nfrom diff(commit,commit^1).\n\nThat's because at present, to compute combine-diff, for first finding\npaths, that \"every parent touches\", we use the following combine-diff\nproperty/definition:\n\nD(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn) (w.r.t. paths)\n\nwhere\n\nD(A,P1...Pn) is combined diff between commit A, and parents Pi\n\nand\n\nD(A,Pi) is usual two-tree diff Pi..A\n\nSo if any of that D(A,Pi) is huge, tracting 1 n-parent combine-diff as n\n1-parent diffs and intersecting results will be slow.\n\nAnd usually, for linux.git and other topic-based workflows, that\nD(A,P2) is huge, because, if merge-base of A and P2, is several dozens\nof merges (from A, via first parent) below, that D(A,P2) will be diffing\nsum of merges from several subsystems to 1 subsystem.\n\nThe solution is to avoid computing n 1-parent diffs, and to find\nchanged-to-all-parents paths via scanning A's and all Pi's trees\nsimultaneously, at each step comparing their entries, and based on that\ncomparison, populate paths result, and deduce we could *skip*\n*recursing* into subdirectories, if at least for 1 parent, sha1 of that\ndir tree is the same as in A. That would save us from doing significant\namount of needless work.\n\nSuch approach is very similar to what diff_tree() does, only there we\ndeal with scanning only 2 trees simultaneously, and for n+1 tree, the\nlogic is a bit more complex:\n\nD(A,X1...Xn) calculation scheme\n-------------------------------\n\nD(A,X1...Xn) = D(A,X1) ^ ... ^ D(A,Xn) (regarding resulting paths set)\n\n D(A,Xj) - diff between A..Xj\n D(A,X1...Xn) - combined diff from A to parents X1,...,Xn\n\nWe start from all trees, which are sorted, and compare their entries in\nlock-step:\n\n A X1 Xn\n - - -\n |a| |x1| |xn|\n |-| |--| ... |--| i = argmin(x1...xn)\n | | | | | |\n |-| |--| |--|\n |.| |. | |. |\n . . .\n . . .\n\nat any time there could be 3 cases:\n\n 1) a < xi;\n 2) a > xi;\n 3) a = xi.\n\nSchematic deduction of what every case means, and what to do, follows:\n\n1) a < xi -> ∀j a ∉ Xj -> \"+a\" ∈ D(A,Xj) -> D += \"+a\"; a↓\n\n2) a > xi\n\n 2.1) ∃j: xj > xi -> \"-xi\" ∉ D(A,Xj) -> D += ø; ∀ xk=xi xk↓\n 2.2) ∀j xj = xi -> xj ∉ A -> \"-xj\" ∈ D(A,Xj) -> D += \"-xi\"; ∀j xj↓\n\n3) a = xi\n\n 3.1) ∃j: xj > xi -> \"+a\" ∈ D(A,Xj) -> only xk=xi remains to investigate\n 3.2) xj = xi -> investigate δ(a,xj)\n |\n |\n v\n\n 3.1+3.2) looking at δ(a,xk) ∀k: xk=xi - if all != ø ->\n\n ⎧δ(a,xk) - if xk=xi\n -> D += ⎨\n ⎩\"+a\" - if xk>xi\n\n in any case a↓ ∀ xk=xi xk↓\n\n~\n\nFor comparison, here is how diff_tree() works:\n\nD(A,B) calculation scheme\n-------------------------\n\n A B\n - -\n |a| |b| a < b -> a ∉ B -> D(A,B) += +a a↓\n |-| |-| a > b -> b ∉ A -> D(A,B) += -b b↓\n | | | | a = b -> investigate δ(a,b) a↓ b↓\n |-| |-|\n |.| |.|\n . .\n . .\n\n~~~~~~~~\n\nThis patch generalizes diff tree-walker to work with arbitrary number of\nparents as described above - i.e. now there is a resulting tree t, and\nsome parents trees tp[i] i=[0..nparent). The generalization builds on\nthe fact that usual diff\n\nD(A,B)\n\nis by definition the same as combined diff\n\nD(A,[B]),\n\nso if we could rework the code for common case and make it be not slower\nfor nparent=1 case, usual diff(t1,t2) generation will not be slower, and\nmultiparent diff tree-walker would greatly benefit generating\ncombine-diff.\n\nWhat we do is as follows:\n\n1) diff tree-walker __diff_tree_sha1() is internally reworked to be\n a paths generator (new name diff_tree_paths()), with each generated path\n being `struct combine_diff_path` with info for path, new sha1,mode and for\n every parent which sha1,mode it was in it.\n\n2) From that info, we can still generate usual diff queue with\n struct diff_filepairs, via \"exporting\" generated\n combine_diff_path, if we know we run for nparent=1 case.\n (see emit_diff() which is now named emit_diff_p0only())\n\n3) In order for diff_can_quit_early(), which checks\n\n DIFF_OPT_TST(opt, HAS_CHANGES))\n\n to work, that exporting have to be happening not in bulk, but\n incrementally, one diff path at a time.\n\n For such consumers, there is a new callback in diff_options\n introduced:\n\n ->pathchange(opt, struct combine_diff_path *)\n\n which, if set to !NULL, is called for every generated path.\n\n (see new compat __diff_tree_sha1() wrapper around new paths\n generator for setup)\n\n4) The paths generation itself, is reworked from previous\n __diff_tree_sha1() code according to \"D(A,X1...Xn) calculation\n scheme\" provided above:\n\n On the start we allocate [nparent] arrays in place what was\n earlier just for one parent tree.\n\n then we just generalize loops, and comparison according to the\n algorithm.\n\nSome notes(*):\n\n1) For loops,\n\n i = 0; do { ... } while (++i < nparent);\n\nis used instead of\n\n for (i = 0; i < nparent; ++i)\n ...\n\nbecause for the former case, the compiler have to emit additional\nprologue code which checks for i >= nparent case before entering the\nloop.\n\nAs we require nparent must be >0, that additional overhead\nconflicts with the \"runs not slower for nparent=1 case than before\"\ngoal.\n\n2) alloca(), for small arrays, is used for the same reason - if we change\nit to xmalloc()/free() the timings get worse\n\n3) For every parent tree, we need to keep a tag, whether entry from that\nparent equals to entry from minimal parent. For performance reasons I'm\nkeeping that tag in entry's mode field in unused bit - see S_IFXMIN_NEQ.\n Not doing so, we'd need to alloca another [nparent] array, which hurts\n performance.\n\n4) For emitted paths, memory could be reused, if we know the path was\n processed via callback and will not be needed later. We efficient\n hand-made realloc-style __path_appendnew(), that saves us from ~1-1.5%\n of potential additional slowdown.\n\n5) goto(s) are used in several places, as the code executes a little bit\n faster with lowered register pressure.\n\nAlso\n\n- we should now check for FIND_COPIES_HARDER not only when two entries\n names are the same, and their hashes are equal, but also for a case,\n when a path was removed from some of all parents having it.\n\n The reason is, if we don't, that path won't be emitted at all (see\n \"a > xi\" case), and we'll just skip it, and FIND_COPIES_HARDER wants\n all paths - with diff or without - to be emitted, to be later analyzed\n for being copies sources.\n\n The new check is only necessary for nparent >1, as for nparent=1 case\n xmin_eqtotal always =1 =nparent, and a path is always added to diff as\n removal.\n\n~~~~~~~~\n\nTimings for\n\n # without -c, i.e. testing only nparent=1 case\n `git log --raw --no-abbrev --no-renames`\n\nbefore and after the patch are as follows:\n\n navy.git linux.git v3.10..v3.11\n\n before 0.611s 1.889s\n after 0.619s 1.907s\n slowdown 1.3% 0.9%\n\nThis timings show we did no harm to usual diff(tree1,tree2) generation.\nFrom the table we can see that we actually did ~1% slowdown, but I think\nI've \"earned\" that 1% in the previous patch (729f7e8e in pu) so for\nnparent=1 case, net timings stays approximately the same.\n\nThe output also stayed the same.\n\n(*) If we revert 1)-5) to more usual techniques, for nparent=1 case,\n we'll get ~2-2.5% of additional slowdown, which I've tried to avoid, as\n \"do no harm for nparent=1 case\" rule.\n\nFor linux.git, combined diff will run an order of magnitude faster and\nappropriate timings will be provided in the next commit, as we'll be\ntaking advantage of the new diff tree-walker for combined-diff\ngeneration there.\n\nP.S. and combined diff is not some exotic/for-play-only stuff - for\nexample for a program I write to represent Git archives as readonly\nfilesystem, there is initial scan with\n\n `git log --reverse --raw --no-abbrev --no-renames -c`\n\nto extract log of what was created/changed when, as a result building a\nmap\n\n {} sha1 -> in which commit (and date) a content was added\n\nthat `-c` means also show combined diff for merges, and without them, if\na merge is non-trivial (merges changes from two parents with both having\nseparate changes to a file), or an evil one, the map will not be full,\ni.e. some valid sha1 would be absent from it.\n\nThat case was my initial motivation for combined diffs speedup.\n\nSigned-off-by: Kirill Smelkov \n---\n diff.c | 1 +\n diff.h | 10 ++\n tree-diff.c | 501 ++++++++++++++++++++++++++++++++++++++++++++++++++++--------\n 3 files changed, 448 insertions(+), 64 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 8e4a6a9..cda4aa8 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3216,6 +3216,7 @@ void diff_setup(struct diff_options *options)\n \toptions->context = diff_context_default;\n \tDIFF_OPT_SET(options, RENAME_EMPTY);\n \n+\t/* pathchange left =NULL by default */\n \toptions->change = diff_change;\n \toptions->add_remove = diff_addremove;\n \toptions->use_color = diff_use_color_default;\ndiff --git a/diff.h b/diff.h\nindex bf834ff..b59e8d6 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -15,6 +15,10 @@ struct diff_filespec;\n struct userdiff_driver;\n struct sha1_array;\n struct commit;\n+struct combine_diff_path;\n+\n+typedef int (*pathchange_fn_t)(struct diff_options *options,\n+\t\t struct combine_diff_path *path);\n \n typedef void (*change_fn_t)(struct diff_options *options,\n \t\t unsigned old_mode, unsigned new_mode,\n@@ -157,6 +161,7 @@ struct diff_options {\n \tint close_file;\n \n \tstruct pathspec pathspec;\n+\tpathchange_fn_t pathchange;\n \tchange_fn_t change;\n \tadd_remove_fn_t add_remove;\n \tdiff_format_fn_t format_callback;\n@@ -189,6 +194,11 @@ const char *diff_line_prefix(struct diff_options *);\n \n extern const char mime_boundary_leader[];\n \n+extern\n+struct combine_diff_path *diff_tree_paths(\n+\tstruct combine_diff_path *p, const unsigned char *sha1,\n+\tconst unsigned char **parent_sha1, int nparent,\n+\tstruct strbuf *base, struct diff_options *opt);\n extern int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,\n \t\t\t struct strbuf *base, struct diff_options *opt);\n extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,\ndiff --git a/tree-diff.c b/tree-diff.c\nindex ab61a0a..92d4087 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -7,6 +7,25 @@\n #include \"tree.h\"\n \n /*\n+ * internal mode marker, saying a tree entry != entry of tp[imin]\n+ * (see __diff_tree_paths for what it means there)\n+ *\n+ * it *must* not overlap with any valid modes, and we will update/use/emit\n+ * entry for diff only with it unset. Only non-overlapping to valid modes is\n+ * required, because mode in tree_desc, comes here canonicalized via\n+ * canon_mode().\n+ *\n+ * the definition assumes unsigned is at least 32 bits.\n+ */\n+#define S_IFXMIN_NEQ\t0x80000000\n+\n+\n+static struct combine_diff_path *__diff_tree_paths(\n+\tstruct combine_diff_path *p, const unsigned char *sha1,\n+\tconst unsigned char **parents_sha1, int nparent,\n+\tstruct strbuf *base, struct diff_options *opt);\n+\n+/*\n * Compare two tree entries, taking into account only path/S_ISDIR(mode),\n * but not their sha1's.\n *\n@@ -33,72 +52,148 @@ static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)\n }\n \n \n-/* convert path, t1/t2 -> opt->diff_*() callbacks */\n-static void emit_diff(struct diff_options *opt, struct strbuf *path,\n-\t\t struct tree_desc *t1, struct tree_desc *t2)\n+/* convert path -> opt->diff_*() callbacks\n+ *\n+ * emits diff to parent0 only.\n+ */\n+static int emit_diff_p0only(struct diff_options *opt, struct combine_diff_path *p)\n {\n-\tunsigned int mode1 = t1 ? t1->entry.mode : 0;\n-\tunsigned int mode2 = t2 ? t2->entry.mode : 0;\n-\n-\tif (mode1 && mode2) {\n-\t\topt->change(opt, mode1, mode2, t1->entry.sha1, t2->entry.sha1,\n-\t\t\t1, 1, path->buf, 0, 0);\n+\tstruct combine_diff_parent *p0 = &p->parent[0];\n+\tif (p->mode && p0->mode) {\n+\t\topt->change(opt, p0->mode, p->mode, p0->sha1, p->sha1,\n+\t\t\t1, 1, p->path, 0, 0);\n \t}\n \telse {\n \t\tconst unsigned char *sha1;\n \t\tunsigned int mode;\n \t\tint addremove;\n \n-\t\tif (mode2) {\n+\t\tif (p->mode) {\n \t\t\taddremove = '+';\n-\t\t\tsha1 = t2->entry.sha1;\n-\t\t\tmode = mode2;\n+\t\t\tsha1 = p->sha1;\n+\t\t\tmode = p->mode;\n \t\t}\n \t\telse {\n \t\t\taddremove = '-';\n-\t\t\tsha1 = t1->entry.sha1;\n-\t\t\tmode = mode1;\n+\t\t\tsha1 = p0->sha1;\n+\t\t\tmode = p0->mode;\n \t\t}\n \n-\t\topt->add_remove(opt, addremove, mode, sha1, 1, path->buf, 0);\n+\t\topt->add_remove(opt, addremove, mode, sha1, 1, p->path, 0);\n \t}\n+\n+\treturn 0;\t/* = no need to keep allocated combine_diff_path */\n }\n \n \n-/* new path should be added to diff\n+/*\n+ * Make a new combine_diff_path from path/mode/sha1\n+ * and append it to paths list tail.\n+ *\n+ * Memory for created elements could be reused:\n+ *\n+ *\t- if last->next == NULL, the memory is allocated;\n+ *\n+ *\t- if last->next != NULL, it is assumed that p=last->next was returned\n+ *\t earlier by this function, and p->next was *not* modified.\n+ *\t The memory is then reused from p.\n+ *\n+ * so for clients,\n+ *\n+ * - if you do need to keep the element\n+ *\n+ *\tp = __path_appendnew(p, ...);\n+ *\tprocess(p);\n+ *\tp->next = NULL;\n+ *\n+ * - if you don't need to keep the element after processing\n+ *\n+ *\tpprev = p;\n+ *\tp = __path_appendnew(p, ...);\n+ *\tprocess(p);\n+ *\tp = pprev;\n+ *\t; don't forget to free tail->next in the end\n+ *\n+ * p->parent[] remains uninitialized.\n+ */\n+static struct combine_diff_path *__path_appendnew(struct combine_diff_path *last,\n+\tint nparent, const struct strbuf *base, const char *path, int pathlen,\n+\tunsigned mode, const unsigned char *sha1)\n+{\n+\tstruct combine_diff_path *p;\n+\tint len = base->len + pathlen;\n+\tint alloclen = combine_diff_path_size(nparent, len);\n+\n+\t/* if last->next is !NULL - it is a pre-allocated memory, we can reuse */\n+\tp = last->next;\n+\tif (p && (alloclen > (int)p->next)) {\n+\t\tfree(p);\n+\t\tp = NULL;\n+\t}\n+\n+\tif (!p) {\n+\t\tp = xmalloc(alloclen);\n+\n+\t\t/* until we go to it next round, .next holds how many bytes we\n+\t\t * allocated (for faster realloc - we don't need copying old data).\n+\t\t */\n+\t\tp->next = (struct combine_diff_path *)alloclen;\n+\t}\n+\n+\tlast->next = p;\n+\n+\tp->path = (char *)&(p->parent[nparent]);\n+\tmemcpy(p->path, base->buf, base->len);\n+\tmemcpy(p->path + base->len, path, pathlen);\n+\tp->path[len] = 0;\n+\tp->mode = mode;\n+\thashcpy(p->sha1, sha1 ? sha1 : null_sha1);\n+\n+\treturn p;\n+}\n+\n+/* new path should be added to combine diff\n *\n * 3 cases on how/when it should be called and behaves:\n *\n- *\t!t1, t2\t-> path added, parent lacks it\n- *\t t1, !t2\t-> path removed from parent\n- *\t t1, t2\t-> path modified\n+ *\t t, !tp\t\t-> path added, all parents lack it\n+ *\t!t, tp\t\t-> path removed from all parents\n+ *\t t, tp\t\t-> path modified/added\n+ *\t\t\t (M for tp[i]=tp[imin], A otherwise)\n */\n-static void show_path(struct strbuf *base, struct diff_options *opt,\n-\t\t struct tree_desc *t1, struct tree_desc *t2)\n+static struct combine_diff_path *emit_path(struct combine_diff_path *p,\n+\tstruct strbuf *base, struct diff_options *opt, int nparent,\n+\tstruct tree_desc *t, struct tree_desc *tp,\n+\tint imin)\n {\n \tunsigned mode;\n \tconst char *path;\n+\tconst unsigned char *sha1;\n \tint pathlen;\n \tint old_baselen = base->len;\n-\tint isdir, recurse = 0, emitthis = 1;\n+\tint i, isdir, recurse = 0, emitthis = 1;\n \n \t/* at least something has to be valid */\n-\tassert(t1 || t2);\n+\tassert(t || tp);\n \n-\tif (t2) {\n+\tif (t) {\n \t\t/* path present in resulting tree */\n-\t\ttree_entry_extract(t2, &path, &mode);\n-\t\tpathlen = tree_entry_len(&t2->entry);\n+\t\tsha1 = tree_entry_extract(t, &path, &mode);\n+\t\tpathlen = tree_entry_len(&t->entry);\n \t\tisdir = S_ISDIR(mode);\n \t}\n \telse {\n-\t\t/* a path was removed - take path from parent. Also take\n-\t\t * mode from parent, to decide on recursion.\n+\t\t/* a path was removed - take path from imin parent. Also take\n+\t\t * mode from that parent, to decide on recursion(1).\n+\t\t *\n+\t\t * 1) all modes for tp[k]=tp[imin] should be the same wrt\n+\t\t * S_ISDIR, thanks to base_name_compare().\n \t\t */\n-\t\ttree_entry_extract(t1, &path, &mode);\n-\t\tpathlen = tree_entry_len(&t1->entry);\n+\t\ttree_entry_extract(&tp[imin], &path, &mode);\n+\t\tpathlen = tree_entry_len(&tp[imin].entry);\n \n \t\tisdir = S_ISDIR(mode);\n+\t\tsha1 = NULL;\n \t\tmode = 0;\n \t}\n \n@@ -107,18 +202,78 @@ static void show_path(struct strbuf *base, struct diff_options *opt,\n \t\temitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);\n \t}\n \n-\tstrbuf_add(base, path, pathlen);\n+\tif (emitthis) {\n+\t\tint keep;\n+\t\tstruct combine_diff_path *pprev = p;\n+\t\tp = __path_appendnew(p, nparent, base, path, pathlen, mode, sha1);\n \n-\tif (emitthis)\n-\t\temit_diff(opt, base, t1, t2);\n+\t\ti = 0; do {\n+\t\t\t/* tp[i] is valid, if present and if tp[i]==tp[imin] -\n+\t\t\t * otherwise, we should ignore it.\n+\t\t\t */\n+\t\t\tint tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);\n+\n+\t\t\tconst unsigned char *sha1_i;\n+\t\t\tunsigned mode_i;\n+\n+\t\t\tp->parent[i].status =\n+\t\t\t\t!t ? DIFF_STATUS_DELETED :\n+\t\t\t\t\ttpi_valid ?\n+\t\t\t\t\t\tDIFF_STATUS_MODIFIED :\n+\t\t\t\t\t\tDIFF_STATUS_ADDED;\n+\n+\t\t\tif (tpi_valid) {\n+\t\t\t\tsha1_i = tp[i].entry.sha1;\n+\t\t\t\tmode_i = tp[i].entry.mode;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\tsha1_i = NULL;\n+\t\t\t\tmode_i = 0;\n+\t\t\t}\n+\n+\t\t\tp->parent[i].mode = mode_i;\n+\t\t\thashcpy(p->parent[i].sha1, sha1_i ? sha1_i : null_sha1);\n+\t\t} while (++i < nparent);\n+\n+\t\tkeep = 1;\n+\t\tif (opt->pathchange)\n+\t\t\tkeep = opt->pathchange(opt, p);\n+\n+\t\t/* If a path was filtered or consumed - we don't need to add it\n+\t\t * to the list and can reuse its memory, leaving it as\n+\t\t * pre-allocated element on the tail.\n+\t\t *\n+\t\t * On the other hand, if path needs to be kept, we need to\n+\t\t * correct its .next to NULL, as it was pre-initialized to how\n+\t\t * much memory was allocated.\n+\t\t *\n+\t\t * see __path_appendnew() for details.\n+\t\t */\n+\t\tif (!keep)\n+\t\t\tp = pprev;\n+\t\telse\n+\t\t\tp->next = NULL;\n+\t}\n \n \tif (recurse) {\n+\t\tconst unsigned char **parents_sha1;\n+\n+\t\tparents_sha1 = alloca(nparent * sizeof(parents_sha1[0]));\n+\t\ti = 0; do {\n+\t\t\t/* same rule as in emitthis */\n+\t\t\tint tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);\n+\n+\t\t\tparents_sha1[i] = tpi_valid ? tp[i].entry.sha1\n+\t\t\t\t\t\t : NULL;\n+\t\t} while (++i < nparent);\n+\n+\t\tstrbuf_add(base, path, pathlen);\n \t\tstrbuf_addch(base, '/');\n-\t\t__diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,\n-\t\t\t\t t2 ? t2->entry.sha1 : NULL, base, opt);\n+\t\tp = __diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);\n \t}\n \n \tstrbuf_setlen(base, old_baselen);\n+\treturn p;\n }\n \n static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,\n@@ -137,59 +292,259 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,\n \t}\n }\n \n-int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,\n-\t\t struct strbuf *base, struct diff_options *opt)\n+\n+/* generate paths for combined diff D(sha1,parents_sha1[])\n+ *\n+ * Resulting paths are appended to combine_diff_path linked list, and also, are\n+ * emitted on the go via opt->pathchange() callback, so it is possible to\n+ * process the result as batch or incrementally.\n+ *\n+ * The paths are generated scanning new tree and all parents trees\n+ * simultaneously, similarly to what diff_tree() was doing for 2 trees.\n+ * The theory behind such scan is as follows:\n+ *\n+ *\n+ * D(A,X1...Xn) calculation scheme\n+ * -------------------------------\n+ *\n+ * D(A,X1...Xn) = D(A,X1) ^ ... ^ D(A,Xn)\t(regarding resulting paths set)\n+ *\n+ *\tD(A,Xj)\t\t- diff between A..Xj\n+ *\tD(A,X1...Xn)\t- combined diff from A to parents X1,...,Xn\n+ *\n+ *\n+ * We start from all trees, which are sorted, and compare their entries in\n+ * lock-step:\n+ *\n+ *\t A X1 Xn\n+ *\t - - -\n+ *\t|a| |x1| |xn|\n+ *\t|-| |--| ... |--| i = argmin(x1...xn)\n+ *\t| | | | | |\n+ *\t|-| |--| |--|\n+ *\t|.| |. | |. |\n+ *\t . . .\n+ *\t . . .\n+ *\n+ * at any time there could be 3 cases:\n+ *\n+ *\t1) a < xi;\n+ *\t2) a > xi;\n+ *\t3) a = xi.\n+ *\n+ * Schematic deduction of what every case means, and what to do, follows:\n+ *\n+ * 1) a < xi -> ∀j a ∉ Xj -> \"+a\" ∈ D(A,Xj) -> D += \"+a\"; a↓\n+ *\n+ * 2) a > xi\n+ *\n+ * 2.1) ∃j: xj > xi -> \"-xi\" ∉ D(A,Xj) -> D += ø; ∀ xk=xi xk↓\n+ * 2.2) ∀j xj = xi -> xj ∉ A -> \"-xj\" ∈ D(A,Xj) -> D += \"-xi\"; ∀j xj↓\n+ *\n+ * 3) a = xi\n+ *\n+ * 3.1) ∃j: xj > xi -> \"+a\" ∈ D(A,Xj) -> only xk=xi remains to investigate\n+ * 3.2) xj = xi -> investigate δ(a,xj)\n+ * |\n+ * |\n+ * v\n+ *\n+ * 3.1+3.2) looking at δ(a,xk) ∀k: xk=xi - if all != ø ->\n+ *\n+ * ⎧δ(a,xk) - if xk=xi\n+ * -> D += ⎨\n+ * ⎩\"+a\" - if xk>xi\n+ *\n+ *\n+ * in any case a↓ ∀ xk=xi xk↓\n+ *\n+ *\n+ * ~~~~~~~~\n+ *\n+ * NOTE\n+ *\n+ *\tUsual diff D(A,B) is by definition the same as combined diff D(A,[B]),\n+ *\tso this diff paths generator can, and is used, for plain diffs\n+ *\tgeneration too.\n+ *\n+ *\tPlease keep attention to the common D(A,[B]) case when working on the\n+ *\tcode, in order not to slow it down.\n+ *\n+ * NOTE\n+ *\tnparent must be > 0.\n+ */\n+\n+\n+/* ∀ xk=xi xk↓ */\n+static inline void update_tp_entries(struct tree_desc *tp, int nparent)\n {\n-\tstruct tree_desc t1, t2;\n-\tvoid *t1tree, *t2tree;\n+\tint i;\n+\ti = 0; do {\n+\t\tif (!(tp[i].entry.mode & S_IFXMIN_NEQ))\n+\t\t\tupdate_tree_entry(&tp[i]);\n+\t} while (++i < nparent);\n+}\n+\n+static struct combine_diff_path *__diff_tree_paths(\n+\tstruct combine_diff_path *p, const unsigned char *sha1,\n+\tconst unsigned char **parents_sha1, int nparent,\n+\tstruct strbuf *base, struct diff_options *opt)\n+{\n+\tstruct tree_desc t, *tp;\n+\tvoid *ttree, **tptree;\n+\tint i;\n \n-\tt1tree = fill_tree_descriptor(&t1, old);\n-\tt2tree = fill_tree_descriptor(&t2, new);\n+\ttp = alloca(nparent * sizeof(tp[0]));\n+\ttptree = alloca(nparent * sizeof(tptree[0]));\n+\n+\t/* load parents first, as they are probably already cached.\n+\t *\n+\t * ( log_tree_diff() parses commit->parent before calling here via\n+\t * diff_tree_sha1(parent, commit) )\n+\t */\n+\ti = 0; do {\n+\t\ttptree[i] = fill_tree_descriptor(&tp[i], parents_sha1[i]);\n+\t} while (++i < nparent);\n+\tttree = fill_tree_descriptor(&t, sha1);\n \n \t/* Enable recursion indefinitely */\n \topt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);\n \n \tfor (;;) {\n-\t\tint cmp;\n+\t\tint imin, cmp;\n \n \t\tif (diff_can_quit_early(opt))\n \t\t\tbreak;\n+\n \t\tif (opt->pathspec.nr) {\n-\t\t\tskip_uninteresting(&t1, base, opt);\n-\t\t\tskip_uninteresting(&t2, base, opt);\n+\t\t\tskip_uninteresting(&t, base, opt);\n+\t\t\tfor (i = 0; i < nparent; i++)\n+\t\t\t\tskip_uninteresting(&tp[i], base, opt);\n \t\t}\n-\t\tif (!t1.size && !t2.size)\n-\t\t\tbreak;\n \n-\t\tcmp = tree_entry_pathcmp(&t1, &t2);\n+\t\t/* comparing is finished when all trees are done */\n+\t\tif (!t.size) {\n+\t\t\tint done = 1;\n+\t\t\ti = 0; do {\n+\t\t\t\tif (tp[i].size) {\n+\t\t\t\t\tdone = 0;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t} while (++i < nparent);\n+\t\t\tif (done)\n+\t\t\t\tbreak;\n+\t\t}\n \n-\t\t/* t1 = t2 */\n-\t\tif (cmp == 0) {\n-\t\t\tif (DIFF_OPT_TST(opt, FIND_COPIES_HARDER) ||\n-\t\t\t hashcmp(t1.entry.sha1, t2.entry.sha1) ||\n-\t\t\t (t1.entry.mode != t2.entry.mode))\n-\t\t\t\tshow_path(base, opt, &t1, &t2);\n \n-\t\t\tupdate_tree_entry(&t1);\n-\t\t\tupdate_tree_entry(&t2);\n+\t\t/* lookup imin = argmin(x1...xn),\n+\t\t * mark entries whether they =tp[imin] along the way\n+\t\t */\n+\t\timin = 0;\n+\t\ttp[0].entry.mode &= ~S_IFXMIN_NEQ;\n+\n+\t\tfor (i = 1; i < nparent; ++i) {\n+\t\t\tcmp = tree_entry_pathcmp(&tp[i], &tp[imin]);\n+\t\t\tif (cmp < 0) {\n+\t\t\t\timin = i;\n+\t\t\t\ttp[i].entry.mode &= ~S_IFXMIN_NEQ;\n+\t\t\t}\n+\t\t\telse if (cmp == 0) {\n+\t\t\t\ttp[i].entry.mode &= ~S_IFXMIN_NEQ;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\ttp[i].entry.mode |= S_IFXMIN_NEQ;\n+\t\t\t}\n \t\t}\n \n-\t\t/* t1 < t2 */\n+\t\t/* fixup markings for entries before imin */\n+\t\tfor (i = 0; i < imin; ++i)\n+\t\t\ttp[i].entry.mode |= S_IFXMIN_NEQ;\t/* x[i] > x[imin] */\n+\n+\n+\n+\t\t/* compare a vs x[imin] */\n+\t\tcmp = tree_entry_pathcmp(&t, &tp[imin]);\n+\n+\t\t/* a = xi */\n+\t\tif (cmp == 0) {\n+\t\t\t/* are either xk > xi or diff(a,xk) != ø ? */\n+\t\t\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {\n+\t\t\t\ti = 0; do {\n+\t\t\t\t\t/* x[i] > x[imin] */\n+\t\t\t\t\tif (tp[i].entry.mode & S_IFXMIN_NEQ)\n+\t\t\t\t\t\tcontinue;\n+\n+\t\t\t\t\t/* diff(a,xk) != ø */\n+\t\t\t\t\tif (hashcmp(t.entry.sha1, tp[i].entry.sha1) ||\n+\t\t\t\t\t (t.entry.mode != tp[i].entry.mode))\n+\t\t\t\t\t\tcontinue;\n+\n+\t\t\t\t\tgoto skip_emit_t_tp;\n+\t\t\t\t} while (++i < nparent);\n+\t\t\t}\n+\n+\t\t\t/* D += {δ(a,xk) if xk=xi; \"+a\" if xk > xi} */\n+\t\t\tp = emit_path(p, base, opt, nparent,\n+\t\t\t\t\t&t, tp, imin);\n+\n+\t\tskip_emit_t_tp:\n+\t\t\t/* a↓, ∀ xk=ximin xk↓ */\n+\t\t\tupdate_tree_entry(&t);\n+\t\t\tupdate_tp_entries(tp, nparent);\n+\t\t}\n+\n+\t\t/* a < xi */\n \t\telse if (cmp < 0) {\n-\t\t\tshow_path(base, opt, &t1, /*t2=*/NULL);\n-\t\t\tupdate_tree_entry(&t1);\n+\t\t\t/* D += \"+a\" */\n+\t\t\tp = emit_path(p, base, opt, nparent,\n+\t\t\t\t\t&t, /*tp=*/NULL, -1);\n+\n+\t\t\t/* a↓ */\n+\t\t\tupdate_tree_entry(&t);\n \t\t}\n \n-\t\t/* t1 > t2 */\n+\t\t/* a > xi */\n \t\telse {\n-\t\t\tshow_path(base, opt, /*t1=*/NULL, &t2);\n-\t\t\tupdate_tree_entry(&t2);\n+\t\t\t/* ∀j xj=ximin -> D += \"-xi\" */\n+\t\t\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {\n+\t\t\t\ti = 0; do {\n+\t\t\t\t\tif (tp[i].entry.mode & S_IFXMIN_NEQ)\n+\t\t\t\t\t\tgoto skip_emit_tp;\n+\t\t\t\t} while (++i < nparent);\n+\t\t\t}\n+\n+\t\t\tp = emit_path(p, base, opt, nparent,\n+\t\t\t\t\t/*t=*/NULL, tp, imin);\n+\n+\t\tskip_emit_tp:\n+\t\t\t/* ∀ xk=ximin xk↓ */\n+\t\t\tupdate_tp_entries(tp, nparent);\n \t\t}\n \t}\n \n-\tfree(t2tree);\n-\tfree(t1tree);\n-\treturn 0;\n+\tfree(ttree);\n+\tfor (i = nparent-1; i >= 0; i--)\n+\t\tfree(tptree[i]);\n+\n+\treturn p;\n+}\n+\n+struct combine_diff_path *diff_tree_paths(\n+\tstruct combine_diff_path *p, const unsigned char *sha1,\n+\tconst unsigned char **parents_sha1, int nparent,\n+\tstruct strbuf *base, struct diff_options *opt)\n+{\n+\tp = __diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);\n+\n+\t/* free pre-allocated last element, if any\n+\t * (see __path_appendnew() for details about why)\n+\t */\n+\tif (p->next) {\n+\t\tfree(p->next);\n+\t\tp->next = NULL;\n+\t}\n+\n+\treturn p;\n }\n \n /*\n@@ -300,6 +655,24 @@ static void try_to_follow_renames(const unsigned char *old, const unsigned char\n \tq->nr = 1;\n }\n \n+int __diff_tree_sha1(const unsigned char *old, const unsigned char *new, struct strbuf *base, struct diff_options *opt)\n+{\n+\tstruct combine_diff_path phead, *p;\n+\tconst unsigned char *parents_sha1[1] = {old};\n+\n+\tphead.next = NULL;\n+\topt->pathchange = emit_diff_p0only;\n+\tdiff_tree_paths(&phead, new, parents_sha1, 1, base, opt);\n+\n+\tfor (p = phead.next; p;) {\n+\t\tstruct combine_diff_path *pprev = p;\n+\t\tp = p->next;\n+\t\tfree(pprev);\n+\t}\n+\n+\treturn 0;\n+}\n+\n int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base_str, struct diff_options *opt)\n {\n \tstruct strbuf base;\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234729","messageId":"f74c494d4afd0f7428288ce1099a91c9d2ae2125.1392299516.git.kirr@mns.spb.ru","threadId":"35860","inReplyTo":"cover.1392299516.git.kirr@mns.spb.ru","subject":"[PATCH 2/2] combine-diff: speed it up, by using multiparent diff tree-walker directly","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-13T14:02:55Z","receivedAt":"2014-02-13T14:02:55Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"As was recently shown (c839f1bd \"combine-diff: optimize\ncombine_diff_path sets intersection\"), combine-diff runs very slowly. In\nthat commit we optimized paths sets intersection, but that accounted\nonly for ~ 25% of the slowness, and as my tracing showed, for linux.git\nv3.10..v3.11, for merges a lot of time is spent computing\ndiff(commit,commit^2) just to only then intersect that huge diff to\nalmost small set of files from diff(commit,commit^1).\n\nIn previous commit, we described the problem in more details, and\nreworked the diff tree-walker to be general one - i.e. to work in\nmultiple parent case too. Now is the time to take advantage of it for\nfinding paths for combine diff.\n\nThe implementation is straightforward - if we know, we can get generated\ndiff paths directly, and at present that means no diff filtering or\nrename/copy detection was requested(*), we can call multiparent tree-walker\ndirectly and get ready paths.\n\n(*) because e.g. at present, all diffcore transformations work on\n diff_filepair queues, but in the future, that limitation can be\n lifted, if filters would operate directly on combine_diff_paths.\n\nTimings for `git log --raw --no-abbrev --no-renames` without `-c` (\"git log\")\nand with `-c` (\"git log -c\") and with `-c --merges` (\"git log -c --merges\")\nbefore and after the patch are as follows:\n\n linux.git v3.10..v3.11\n\n log log -c log -c --merges\n\n before 1.9s 16.4s 15.2s\n after 1.9s 2.4s 1.1s\n\nThe result stayed the same.\n\nSigned-off-by: Kirill Smelkov \n---\n combine-diff.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----\n diff.c | 1 +\n 2 files changed, 81 insertions(+), 5 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 1732dfd..ddf7495 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1303,7 +1303,7 @@ static const char *path_path(void *obj)\n \n \n /* find set of paths that every parent touches */\n-static struct combine_diff_path *find_paths(const unsigned char *sha1,\n+static struct combine_diff_path *find_paths_generic(const unsigned char *sha1,\n \tconst struct sha1_array *parents, struct diff_options *opt)\n {\n \tstruct combine_diff_path *paths = NULL;\n@@ -1316,6 +1316,7 @@ static struct combine_diff_path *find_paths(const unsigned char *sha1,\n \t/* tell diff_tree to emit paths in sorted (=tree) order */\n \topt->orderfile = NULL;\n \n+\t/* D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn) (wrt paths) */\n \tfor (i = 0; i < num_parent; i++) {\n \t\t/*\n \t\t * show stat against the first parent even when doing\n@@ -1346,6 +1347,35 @@ static struct combine_diff_path *find_paths(const unsigned char *sha1,\n }\n \n \n+/*\n+ * find set of paths that everybody touches, assuming diff is run without\n+ * rename/copy detection, etc, comparing all trees simultaneously (= faster).\n+ */\n+static struct combine_diff_path *find_paths_multitree(\n+\tconst unsigned char *sha1, const struct sha1_array *parents,\n+\tstruct diff_options *opt)\n+{\n+\tint i, nparent = parents->nr;\n+\tconst unsigned char **parents_sha1;\n+\tstruct combine_diff_path paths_head;\n+\tstruct strbuf base;\n+\n+\tparents_sha1 = xmalloc(nparent * sizeof(parents_sha1[0]));\n+\tfor (i = 0; i < nparent; i++)\n+\t\tparents_sha1[i] = parents->sha1[i];\n+\n+\t/* fake list head, so worker can assume it is non-NULL */\n+\tpaths_head.next = NULL;\n+\n+\tstrbuf_init(&base, PATH_MAX);\n+\tdiff_tree_paths(&paths_head, sha1, parents_sha1, nparent, &base, opt);\n+\n+\tstrbuf_release(&base);\n+\tfree(parents_sha1);\n+\treturn paths_head.next;\n+}\n+\n+\n void diff_tree_combined(const unsigned char *sha1,\n \t\t\tconst struct sha1_array *parents,\n \t\t\tint dense,\n@@ -1355,6 +1385,7 @@ void diff_tree_combined(const unsigned char *sha1,\n \tstruct diff_options diffopts;\n \tstruct combine_diff_path *p, *paths;\n \tint i, num_paths, needsep, show_log_first, num_parent = parents->nr;\n+\tint need_generic_pathscan;\n \n \t/* nothing to do, if no parents */\n \tif (!num_parent)\n@@ -1377,11 +1408,55 @@ void diff_tree_combined(const unsigned char *sha1,\n \n \t/* find set of paths that everybody touches\n \t *\n-\t * NOTE find_paths() also handles --stat, as it computes\n-\t * diff(sha1,parent_i) for all i to do the job, specifically\n-\t * for parent0.\n+\t * NOTE\n+\t *\n+\t * Diffcore transformations are bound to diff_filespec and logic\n+\t * comparing two entries - i.e. they do not apply directly to combine\n+\t * diff.\n+\t *\n+\t * If some of such transformations is requested - we launch generic\n+\t * path scanning, which works significantly slower compared to\n+\t * simultaneous all-trees-in-one-go scan in find_paths_multitree().\n+\t *\n+\t * TODO some of the filters could be ported to work on\n+\t * combine_diff_paths - i.e. all functionality that skips paths, so in\n+\t * theory, we could end up having only multitree path scanning.\n+\t *\n+\t * NOTE please keep this semantically in sync with diffcore_std()\n \t */\n-\tpaths = find_paths(sha1, parents, &diffopts);\n+\tneed_generic_pathscan = opt->skip_stat_unmatch\t||\n+\t\t\tDIFF_OPT_TST(opt, FOLLOW_RENAMES)\t||\n+\t\t\topt->break_opt != -1\t||\n+\t\t\topt->detect_rename\t||\n+\t\t\topt->pickaxe\t\t||\n+\t\t\topt->filter;\n+\n+\n+\tif (need_generic_pathscan) {\n+\t\t/* NOTE generic case also handles --stat, as it computes\n+\t\t * diff(sha1,parent_i) for all i to do the job, specifically\n+\t\t * for parent0.\n+\t\t */\n+\t\tpaths = find_paths_generic(sha1, parents, &diffopts);\n+\t}\n+\telse {\n+\t\tpaths = find_paths_multitree(sha1, parents, &diffopts);\n+\n+\t\t/* show stat against the first parent even\n+\t\t * when doing combined diff.\n+\t\t */\n+\t\tint stat_opt = (opt->output_format &\n+\t\t\t\t(DIFF_FORMAT_NUMSTAT|DIFF_FORMAT_DIFFSTAT));\n+\t\tif (stat_opt) {\n+\t\t\tdiffopts.output_format = stat_opt;\n+\n+\t\t\tdiff_tree_sha1(parents->sha1[0], sha1, \"\", &diffopts);\n+\t\t\tdiffcore_std(&diffopts);\n+\t\t\tif (opt->orderfile)\n+\t\t\t\tdiffcore_order(opt->orderfile);\n+\t\t\tdiff_flush(&diffopts);\n+\t\t}\n+\t}\n \n \t/* find out number of surviving paths */\n \tfor (num_paths = 0, p = paths; p; p = p->next)\ndiff --git a/diff.c b/diff.c\nindex cda4aa8..f2fff46 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4764,6 +4764,7 @@ void diffcore_fix_diff_index(struct diff_options *options)\n \n void diffcore_std(struct diff_options *options)\n {\n+\t/* NOTE please keep the following in sync with diff_tree_combined() */\n \tif (options->skip_stat_unmatch)\n \t\tdiffcore_skip_stat_unmatch(options);\n \tif (!options->found_follow) {\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234741","messageId":"xmqqbnyalrk8.fsf@gitster.dls.corp.google.com","threadId":"35860","inReplyTo":"1dd9ca564e00ef235875aae4944675f53dcd25a3.1392299516.git.kirr@mns.spb.ru","subject":"Re: [PATCH 1/2] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-13T19:51:19Z","receivedAt":"2014-02-13T19:51:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> +\t\t/* until we go to it next round, .next holds how many bytes we\n> +\t\t * allocated (for faster realloc - we don't need copying old data).\n> +\t\t */\n> +\t\tp->next = (struct combine_diff_path *)alloclen;\n\nI am getting this here:\n\ntree-diff.c: In function '__path_appendnew':\ntree-diff.c:140:13: error: cast to pointer from integer of different size [-Werror=int-to-pointer-cast]\n"},{"id":"234742","messageId":"xmqq7g8ylrdv.fsf@gitster.dls.corp.google.com","threadId":"35860","inReplyTo":"f74c494d4afd0f7428288ce1099a91c9d2ae2125.1392299516.git.kirr@mns.spb.ru","subject":"Re: [PATCH 2/2] combine-diff: speed it up, by using multiparent diff tree-walker directly","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-13T19:55:08Z","receivedAt":"2014-02-13T19:55:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> +\tif (need_generic_pathscan) {\n> +\t\t/* NOTE generic case also handles --stat, as it computes\n> +\t\t * diff(sha1,parent_i) for all i to do the job, specifically\n> +\t\t * for parent0.\n> +\t\t */\n> +\t\tpaths = find_paths_generic(sha1, parents, &diffopts);\n> +\t}\n> +\telse {\n> +\t\tpaths = find_paths_multitree(sha1, parents, &diffopts);\n> +\n> +\t\t/* show stat against the first parent even\n> +\t\t * when doing combined diff.\n> +\t\t */\n> +\t\tint stat_opt = (opt->output_format &\n> +\t\t\t\t(DIFF_FORMAT_NUMSTAT|DIFF_FORMAT_DIFFSTAT));\n\n/*\n * We see decl-after-stmt here.\n * Also please have slash-asterisk and asterisk-slash\n * at the beginning and the end of a multi-line comment\n * block on their own line.\n */\n"},{"id":"234763","messageId":"20140214121529.GB3416@tugrik.mns.mnsspb.ru","threadId":"35860","inReplyTo":"xmqqbnyalrk8.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 1/2] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-14T12:15:29Z","receivedAt":"2014-02-14T12:15:29Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Thu, Feb 13, 2014 at 11:51:19AM -0800, Junio C Hamano wrote:\n> Kirill Smelkov writes:\n> \n> > +\t\t/* until we go to it next round, .next holds how many bytes we\n> > +\t\t * allocated (for faster realloc - we don't need copying old data).\n> > +\t\t */\n> > +\t\tp->next = (struct combine_diff_path *)alloclen;\n> \n> I am getting this here:\n> \n> tree-diff.c: In function '__path_appendnew':\n> tree-diff.c:140:13: error: cast to pointer from integer of different size [-Werror=int-to-pointer-cast]\n\nAh, sorry, I only tested on 32 bits, and this indeed could be a valid\nwarning on systems where sizeof(ptr) != sizeof(int).\n\nIn our case, alloclen is small enough that the code should be valid,\nand we can avoid the warning, via proper usage of intptr_t.\n\nPlease find corrected patch below.\n\nThanks,\nKirill\n\n---- 8< ----\nFrom: Kirill Smelkov \nSubject: [PATCH v2 1/2] tree-diff: rework diff_tree() to generate diffs for\n multiparent cases as well\nMIME-Version: 1.0\nContent-Type: text/plain; charset=UTF-8\nContent-Transfer-Encoding: 8bit\n\nPreviously diff_tree(), which is now named __diff_tree_sha1(), was\ngenerating diff_filepair(s) for two trees t1 and t2, and that was\nusually used for a commit as t1=HEAD~, and t2=HEAD - i.e. to see changes\na commit introduces.\n\nIn Git, however, we have fundamentally built flexibility in that a\ncommit can have many parents - 1 for a plain commit, 2 for a simple merge,\nbut also more than 2 for merging several heads at once.\n\nFor merges there is a so called combine-diff, which shows diff, a merge\nintroduces by itself, omitting changes done by any parent. That works\nthrough first finding paths, that are different to all parents, and then\nshowing generalized diff, with separate columns for +/- for each parent.\nThe code lives in combine-diff.c .\n\nThere is an impedance mismatch, however, in that a commit could\ngenerally have any number of parents, and that while diffing trees, we\ndivide cases for 2-tree diffs and more-than-2-tree diffs. I mean there\nis no special casing for multiple parents commits in e.g.\nrevision-walker .\n\nThat impedance mismatch *hurts* *performance* *badly* for generating\ncombined diffs - in c839f1bd (combine-diff: optimize combine_diff_path\nsets intersection) I've already removed some slowness from it, but from\nthe timings provided there, it could be seen, that combined diffs still\ncost more than an order of magnitude more cpu time, compared to diff for\nusual commits, and that would only be an optimistic estimate, if we take\ninto account that for e.g. linux.git there is only one merge for several\ndozens of plain commits.\n\nThat slowness comes from the fact that currently, while generating\ncombined diff, a lot of time is spent computing diff(commit,commit^2)\njust to only then intersect that huge diff to almost small set of files\nfrom diff(commit,commit^1).\n\nThat's because at present, to compute combine-diff, for first finding\npaths, that \"every parent touches\", we use the following combine-diff\nproperty/definition:\n\nD(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn) (w.r.t. paths)\n\nwhere\n\nD(A,P1...Pn) is combined diff between commit A, and parents Pi\n\nand\n\nD(A,Pi) is usual two-tree diff Pi..A\n\nSo if any of that D(A,Pi) is huge, tracting 1 n-parent combine-diff as n\n1-parent diffs and intersecting results will be slow.\n\nAnd usually, for linux.git and other topic-based workflows, that\nD(A,P2) is huge, because, if merge-base of A and P2, is several dozens\nof merges (from A, via first parent) below, that D(A,P2) will be diffing\nsum of merges from several subsystems to 1 subsystem.\n\nThe solution is to avoid computing n 1-parent diffs, and to find\nchanged-to-all-parents paths via scanning A's and all Pi's trees\nsimultaneously, at each step comparing their entries, and based on that\ncomparison, populate paths result, and deduce we could *skip*\n*recursing* into subdirectories, if at least for 1 parent, sha1 of that\ndir tree is the same as in A. That would save us from doing significant\namount of needless work.\n\nSuch approach is very similar to what diff_tree() does, only there we\ndeal with scanning only 2 trees simultaneously, and for n+1 tree, the\nlogic is a bit more complex:\n\nD(A,X1...Xn) calculation scheme\n-------------------------------\n\nD(A,X1...Xn) = D(A,X1) ^ ... ^ D(A,Xn) (regarding resulting paths set)\n\n D(A,Xj) - diff between A..Xj\n D(A,X1...Xn) - combined diff from A to parents X1,...,Xn\n\nWe start from all trees, which are sorted, and compare their entries in\nlock-step:\n\n A X1 Xn\n - - -\n |a| |x1| |xn|\n |-| |--| ... |--| i = argmin(x1...xn)\n | | | | | |\n |-| |--| |--|\n |.| |. | |. |\n . . .\n . . .\n\nat any time there could be 3 cases:\n\n 1) a < xi;\n 2) a > xi;\n 3) a = xi.\n\nSchematic deduction of what every case means, and what to do, follows:\n\n1) a < xi -> ∀j a ∉ Xj -> \"+a\" ∈ D(A,Xj) -> D += \"+a\"; a↓\n\n2) a > xi\n\n 2.1) ∃j: xj > xi -> \"-xi\" ∉ D(A,Xj) -> D += ø; ∀ xk=xi xk↓\n 2.2) ∀j xj = xi -> xj ∉ A -> \"-xj\" ∈ D(A,Xj) -> D += \"-xi\"; ∀j xj↓\n\n3) a = xi\n\n 3.1) ∃j: xj > xi -> \"+a\" ∈ D(A,Xj) -> only xk=xi remains to investigate\n 3.2) xj = xi -> investigate δ(a,xj)\n |\n |\n v\n\n 3.1+3.2) looking at δ(a,xk) ∀k: xk=xi - if all != ø ->\n\n ⎧δ(a,xk) - if xk=xi\n -> D += ⎨\n ⎩\"+a\" - if xk>xi\n\n in any case a↓ ∀ xk=xi xk↓\n\n~\n\nFor comparison, here is how diff_tree() works:\n\nD(A,B) calculation scheme\n-------------------------\n\n A B\n - -\n |a| |b| a < b -> a ∉ B -> D(A,B) += +a a↓\n |-| |-| a > b -> b ∉ A -> D(A,B) += -b b↓\n | | | | a = b -> investigate δ(a,b) a↓ b↓\n |-| |-|\n |.| |.|\n . .\n . .\n\n~~~~~~~~\n\nThis patch generalizes diff tree-walker to work with arbitrary number of\nparents as described above - i.e. now there is a resulting tree t, and\nsome parents trees tp[i] i=[0..nparent). The generalization builds on\nthe fact that usual diff\n\nD(A,B)\n\nis by definition the same as combined diff\n\nD(A,[B]),\n\nso if we could rework the code for common case and make it be not slower\nfor nparent=1 case, usual diff(t1,t2) generation will not be slower, and\nmultiparent diff tree-walker would greatly benefit generating\ncombine-diff.\n\nWhat we do is as follows:\n\n1) diff tree-walker __diff_tree_sha1() is internally reworked to be\n a paths generator (new name diff_tree_paths()), with each generated path\n being `struct combine_diff_path` with info for path, new sha1,mode and for\n every parent which sha1,mode it was in it.\n\n2) From that info, we can still generate usual diff queue with\n struct diff_filepairs, via \"exporting\" generated\n combine_diff_path, if we know we run for nparent=1 case.\n (see emit_diff() which is now named emit_diff_p0only())\n\n3) In order for diff_can_quit_early(), which checks\n\n DIFF_OPT_TST(opt, HAS_CHANGES))\n\n to work, that exporting have to be happening not in bulk, but\n incrementally, one diff path at a time.\n\n For such consumers, there is a new callback in diff_options\n introduced:\n\n ->pathchange(opt, struct combine_diff_path *)\n\n which, if set to !NULL, is called for every generated path.\n\n (see new compat __diff_tree_sha1() wrapper around new paths\n generator for setup)\n\n4) The paths generation itself, is reworked from previous\n __diff_tree_sha1() code according to \"D(A,X1...Xn) calculation\n scheme\" provided above:\n\n On the start we allocate [nparent] arrays in place what was\n earlier just for one parent tree.\n\n then we just generalize loops, and comparison according to the\n algorithm.\n\nSome notes(*):\n\n1) For loops,\n\n i = 0; do { ... } while (++i < nparent);\n\nis used instead of\n\n for (i = 0; i < nparent; ++i)\n ...\n\nbecause for the former case, the compiler have to emit additional\nprologue code which checks for i >= nparent case before entering the\nloop.\n\nAs we require nparent must be >0, that additional overhead\nconflicts with the \"runs not slower for nparent=1 case than before\"\ngoal.\n\n2) alloca(), for small arrays, is used for the same reason - if we change\nit to xmalloc()/free() the timings get worse\n\n3) For every parent tree, we need to keep a tag, whether entry from that\nparent equals to entry from minimal parent. For performance reasons I'm\nkeeping that tag in entry's mode field in unused bit - see S_IFXMIN_NEQ.\n Not doing so, we'd need to alloca another [nparent] array, which hurts\n performance.\n\n4) For emitted paths, memory could be reused, if we know the path was\n processed via callback and will not be needed later. We efficient\n hand-made realloc-style __path_appendnew(), that saves us from ~1-1.5%\n of potential additional slowdown.\n\n5) goto(s) are used in several places, as the code executes a little bit\n faster with lowered register pressure.\n\nAlso\n\n- we should now check for FIND_COPIES_HARDER not only when two entries\n names are the same, and their hashes are equal, but also for a case,\n when a path was removed from some of all parents having it.\n\n The reason is, if we don't, that path won't be emitted at all (see\n \"a > xi\" case), and we'll just skip it, and FIND_COPIES_HARDER wants\n all paths - with diff or without - to be emitted, to be later analyzed\n for being copies sources.\n\n The new check is only necessary for nparent >1, as for nparent=1 case\n xmin_eqtotal always =1 =nparent, and a path is always added to diff as\n removal.\n\n~~~~~~~~\n\nTimings for\n\n # without -c, i.e. testing only nparent=1 case\n `git log --raw --no-abbrev --no-renames`\n\nbefore and after the patch are as follows:\n\n navy.git linux.git v3.10..v3.11\n\n before 0.611s 1.889s\n after 0.619s 1.907s\n slowdown 1.3% 0.9%\n\nThis timings show we did no harm to usual diff(tree1,tree2) generation.\n>From the table we can see that we actually did ~1% slowdown, but I think\nI've \"earned\" that 1% in the previous patch (729f7e8e in pu) so for\nnparent=1 case, net timings stays approximately the same.\n\nThe output also stayed the same.\n\n(*) If we revert 1)-5) to more usual techniques, for nparent=1 case,\n we'll get ~2-2.5% of additional slowdown, which I've tried to avoid, as\n \"do no harm for nparent=1 case\" rule.\n\nFor linux.git, combined diff will run an order of magnitude faster and\nappropriate timings will be provided in the next commit, as we'll be\ntaking advantage of the new diff tree-walker for combined-diff\ngeneration there.\n\nP.S. and combined diff is not some exotic/for-play-only stuff - for\nexample for a program I write to represent Git archives as readonly\nfilesystem, there is initial scan with\n\n `git log --reverse --raw --no-abbrev --no-renames -c`\n\nto extract log of what was created/changed when, as a result building a\nmap\n\n {} sha1 -> in which commit (and date) a content was added\n\nthat `-c` means also show combined diff for merges, and without them, if\na merge is non-trivial (merges changes from two parents with both having\nseparate changes to a file), or an evil one, the map will not be full,\ni.e. some valid sha1 would be absent from it.\n\nThat case was my initial motivation for combined diffs speedup.\n\nSigned-off-by: Kirill Smelkov \n---\n diff.c | 1 +\n diff.h | 10 ++\n tree-diff.c | 510 ++++++++++++++++++++++++++++++++++++++++++++++++++++--------\n 3 files changed, 457 insertions(+), 64 deletions(-)\n\nChanges since v1:\n\n - fixed p->next assignment/\"dereference\" as integer, via proper use of intptr_t;\n - reworked multiline comments to start and end with /* and */ on separate lines.\n\ndiff --git a/diff.c b/diff.c\nindex 8e4a6a9..cda4aa8 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3216,6 +3216,7 @@ void diff_setup(struct diff_options *options)\n \toptions->context = diff_context_default;\n \tDIFF_OPT_SET(options, RENAME_EMPTY);\n \n+\t/* pathchange left =NULL by default */\n \toptions->change = diff_change;\n \toptions->add_remove = diff_addremove;\n \toptions->use_color = diff_use_color_default;\ndiff --git a/diff.h b/diff.h\nindex bf834ff..b59e8d6 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -15,6 +15,10 @@ struct diff_filespec;\n struct userdiff_driver;\n struct sha1_array;\n struct commit;\n+struct combine_diff_path;\n+\n+typedef int (*pathchange_fn_t)(struct diff_options *options,\n+\t\t struct combine_diff_path *path);\n \n typedef void (*change_fn_t)(struct diff_options *options,\n \t\t unsigned old_mode, unsigned new_mode,\n@@ -157,6 +161,7 @@ struct diff_options {\n \tint close_file;\n \n \tstruct pathspec pathspec;\n+\tpathchange_fn_t pathchange;\n \tchange_fn_t change;\n \tadd_remove_fn_t add_remove;\n \tdiff_format_fn_t format_callback;\n@@ -189,6 +194,11 @@ const char *diff_line_prefix(struct diff_options *);\n \n extern const char mime_boundary_leader[];\n \n+extern\n+struct combine_diff_path *diff_tree_paths(\n+\tstruct combine_diff_path *p, const unsigned char *sha1,\n+\tconst unsigned char **parent_sha1, int nparent,\n+\tstruct strbuf *base, struct diff_options *opt);\n extern int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,\n \t\t\t struct strbuf *base, struct diff_options *opt);\n extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,\ndiff --git a/tree-diff.c b/tree-diff.c\nindex ab61a0a..2b7c991 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -7,6 +7,25 @@\n #include \"tree.h\"\n \n /*\n+ * internal mode marker, saying a tree entry != entry of tp[imin]\n+ * (see __diff_tree_paths for what it means there)\n+ *\n+ * it *must* not overlap with any valid modes, and we will update/use/emit\n+ * entry for diff only with it unset. Only non-overlapping to valid modes is\n+ * required, because mode in tree_desc, comes here canonicalized via\n+ * canon_mode().\n+ *\n+ * the definition assumes unsigned is at least 32 bits.\n+ */\n+#define S_IFXMIN_NEQ\t0x80000000\n+\n+\n+static struct combine_diff_path *__diff_tree_paths(\n+\tstruct combine_diff_path *p, const unsigned char *sha1,\n+\tconst unsigned char **parents_sha1, int nparent,\n+\tstruct strbuf *base, struct diff_options *opt);\n+\n+/*\n * Compare two tree entries, taking into account only path/S_ISDIR(mode),\n * but not their sha1's.\n *\n@@ -33,72 +52,152 @@ static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)\n }\n \n \n-/* convert path, t1/t2 -> opt->diff_*() callbacks */\n-static void emit_diff(struct diff_options *opt, struct strbuf *path,\n-\t\t struct tree_desc *t1, struct tree_desc *t2)\n+/*\n+ * convert path -> opt->diff_*() callbacks\n+ *\n+ * emits diff to parent0 only.\n+ */\n+static int emit_diff_p0only(struct diff_options *opt, struct combine_diff_path *p)\n {\n-\tunsigned int mode1 = t1 ? t1->entry.mode : 0;\n-\tunsigned int mode2 = t2 ? t2->entry.mode : 0;\n-\n-\tif (mode1 && mode2) {\n-\t\topt->change(opt, mode1, mode2, t1->entry.sha1, t2->entry.sha1,\n-\t\t\t1, 1, path->buf, 0, 0);\n+\tstruct combine_diff_parent *p0 = &p->parent[0];\n+\tif (p->mode && p0->mode) {\n+\t\topt->change(opt, p0->mode, p->mode, p0->sha1, p->sha1,\n+\t\t\t1, 1, p->path, 0, 0);\n \t}\n \telse {\n \t\tconst unsigned char *sha1;\n \t\tunsigned int mode;\n \t\tint addremove;\n \n-\t\tif (mode2) {\n+\t\tif (p->mode) {\n \t\t\taddremove = '+';\n-\t\t\tsha1 = t2->entry.sha1;\n-\t\t\tmode = mode2;\n+\t\t\tsha1 = p->sha1;\n+\t\t\tmode = p->mode;\n \t\t}\n \t\telse {\n \t\t\taddremove = '-';\n-\t\t\tsha1 = t1->entry.sha1;\n-\t\t\tmode = mode1;\n+\t\t\tsha1 = p0->sha1;\n+\t\t\tmode = p0->mode;\n \t\t}\n \n-\t\topt->add_remove(opt, addremove, mode, sha1, 1, path->buf, 0);\n+\t\topt->add_remove(opt, addremove, mode, sha1, 1, p->path, 0);\n \t}\n+\n+\treturn 0;\t/* = no need to keep allocated combine_diff_path */\n }\n \n \n-/* new path should be added to diff\n+/*\n+ * Make a new combine_diff_path from path/mode/sha1\n+ * and append it to paths list tail.\n+ *\n+ * Memory for created elements could be reused:\n+ *\n+ *\t- if last->next == NULL, the memory is allocated;\n+ *\n+ *\t- if last->next != NULL, it is assumed that p=last->next was returned\n+ *\t earlier by this function, and p->next was *not* modified.\n+ *\t The memory is then reused from p.\n+ *\n+ * so for clients,\n+ *\n+ * - if you do need to keep the element\n+ *\n+ *\tp = __path_appendnew(p, ...);\n+ *\tprocess(p);\n+ *\tp->next = NULL;\n+ *\n+ * - if you don't need to keep the element after processing\n+ *\n+ *\tpprev = p;\n+ *\tp = __path_appendnew(p, ...);\n+ *\tprocess(p);\n+ *\tp = pprev;\n+ *\t; don't forget to free tail->next in the end\n+ *\n+ * p->parent[] remains uninitialized.\n+ */\n+static struct combine_diff_path *__path_appendnew(struct combine_diff_path *last,\n+\tint nparent, const struct strbuf *base, const char *path, int pathlen,\n+\tunsigned mode, const unsigned char *sha1)\n+{\n+\tstruct combine_diff_path *p;\n+\tint len = base->len + pathlen;\n+\tint alloclen = combine_diff_path_size(nparent, len);\n+\n+\t/* if last->next is !NULL - it is a pre-allocated memory, we can reuse */\n+\tp = last->next;\n+\tif (p && (alloclen > (intptr_t)p->next)) {\n+\t\tfree(p);\n+\t\tp = NULL;\n+\t}\n+\n+\tif (!p) {\n+\t\tp = xmalloc(alloclen);\n+\n+\t\t/*\n+\t\t * until we go to it next round, .next holds how many bytes we\n+\t\t * allocated (for faster realloc - we don't need copying old data).\n+\t\t */\n+\t\tp->next = (struct combine_diff_path *)(intptr_t)alloclen;\n+\t}\n+\n+\tlast->next = p;\n+\n+\tp->path = (char *)&(p->parent[nparent]);\n+\tmemcpy(p->path, base->buf, base->len);\n+\tmemcpy(p->path + base->len, path, pathlen);\n+\tp->path[len] = 0;\n+\tp->mode = mode;\n+\thashcpy(p->sha1, sha1 ? sha1 : null_sha1);\n+\n+\treturn p;\n+}\n+\n+/*\n+ * new path should be added to combine diff\n *\n * 3 cases on how/when it should be called and behaves:\n *\n- *\t!t1, t2\t-> path added, parent lacks it\n- *\t t1, !t2\t-> path removed from parent\n- *\t t1, t2\t-> path modified\n+ *\t t, !tp\t\t-> path added, all parents lack it\n+ *\t!t, tp\t\t-> path removed from all parents\n+ *\t t, tp\t\t-> path modified/added\n+ *\t\t\t (M for tp[i]=tp[imin], A otherwise)\n */\n-static void show_path(struct strbuf *base, struct diff_options *opt,\n-\t\t struct tree_desc *t1, struct tree_desc *t2)\n+static struct combine_diff_path *emit_path(struct combine_diff_path *p,\n+\tstruct strbuf *base, struct diff_options *opt, int nparent,\n+\tstruct tree_desc *t, struct tree_desc *tp,\n+\tint imin)\n {\n \tunsigned mode;\n \tconst char *path;\n+\tconst unsigned char *sha1;\n \tint pathlen;\n \tint old_baselen = base->len;\n-\tint isdir, recurse = 0, emitthis = 1;\n+\tint i, isdir, recurse = 0, emitthis = 1;\n \n \t/* at least something has to be valid */\n-\tassert(t1 || t2);\n+\tassert(t || tp);\n \n-\tif (t2) {\n+\tif (t) {\n \t\t/* path present in resulting tree */\n-\t\ttree_entry_extract(t2, &path, &mode);\n-\t\tpathlen = tree_entry_len(&t2->entry);\n+\t\tsha1 = tree_entry_extract(t, &path, &mode);\n+\t\tpathlen = tree_entry_len(&t->entry);\n \t\tisdir = S_ISDIR(mode);\n \t}\n \telse {\n-\t\t/* a path was removed - take path from parent. Also take\n-\t\t * mode from parent, to decide on recursion.\n+\t\t/*\n+\t\t * a path was removed - take path from imin parent. Also take\n+\t\t * mode from that parent, to decide on recursion(1).\n+\t\t *\n+\t\t * 1) all modes for tp[k]=tp[imin] should be the same wrt\n+\t\t * S_ISDIR, thanks to base_name_compare().\n \t\t */\n-\t\ttree_entry_extract(t1, &path, &mode);\n-\t\tpathlen = tree_entry_len(&t1->entry);\n+\t\ttree_entry_extract(&tp[imin], &path, &mode);\n+\t\tpathlen = tree_entry_len(&tp[imin].entry);\n \n \t\tisdir = S_ISDIR(mode);\n+\t\tsha1 = NULL;\n \t\tmode = 0;\n \t}\n \n@@ -107,18 +206,80 @@ static void show_path(struct strbuf *base, struct diff_options *opt,\n \t\temitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);\n \t}\n \n-\tstrbuf_add(base, path, pathlen);\n+\tif (emitthis) {\n+\t\tint keep;\n+\t\tstruct combine_diff_path *pprev = p;\n+\t\tp = __path_appendnew(p, nparent, base, path, pathlen, mode, sha1);\n \n-\tif (emitthis)\n-\t\temit_diff(opt, base, t1, t2);\n+\t\ti = 0; do {\n+\t\t\t/*\n+\t\t\t * tp[i] is valid, if present and if tp[i]==tp[imin] -\n+\t\t\t * otherwise, we should ignore it.\n+\t\t\t */\n+\t\t\tint tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);\n+\n+\t\t\tconst unsigned char *sha1_i;\n+\t\t\tunsigned mode_i;\n+\n+\t\t\tp->parent[i].status =\n+\t\t\t\t!t ? DIFF_STATUS_DELETED :\n+\t\t\t\t\ttpi_valid ?\n+\t\t\t\t\t\tDIFF_STATUS_MODIFIED :\n+\t\t\t\t\t\tDIFF_STATUS_ADDED;\n+\n+\t\t\tif (tpi_valid) {\n+\t\t\t\tsha1_i = tp[i].entry.sha1;\n+\t\t\t\tmode_i = tp[i].entry.mode;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\tsha1_i = NULL;\n+\t\t\t\tmode_i = 0;\n+\t\t\t}\n+\n+\t\t\tp->parent[i].mode = mode_i;\n+\t\t\thashcpy(p->parent[i].sha1, sha1_i ? sha1_i : null_sha1);\n+\t\t} while (++i < nparent);\n+\n+\t\tkeep = 1;\n+\t\tif (opt->pathchange)\n+\t\t\tkeep = opt->pathchange(opt, p);\n+\n+\t\t/*\n+\t\t * If a path was filtered or consumed - we don't need to add it\n+\t\t * to the list and can reuse its memory, leaving it as\n+\t\t * pre-allocated element on the tail.\n+\t\t *\n+\t\t * On the other hand, if path needs to be kept, we need to\n+\t\t * correct its .next to NULL, as it was pre-initialized to how\n+\t\t * much memory was allocated.\n+\t\t *\n+\t\t * see __path_appendnew() for details.\n+\t\t */\n+\t\tif (!keep)\n+\t\t\tp = pprev;\n+\t\telse\n+\t\t\tp->next = NULL;\n+\t}\n \n \tif (recurse) {\n+\t\tconst unsigned char **parents_sha1;\n+\n+\t\tparents_sha1 = alloca(nparent * sizeof(parents_sha1[0]));\n+\t\ti = 0; do {\n+\t\t\t/* same rule as in emitthis */\n+\t\t\tint tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);\n+\n+\t\t\tparents_sha1[i] = tpi_valid ? tp[i].entry.sha1\n+\t\t\t\t\t\t : NULL;\n+\t\t} while (++i < nparent);\n+\n+\t\tstrbuf_add(base, path, pathlen);\n \t\tstrbuf_addch(base, '/');\n-\t\t__diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,\n-\t\t\t\t t2 ? t2->entry.sha1 : NULL, base, opt);\n+\t\tp = __diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);\n \t}\n \n \tstrbuf_setlen(base, old_baselen);\n+\treturn p;\n }\n \n static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,\n@@ -137,59 +298,262 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,\n \t}\n }\n \n-int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,\n-\t\t struct strbuf *base, struct diff_options *opt)\n+\n+/*\n+ * generate paths for combined diff D(sha1,parents_sha1[])\n+ *\n+ * Resulting paths are appended to combine_diff_path linked list, and also, are\n+ * emitted on the go via opt->pathchange() callback, so it is possible to\n+ * process the result as batch or incrementally.\n+ *\n+ * The paths are generated scanning new tree and all parents trees\n+ * simultaneously, similarly to what diff_tree() was doing for 2 trees.\n+ * The theory behind such scan is as follows:\n+ *\n+ *\n+ * D(A,X1...Xn) calculation scheme\n+ * -------------------------------\n+ *\n+ * D(A,X1...Xn) = D(A,X1) ^ ... ^ D(A,Xn)\t(regarding resulting paths set)\n+ *\n+ *\tD(A,Xj)\t\t- diff between A..Xj\n+ *\tD(A,X1...Xn)\t- combined diff from A to parents X1,...,Xn\n+ *\n+ *\n+ * We start from all trees, which are sorted, and compare their entries in\n+ * lock-step:\n+ *\n+ *\t A X1 Xn\n+ *\t - - -\n+ *\t|a| |x1| |xn|\n+ *\t|-| |--| ... |--| i = argmin(x1...xn)\n+ *\t| | | | | |\n+ *\t|-| |--| |--|\n+ *\t|.| |. | |. |\n+ *\t . . .\n+ *\t . . .\n+ *\n+ * at any time there could be 3 cases:\n+ *\n+ *\t1) a < xi;\n+ *\t2) a > xi;\n+ *\t3) a = xi.\n+ *\n+ * Schematic deduction of what every case means, and what to do, follows:\n+ *\n+ * 1) a < xi -> ∀j a ∉ Xj -> \"+a\" ∈ D(A,Xj) -> D += \"+a\"; a↓\n+ *\n+ * 2) a > xi\n+ *\n+ * 2.1) ∃j: xj > xi -> \"-xi\" ∉ D(A,Xj) -> D += ø; ∀ xk=xi xk↓\n+ * 2.2) ∀j xj = xi -> xj ∉ A -> \"-xj\" ∈ D(A,Xj) -> D += \"-xi\"; ∀j xj↓\n+ *\n+ * 3) a = xi\n+ *\n+ * 3.1) ∃j: xj > xi -> \"+a\" ∈ D(A,Xj) -> only xk=xi remains to investigate\n+ * 3.2) xj = xi -> investigate δ(a,xj)\n+ * |\n+ * |\n+ * v\n+ *\n+ * 3.1+3.2) looking at δ(a,xk) ∀k: xk=xi - if all != ø ->\n+ *\n+ * ⎧δ(a,xk) - if xk=xi\n+ * -> D += ⎨\n+ * ⎩\"+a\" - if xk>xi\n+ *\n+ *\n+ * in any case a↓ ∀ xk=xi xk↓\n+ *\n+ *\n+ * ~~~~~~~~\n+ *\n+ * NOTE\n+ *\n+ *\tUsual diff D(A,B) is by definition the same as combined diff D(A,[B]),\n+ *\tso this diff paths generator can, and is used, for plain diffs\n+ *\tgeneration too.\n+ *\n+ *\tPlease keep attention to the common D(A,[B]) case when working on the\n+ *\tcode, in order not to slow it down.\n+ *\n+ * NOTE\n+ *\tnparent must be > 0.\n+ */\n+\n+\n+/* ∀ xk=xi xk↓ */\n+static inline void update_tp_entries(struct tree_desc *tp, int nparent)\n+{\n+\tint i;\n+\ti = 0; do {\n+\t\tif (!(tp[i].entry.mode & S_IFXMIN_NEQ))\n+\t\t\tupdate_tree_entry(&tp[i]);\n+\t} while (++i < nparent);\n+}\n+\n+static struct combine_diff_path *__diff_tree_paths(\n+\tstruct combine_diff_path *p, const unsigned char *sha1,\n+\tconst unsigned char **parents_sha1, int nparent,\n+\tstruct strbuf *base, struct diff_options *opt)\n {\n-\tstruct tree_desc t1, t2;\n-\tvoid *t1tree, *t2tree;\n+\tstruct tree_desc t, *tp;\n+\tvoid *ttree, **tptree;\n+\tint i;\n \n-\tt1tree = fill_tree_descriptor(&t1, old);\n-\tt2tree = fill_tree_descriptor(&t2, new);\n+\ttp = alloca(nparent * sizeof(tp[0]));\n+\ttptree = alloca(nparent * sizeof(tptree[0]));\n+\n+\t/*\n+\t * load parents first, as they are probably already cached.\n+\t *\n+\t * ( log_tree_diff() parses commit->parent before calling here via\n+\t * diff_tree_sha1(parent, commit) )\n+\t */\n+\ti = 0; do {\n+\t\ttptree[i] = fill_tree_descriptor(&tp[i], parents_sha1[i]);\n+\t} while (++i < nparent);\n+\tttree = fill_tree_descriptor(&t, sha1);\n \n \t/* Enable recursion indefinitely */\n \topt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);\n \n \tfor (;;) {\n-\t\tint cmp;\n+\t\tint imin, cmp;\n \n \t\tif (diff_can_quit_early(opt))\n \t\t\tbreak;\n+\n \t\tif (opt->pathspec.nr) {\n-\t\t\tskip_uninteresting(&t1, base, opt);\n-\t\t\tskip_uninteresting(&t2, base, opt);\n+\t\t\tskip_uninteresting(&t, base, opt);\n+\t\t\tfor (i = 0; i < nparent; i++)\n+\t\t\t\tskip_uninteresting(&tp[i], base, opt);\n \t\t}\n-\t\tif (!t1.size && !t2.size)\n-\t\t\tbreak;\n \n-\t\tcmp = tree_entry_pathcmp(&t1, &t2);\n+\t\t/* comparing is finished when all trees are done */\n+\t\tif (!t.size) {\n+\t\t\tint done = 1;\n+\t\t\ti = 0; do {\n+\t\t\t\tif (tp[i].size) {\n+\t\t\t\t\tdone = 0;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t} while (++i < nparent);\n+\t\t\tif (done)\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\t/*\n+\t\t * lookup imin = argmin(x1...xn),\n+\t\t * mark entries whether they =tp[imin] along the way\n+\t\t */\n+\t\timin = 0;\n+\t\ttp[0].entry.mode &= ~S_IFXMIN_NEQ;\n+\n+\t\tfor (i = 1; i < nparent; ++i) {\n+\t\t\tcmp = tree_entry_pathcmp(&tp[i], &tp[imin]);\n+\t\t\tif (cmp < 0) {\n+\t\t\t\timin = i;\n+\t\t\t\ttp[i].entry.mode &= ~S_IFXMIN_NEQ;\n+\t\t\t}\n+\t\t\telse if (cmp == 0) {\n+\t\t\t\ttp[i].entry.mode &= ~S_IFXMIN_NEQ;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\ttp[i].entry.mode |= S_IFXMIN_NEQ;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* fixup markings for entries before imin */\n+\t\tfor (i = 0; i < imin; ++i)\n+\t\t\ttp[i].entry.mode |= S_IFXMIN_NEQ;\t/* x[i] > x[imin] */\n+\n \n-\t\t/* t1 = t2 */\n-\t\tif (cmp == 0) {\n-\t\t\tif (DIFF_OPT_TST(opt, FIND_COPIES_HARDER) ||\n-\t\t\t hashcmp(t1.entry.sha1, t2.entry.sha1) ||\n-\t\t\t (t1.entry.mode != t2.entry.mode))\n-\t\t\t\tshow_path(base, opt, &t1, &t2);\n \n-\t\t\tupdate_tree_entry(&t1);\n-\t\t\tupdate_tree_entry(&t2);\n+\t\t/* compare a vs x[imin] */\n+\t\tcmp = tree_entry_pathcmp(&t, &tp[imin]);\n+\n+\t\t/* a = xi */\n+\t\tif (cmp == 0) {\n+\t\t\t/* are either xk > xi or diff(a,xk) != ø ? */\n+\t\t\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {\n+\t\t\t\ti = 0; do {\n+\t\t\t\t\t/* x[i] > x[imin] */\n+\t\t\t\t\tif (tp[i].entry.mode & S_IFXMIN_NEQ)\n+\t\t\t\t\t\tcontinue;\n+\n+\t\t\t\t\t/* diff(a,xk) != ø */\n+\t\t\t\t\tif (hashcmp(t.entry.sha1, tp[i].entry.sha1) ||\n+\t\t\t\t\t (t.entry.mode != tp[i].entry.mode))\n+\t\t\t\t\t\tcontinue;\n+\n+\t\t\t\t\tgoto skip_emit_t_tp;\n+\t\t\t\t} while (++i < nparent);\n+\t\t\t}\n+\n+\t\t\t/* D += {δ(a,xk) if xk=xi; \"+a\" if xk > xi} */\n+\t\t\tp = emit_path(p, base, opt, nparent,\n+\t\t\t\t\t&t, tp, imin);\n+\n+\t\tskip_emit_t_tp:\n+\t\t\t/* a↓, ∀ xk=ximin xk↓ */\n+\t\t\tupdate_tree_entry(&t);\n+\t\t\tupdate_tp_entries(tp, nparent);\n \t\t}\n \n-\t\t/* t1 < t2 */\n+\t\t/* a < xi */\n \t\telse if (cmp < 0) {\n-\t\t\tshow_path(base, opt, &t1, /*t2=*/NULL);\n-\t\t\tupdate_tree_entry(&t1);\n+\t\t\t/* D += \"+a\" */\n+\t\t\tp = emit_path(p, base, opt, nparent,\n+\t\t\t\t\t&t, /*tp=*/NULL, -1);\n+\n+\t\t\t/* a↓ */\n+\t\t\tupdate_tree_entry(&t);\n \t\t}\n \n-\t\t/* t1 > t2 */\n+\t\t/* a > xi */\n \t\telse {\n-\t\t\tshow_path(base, opt, /*t1=*/NULL, &t2);\n-\t\t\tupdate_tree_entry(&t2);\n+\t\t\t/* ∀j xj=ximin -> D += \"-xi\" */\n+\t\t\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {\n+\t\t\t\ti = 0; do {\n+\t\t\t\t\tif (tp[i].entry.mode & S_IFXMIN_NEQ)\n+\t\t\t\t\t\tgoto skip_emit_tp;\n+\t\t\t\t} while (++i < nparent);\n+\t\t\t}\n+\n+\t\t\tp = emit_path(p, base, opt, nparent,\n+\t\t\t\t\t/*t=*/NULL, tp, imin);\n+\n+\t\tskip_emit_tp:\n+\t\t\t/* ∀ xk=ximin xk↓ */\n+\t\t\tupdate_tp_entries(tp, nparent);\n \t\t}\n \t}\n \n-\tfree(t2tree);\n-\tfree(t1tree);\n-\treturn 0;\n+\tfree(ttree);\n+\tfor (i = nparent-1; i >= 0; i--)\n+\t\tfree(tptree[i]);\n+\n+\treturn p;\n+}\n+\n+struct combine_diff_path *diff_tree_paths(\n+\tstruct combine_diff_path *p, const unsigned char *sha1,\n+\tconst unsigned char **parents_sha1, int nparent,\n+\tstruct strbuf *base, struct diff_options *opt)\n+{\n+\tp = __diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);\n+\n+\t/*\n+\t * free pre-allocated last element, if any\n+\t * (see __path_appendnew() for details about why)\n+\t */\n+\tif (p->next) {\n+\t\tfree(p->next);\n+\t\tp->next = NULL;\n+\t}\n+\n+\treturn p;\n }\n \n /*\n@@ -300,6 +664,24 @@ static void try_to_follow_renames(const unsigned char *old, const unsigned char\n \tq->nr = 1;\n }\n \n+int __diff_tree_sha1(const unsigned char *old, const unsigned char *new, struct strbuf *base, struct diff_options *opt)\n+{\n+\tstruct combine_diff_path phead, *p;\n+\tconst unsigned char *parents_sha1[1] = {old};\n+\n+\tphead.next = NULL;\n+\topt->pathchange = emit_diff_p0only;\n+\tdiff_tree_paths(&phead, new, parents_sha1, 1, base, opt);\n+\n+\tfor (p = phead.next; p;) {\n+\t\tstruct combine_diff_path *pprev = p;\n+\t\tp = p->next;\n+\t\tfree(pprev);\n+\t}\n+\n+\treturn 0;\n+}\n+\n int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base_str, struct diff_options *opt)\n {\n \tstruct strbuf base;\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234764","messageId":"20140214121604.GC3416@tugrik.mns.mnsspb.ru","threadId":"35860","inReplyTo":"xmqq7g8ylrdv.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 2/2] combine-diff: speed it up, by using multiparent diff tree-walker directly","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-14T12:16:04Z","receivedAt":"2014-02-14T12:16:04Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Thu, Feb 13, 2014 at 11:55:08AM -0800, Junio C Hamano wrote:\n> Kirill Smelkov writes:\n> \n> > +\tif (need_generic_pathscan) {\n> > +\t\t/* NOTE generic case also handles --stat, as it computes\n> > +\t\t * diff(sha1,parent_i) for all i to do the job, specifically\n> > +\t\t * for parent0.\n> > +\t\t */\n> > +\t\tpaths = find_paths_generic(sha1, parents, &diffopts);\n> > +\t}\n> > +\telse {\n> > +\t\tpaths = find_paths_multitree(sha1, parents, &diffopts);\n> > +\n> > +\t\t/* show stat against the first parent even\n> > +\t\t * when doing combined diff.\n> > +\t\t */\n> > +\t\tint stat_opt = (opt->output_format &\n> > +\t\t\t\t(DIFF_FORMAT_NUMSTAT|DIFF_FORMAT_DIFFSTAT));\n> \n> /*\n> * We see decl-after-stmt here.\n> * Also please have slash-asterisk and asterisk-slash\n> * at the beginning and the end of a multi-line comment\n> * block on their own line.\n> */\n\nSorry, and thanks for noticing. I usually compile with -Wall, but it\nseems it is not enough without explicitly specifying -std=c89.\n\nComments corrected and the decl-after-stmt fixed, and this time I've\ncompiled with `-std=c89 -pedantic -Wall -Wextra` to assure no new\nwarnings are introduced.\n\nPlease apply and thanks beforehand,\nKirill\n\n---- 8< ----\nFrom: Kirill Smelkov \nSubject: [PATCH v2 2/2] combine-diff: speed it up, by using multiparent diff\n tree-walker directly\n\nAs was recently shown (c839f1bd \"combine-diff: optimize\ncombine_diff_path sets intersection\"), combine-diff runs very slowly. In\nthat commit we optimized paths sets intersection, but that accounted\nonly for ~ 25% of the slowness, and as my tracing showed, for linux.git\nv3.10..v3.11, for merges a lot of time is spent computing\ndiff(commit,commit^2) just to only then intersect that huge diff to\nalmost small set of files from diff(commit,commit^1).\n\nIn previous commit, we described the problem in more details, and\nreworked the diff tree-walker to be general one - i.e. to work in\nmultiple parent case too. Now is the time to take advantage of it for\nfinding paths for combine diff.\n\nThe implementation is straightforward - if we know, we can get generated\ndiff paths directly, and at present that means no diff filtering or\nrename/copy detection was requested(*), we can call multiparent tree-walker\ndirectly and get ready paths.\n\n(*) because e.g. at present, all diffcore transformations work on\n diff_filepair queues, but in the future, that limitation can be\n lifted, if filters would operate directly on combine_diff_paths.\n\nTimings for `git log --raw --no-abbrev --no-renames` without `-c` (\"git log\")\nand with `-c` (\"git log -c\") and with `-c --merges` (\"git log -c --merges\")\nbefore and after the patch are as follows:\n\n linux.git v3.10..v3.11\n\n log log -c log -c --merges\n\n before 1.9s 16.4s 15.2s\n after 1.9s 2.4s 1.1s\n\nThe result stayed the same.\n\nSigned-off-by: Kirill Smelkov \n---\n combine-diff.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++----\n diff.c | 1 +\n 2 files changed, 84 insertions(+), 5 deletions(-)\n\nChages since v1:\n\n - fixed declaration-after-statement, and reworked multiline comments to\n start and end with /* and */ on separate lines.\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 1732dfd..12764fb 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1303,7 +1303,7 @@ static const char *path_path(void *obj)\n \n \n /* find set of paths that every parent touches */\n-static struct combine_diff_path *find_paths(const unsigned char *sha1,\n+static struct combine_diff_path *find_paths_generic(const unsigned char *sha1,\n \tconst struct sha1_array *parents, struct diff_options *opt)\n {\n \tstruct combine_diff_path *paths = NULL;\n@@ -1316,6 +1316,7 @@ static struct combine_diff_path *find_paths(const unsigned char *sha1,\n \t/* tell diff_tree to emit paths in sorted (=tree) order */\n \topt->orderfile = NULL;\n \n+\t/* D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn) (wrt paths) */\n \tfor (i = 0; i < num_parent; i++) {\n \t\t/*\n \t\t * show stat against the first parent even when doing\n@@ -1346,6 +1347,35 @@ static struct combine_diff_path *find_paths(const unsigned char *sha1,\n }\n \n \n+/*\n+ * find set of paths that everybody touches, assuming diff is run without\n+ * rename/copy detection, etc, comparing all trees simultaneously (= faster).\n+ */\n+static struct combine_diff_path *find_paths_multitree(\n+\tconst unsigned char *sha1, const struct sha1_array *parents,\n+\tstruct diff_options *opt)\n+{\n+\tint i, nparent = parents->nr;\n+\tconst unsigned char **parents_sha1;\n+\tstruct combine_diff_path paths_head;\n+\tstruct strbuf base;\n+\n+\tparents_sha1 = xmalloc(nparent * sizeof(parents_sha1[0]));\n+\tfor (i = 0; i < nparent; i++)\n+\t\tparents_sha1[i] = parents->sha1[i];\n+\n+\t/* fake list head, so worker can assume it is non-NULL */\n+\tpaths_head.next = NULL;\n+\n+\tstrbuf_init(&base, PATH_MAX);\n+\tdiff_tree_paths(&paths_head, sha1, parents_sha1, nparent, &base, opt);\n+\n+\tstrbuf_release(&base);\n+\tfree(parents_sha1);\n+\treturn paths_head.next;\n+}\n+\n+\n void diff_tree_combined(const unsigned char *sha1,\n \t\t\tconst struct sha1_array *parents,\n \t\t\tint dense,\n@@ -1355,6 +1385,7 @@ void diff_tree_combined(const unsigned char *sha1,\n \tstruct diff_options diffopts;\n \tstruct combine_diff_path *p, *paths;\n \tint i, num_paths, needsep, show_log_first, num_parent = parents->nr;\n+\tint need_generic_pathscan;\n \n \t/* nothing to do, if no parents */\n \tif (!num_parent)\n@@ -1377,11 +1408,58 @@ void diff_tree_combined(const unsigned char *sha1,\n \n \t/* find set of paths that everybody touches\n \t *\n-\t * NOTE find_paths() also handles --stat, as it computes\n-\t * diff(sha1,parent_i) for all i to do the job, specifically\n-\t * for parent0.\n+\t * NOTE\n+\t *\n+\t * Diffcore transformations are bound to diff_filespec and logic\n+\t * comparing two entries - i.e. they do not apply directly to combine\n+\t * diff.\n+\t *\n+\t * If some of such transformations is requested - we launch generic\n+\t * path scanning, which works significantly slower compared to\n+\t * simultaneous all-trees-in-one-go scan in find_paths_multitree().\n+\t *\n+\t * TODO some of the filters could be ported to work on\n+\t * combine_diff_paths - i.e. all functionality that skips paths, so in\n+\t * theory, we could end up having only multitree path scanning.\n+\t *\n+\t * NOTE please keep this semantically in sync with diffcore_std()\n \t */\n-\tpaths = find_paths(sha1, parents, &diffopts);\n+\tneed_generic_pathscan = opt->skip_stat_unmatch\t||\n+\t\t\tDIFF_OPT_TST(opt, FOLLOW_RENAMES)\t||\n+\t\t\topt->break_opt != -1\t||\n+\t\t\topt->detect_rename\t||\n+\t\t\topt->pickaxe\t\t||\n+\t\t\topt->filter;\n+\n+\n+\tif (need_generic_pathscan) {\n+\t\t/*\n+\t\t * NOTE generic case also handles --stat, as it computes\n+\t\t * diff(sha1,parent_i) for all i to do the job, specifically\n+\t\t * for parent0.\n+\t\t */\n+\t\tpaths = find_paths_generic(sha1, parents, &diffopts);\n+\t}\n+\telse {\n+\t\tint stat_opt;\n+\t\tpaths = find_paths_multitree(sha1, parents, &diffopts);\n+\n+\t\t/*\n+\t\t * show stat against the first parent even\n+\t\t * when doing combined diff.\n+\t\t */\n+\t\tstat_opt = (opt->output_format &\n+\t\t\t\t(DIFF_FORMAT_NUMSTAT|DIFF_FORMAT_DIFFSTAT));\n+\t\tif (stat_opt) {\n+\t\t\tdiffopts.output_format = stat_opt;\n+\n+\t\t\tdiff_tree_sha1(parents->sha1[0], sha1, \"\", &diffopts);\n+\t\t\tdiffcore_std(&diffopts);\n+\t\t\tif (opt->orderfile)\n+\t\t\t\tdiffcore_order(opt->orderfile);\n+\t\t\tdiff_flush(&diffopts);\n+\t\t}\n+\t}\n \n \t/* find out number of surviving paths */\n \tfor (num_paths = 0, p = paths; p; p = p->next)\ndiff --git a/diff.c b/diff.c\nindex cda4aa8..f2fff46 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4764,6 +4764,7 @@ void diffcore_fix_diff_index(struct diff_options *options)\n \n void diffcore_std(struct diff_options *options)\n {\n+\t/* NOTE please keep the following in sync with diff_tree_combined() */\n \tif (options->skip_stat_unmatch)\n \t\tdiffcore_skip_stat_unmatch(options);\n \tif (!options->found_follow) {\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234780","messageId":"xmqqppmpiojn.fsf@gitster.dls.corp.google.com","threadId":"35860","inReplyTo":"20140214121529.GB3416@tugrik.mns.mnsspb.ru","subject":"Re: [PATCH 1/2] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-14T17:37:00Z","receivedAt":"2014-02-14T17:37:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> ---- 8< ----\n> From: Kirill Smelkov \n> Subject: [PATCH v2 1/2] tree-diff: rework diff_tree() to generate diffs for\n> multiparent cases as well\n> MIME-Version: 1.0\n> Content-Type: text/plain; charset=UTF-8\n> Content-Transfer-Encoding: 8bit\n\nThe last three do not belong here. Only From, Date and Subject are\nrelevant and taken as in-body headers.\n\nFor that matter, as the From and Subject above are exactly the same\nas what you have on the e-mail header, you do not want any of them.\n\nI'll strip them out here, so no need to resend. Thanks.\n\n> Previously diff_tree(), which is now named __diff_tree_sha1(), was\n\nThat name with two leading underscores is a rather unfortunate,\nespecially for a function that is not a file scope static. No way\nto rename this to something more sensible?\n\n> That impedance mismatch *hurts* *performance* *badly* for generating\n> combined diffs - in c839f1bd (combine-diff: optimize combine_diff_path\n\nPlease avoid referring to a commit that is not in 'master' by its\nobject name. It can be reworked later and get a different name.\n\n> That slowness comes from the fact that currently, while generating\n> combined diff, a lot of time is spent computing diff(commit,commit^2)\n> just to only then intersect that huge diff to almost small set of files\n> from diff(commit,commit^1).\n\nGood observation.\n\n> |a| |b| a < b -> a ∉ B -> D(A,B) += +a a↓\n> |-| |-| a > b -> b ∉ A -> D(A,B) += -b b↓\n> | | | | a = b -> investigate δ(a,b) a↓ b↓\n\nIn both the \"n-parallel\" and \"diff-tree\", when an entry 'a' is a\ntree, I take this \"D(A,B) += +a\" to mean (recursively) adding all\nthe paths within 'a' to the result as addition. Sounds sensible.\n\n> D(A,B)\n>\n> is by definition the same as combined diff\n>\n> D(A,[B]),\n>\n> so if we could rework the code for common case and make it be not slower\n> for nparent=1 case, usual diff(t1,t2) generation will not be slower, and\n> multiparent diff tree-walker would greatly benefit generating\n> combine-diff.\n\nOK.\n\n> What we do is as follows:\n>\n> 1) diff tree-walker __diff_tree_sha1() is internally reworked to be\n> a paths generator (new name diff_tree_paths()), with each generated path\n> being `struct combine_diff_path` with info for path, new sha1,mode and for\n> every parent which sha1,mode it was in it.\n>\n> 2) From that info, we can still generate usual diff queue with\n> struct diff_filepairs, via \"exporting\" generated\n> combine_diff_path, if we know we run for nparent=1 case.\n> (see emit_diff() which is now named emit_diff_p0only())\n\ns/p0/first_parent_/; perhaps?\n\n> 3) In order for diff_can_quit_early(), which checks\n>\n> DIFF_OPT_TST(opt, HAS_CHANGES))\n>\n> to work, that exporting have to be happening not in bulk, but\n> incrementally, one diff path at a time.\n\nGood thinking.\n\n> Some notes(*):\n>\n> 1) For loops,\n>\n> i = 0; do { ... } while (++i < nparent);\n>\n> is used instead of\n>\n> for (i = 0; i < nparent; ++i)\n> ...\n>\n> because for the former case, the compiler have to emit additional\n> prologue code which checks for i >= nparent case before entering the\n> loop.\n>\n> As we require nparent must be >0, that additional overhead\n> conflicts with the \"runs not slower for nparent=1 case than before\"\n> goal.\n\nUnfortunate. I'd rather see us stick to more readable and familiar\nform for maintainability if this were not measurable.\n\n> 2) alloca(), for small arrays, is used for the same reason - if we change\n> it to xmalloc()/free() the timings get worse\n\nDo you see any use of it outside compat/?\n\nI thought we specifically avoid alloca() for portability. Also we\ndo not use variable-length-arrays on the stack either, I think.\n\n> 3) For every parent tree, we need to keep a tag, whether entry from that\n> parent equals to entry from minimal parent. For performance reasons I'm\n> keeping that tag in entry's mode field in unused bit - see S_IFXMIN_NEQ.\n\nUnfortunate, but I do not see another place to keep this\ninformation offhand (nor implement this approach without keeping\nthat piece of information).\n\n> P.S. and combined diff is not some exotic/for-play-only stuff - for\n\nNo need to convince us about that ;-)\n\n> example for a program I write to represent Git archives as readonly\n> filesystem, there is initial scan with\n>\n> `git log --reverse --raw --no-abbrev --no-renames -c`\n>\n> to extract log of what was created/changed when, as a result building a\n> map\n>\n> {} sha1 -> in which commit (and date) a content was added\n>\n> that `-c` means also show combined diff for merges, and without them, if\n> a merge is non-trivial (merges changes from two parents with both having\n> separate changes to a file), or an evil one, the map will not be full,\n> i.e. some valid sha1 would be absent from it.\n>\n> That case was my initial motivation for combined diffs speedup.\n\nI wonder if this machinery can be reused for \"log -m\" as well (or\nperhaps you do that already?). After all, by performing a single\nparallel scan, you are gathering all the necessary information to\nlet you pretend that you did N pairwise diff-tree.\n\n> diff --git a/tree-diff.c b/tree-diff.c\n> index ab61a0a..2b7c991 100644\n> --- a/tree-diff.c\n> +++ b/tree-diff.c\n> @@ -7,6 +7,25 @@\n> #include \"tree.h\"\n> \n> /*\n> + * internal mode marker, saying a tree entry != entry of tp[imin]\n> + * (see __diff_tree_paths for what it means there)\n> + *\n> + * it *must* not overlap with any valid modes, and we will update/use/emit\n> + * entry for diff only with it unset. Only non-overlapping to valid modes is\n> + * required, because mode in tree_desc, comes here canonicalized via\n> + * canon_mode().\n> + *\n> + * the definition assumes unsigned is at least 32 bits.\n> + */\n> +#define S_IFXMIN_NEQ\t0x80000000\n\nTo allow better coordination across multiple codepaths that deal\nwith modes, I am wondering if this should be defined in cache.h\nwhere made-up S_FIGITLINK and S_IFINVALID are defined (note the\ncomment that is there, as well).\n\n> +static struct combine_diff_path *__diff_tree_paths(\n> +\tstruct combine_diff_path *p, const unsigned char *sha1,\n> +\tconst unsigned char **parents_sha1, int nparent,\n> +\tstruct strbuf *base, struct diff_options *opt);\n\nMost of our code do not name private helper functions with leading\nunderscores.\n\nI do like the direction this is going, but it looks to me that\n\"struct combine_diff\" is now misnamed, because it no longer is about\ncombined diff. You are introducing a good framework for n-way diff,\nand producing combined diff (i.e. -c or --cc) is now merely one way\nto use that framework. We may want to clean these names up after\nthis series settles---perhaps \"struct nway_diff\" or something.\n\n> +\n> +/*\n> * Compare two tree entries, taking into account only path/S_ISDIR(mode),\n> * but not their sha1's.\n> *\n> @@ -33,72 +52,152 @@ static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)\n> }\n> \n> \n> -/* convert path, t1/t2 -> opt->diff_*() callbacks */\n> -static void emit_diff(struct diff_options *opt, struct strbuf *path,\n> -\t\t struct tree_desc *t1, struct tree_desc *t2)\n> +/*\n> + * convert path -> opt->diff_*() callbacks\n> + *\n> + * emits diff to parent0 only.\n\nPlease call that \"first parent\".\n\n> + */\n\n\"Returns 0 to tell the caller that we are done with p and it can be\nfreed\" or something?\n\n> +static int emit_diff_p0only(struct diff_options *opt, struct combine_diff_path *p)\n> {\n> ...\n> +\n> +\treturn 0;\t/* = no need to keep allocated combine_diff_path */\n\nCurious; what is that equal sign in the comment?\n"},{"id":"234882","messageId":"20140216080829.GA3820@mini.zxlink","threadId":"35860","inReplyTo":"xmqqppmpiojn.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 1/2] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well","fromName":"Kirill Smelkov","fromEmail":"kirr@navytux.spb.ru","sentAt":"2014-02-16T08:08:29Z","receivedAt":"2014-02-16T08:08:29Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Fri, Feb 14, 2014 at 09:37:00AM -0800, Junio C Hamano wrote:\n> Kirill Smelkov writes:\n> \n> > Previously diff_tree(), which is now named __diff_tree_sha1(), was\n> \n> That name with two leading underscores is a rather unfortunate,\n> especially for a function that is not a file scope static. No way\n> to rename this to something more sensible?\n\nI agree. In preparatory patches I thought this will go away, but it\nstayed. I'll try to come up with something reasonable.\n\n\n> > That impedance mismatch *hurts* *performance* *badly* for generating\n> > combined diffs - in c839f1bd (combine-diff: optimize combine_diff_path\n> \n> Please avoid referring to a commit that is not in 'master' by its\n> object name. It can be reworked later and get a different name.\n\nI agree, this makes sense. Is it ok to refer to nearby commits, by say\nHEAD~3, if we know we are referring to 3-times previous commit?\n\n\n> > That slowness comes from the fact that currently, while generating\n> > combined diff, a lot of time is spent computing diff(commit,commit^2)\n> > just to only then intersect that huge diff to almost small set of files\n> > from diff(commit,commit^1).\n> \n> Good observation.\n> \n> > |a| |b| a < b -> a ∉ B -> D(A,B) += +a a↓\n> > |-| |-| a > b -> b ∉ A -> D(A,B) += -b b↓\n> > | | | | a = b -> investigate δ(a,b) a↓ b↓\n> \n> In both the \"n-parallel\" and \"diff-tree\", when an entry 'a' is a\n> tree, I take this \"D(A,B) += +a\" to mean (recursively) adding all\n> the paths within 'a' to the result as addition. Sounds sensible.\n\nCorrect.\n\n\n> > D(A,B)\n> >\n> > is by definition the same as combined diff\n> >\n> > D(A,[B]),\n> >\n> > so if we could rework the code for common case and make it be not slower\n> > for nparent=1 case, usual diff(t1,t2) generation will not be slower, and\n> > multiparent diff tree-walker would greatly benefit generating\n> > combine-diff.\n> \n> OK.\n\nThanks. My first goal was to demonstrate it is doable - i.e. we could\njoin two diff tree-walkers into generalized one, and that approach would\nbe sound and have chances to be accepted.\n\n\n> > What we do is as follows:\n> >\n> > 1) diff tree-walker __diff_tree_sha1() is internally reworked to be\n> > a paths generator (new name diff_tree_paths()), with each generated path\n> > being `struct combine_diff_path` with info for path, new sha1,mode and for\n> > every parent which sha1,mode it was in it.\n> >\n> > 2) From that info, we can still generate usual diff queue with\n> > struct diff_filepairs, via \"exporting\" generated\n> > combine_diff_path, if we know we run for nparent=1 case.\n> > (see emit_diff() which is now named emit_diff_p0only())\n> \n> s/p0/first_parent_/; perhaps?\n\nOk.\n\n\n> > 3) In order for diff_can_quit_early(), which checks\n> >\n> > DIFF_OPT_TST(opt, HAS_CHANGES))\n> >\n> > to work, that exporting have to be happening not in bulk, but\n> > incrementally, one diff path at a time.\n> \n> Good thinking.\n\nYes. This requirement made the diff-paths producer be real generator,\nwhich emits paths incrementally, which is imho, could be a good design\nfor making the component more reusable.\n\n\n> > Some notes(*):\n> >\n> > 1) For loops,\n> >\n> > i = 0; do { ... } while (++i < nparent);\n> >\n> > is used instead of\n> >\n> > for (i = 0; i < nparent; ++i)\n> > ...\n> >\n> > because for the former case, the compiler have to emit additional\n> > prologue code which checks for i >= nparent case before entering the\n> > loop.\n> >\n> > As we require nparent must be >0, that additional overhead\n> > conflicts with the \"runs not slower for nparent=1 case than before\"\n> > goal.\n> \n> Unfortunate. I'd rather see us stick to more readable and familiar\n> form for maintainability if this were not measurable.\n\nThe most effect on performance were avoiding mallocs and reduce register\npressure. This too, was measurable, but of lower impact. If giving away\nsome part of percent for nparent=1 case is ok, this could be back to\nusual for loops.\n\nBy the way, I find it a bit unfortunate, we don't have some for-loop\nform with post-conditions in C, only do-while. Another observation, is\nthat it would be good to say to compiler e.g.\n\n assume nparent > 0;\n\nand then in e.g.\n\n for (i = 0; i < nparent; i++)\n ...\n\nthe compiler could know it should not do pre-conditions checks before\nentering the loop.\n\nI've verified, that such behaviour, at least with gcc, could be achieved\nwith\n\n if (nparent <= 0)\n return;\n\nin function prologue - then the compiler deduces, at least with O2, that\nafter return point, nparent is >0, but this adds slight overhead on each\nentry to function, and we have as many calls as there would be\nrecursions.\n\nTo me, the do-while is still readable, but if fors are preferred, I'll\nre-measure what it costs and come back.\n\n\n> > 2) alloca(), for small arrays, is used for the same reason - if we change\n> > it to xmalloc()/free() the timings get worse\n> \n> Do you see any use of it outside compat/?\n> \n> I thought we specifically avoid alloca() for portability. Also we\n> do not use variable-length-arrays on the stack either, I think.\n\nNo, no usage outside compat/ and I knew alloca and VLAs are not used in\nGit codebase for portability, and I understand alloca will be\ncriticized, but wanted to start the discussion rolling.\n\nI've actually started without alloca, and used xmalloc/free for\n[nparent] vectors, but the impact was measurable, so it just had to be\nchanged to something more optimal.\n\nFor me, personally, alloca is ok, but I understand there could be\nportability issues (by the way, what compiler/system Git cares about\ndoes not have working alloca?). Thats why I propose we do the following\n\n\n1. at configure time, determine, do we have working alloca, and define\n\n #define HAVE_ALLOCA\n\n if yes.\n\n2. in code\n\n #ifdef HAVE_ALLOCA\n # define xalloca(size) (alloca(size))\n # define xalloca_free(p) do {} while(0)\n #else\n # define xalloca(size) (xmalloc(size))\n # define xalloca_free(p) (free(p))\n #endif\n\n and use it like\n\n func() {\n p = xalloca(size);\n ...\n\n xalloca_free(p);\n }\n\nThis way, for systems, where alloca is available, we'll have optimal\non-stack allocations with fast executions. On the other hand, on\nsystems, where alloca is not available, this gracefully fallbacks to\nxmalloc/free.\n\nPlease tell me what you think.\n\n> > 3) For every parent tree, we need to keep a tag, whether entry from that\n> > parent equals to entry from minimal parent. For performance reasons I'm\n> > keeping that tag in entry's mode field in unused bit - see S_IFXMIN_NEQ.\n> \n> Unfortunate, but I do not see another place to keep this\n> information offhand (nor implement this approach without keeping\n> that piece of information).\n\nMe neither. I've actually started with separate on-stack (via alloca)\n[nparent] vector for such tags, and removing it was measurable.\n\n\n> > P.S. and combined diff is not some exotic/for-play-only stuff - for\n> \n> No need to convince us about that ;-)\n\nThanks ;) May I ask to please keep my \"motivation\" part in the commit\nlog for historical reasons?\n\n\n> > example for a program I write to represent Git archives as readonly\n> > filesystem, there is initial scan with\n> >\n> > `git log --reverse --raw --no-abbrev --no-renames -c`\n> >\n> > to extract log of what was created/changed when, as a result building a\n> > map\n> >\n> > {} sha1 -> in which commit (and date) a content was added\n> >\n> > that `-c` means also show combined diff for merges, and without them, if\n> > a merge is non-trivial (merges changes from two parents with both having\n> > separate changes to a file), or an evil one, the map will not be full,\n> > i.e. some valid sha1 would be absent from it.\n> >\n> > That case was my initial motivation for combined diffs speedup.\n> \n> I wonder if this machinery can be reused for \"log -m\" as well (or\n> perhaps you do that already?). After all, by performing a single\n> parallel scan, you are gathering all the necessary information to\n> let you pretend that you did N pairwise diff-tree.\n\nUnfortunately, as it is now, no, and let me explain why:\n\nThe reason that is not true, is that we omit recursing into directories,\nif we know D(A,some-parent) for that path is empty. That means we don't\ncalculate D(A,any-other-parents) for that path and subpaths.\n\nMore structured description is that combined diff and \"log -m\", which\ncould be though as all diffs D(A,Pi) are different things:\n\n - the combined diff is D(A,B) generalization based on \"^\" (sets\n intersection) operator, and\n\n - log -m, aka \"all diffs\" is D(A,B) generalization based on \"v\"\n (sets union) operator.\n\nIntersection means, we can omit calculating parts from other sets, if we\nknow some set does not have an element (remember \"don't recurse into\nsubdirectories\"?), and unioning does not have this property.\n\nIt does so happen, that \"^\" case (combine-diff) is more interesting,\nbecause in the end it allows to see new information - the diff a merge\nitself introduces. \"log -m\" does not have this property and is no more\ninteresting to what plain diff(HEAD,HEAD^n) can provide - in other words\nit's just a convenience.\n\nNow, the diff tree-walker could be generalized once more, to allow\nclients specify, which diffs combination operator to use - intersection\nor unioning, but I doubt that for unioning case that would add\nsignificant speedup - we can't reduce any diff generation based on\nanother diff and the only saving is that we traverse resulting commit\ntree once, but for some cases that could be maybe slower, say if result\nand some parents don't have a path and some parent does, we'll be\nrecursing into that path and do more work compared to plain D(A,Pi) for\nPi that lacks the path.\n\nIn short: it could be generalized more, if needed, but I propose we\nfirst establish the ground with generalizing to just combine-diff.\n\n\n> > diff --git a/tree-diff.c b/tree-diff.c\n> > index ab61a0a..2b7c991 100644\n> > --- a/tree-diff.c\n> > +++ b/tree-diff.c\n> > @@ -7,6 +7,25 @@\n> > #include \"tree.h\"\n> > \n> > /*\n> > + * internal mode marker, saying a tree entry != entry of tp[imin]\n> > + * (see __diff_tree_paths for what it means there)\n> > + *\n> > + * it *must* not overlap with any valid modes, and we will update/use/emit\n> > + * entry for diff only with it unset. Only non-overlapping to valid modes is\n> > + * required, because mode in tree_desc, comes here canonicalized via\n> > + * canon_mode().\n> > + *\n> > + * the definition assumes unsigned is at least 32 bits.\n> > + */\n> > +#define S_IFXMIN_NEQ\t0x80000000\n> \n> To allow better coordination across multiple codepaths that deal\n> with modes, I am wondering if this should be defined in cache.h\n> where made-up S_FIGITLINK and S_IFINVALID are defined (note the\n> comment that is there, as well).\n\nI knew about S_IFGITLINK and S_IFINVALID being located in cache.h with\ncomments.\n\nThe reason I decided to place S_IFXMIN_NEQ here, is that it is local tag\n- it is used locally in diff-tree, and neither is coming in, nor\ncoming out of it in set state.\n\nSo putting it in cache.h would mean we'll reserve the bit for something\nwhich is used only temporarily and that bit would be not available for\nother temporary uses.\n\nOn the other hand, it would be better, to mark in cache.h that some bits\ncould be used temporarily for application specific things. Maybe provide\na mask there or something similar to S_IFUSR1, S_IFUSR2 :)\n\nS_IFXMIN_NEQ is just has no meaning for code outside of tree-diff.c ...\n\nWhat do you think?\n\n\n> > +static struct combine_diff_path *__diff_tree_paths(\n> > +\tstruct combine_diff_path *p, const unsigned char *sha1,\n> > +\tconst unsigned char **parents_sha1, int nparent,\n> > +\tstruct strbuf *base, struct diff_options *opt);\n> \n> Most of our code do not name private helper functions with leading\n> underscores.\n\nWhat would be a good name here? In contrast to __diff_tree_sha1, it is\nstatic, and adding some prefix/suffix to the name is maybe adding more\nnoise than value? We have diff_tree_paths() which does the setup and\ncleanup and this worker __diff_tree_paths... Some names come to me as\ndiff_tree_paths_raw, or diff_tree_paths_worker, but having Linux\nheritage, I like __diff_tree_paths more.\n\nWhat would be a good approach for Git style here?\n\n\n> I do like the direction this is going, but it looks to me that\n> \"struct combine_diff\" is now misnamed, because it no longer is about\n> combined diff. You are introducing a good framework for n-way diff,\n> and producing combined diff (i.e. -c or --cc) is now merely one way\n> to use that framework. We may want to clean these names up after\n> this series settles---perhaps \"struct nway_diff\" or something.\n\nThanks. It was my main question whether this reworking will be a\ngood/accepted idea or not. I agree about `struct combine_diff_path`\nname and that it should be changed afterwards (my idea was `struct\ndiff_path` for it).\n\nGiven that we had diff_filepair for n=2 diffs, it would logical to call\nit as maybe\n\n diff_nway,\n diff_filevector,\n or something else\n\nbut maybe emphasizing n/vector/... in the name is not so good in the\nlong run, and using, for generalized diff just\n\n diff_file, or\n diff_path\n\nis better.\n\n\nNaming is important and I don't settled on it however, yet...\n\n\n> > +\n> > +/*\n> > * Compare two tree entries, taking into account only path/S_ISDIR(mode),\n> > * but not their sha1's.\n> > *\n> > @@ -33,72 +52,152 @@ static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)\n> > }\n> > \n> > \n> > -/* convert path, t1/t2 -> opt->diff_*() callbacks */\n> > -static void emit_diff(struct diff_options *opt, struct strbuf *path,\n> > -\t\t struct tree_desc *t1, struct tree_desc *t2)\n> > +/*\n> > + * convert path -> opt->diff_*() callbacks\n> > + *\n> > + * emits diff to parent0 only.\n> \n> Please call that \"first parent\".\n\nOk.\n\n\n> > + */\n> \n> \"Returns 0 to tell the caller that we are done with p and it can be\n> freed\" or something?\n> \n> > +static int emit_diff_p0only(struct diff_options *opt, struct combine_diff_path *p)\n> > {\n> > ...\n> > +\n> > +\treturn 0;\t/* = no need to keep allocated combine_diff_path */\n> \n> Curious; what is that equal sign in the comment?\n\nIt stands for \"that means\", \"i.e.\" or something similar. In other words\nit is semantically equal to your comment from the above.\n\nI'm open to reworking the commenting style for it to reads more well.\nShould I?\n\n~~~~\n\nThanks again for reviewing this and for generally accepting the\napproach. Please tell me your thoughts. Based on your input, I'll try\nto come up with something improved on monday.\n\nThanks,\nKirill\n"},{"id":"235023","messageId":"xmqqtxbwcdol.fsf@gitster.dls.corp.google.com","threadId":"35860","inReplyTo":"20140216080829.GA3820@mini.zxlink","subject":"Re: [PATCH 1/2] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-18T21:29:30Z","receivedAt":"2014-02-18T21:29:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n>> > 2) alloca(), for small arrays, is used for the same reason - if we change\n>> > it to xmalloc()/free() the timings get worse\n>> \n>> Do you see any use of it outside compat/?\n>> \n>> I thought we specifically avoid alloca() for portability. Also we\n>> do not use variable-length-arrays on the stack either, I think.\n>\n> No, no usage outside compat/ and I knew alloca and VLAs are not used in\n> Git codebase for portability, and I understand alloca will be\n> criticized, but wanted to start the discussion rolling.\n>\n> I've actually started without alloca, and used xmalloc/free for\n> [nparent] vectors, but the impact was measurable, so it just had to be\n> changed to something more optimal.\n>\n> For me, personally, alloca is ok, but I understand there could be\n> portability issues (by the way, what compiler/system Git cares about\n> does not have working alloca?). Thats why I propose we do the following\n>\n> 1. at configure time, determine, do we have working alloca, and define\n>\n> #define HAVE_ALLOCA\n>\n> if yes.\n>\n> 2. in code\n>\n> #ifdef HAVE_ALLOCA\n> # define xalloca(size) (alloca(size))\n> # define xalloca_free(p) do {} while(0)\n> #else\n> # define xalloca(size) (xmalloc(size))\n> # define xalloca_free(p) (free(p))\n> #endif\n>\n> and use it like\n>\n> func() {\n> p = xalloca(size);\n> ...\n>\n> xalloca_free(p);\n> }\n>\n> This way, for systems, where alloca is available, we'll have optimal\n> on-stack allocations with fast executions. On the other hand, on\n> systems, where alloca is not available, this gracefully fallbacks to\n> xmalloc/free.\n>\n> Please tell me what you think.\n\nI guess the above is clean enough, and we cannot do better than that,\nif we want to use alloca() on platforms where we can.\n"}]}