{"thread":{"id":"35786","subject":"[PATCH 0/8] `log -c` speedup (part 2)","startedAt":"2014-02-03T12:47:14Z","lastAt":"2014-02-06T16:22:54Z","messageCount":26,"participants":["Kirill Smelkov","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"234102","messageId":"cover.1391430523.git.kirr@mns.spb.ru","threadId":"35786","inReplyTo":null,"subject":"[PATCH 0/8] `log -c` speedup (part 2)","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-03T12:47:14Z","receivedAt":"2014-02-03T12:47:14Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"Hello up there,\n\nI'm still trying to speedup combined-diff to be not so slow, to be able to\nrealistically use it in my readonly filesystem for git archives.\n\nIn the first part[1], we optimized paths intersections, but combined-diff still\nremained slow, because internally it was computing huge diffs, even for small,\nor empty output.\n\nThis time, here goes paths scanning rework, which results in significant\ncombine-diff speedup. Please apply.\n\nThanks beforehand,\nKirill\n\nP.S. the code depends on ks/diff-c-with-diff-order\n\n[1] http://permalink.gmane.org/gmane.comp.version-control.git/240713\n\n\nKirill Smelkov (8):\n fixup! combine_diff: simplify intersect_paths() further\n tests: add checking that combine-diff emits only correct paths\n tree-diff: no need to manually verify that there is no mode change for\n a path\n tree-diff: no need to pass match to skip_uninteresting()\n combine-diff: move show_log_first logic/action out of paths scanning\n combine-diff: Move changed-paths scanning logic into its own function\n combine-diff: Fast changed-to-all-parents paths scanning\n combine-diff: bail out early, if num_paths=0\n\n combine-diff.c | 215 +++++++++++++++-----\n diff.c | 1 +\n diff.h | 6 +\n t/t4057-diff-combined-paths.sh | 106 ++++++++++\n tree-diff.c | 442 +++++++++++++++++++++++++++++++++++++++--\n 5 files changed, 696 insertions(+), 74 deletions(-)\n create mode 100755 t/t4057-diff-combined-paths.sh\n\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234104","messageId":"60ec61bdd2ef3cba7537e29c42f9c8a810da245d.1391430523.git.kirr@mns.spb.ru","threadId":"35786","inReplyTo":"cover.1391430523.git.kirr@mns.spb.ru","subject":"[PATCH 1/8] fixup! combine_diff: simplify intersect_paths() further","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-03T12:47:15Z","receivedAt":"2014-02-03T12:47:15Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"That cleanup patch is good, but I've found a bug in it. In the item removal\ncode\n\n> + /* p->path not in q->queue[]; drop it */\n> + struct combine_diff_path *next = p->next;\n> +\n> + if ((*tail = next) != NULL)\n> + tail = &next->next;\n> + free(p);\n> continue;\n\n *tail = next\n\nis right, but\n\n tail = &next->next\n\nis wrong, because it will lead to skipping the element after removed\none. Proof:\n\n tail p\n | |\n | |\n v v\n +-+ +------+-+ +------+-+ +------+-+\n | | | | | | | | | | |\n |o------->| |o------->| |o------->| |o------->\n |0| | 1| | | 2| | | 3| |\n +-+ +------+-+ +------+-+ +------+-+\n\nsuppose, we are removing element 1. p->next points to 2, after\n\n *tail = next\n\n0 points to 2, which != NULL. After\n\n tail = &next->next\n\ntail points to &2->next.\n\nOn the next cycle iteration, after\n\n p = *tail\n\nwe'll have\n\n p = *2->next = 3\n\nso 2 was skipped, oops.\n\nI've actually hit the bug - when generating combine-diff, for merges with\nshould-be empty `log -c` output, every second path was present in the diff.\nThat, by the way, means we need to extend combine-diff tests somewhat.\n\nSigned-off-by: Kirill Smelkov \n---\n combine-diff.c | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 0809e79..a03147c 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -58,8 +58,7 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n \t\t\t/* p->path not in q->queue[]; drop it */\n \t\t\tstruct combine_diff_path *next = p->next;\n \n-\t\t\tif ((*tail = next) != NULL)\n-\t\t\t\ttail = &next->next;\n+\t\t\t*tail = next;\n \t\t\tfree(p);\n \t\t\tcontinue;\n \t\t}\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234103","messageId":"9ee3e17af9a8da1f47423a74171d5cb95293f677.1391430523.git.kirr@mns.spb.ru","threadId":"35786","inReplyTo":"cover.1391430523.git.kirr@mns.spb.ru","subject":"[PATCH 2/8] tests: add checking that combine-diff emits only correct paths","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-03T12:47:16Z","receivedAt":"2014-02-03T12:47:16Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"where \"correct paths\" stands for paths that are different to all\nparents.\n\nUp until now, we were testing combined diff only on one file, or on\nseveral files which were all different (t4038-diff-combined.sh).\n\nAs recent thinko in \"simplify intersect_paths() further\" showed, and\nalso, since we are going to rework code for finding paths different to\nall parents, lets write at least basic tests.\n\nSigned-off-by: Kirill Smelkov \n---\n t/t4057-diff-combined-paths.sh | 106 +++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 106 insertions(+)\n create mode 100755 t/t4057-diff-combined-paths.sh\n\ndiff --git a/t/t4057-diff-combined-paths.sh b/t/t4057-diff-combined-paths.sh\nnew file mode 100755\nindex 0000000..e6e457d\n--- /dev/null\n+++ b/t/t4057-diff-combined-paths.sh\n@@ -0,0 +1,106 @@\n+#!/bin/sh\n+\n+test_description='combined diff show only paths that are different to all parents'\n+\n+. ./test-lib.sh\n+\n+# verify that diffc.expect matches output of\n+# `git diff -c --name-only HEAD HEAD^ HEAD^2`\n+diffc_verify() {\n+\tgit diff -c --name-only HEAD HEAD^ HEAD^2 >diffc.actual &&\n+\ttest_cmp diffc.expect diffc.actual\n+}\n+\n+test_expect_success 'trivial merge - combine-diff empty' '\n+\tfor i in `test_seq 1 9`\n+\tdo\n+\t\techo $i >$i.txt\t&&\n+\t\tgit add $i.txt\n+\tdone &&\n+\tgit commit -m \"init\" &&\n+\tgit checkout -b side &&\n+\tfor i in `test_seq 2 9`\n+\tdo\n+\t\techo $i/2 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"side 2-9\" &&\n+\tgit checkout master &&\n+\techo 1/2 >1.txt &&\n+\tgit commit -a -m \"master 1\" &&\n+\tgit merge side &&\n+\t>diffc.expect &&\n+\tdiffc_verify\n+'\n+\n+\n+test_expect_success 'only one trully conflicting path' '\n+\tgit checkout side &&\n+\tfor i in `test_seq 2 9`\n+\tdo\n+\t\techo $i/3 >>$i.txt\n+\tdone &&\n+\techo \"4side\" >>4.txt &&\n+\tgit commit -a -m \"side 2-9 +4\" &&\n+\tgit checkout master &&\n+\tfor i in `test_seq 1 9`\n+\tdo\n+\t\techo $i/3 >>$i.txt\n+\tdone &&\n+\techo \"4master\" >>4.txt &&\n+\tgit commit -a -m \"master 1-9 +4\" &&\n+\ttest_must_fail git merge side &&\n+\tcat <<-\\EOF >4.txt &&\n+\t4\n+\t4/2\n+\t4/3\n+\t4master\n+\t4side\n+\tEOF\n+\tgit add 4.txt &&\n+\tgit commit -m \"merge side (2)\" &&\n+\techo 4.txt >diffc.expect &&\n+\tdiffc_verify\n+'\n+\n+test_expect_success 'merge introduces new file' '\n+\tgit checkout side &&\n+\tfor i in `test_seq 5 9`\n+\tdo\n+\t\techo $i/4 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"side 5-9\" &&\n+\tgit checkout master &&\n+\tfor i in `test_seq 1 3`\n+\tdo\n+\t\techo $i/4 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"master 1-3 +4hello\" &&\n+\tgit merge side &&\n+\techo \"Hello World\" >4hello.txt &&\n+\tgit add 4hello.txt &&\n+\tgit commit --amend &&\n+\techo 4hello.txt >diffc.expect &&\n+\tdiffc_verify\n+'\n+\n+test_expect_success 'merge removed a file' '\n+\tgit checkout side &&\n+\tfor i in `test_seq 5 9`\n+\tdo\n+\t\techo $i/5 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"side 5-9\" &&\n+\tgit checkout master &&\n+\tfor i in `test_seq 1 3`\n+\tdo\n+\t\techo $i/4 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"master 1-3\" &&\n+\tgit merge side &&\n+\tgit rm 4.txt &&\n+\tgit commit --amend &&\n+\techo 4.txt >diffc.expect &&\n+\tdiffc_verify\n+'\n+\n+test_done\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234105","messageId":"83f38f44dab9e07e99ad851f531e01cee52e7019.1391430523.git.kirr@mns.spb.ru","threadId":"35786","inReplyTo":"cover.1391430523.git.kirr@mns.spb.ru","subject":"[PATCH 3/8] tree-diff: no need to manually verify that there is no mode change for a path","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-03T12:47:17Z","receivedAt":"2014-02-03T12:47:17Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"Because if there is, such two tree entries would never be compared as\nequal - the code in base_name_compare() explicitly compares modes, if\nthere is a change for dir bit, even for equal paths, entries would\ncompare as different.\n\nThe code I'm removing here is from 2005 April 262e82b4 (Fix diff-tree\nrecursion), which pre-dates base_name_compare() introduction in 958ba6c9\n(Introduce \"base_name_compare()\" helper function) by a month.\n\nSigned-off-by: Kirill Smelkov \n---\n tree-diff.c | 14 ++++----------\n 1 file changed, 4 insertions(+), 10 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 456660c..c2c67fd 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -23,6 +23,10 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,\n \n \tpathlen1 = tree_entry_len(&t1->entry);\n \tpathlen2 = tree_entry_len(&t2->entry);\n+\n+\t/* NOTE files and directories *always* compare differently, event when\n+\t * having the same name.\n+\t */\n \tcmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);\n \tif (cmp < 0) {\n \t\tshow_entry(opt, \"-\", t1, base);\n@@ -35,16 +39,6 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,\n \tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)\n \t\treturn 0;\n \n-\t/*\n-\t * If the filemode has changed to/from a directory from/to a regular\n-\t * file, we need to consider it a remove and an add.\n-\t */\n-\tif (S_ISDIR(mode1) != S_ISDIR(mode2)) {\n-\t\tshow_entry(opt, \"-\", t1, base);\n-\t\tshow_entry(opt, \"+\", t2, base);\n-\t\treturn 0;\n-\t}\n-\n \tstrbuf_add(base, path1, pathlen1);\n \tif (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode1)) {\n \t\tif (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE)) {\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234106","messageId":"2ba70db8557654c30d6b07c988075123fa14acd4.1391430523.git.kirr@mns.spb.ru","threadId":"35786","inReplyTo":"cover.1391430523.git.kirr@mns.spb.ru","subject":"[PATCH 4/8] tree-diff: no need to pass match to skip_uninteresting()","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-03T12:47:18Z","receivedAt":"2014-02-03T12:47:18Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"It is neither used there as input, nor the output written through it, is\nused outside.\n\nSigned-off-by: Kirill Smelkov \n---\n tree-diff.c | 17 ++++++++---------\n 1 file changed, 8 insertions(+), 9 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex c2c67fd..f7b3ade 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -108,13 +108,14 @@ static void show_entry(struct diff_options *opt, const char *prefix,\n }\n \n static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,\n-\t\t\t struct diff_options *opt,\n-\t\t\t enum interesting *match)\n+\t\t\t struct diff_options *opt)\n {\n+\tenum interesting match;\n+\n \twhile (t->size) {\n-\t\t*match = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec);\n-\t\tif (*match) {\n-\t\t\tif (*match == all_entries_not_interesting)\n+\t\tmatch = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec);\n+\t\tif (match) {\n+\t\t\tif (match == all_entries_not_interesting)\n \t\t\t\tt->size = 0;\n \t\t\tbreak;\n \t\t}\n@@ -127,8 +128,6 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,\n {\n \tstruct strbuf base;\n \tint baselen = strlen(base_str);\n-\tenum interesting t1_match = entry_not_interesting;\n-\tenum interesting t2_match = entry_not_interesting;\n \n \t/* Enable recursion indefinitely */\n \topt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);\n@@ -140,8 +139,8 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,\n \t\tif (diff_can_quit_early(opt))\n \t\t\tbreak;\n \t\tif (opt->pathspec.nr) {\n-\t\t\tskip_uninteresting(t1, &base, opt, &t1_match);\n-\t\t\tskip_uninteresting(t2, &base, opt, &t2_match);\n+\t\t\tskip_uninteresting(t1, &base, opt);\n+\t\t\tskip_uninteresting(t2, &base, opt);\n \t\t}\n \t\tif (!t1->size) {\n \t\t\tif (!t2->size)\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234107","messageId":"3f729b3cac37e11e8ec74d88b4caac79f037194b.1391430523.git.kirr@mns.spb.ru","threadId":"35786","inReplyTo":"cover.1391430523.git.kirr@mns.spb.ru","subject":"[PATCH 5/8] combine-diff: move show_log_first logic/action out of paths scanning","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-03T12:47:19Z","receivedAt":"2014-02-03T12:47:19Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"Judging from sample outputs and tests nothing changes in diff -c output,\nand this change will help later patches, when we'll be refactoring paths\nscanning into its own function with several variants - the\nshow_log_first logic / code will stay common to all of them.\n\nNOTE: only now we have to take care to explicitly not show anything if\n parents array is empty, as in fact there are some clients in Git code,\n which calls diff_tree_combined() in such a way.\n\nSigned-off-by: Kirill Smelkov \n---\n combine-diff.c | 24 ++++++++++++++----------\n 1 file changed, 14 insertions(+), 10 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex a03147c..272931f 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1313,6 +1313,20 @@ void diff_tree_combined(const unsigned char *sha1,\n \tstruct combine_diff_path *p, *paths = NULL;\n \tint i, num_paths, needsep, show_log_first, num_parent = parents->nr;\n \n+\t/* nothing to do, if no parents */\n+\tif (!num_parent)\n+\t\treturn;\n+\n+\tshow_log_first = !!rev->loginfo && !rev->no_commit_id;\n+\tneedsep = 0;\n+\tif (show_log_first) {\n+\t\tshow_log(rev);\n+\n+\t\tif (rev->verbose_header && opt->output_format)\n+\t\t\tprintf(\"%s%c\", diff_line_prefix(opt),\n+\t\t\t opt->line_termination);\n+\t}\n+\n \tdiffopts = *opt;\n \tcopy_pathspec(&diffopts.pathspec, &opt->pathspec);\n \tdiffopts.output_format = DIFF_FORMAT_NO_OUTPUT;\n@@ -1321,8 +1335,6 @@ void diff_tree_combined(const unsigned char *sha1,\n \t/* tell diff_tree to emit paths in sorted (=tree) order */\n \tdiffopts.orderfile = NULL;\n \n-\tshow_log_first = !!rev->loginfo && !rev->no_commit_id;\n-\tneedsep = 0;\n \t/* find set of paths that everybody touches */\n \tfor (i = 0; i < num_parent; i++) {\n \t\t/* show stat against the first parent even\n@@ -1338,14 +1350,6 @@ void diff_tree_combined(const unsigned char *sha1,\n \t\tdiffcore_std(&diffopts);\n \t\tpaths = intersect_paths(paths, i, num_parent);\n \n-\t\tif (show_log_first && i == 0) {\n-\t\t\tshow_log(rev);\n-\n-\t\t\tif (rev->verbose_header && opt->output_format)\n-\t\t\t\tprintf(\"%s%c\", diff_line_prefix(opt),\n-\t\t\t\t opt->line_termination);\n-\t\t}\n-\n \t\t/* if showing diff, show it in requested order */\n \t\tif (diffopts.output_format != DIFF_FORMAT_NO_OUTPUT &&\n \t\t opt->orderfile) {\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234108","messageId":"19328cce4bfb32f7f514f0bd81aa8b1081e0c0cf.1391430523.git.kirr@mns.spb.ru","threadId":"35786","inReplyTo":"cover.1391430523.git.kirr@mns.spb.ru","subject":"[PATCH 6/8] combine-diff: Move changed-paths scanning logic into its own function","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-03T12:47:20Z","receivedAt":"2014-02-03T12:47:20Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"Move code for finding paths for which diff(commit,parent_i) is not-empty\nfor all parents to separate function - at present we have generic (and\nslow) code for this job, which translates 1 n-parent problem to n\n1-parent problems and then intersect results, and will be adding another\nlimited, but faster, paths scanning implementation in the next patch.\n\nSigned-off-by: Kirill Smelkov \n---\n combine-diff.c | 79 ++++++++++++++++++++++++++++++++++++++--------------------\n 1 file changed, 52 insertions(+), 27 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 272931f..427a7c1 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1303,6 +1303,50 @@ static const char *path_path(void *obj)\n \treturn path->path;\n }\n \n+\n+/* find set of paths that every parent touches */\n+static struct combine_diff_path *find_paths(const unsigned char *sha1,\n+\tconst struct sha1_array *parents, struct diff_options *opt)\n+{\n+\tstruct combine_diff_path *paths = NULL;\n+\tint i, num_parent = parents->nr;\n+\n+\tint output_format = opt->output_format;\n+\tconst char *orderfile = opt->orderfile;\n+\n+\topt->output_format = DIFF_FORMAT_NO_OUTPUT;\n+\t/* tell diff_tree to emit paths in sorted (=tree) order */\n+\topt->orderfile = NULL;\n+\n+\tfor (i = 0; i < num_parent; i++) {\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 = (output_format &\n+\t\t\t\t(DIFF_FORMAT_NUMSTAT|DIFF_FORMAT_DIFFSTAT));\n+\t\tif (i == 0 && stat_opt)\n+\t\t\topt->output_format = stat_opt;\n+\t\telse\n+\t\t\topt->output_format = DIFF_FORMAT_NO_OUTPUT;\n+\t\tdiff_tree_sha1(parents->sha1[i], sha1, \"\", opt);\n+\t\tdiffcore_std(opt);\n+\t\tpaths = intersect_paths(paths, i, num_parent);\n+\n+\t\t/* if showing diff, show it in requested order */\n+\t\tif (opt->output_format != DIFF_FORMAT_NO_OUTPUT &&\n+\t\t orderfile) {\n+\t\t\tdiffcore_order(orderfile);\n+\t\t}\n+\n+\t\tdiff_flush(opt);\n+\t}\n+\n+\topt->output_format = output_format;\n+\topt->orderfile = orderfile;\n+\treturn paths;\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@@ -1310,7 +1354,7 @@ void diff_tree_combined(const unsigned char *sha1,\n {\n \tstruct diff_options *opt = &rev->diffopt;\n \tstruct diff_options diffopts;\n-\tstruct combine_diff_path *p, *paths = NULL;\n+\tstruct combine_diff_path *p, *paths;\n \tint i, num_paths, needsep, show_log_first, num_parent = parents->nr;\n \n \t/* nothing to do, if no parents */\n@@ -1329,35 +1373,16 @@ void diff_tree_combined(const unsigned char *sha1,\n \n \tdiffopts = *opt;\n \tcopy_pathspec(&diffopts.pathspec, &opt->pathspec);\n-\tdiffopts.output_format = DIFF_FORMAT_NO_OUTPUT;\n \tDIFF_OPT_SET(&diffopts, RECURSIVE);\n \tDIFF_OPT_CLR(&diffopts, ALLOW_EXTERNAL);\n-\t/* tell diff_tree to emit paths in sorted (=tree) order */\n-\tdiffopts.orderfile = NULL;\n \n-\t/* find set of paths that everybody touches */\n-\tfor (i = 0; i < num_parent; i++) {\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 (i == 0 && stat_opt)\n-\t\t\tdiffopts.output_format = stat_opt;\n-\t\telse\n-\t\t\tdiffopts.output_format = DIFF_FORMAT_NO_OUTPUT;\n-\t\tdiff_tree_sha1(parents->sha1[i], sha1, \"\", &diffopts);\n-\t\tdiffcore_std(&diffopts);\n-\t\tpaths = intersect_paths(paths, i, num_parent);\n-\n-\t\t/* if showing diff, show it in requested order */\n-\t\tif (diffopts.output_format != DIFF_FORMAT_NO_OUTPUT &&\n-\t\t opt->orderfile) {\n-\t\t\tdiffcore_order(opt->orderfile);\n-\t\t}\n-\n-\t\tdiff_flush(&diffopts);\n-\t}\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 */\n+\tpaths = find_paths(sha1, parents, &diffopts);\n \n \t/* find out number of surviving paths */\n \tfor (num_paths = 0, p = paths; p; p = p->next)\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234109","messageId":"c0ad49d850377aedffa0a593fef8738112019b01.1391430523.git.kirr@mns.spb.ru","threadId":"35786","inReplyTo":"cover.1391430523.git.kirr@mns.spb.ru","subject":"[PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-03T12:47:21Z","receivedAt":"2014-02-03T12:47:21Z","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\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\n D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn) (w.r.t. paths)\n\nwhere\n\n D(A,P1...Pn) is combined diff between commit A, and parents Pi\n\nand\n\n D(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\n D(A,X1...Xn) calculation scheme\n -------------------------------\n\n D(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\n We start from all trees, which are sorted, and compare their entries in\n lock-step:\n\n A X1 Xn\n - - -\n |a| |x1| |xn|\n |-| |--| ... |--| i = argmin(x1...xn)\n | | | | | |\n |-| |--| |--|\n |.| |. | |. |\n . . .\n . . .\n\n at any time there could be 3 cases:\n\n 1) a < xi;\n 2) a > xi;\n 3) 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 in any case a↓ ∀ xk=xi xk↓\n\n~\n\nFor comparison, here is how diff_tree() works:\n\n D(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\nFor now there is a limitation however - for simple scan to work, we have\nto know in advance, a user had not asked for finding rename/copies\ndetection. At present, if he/she has, we fallback to calling old n\n1-parent diffs code. I think that restriction, at least in theory,\ncould be lifted. I propose we have fast code for at least common case,\nand move on incrementally.\n\nAnother similar limitation, is that if diffcore transforms which\nfilter-out paths, are active, we also fallback to old code. The reason\nhere is pure \"technical\" - all transforms expect to find paths in\ndiff_filepair's queue, which applies only to 1-parent case. If needed,\nThe solution here would be to generalize diff_filepair to\ncombine_diff_path everywhere, and do not differentiate between plain and\ncombined diffs (all diffs will be combined with diff(A,B) being\ncombined diff with only 1 parent), but again, let's move on\nincrementally.\n\nI consciously placed trees-scanning code in tree-diff.c, foreseeing diff\nand combine-diff merge, and because that code is very similar to\ndiff_tree - to keep similar codes near.\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.6s 15.5s\n after 1.9s 2.4s 1.1s(*)\n\nThe result stayed the same.\n\n(*) that 15.5/1.1 = ~14.1 ratio, is the most appropriate estimate for\n combine-diff speedup.\n\nSigned-off-by: Kirill Smelkov \n---\n combine-diff.c | 85 +++++++++++-\n diff.c | 1 +\n diff.h | 6 +\n tree-diff.c | 411 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 498 insertions(+), 5 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 427a7c1..3e3f328 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1305,7 +1305,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@@ -1318,6 +1318,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/* show stat against the first parent even\n \t\t * when doing combined diff.\n@@ -1347,6 +1348,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+\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+\tstruct combine_diff_path paths_head;\n+\tpaths_head.next = NULL;\n+\n+\tstruct strbuf base;\n+\tstrbuf_init(&base, PATH_MAX);\n+\n+\tdiff_tree_combined_paths(&paths_head, sha1, parents_sha1, nparent, &base, opt);\n+\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@@ -1356,6 +1386,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@@ -1378,11 +1409,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 49e71f4..29ede0b 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -4755,6 +4755,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) {\ndiff --git a/diff.h b/diff.h\nindex a24a767..5496560 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -214,6 +214,12 @@ struct combine_diff_path {\n extern void show_combined_diff(struct combine_diff_path *elem, int num_parent,\n \t\t\t int dense, struct rev_info *);\n \n+extern\n+struct combine_diff_path *diff_tree_combined_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+\n extern void diff_tree_combined(const unsigned char *sha1, const struct sha1_array *parents, int dense, struct rev_info *rev);\n \n extern void diff_tree_combined_merge(const struct commit *commit, int dense, struct rev_info *rev);\ndiff --git a/tree-diff.c b/tree-diff.c\nindex f7b3ade..7f4f917 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -172,6 +172,417 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,\n \treturn 0;\n }\n \n+\n+/*\n+ * Compare two tree descriptors, taking into account only path/mode,\n+ * but not their sha1's.\n+ *\n+ * NOTE files and directories *always* compare differently, even when having\n+ * the same name - thanks to base_name_compare().\n+ *\n+ * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty.\n+ */\n+static int tree_desc_pathcmp(struct tree_desc *t1, struct tree_desc *t2)\n+{\n+\tconst unsigned char *t1_sha1, *t2_sha1;\n+\tconst char *path1, *path2;\n+\tint path1_len, path2_len;\n+\tunsigned mode1, mode2;\n+\tint cmp;\n+\n+\tif (!t1->size)\n+\t\treturn t2->size ? +1 /* +∞ > c */ : 0 /* +∞ = +∞ */;\n+\telse if (!t2->size)\n+\t\treturn -1;\t/* c < +∞ */\n+\n+\n+\tt1_sha1 = tree_entry_extract(t1, &path1, &mode1);\n+\tt2_sha1 = tree_entry_extract(t2, &path2, &mode2);\n+\n+\tpath1_len = tree_entry_len(&t1->entry);\n+\tpath2_len = tree_entry_len(&t2->entry);\n+\n+\tcmp = base_name_compare(path1, path1_len, mode1,\n+\t\t\t\tpath2, path2_len, mode2);\n+\treturn cmp;\n+}\n+\n+\n+/*\n+ * Make a new combine_diff_path from path/mode/sha1\n+ * and append it to paths list tail.\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+\n+\tp = xmalloc(combine_diff_path_size(nparent, len));\n+\tp->next = NULL;\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);\n+\n+\tlast->next = p;\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 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 struct combine_diff_path *path_appendnew(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, int *xmin_pathcmpv)\n+{\n+\tint i, isdir, recurse=0, emitthis=1;\n+\n+\tconst unsigned char *sha1;\n+\tconst char *path;\n+\tint pathlen;\n+\tunsigned mode;\n+\n+\t/* at least something has to be valid */\n+\tassert(t || tp);\n+\n+\tif (t) {\n+\t\t/* path present in resulting tree */\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 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(&tp[imin], &path, &mode);\n+\t\tpathlen = tree_entry_len(&tp[imin].entry);\n+\n+\t\tisdir = S_ISDIR(mode);\n+\t\tsha1 = null_sha1;\n+\t\tmode = 0;\n+\t}\n+\n+\n+\tif (DIFF_OPT_TST(opt, RECURSIVE) && isdir) {\n+\t\trecurse = 1;\n+\t\temitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);\n+\t}\n+\n+\tif (emitthis) {\n+\t\tp = __path_appendnew(p, nparent, base, path, pathlen, mode, sha1);\n+\t\tfor (i = 0; i < nparent; ++i) {\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 && !xmin_pathcmpv[i];\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 = canon_mode(tp[i].entry.mode);\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\tsha1_i = null_sha1;\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);\n+\t\t}\n+\t}\n+\n+\tif (recurse) {\n+\t\tconst unsigned char **parents_sha1;\n+\t\tint old_baselen = base->len;\n+\n+\t\tparents_sha1 = xmalloc(nparent * sizeof(parents_sha1[0]));\n+\t\tfor (i = 0; i < nparent; ++i) {\n+\t\t\t/* same rule as in emitthis */\n+\t\t\tint tpi_valid = tp && !xmin_pathcmpv[i];\n+\n+\t\t\tparents_sha1[i] = tpi_valid ? tp[i].entry.sha1\n+\t\t\t\t\t\t : null_sha1;\n+\t\t}\n+\n+\t\t/* base += path+'/' */\n+\t\tstrbuf_add(base, path, pathlen);\n+\t\tstrbuf_addch(base, '/');\n+\n+\t\tp = diff_tree_combined_paths(p, sha1, parents_sha1, nparent, base, opt);\n+\n+\t\t/* restore base */\n+\t\tstrbuf_setlen(base, old_baselen);\n+\n+\t\tfree(parents_sha1);\n+\t}\n+\n+\treturn p;\n+}\n+\n+\n+/* Like fill_tree_descriptor, but returns empty tree_desc for null_sha1 */\n+static void *xfill_tree_descriptor(struct tree_desc *t, const unsigned char *sha1)\n+{\n+\tif (!is_null_sha1(sha1))\n+\t\treturn fill_tree_descriptor(t, sha1);\n+\n+\tinit_tree_desc(t, NULL, 0);\n+\treturn NULL;\n+}\n+\n+\n+/* generate paths for combined diff D(sha1,parents_sha1[])\n+ *\n+ * The paths are generated scanning new tree and all parents trees\n+ * simultaneously, similarly to what diff_tree() does for 2 trees. The theory\n+ * 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+struct combine_diff_path *diff_tree_combined_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 *xmin_pathcmpv;\t/* [i] = pathcmp(tp[i], tp[imin]) */\n+\tint i;\n+\n+\ttp = xmalloc(nparent * sizeof(tp[0]));\n+\ttptree = xmalloc(nparent * sizeof(tptree[0]));\n+\n+\tttree = xfill_tree_descriptor(&t, sha1);\n+\tfor (i = 0; i < nparent; i++)\n+\t\ttptree[i] = xfill_tree_descriptor(&tp[i], parents_sha1[i]);\n+\n+\txmin_pathcmpv = xmalloc(nparent * sizeof(xmin_pathcmpv[0]));\n+\n+\t/* Enable recursion indefinitely */\n+\topt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);\n+\n+\tfor (;;) {\n+\t\tint imin, xmin_eqtotal, cmp, alldifferent;\n+\t\tint a_next, tp_next;\n+\t\tconst unsigned char *entry_sha1;\n+\t\tconst char *path;\n+\t\tunsigned mode;\n+\n+\n+\t\t/* TODO Something similiar to if diff_can_quit_early -> break */\n+\n+\t\tif (opt->pathspec.nr) {\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+\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\tfor (i = 0; i < nparent; ++i)\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\tif (done)\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\n+\n+\t\t/* lookup imin = argmin(x1...xn), build X compare vector along the way */\n+\t\timin = 0;\t\t/* argmin(x1...xn)\t*/\n+\t\txmin_eqtotal = 1;\t/* len([xk: xk=ximin])\t*/\n+\t\txmin_pathcmpv[0] = 0;\n+\n+\t\tfor (i = 1; i < nparent; ++i) {\n+\t\t\tcmp = tree_desc_pathcmp(&tp[i], &tp[imin]);\n+\t\t\tif (cmp == -1) {\n+\t\t\t\timin = i;\n+\t\t\t\txmin_eqtotal = 1;\n+\t\t\t\txmin_pathcmpv[i] = 0;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\txmin_pathcmpv[i] = cmp;\n+\t\t\t\tif (cmp == 0)\n+\t\t\t\t\txmin_eqtotal++;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* fixup compare vector for entries before imin */\n+\t\tfor (i = 0; i < imin; ++i)\n+\t\t\txmin_pathcmpv[i] = +1;\t/* x[i] > x[imin] */\n+\n+\n+\t\t/* what tree entries will we update, in the end of this step? */\n+\t\ta_next = 0;\t/* a */\n+\t\ttp_next = 0;\t/* tp[k: xk=xmin] */\n+\n+\n+\t\t/* compare a vs x[imin] */\n+\t\tcmp = tree_desc_pathcmp(&t, &tp[imin]);\n+\n+\t\tswitch (cmp) {\n+\t\t/* a < xi */\n+\t\tcase -1:\n+\t\t\t/* D += \"+a\" */\n+\t\t\tp = path_appendnew(p, base, opt, nparent,\n+\t\t\t\t\t&t, /*tp=*/NULL, -1, NULL);\n+\n+\t\t\t/* a↓ */\n+\t\t\ta_next = 1;\n+\t\t\tbreak;\n+\n+\n+\t\t/* a > xi */\n+\t\tcase +1:\n+\t\t\t/* ∀j xj=ximin -> D += \"-xi\" */\n+\t\t\tif (xmin_eqtotal == nparent)\n+\t\t\t\tp = path_appendnew(p, base, opt, nparent,\n+\t\t\t\t\t/*t=*/NULL, tp, imin, xmin_pathcmpv);\n+\n+\t\t\t/* ∀ xk=ximin xk↓ */\n+\t\t\ttp_next = 1;\n+\t\t\tbreak;\n+\n+\n+\t\t/* a = xi */\n+\t\tcase 0:\n+\t\t\t/* are either xk > xi or diff(a,xk) != ø ? */\n+\t\t\talldifferent = 1;\n+\t\t\tentry_sha1 = tree_entry_extract(&t, &path, &mode);\n+\t\t\tfor (i = 0; i < nparent; i++) {\n+\t\t\t\tconst unsigned char *sha1_i;\n+\t\t\t\tconst char *path_i;\n+\t\t\t\tunsigned mode_i;\n+\n+\t\t\t\t/* x[i] > x[imin] */\n+\t\t\t\tif (xmin_pathcmpv[i])\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\t/* diff(a,xk) != ø */\n+\t\t\t\tsha1_i = tree_entry_extract(&tp[i], &path_i, &mode_i);\n+\t\t\t\tif (hashcmp(entry_sha1, sha1_i) || (mode != mode_i))\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\talldifferent = 0;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\n+\t\t\t/* D += {δ(a,xk) if xk=xi; \"+a\" if xk > xi} */\n+\t\t\tif (alldifferent)\n+\t\t\t\tp = path_appendnew(p, base, opt, nparent,\n+\t\t\t\t\t\t&t, tp, imin, xmin_pathcmpv);\n+\n+\t\t\t/* a↓, ∀ xk=ximin xk↓ */\n+\t\t\ta_next = 1;\n+\t\t\ttp_next = 1;\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\t/* perform scheduled tree entries updates: */\n+\t\tif (a_next)\n+\t\t\t/* a↓ */\n+\t\t\tupdate_tree_entry(&t);\n+\n+\t\tif (tp_next)\n+\t\t\t/* ∀ xk=xi xk↓ */\n+\t\t\tfor (i = 0; i < nparent; ++i)\n+\t\t\t\tif (!xmin_pathcmpv[i])\n+\t\t\t\t\tupdate_tree_entry(&tp[i]);\n+\t}\n+\n+\tfree(xmin_pathcmpv);\n+\tfor (i = nparent-1; i >= 0; i--)\n+\t\tfree(tptree[i]);\n+\tfree(ttree);\n+\tfree(tptree);\n+\tfree(tp);\n+\n+\treturn p;\n+}\n+\n+\n+\n /*\n * Does it look like the resulting diff might be due to a rename?\n * - single entry\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234110","messageId":"2dc2bcce19105cdd384f119328c06321cbea599a.1391430523.git.kirr@mns.spb.ru","threadId":"35786","inReplyTo":"cover.1391430523.git.kirr@mns.spb.ru","subject":"[PATCH 8/8] combine-diff: bail out early, if num_paths=0","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-03T12:47:22Z","receivedAt":"2014-02-03T12:47:22Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"That simplifies the code - instead of repeated checking for\nnum_paths !=0, let's verify it once, and return if it is, and\nfree following code from repeated ifs.\n\nSigned-off-by: Kirill Smelkov \n---\n combine-diff.c | 52 +++++++++++++++++++++++++++-------------------------\n 1 file changed, 27 insertions(+), 25 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 3e3f328..c1f481f 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1459,12 +1459,18 @@ void diff_tree_combined(const unsigned char *sha1,\n \t\t}\n \t}\n \n+\tfree_pathspec(&diffopts.pathspec);\n+\n \t/* find out number of surviving paths */\n \tfor (num_paths = 0, p = paths; p; p = p->next)\n \t\tnum_paths++;\n \n+\t/* nothing to do, if no paths */\n+\tif (!num_paths)\n+\t\treturn;\n+\n \t/* order paths according to diffcore_order */\n-\tif (opt->orderfile && num_paths) {\n+\tif (opt->orderfile) {\n \t\tstruct obj_order *o;\n \n \t\to = xmalloc(sizeof(*o) * num_paths);\n@@ -1483,28 +1489,26 @@ void diff_tree_combined(const unsigned char *sha1,\n \t}\n \n \n-\tif (num_paths) {\n-\t\tif (opt->output_format & (DIFF_FORMAT_RAW |\n-\t\t\t\t\t DIFF_FORMAT_NAME |\n-\t\t\t\t\t DIFF_FORMAT_NAME_STATUS)) {\n-\t\t\tfor (p = paths; p; p = p->next)\n-\t\t\t\tshow_raw_diff(p, num_parent, rev);\n-\t\t\tneedsep = 1;\n-\t\t}\n-\t\telse if (opt->output_format &\n-\t\t\t (DIFF_FORMAT_NUMSTAT|DIFF_FORMAT_DIFFSTAT))\n-\t\t\tneedsep = 1;\n-\t\telse if (opt->output_format & DIFF_FORMAT_CALLBACK)\n-\t\t\thandle_combined_callback(opt, paths, num_parent, num_paths);\n-\n-\t\tif (opt->output_format & DIFF_FORMAT_PATCH) {\n-\t\t\tif (needsep)\n-\t\t\t\tprintf(\"%s%c\", diff_line_prefix(opt),\n-\t\t\t\t opt->line_termination);\n-\t\t\tfor (p = paths; p; p = p->next)\n-\t\t\t\tshow_patch_diff(p, num_parent, dense,\n-\t\t\t\t\t\t0, rev);\n-\t\t}\n+\tif (opt->output_format & (DIFF_FORMAT_RAW |\n+\t\t\t\t DIFF_FORMAT_NAME |\n+\t\t\t\t DIFF_FORMAT_NAME_STATUS)) {\n+\t\tfor (p = paths; p; p = p->next)\n+\t\t\tshow_raw_diff(p, num_parent, rev);\n+\t\tneedsep = 1;\n+\t}\n+\telse if (opt->output_format &\n+\t\t (DIFF_FORMAT_NUMSTAT|DIFF_FORMAT_DIFFSTAT))\n+\t\tneedsep = 1;\n+\telse if (opt->output_format & DIFF_FORMAT_CALLBACK)\n+\t\thandle_combined_callback(opt, paths, num_parent, num_paths);\n+\n+\tif (opt->output_format & DIFF_FORMAT_PATCH) {\n+\t\tif (needsep)\n+\t\t\tprintf(\"%s%c\", diff_line_prefix(opt),\n+\t\t\t opt->line_termination);\n+\t\tfor (p = paths; p; p = p->next)\n+\t\t\tshow_patch_diff(p, num_parent, dense,\n+\t\t\t\t\t0, rev);\n \t}\n \n \t/* Clean things up */\n@@ -1513,8 +1517,6 @@ void diff_tree_combined(const unsigned char *sha1,\n \t\tpaths = paths->next;\n \t\tfree(tmp);\n \t}\n-\n-\tfree_pathspec(&diffopts.pathspec);\n }\n \n void diff_tree_combined_merge(const struct commit *commit, int dense,\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234130","messageId":"xmqqy51sdly5.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"60ec61bdd2ef3cba7537e29c42f9c8a810da245d.1391430523.git.kirr@mns.spb.ru","subject":"Re: [PATCH 1/8] fixup! combine_diff: simplify intersect_paths() further","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-03T19:40:18Z","receivedAt":"2014-02-03T19:40:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> That cleanup patch is good, but I've found a bug in it. In the item removal\n> code\n>\n>> + /* p->path not in q->queue[]; drop it */\n>> + struct combine_diff_path *next = p->next;\n>> +\n>> + if ((*tail = next) != NULL)\n>> + tail = &next->next;\n>> + free(p);\n>> continue;\n>\n> *tail = next\n>\n> is right, but\n>\n> tail = &next->next\n>\n> is wrong,\n\nHeh, surely. We just have skipped, and the fact that tail points at\nthe pointer variable that points at the first of the remaining items\ndoes not change with this skipping of next by assigning it to *tail. \nAn extra assignment to tail will skip one more, which is unnecessary.\n"},{"id":"234166","messageId":"xmqqzjm7bxny.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"9ee3e17af9a8da1f47423a74171d5cb95293f677.1391430523.git.kirr@mns.spb.ru","subject":"Re: [PATCH 2/8] tests: add checking that combine-diff emits only correct paths","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-03T23:10:08Z","receivedAt":"2014-02-03T23:10:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> where \"correct paths\" stands for paths that are different to all\n> parents.\n>\n> Up until now, we were testing combined diff only on one file, or on\n> several files which were all different (t4038-diff-combined.sh).\n>\n> As recent thinko in \"simplify intersect_paths() further\" showed, and\n> also, since we are going to rework code for finding paths different to\n> all parents, lets write at least basic tests.\n\nThanks. Some nitpicks.\n\n>\n> Signed-off-by: Kirill Smelkov \n> ---\n> t/t4057-diff-combined-paths.sh | 106 +++++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 106 insertions(+)\n> create mode 100755 t/t4057-diff-combined-paths.sh\n>\n> diff --git a/t/t4057-diff-combined-paths.sh b/t/t4057-diff-combined-paths.sh\n> new file mode 100755\n> index 0000000..e6e457d\n> --- /dev/null\n> +++ b/t/t4057-diff-combined-paths.sh\n> @@ -0,0 +1,106 @@\n> +#!/bin/sh\n> +\n> +test_description='combined diff show only paths that are different to all parents'\n> +\n> +. ./test-lib.sh\n> +\n> +# verify that diffc.expect matches output of\n> +# `git diff -c --name-only HEAD HEAD^ HEAD^2`\n> +diffc_verify() {\n\nStyle: SP before (), i.e.\n\n\tdiffc_verify () {\n\n> +\tgit diff -c --name-only HEAD HEAD^ HEAD^2 >diffc.actual &&\n> +\ttest_cmp diffc.expect diffc.actual\n> +}\n> +\n> +test_expect_success 'trivial merge - combine-diff empty' '\n> +\tfor i in `test_seq 1 9`\n\nStyle: prefer $() over ``\n\n> +\tdo\n> +\t\techo $i >$i.txt\t&&\n> +\t\tgit add $i.txt\n\nQuiz. What happens when this \"git add\" fails with an earlier value\nof $i?\n\n> +\tdone &&\n"},{"id":"234167","messageId":"xmqqvbwvbxju.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"83f38f44dab9e07e99ad851f531e01cee52e7019.1391430523.git.kirr@mns.spb.ru","subject":"Re: [PATCH 3/8] tree-diff: no need to manually verify that there is no mode change for a path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-03T23:12:37Z","receivedAt":"2014-02-03T23:12:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> Because if there is, such two tree entries would never be compared as\n> equal - the code in base_name_compare() explicitly compares modes, if\n> there is a change for dir bit, even for equal paths, entries would\n> compare as different.\n\nOK.\n"},{"id":"234170","messageId":"xmqqr47jbx5i.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"3f729b3cac37e11e8ec74d88b4caac79f037194b.1391430523.git.kirr@mns.spb.ru","subject":"Re: [PATCH 5/8] combine-diff: move show_log_first logic/action out of paths scanning","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-03T23:21:13Z","receivedAt":"2014-02-03T23:21:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> Judging from sample outputs and tests nothing changes in diff -c output,\n\nYuck.\n\nI do not think the processing done inside the loop for the first\npath (i.e. i==0) before we call show_log(rev) affects what that\ncalled show_log(rev) does, so it probably is a good readability\nchange.\n\nThanks.\n\n> and this change will help later patches, when we'll be refactoring paths\n> scanning into its own function with several variants - the\n> show_log_first logic / code will stay common to all of them.\n>\n> NOTE: only now we have to take care to explicitly not show anything if\n> parents array is empty, as in fact there are some clients in Git code,\n> which calls diff_tree_combined() in such a way.\n>\n> Signed-off-by: Kirill Smelkov \n> ---\n> combine-diff.c | 24 ++++++++++++++----------\n> 1 file changed, 14 insertions(+), 10 deletions(-)\n>\n> diff --git a/combine-diff.c b/combine-diff.c\n> index a03147c..272931f 100644\n> --- a/combine-diff.c\n> +++ b/combine-diff.c\n> @@ -1313,6 +1313,20 @@ void diff_tree_combined(const unsigned char *sha1,\n> \tstruct combine_diff_path *p, *paths = NULL;\n> \tint i, num_paths, needsep, show_log_first, num_parent = parents->nr;\n> \n> +\t/* nothing to do, if no parents */\n> +\tif (!num_parent)\n> +\t\treturn;\n> +\n> +\tshow_log_first = !!rev->loginfo && !rev->no_commit_id;\n> +\tneedsep = 0;\n> +\tif (show_log_first) {\n> +\t\tshow_log(rev);\n> +\n> +\t\tif (rev->verbose_header && opt->output_format)\n> +\t\t\tprintf(\"%s%c\", diff_line_prefix(opt),\n> +\t\t\t opt->line_termination);\n> +\t}\n> +\n> \tdiffopts = *opt;\n> \tcopy_pathspec(&diffopts.pathspec, &opt->pathspec);\n> \tdiffopts.output_format = DIFF_FORMAT_NO_OUTPUT;\n> @@ -1321,8 +1335,6 @@ void diff_tree_combined(const unsigned char *sha1,\n> \t/* tell diff_tree to emit paths in sorted (=tree) order */\n> \tdiffopts.orderfile = NULL;\n> \n> -\tshow_log_first = !!rev->loginfo && !rev->no_commit_id;\n> -\tneedsep = 0;\n> \t/* find set of paths that everybody touches */\n> \tfor (i = 0; i < num_parent; i++) {\n> \t\t/* show stat against the first parent even\n> @@ -1338,14 +1350,6 @@ void diff_tree_combined(const unsigned char *sha1,\n> \t\tdiffcore_std(&diffopts);\n> \t\tpaths = intersect_paths(paths, i, num_parent);\n> \n> -\t\tif (show_log_first && i == 0) {\n> -\t\t\tshow_log(rev);\n> -\n> -\t\t\tif (rev->verbose_header && opt->output_format)\n> -\t\t\t\tprintf(\"%s%c\", diff_line_prefix(opt),\n> -\t\t\t\t opt->line_termination);\n> -\t\t}\n> -\n> \t\t/* if showing diff, show it in requested order */\n> \t\tif (diffopts.output_format != DIFF_FORMAT_NO_OUTPUT &&\n> \t\t opt->orderfile) {\n"},{"id":"234171","messageId":"xmqqk3dbbwwf.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"c0ad49d850377aedffa0a593fef8738112019b01.1391430523.git.kirr@mns.spb.ru","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-03T23:26:40Z","receivedAt":"2014-02-03T23:26:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> As was recently shown (c839f1bd \"combine-diff: optimize\n> combine_diff_path sets intersection\"), combine-diff runs very slowly. In\n> that commit we optimized paths sets intersection, but that accounted\n> only for ~ 25% of the slowness, and as my tracing showed, for linux.git\n> v3.10..v3.11, for merges a lot of time is spent computing\n> diff(commit,commit^2) just to only then intersect that huge diff to\n> almost small set of files from diff(commit,commit^1).\n>\n> That's because at present, to compute combine-diff, for first finding\n> paths, that \"every parent touches\", we use the following combine-diff\n> property/definition:\n>\n> D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn) (w.r.t. paths)\n>\n> where\n>\n> D(A,P1...Pn) is combined diff between commit A, and parents Pi\n>\n> and\n>\n> D(A,Pi) is usual two-tree diff Pi..A\n\nand A ^ B means what???\n\nI do like the approach of walking the tree entries and stop as\nshallowly as possible without recursing.\n"},{"id":"234172","messageId":"xmqqeh3jbwbt.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"xmqqk3dbbwwf.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-03T23:39:02Z","receivedAt":"2014-02-03T23:39:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Kirill Smelkov writes:\n>\n>> As was recently shown (c839f1bd \"combine-diff: optimize\n>> combine_diff_path sets intersection\"), combine-diff runs very slowly. In\n>> that commit we optimized paths sets intersection, but that accounted\n>> only for ~ 25% of the slowness, and as my tracing showed, for linux.git\n>> v3.10..v3.11, for merges a lot of time is spent computing\n>> diff(commit,commit^2) just to only then intersect that huge diff to\n>> almost small set of files from diff(commit,commit^1).\n>>\n>> That's because at present, to compute combine-diff, for first finding\n>> paths, that \"every parent touches\", we use the following combine-diff\n>> property/definition:\n>>\n>> D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn) (w.r.t. paths)\n>>\n>> where\n>>\n>> D(A,P1...Pn) is combined diff between commit A, and parents Pi\n>>\n>> and\n>>\n>> D(A,Pi) is usual two-tree diff Pi..A\n>\n> and A ^ B means what???\n\nSilly me; obviously it is the \"set intersection\" operator.\n\nWe probably could instead use the \"current\" set of paths as literal\npathspec to compute subsequent paths, i.e.\n\n\tD(A,Pi,PS) is two tree diff P1..A limited to paths PS\n\n\tD(A,P1...Pn) = D(A,P1,[]) ^\n \t D(A,P2,D(A,P1,[])) ^\n ...\n \t D(A,Pn,D(A,P1...Pn-1))\n\nif we did not want to reinvent the whole tree walking thing, which\nwould add risks for new bugs and burden to maintain this and the\nusual two-tree diff tree walking in sync.\n"},{"id":"234175","messageId":"xmqq61ovbvcm.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"c0ad49d850377aedffa0a593fef8738112019b01.1391430523.git.kirr@mns.spb.ru","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-04T00:00:09Z","receivedAt":"2014-02-04T00:00:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\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> +\tstruct combine_diff_path paths_head;\n\ndecl-after-statement; please fix.\n\n> +\tpaths_head.next = NULL;\n> +\n> +\tstruct strbuf base;\n\nlikewise.\n"},{"id":"234206","messageId":"20140204163400.GA20436@tugrik.mns.mnsspb.ru","threadId":"35786","inReplyTo":"xmqqeh3jbwbt.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-04T16:34:00Z","receivedAt":"2014-02-04T16:34:00Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Mon, Feb 03, 2014 at 03:39:02PM -0800, Junio C Hamano wrote:\n> Junio C Hamano writes:\n> \n> > Kirill Smelkov writes:\n> >\n> >> As was recently shown (c839f1bd \"combine-diff: optimize\n> >> combine_diff_path sets intersection\"), combine-diff runs very slowly. In\n> >> that commit we optimized paths sets intersection, but that accounted\n> >> only for ~ 25% of the slowness, and as my tracing showed, for linux.git\n> >> v3.10..v3.11, for merges a lot of time is spent computing\n> >> diff(commit,commit^2) just to only then intersect that huge diff to\n> >> almost small set of files from diff(commit,commit^1).\n> >>\n> >> That's because at present, to compute combine-diff, for first finding\n> >> paths, that \"every parent touches\", we use the following combine-diff\n> >> property/definition:\n> >>\n> >> D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn) (w.r.t. paths)\n> >>\n> >> where\n> >>\n> >> D(A,P1...Pn) is combined diff between commit A, and parents Pi\n> >>\n> >> and\n> >>\n> >> D(A,Pi) is usual two-tree diff Pi..A\n> >\n> > and A ^ B means what???\n> \n> Silly me; obviously it is the \"set intersection\" operator.\n> \n> We probably could instead use the \"current\" set of paths as literal\n> pathspec to compute subsequent paths, i.e.\n> \n> \tD(A,Pi,PS) is two tree diff P1..A limited to paths PS\n> \n> \tD(A,P1...Pn) = D(A,P1,[]) ^\n> \t D(A,P2,D(A,P1,[])) ^\n> ...\n> \t D(A,Pn,D(A,P1...Pn-1))\n> \n> if we did not want to reinvent the whole tree walking thing, which\n> would add risks for new bugs and burden to maintain this and the\n> usual two-tree diff tree walking in sync.\n\nJunio, I understand it is not good to duplicate code and increase\nmaintenance risks. On the other hand, I don't quite like the approach\nwith keeping current paths - it could work and be faster compared to\nwhat we had, but to me it is still suboptimal, because if the first diff\nD(A,P1) is huge then oops. Also, to implement it rationally, without\ndelving into unneeded recursion, we would need to do the diffing without\nrecursion, intersect results, and then recurse into overlapping subtrees,\nwhich means tree-walker rework anyway.\n\n\nInstead I propose we switch to the new tree walker completely. With the\nattached patch which draftly shows it (diff_tree is gone, the work is\ndone through diff_tree_combined_paths, and then the result is\n\"exported\" to diff_filepairs) all the tests pass. Also, timings for\n\n git log --raw --no-abbrev --no-renames\n \n ( without -c - it would be the same - we are not touching that code, it\n would only add, irrelevant-to-the-change constant time )\n\nare\n\n linux.git v3.10..v3.11 became 0.1% _faster_\n navy.git became 1.4% slower\n\n\nThat means, that the new tree-walker is correct and should be ok\nperformance-wise (I had not optimized it at all, yet).\n\nWhat would you say?\n\nThanks,\nKirill\n\nP.S. Thanks for commenting on other patches. I'll try to correct them\ntomorrow, as I have no more time today and need to run.\n\n\n---- 8< ----\nFrom: Kirill Smelkov \nDate: Tue, 4 Feb 2014 20:11:16 +0400\nSubject: [PATCH] X Show new tree-walker could be used instead of the old one\n\nAll tests pass. Timings for git log --raw --no-abrev --no-renames\n\n linux.git v3.10..v3.11 became 0.1% _faster_\n navy.git became 1.4% slower\n---\n diff.h | 2 ++\n line-log.c | 12 +++++++--\n revision.c | 16 ++++++-----\n tree-diff.c | 88 +++++++++++++++++++++++++++++++++++++++++++++++--------------\n 4 files changed, 90 insertions(+), 28 deletions(-)\n\ndiff --git a/diff.h b/diff.h\nindex 5496560..0a9845a 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -189,8 +189,10 @@ const char *diff_line_prefix(struct diff_options *);\n \n extern const char mime_boundary_leader[];\n \n+#if 0\n extern int diff_tree(struct tree_desc *t1, struct tree_desc *t2,\n \t\t const char *base, struct diff_options *opt);\n+#endif\n extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,\n \t\t\t const char *base, struct diff_options *opt);\n extern int diff_root_tree_sha1(const unsigned char *new, const char *base,\ndiff --git a/line-log.c b/line-log.c\nindex 717638b..5739bbf 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -766,6 +766,7 @@ void line_log_init(struct rev_info *rev, const char *prefix, struct string_list\n \t}\n }\n \n+#if 0\n static void load_tree_desc(struct tree_desc *desc, void **tree,\n \t\t\t const unsigned char *sha1)\n {\n@@ -775,6 +776,7 @@ static void load_tree_desc(struct tree_desc *desc, void **tree,\n \t\tdie(\"Unable to read tree (%s)\", sha1_to_hex(sha1));\n \tinit_tree_desc(desc, *tree, size);\n }\n+#endif\n \n static int count_parents(struct commit *commit)\n {\n@@ -843,17 +845,23 @@ static void queue_diffs(struct line_log_data *range,\n \t\t\tstruct commit *commit, struct commit *parent)\n {\n \tvoid *tree1 = NULL, *tree2 = NULL;\n-\tstruct tree_desc desc1, desc2;\n+//\tstruct tree_desc desc1, desc2;\n \n \tassert(commit);\n+#if 0\n \tload_tree_desc(&desc2, &tree2, commit->tree->object.sha1);\n \tif (parent)\n \t\tload_tree_desc(&desc1, &tree1, parent->tree->object.sha1);\n \telse\n \t\tinit_tree_desc(&desc1, \"\", 0);\n+#endif\n \n \tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n-\tdiff_tree(&desc1, &desc2, \"\", opt);\n+//\tdiff_tree(&desc1, &desc2, \"\", opt);\n+\tdiff_tree_sha1(parent ? parent->tree->object.sha1 : null_sha1,\n+\t\t\tcommit->tree->object.sha1, \"\", opt);\n+\n+\n \tif (opt->detect_rename) {\n \t\tfilter_diffs_for_paths(range, 1);\n \t\tif (diff_might_be_rename())\ndiff --git a/revision.c b/revision.c\nindex 18ec339..ecc250b 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -496,24 +496,28 @@ static int rev_compare_tree(struct rev_info *revs,\n static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n {\n \tint retval;\n-\tvoid *tree;\n-\tunsigned long size;\n-\tstruct tree_desc empty, real;\n+//\tvoid *tree;\n+//\tunsigned long size;\n+//\tstruct tree_desc empty, real;\n \tstruct tree *t1 = commit->tree;\n \n \tif (!t1)\n \t\treturn 0;\n \n+#if 0\n \ttree = read_object_with_reference(t1->object.sha1, tree_type, &size, NULL);\n \tif (!tree)\n-\t\treturn 0;\n+\t\treturn 0;\t// XXX ok?\n \tinit_tree_desc(&real, tree, size);\n \tinit_tree_desc(&empty, \"\", 0);\n+#endif\n \n \ttree_difference = REV_TREE_SAME;\n \tDIFF_OPT_CLR(&revs->pruning, HAS_CHANGES);\n-\tretval = diff_tree(&empty, &real, \"\", &revs->pruning);\n-\tfree(tree);\n+//\tretval = diff_tree(&empty, &real, \"\", &revs->pruning);\n+\tretval = diff_tree_sha1(null_sha1, t1->object.sha1, \"\", &revs->pruning);\n+\n+//\tfree(tree);\n \n \treturn retval >= 0 && (tree_difference == REV_TREE_SAME);\n }\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 7f4f917..9f2a69b 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -6,6 +6,7 @@\n #include \"diffcore.h\"\n #include \"tree.h\"\n \n+#if 0\n static void show_entry(struct diff_options *opt, const char *prefix,\n \t\t struct tree_desc *desc, struct strbuf *base);\n \n@@ -106,6 +107,7 @@ static void show_entry(struct diff_options *opt, const char *prefix,\n \n \tstrbuf_setlen(base, old_baselen);\n }\n+#endif\n \n static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,\n \t\t\t struct diff_options *opt)\n@@ -123,6 +125,7 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,\n \t}\n }\n \n+#if 0\n int diff_tree(struct tree_desc *t1, struct tree_desc *t2,\n \t const char *base_str, struct diff_options *opt)\n {\n@@ -171,6 +174,7 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,\n \tstrbuf_release(&base);\n \treturn 0;\n }\n+#endif\n \n \n /*\n@@ -529,23 +533,25 @@ struct combine_diff_path *diff_tree_combined_paths(\n \t\tcase 0:\n \t\t\t/* are either xk > xi or diff(a,xk) != ø ? */\n \t\t\talldifferent = 1;\n-\t\t\tentry_sha1 = tree_entry_extract(&t, &path, &mode);\n-\t\t\tfor (i = 0; i < nparent; i++) {\n-\t\t\t\tconst unsigned char *sha1_i;\n-\t\t\t\tconst char *path_i;\n-\t\t\t\tunsigned mode_i;\n-\n-\t\t\t\t/* x[i] > x[imin] */\n-\t\t\t\tif (xmin_pathcmpv[i])\n-\t\t\t\t\tcontinue;\n-\n-\t\t\t\t/* diff(a,xk) != ø */\n-\t\t\t\tsha1_i = tree_entry_extract(&tp[i], &path_i, &mode_i);\n-\t\t\t\tif (hashcmp(entry_sha1, sha1_i) || (mode != mode_i))\n-\t\t\t\t\tcontinue;\n-\n-\t\t\t\talldifferent = 0;\n-\t\t\t\tbreak;\n+\t\t\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER)) {\n+\t\t\t\tentry_sha1 = tree_entry_extract(&t, &path, &mode);\n+\t\t\t\tfor (i = 0; i < nparent; i++) {\n+\t\t\t\t\tconst unsigned char *sha1_i;\n+\t\t\t\t\tconst char *path_i;\n+\t\t\t\t\tunsigned mode_i;\n+\n+\t\t\t\t\t/* x[i] > x[imin] */\n+\t\t\t\t\tif (xmin_pathcmpv[i])\n+\t\t\t\t\t\tcontinue;\n+\n+\t\t\t\t\t/* diff(a,xk) != ø */\n+\t\t\t\t\tsha1_i = tree_entry_extract(&tp[i], &path_i, &mode_i);\n+\t\t\t\t\tif (hashcmp(entry_sha1, sha1_i) || (mode != mode_i))\n+\t\t\t\t\t\tcontinue;\n+\n+\t\t\t\t\talldifferent = 0;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t}\n \n \t\t\t/* D += {δ(a,xk) if xk=xi; \"+a\" if xk > xi} */\n@@ -594,7 +600,8 @@ static inline int diff_might_be_rename(void)\n \t\t!DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);\n }\n \n-static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)\n+//static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)\n+static void try_to_follow_renames(const unsigned char *sha1_old, const unsigned char *sha1_new, const char *base, struct diff_options *opt)\n {\n \tstruct diff_options diff_opts;\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n@@ -632,7 +639,8 @@ static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, co\n \tdiff_opts.break_opt = opt->break_opt;\n \tdiff_opts.rename_score = opt->rename_score;\n \tdiff_setup_done(&diff_opts);\n-\tdiff_tree(t1, t2, base, &diff_opts);\n+//\tdiff_tree(t1, t2, base, &diff_opts);\n+\tdiff_tree_sha1(sha1_old, sha1_new, base, &diff_opts);\n \tdiffcore_std(&diff_opts);\n \tfree_pathspec(&diff_opts.pathspec);\n \n@@ -693,11 +701,13 @@ static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, co\n \n int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)\n {\n+#if 0\n \tvoid *tree1, *tree2;\n \tstruct tree_desc t1, t2;\n \tunsigned long size1, size2;\n \tint retval;\n \n+\t// TODO use xfill_tree_descriptor\n \ttree1 = read_object_with_reference(old, tree_type, &size1, NULL);\n \tif (!tree1)\n \t\tdie(\"unable to read source tree (%s)\", sha1_to_hex(old));\n@@ -707,23 +717,60 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha\n \tinit_tree_desc(&t1, tree1, size1);\n \tinit_tree_desc(&t2, tree2, size2);\n \tretval = diff_tree(&t1, &t2, base, opt);\n+#endif\n+\tstruct combine_diff_path phead, *p, *pprev;\n+\tphead.next = NULL;\n+\n+\tstruct strbuf basebuf;\n+\tstrbuf_init(&basebuf, PATH_MAX);\n+\tstrbuf_addstr(&basebuf, base);\n+\n+\tconst unsigned char *parents_sha1[1] = {new};\n+\n+\tdiff_tree_combined_paths(&phead, old, parents_sha1, 1, &basebuf, opt);\n+\n+\tstrbuf_release(&basebuf);\n+\n+\t// paths -> diff_q\n+\tfor (p = phead.next; p;) {\n+\t\tstruct combine_diff_parent *p0 = &p->parent[0];\n+\t\topt->change(opt, p->mode, p0->mode, p->sha1, p0->sha1,\n+\t\t\tp->mode != 0, p0->mode != 0,\n+\t\t\tp->path, 0, 0);\n+\n+\t\tpprev = p;\n+\t\tp = p->next;\n+\t\tfree(pprev);\n+\t}\n+\n \tif (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {\n+#if 0\n \t\tinit_tree_desc(&t1, tree1, size1);\n \t\tinit_tree_desc(&t2, tree2, size2);\n \t\ttry_to_follow_renames(&t1, &t2, base, opt);\n+#endif\n+\t\ttry_to_follow_renames(old, new, base, opt);\n \t}\n+#if 0\n \tfree(tree1);\n \tfree(tree2);\n-\treturn retval;\n+#endif\n+//\treturn retval;\n+\treturn 0;\n }\n \n int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)\n {\n+#if 0\n \tint retval;\n \tvoid *tree;\n \tunsigned long size;\n \tstruct tree_desc empty, real;\n+#endif\n \n+\treturn diff_tree_sha1(null_sha1, new, base, opt);\n+\n+#if 0\n \ttree = read_object_with_reference(new, tree_type, &size, NULL);\n \tif (!tree)\n \t\tdie(\"unable to read root tree (%s)\", sha1_to_hex(new));\n@@ -733,4 +780,5 @@ int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_\n \tretval = diff_tree(&empty, &real, base, opt);\n \tfree(tree);\n \treturn retval;\n+#endif\n }\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234213","messageId":"xmqq4n4eafmj.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"20140204163400.GA20436@tugrik.mns.mnsspb.ru","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-04T18:37:24Z","receivedAt":"2014-02-04T18:37:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n>> if we did not want to reinvent the whole tree walking thing, which\n>> would add risks for new bugs and burden to maintain this and the\n>> usual two-tree diff tree walking in sync.\n>\n> Junio, I understand it is not good to duplicate code and increase\n> maintenance risks....\n> Instead I propose we switch to the new tree walker completely.\n\nI am not fundamentally opposed to the idea. We'll see what happens.\n"},{"id":"234276","messageId":"20140205103601.GA5034@tugrik.mns.mnsspb.ru","threadId":"35786","inReplyTo":"xmqqzjm7bxny.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 2/8] tests: add checking that combine-diff emits only correct paths","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-05T10:36:01Z","receivedAt":"2014-02-05T10:36:01Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Mon, Feb 03, 2014 at 03:10:08PM -0800, Junio C Hamano wrote:\n> Kirill Smelkov writes:\n> \n> > where \"correct paths\" stands for paths that are different to all\n> > parents.\n> >\n> > Up until now, we were testing combined diff only on one file, or on\n> > several files which were all different (t4038-diff-combined.sh).\n> >\n> > As recent thinko in \"simplify intersect_paths() further\" showed, and\n> > also, since we are going to rework code for finding paths different to\n> > all parents, lets write at least basic tests.\n> \n> Thanks. Some nitpicks.\n> \n> >\n> > Signed-off-by: Kirill Smelkov \n> > ---\n> > t/t4057-diff-combined-paths.sh | 106 +++++++++++++++++++++++++++++++++++++++++\n> > 1 file changed, 106 insertions(+)\n> > create mode 100755 t/t4057-diff-combined-paths.sh\n> >\n> > diff --git a/t/t4057-diff-combined-paths.sh b/t/t4057-diff-combined-paths.sh\n> > new file mode 100755\n> > index 0000000..e6e457d\n> > --- /dev/null\n> > +++ b/t/t4057-diff-combined-paths.sh\n> > @@ -0,0 +1,106 @@\n> > +#!/bin/sh\n> > +\n> > +test_description='combined diff show only paths that are different to all parents'\n> > +\n> > +. ./test-lib.sh\n> > +\n> > +# verify that diffc.expect matches output of\n> > +# `git diff -c --name-only HEAD HEAD^ HEAD^2`\n> > +diffc_verify() {\n> \n> Style: SP before (), i.e.\n> \n> \tdiffc_verify () {\n> \n> > +\tgit diff -c --name-only HEAD HEAD^ HEAD^2 >diffc.actual &&\n> > +\ttest_cmp diffc.expect diffc.actual\n> > +}\n> > +\n> > +test_expect_success 'trivial merge - combine-diff empty' '\n> > +\tfor i in `test_seq 1 9`\n> \n> Style: prefer $() over ``\n\nThanks, I've corrected the style.\n\n> \n> > +\tdo\n> > +\t\techo $i >$i.txt\t&&\n> > +\t\tgit add $i.txt\n> \n> Quiz. What happens when this \"git add\" fails with an earlier value\n> of $i?\n\nWe just continue and ignore the error = bad. On the other hand, there\nare a lot of places like this one in git's testsuite, and almost almost\nnobody cares. In a few places people add\n\n || exit\n\nto last command, but I wonder, is there a way to omit the boilerplate,\nand also || exit is not strictly correct, as sometime we would need to\nanalyse `for` exit code for good and also for bad, and exit just exits\nfrom shell... What would be the most convenient thing to do here?\n\nPlease find patch with style issues corrected below\n\nThanks,\nKirill\n\n---- 8< -----\nFrom: Kirill Smelkov \nDate: Mon, 3 Feb 2014 13:08:49 +0400\nSubject: [PATCH] tests: add checking that combine-diff emits only correct paths\n\nwhere \"correct paths\" stands for paths that are different to all\nparents.\n\nUp until now, we were testing combined diff only on one file, or on\nseveral files which were all different (t4038-diff-combined.sh).\n\nAs recent thinko in \"simplify intersect_paths() further\" showed, and\nalso, since we are going to rework code for finding paths different to\nall parents, lets write at least basic tests.\n\nSigned-off-by: Kirill Smelkov \n---\n t/t4057-diff-combined-paths.sh | 106 +++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 106 insertions(+)\n create mode 100755 t/t4057-diff-combined-paths.sh\n\ndiff --git a/t/t4057-diff-combined-paths.sh b/t/t4057-diff-combined-paths.sh\nnew file mode 100755\nindex 0000000..097e632\n--- /dev/null\n+++ b/t/t4057-diff-combined-paths.sh\n@@ -0,0 +1,106 @@\n+#!/bin/sh\n+\n+test_description='combined diff show only paths that are different to all parents'\n+\n+. ./test-lib.sh\n+\n+# verify that diffc.expect matches output of\n+# `git diff -c --name-only HEAD HEAD^ HEAD^2`\n+diffc_verify () {\n+\tgit diff -c --name-only HEAD HEAD^ HEAD^2 >diffc.actual &&\n+\ttest_cmp diffc.expect diffc.actual\n+}\n+\n+test_expect_success 'trivial merge - combine-diff empty' '\n+\tfor i in $(test_seq 1 9)\n+\tdo\n+\t\techo $i >$i.txt\t&&\n+\t\tgit add $i.txt\n+\tdone &&\n+\tgit commit -m \"init\" &&\n+\tgit checkout -b side &&\n+\tfor i in $(test_seq 2 9)\n+\tdo\n+\t\techo $i/2 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"side 2-9\" &&\n+\tgit checkout master &&\n+\techo 1/2 >1.txt &&\n+\tgit commit -a -m \"master 1\" &&\n+\tgit merge side &&\n+\t>diffc.expect &&\n+\tdiffc_verify\n+'\n+\n+\n+test_expect_success 'only one trully conflicting path' '\n+\tgit checkout side &&\n+\tfor i in $(test_seq 2 9)\n+\tdo\n+\t\techo $i/3 >>$i.txt\n+\tdone &&\n+\techo \"4side\" >>4.txt &&\n+\tgit commit -a -m \"side 2-9 +4\" &&\n+\tgit checkout master &&\n+\tfor i in $(test_seq 1 9)\n+\tdo\n+\t\techo $i/3 >>$i.txt\n+\tdone &&\n+\techo \"4master\" >>4.txt &&\n+\tgit commit -a -m \"master 1-9 +4\" &&\n+\ttest_must_fail git merge side &&\n+\tcat <<-\\EOF >4.txt &&\n+\t4\n+\t4/2\n+\t4/3\n+\t4master\n+\t4side\n+\tEOF\n+\tgit add 4.txt &&\n+\tgit commit -m \"merge side (2)\" &&\n+\techo 4.txt >diffc.expect &&\n+\tdiffc_verify\n+'\n+\n+test_expect_success 'merge introduces new file' '\n+\tgit checkout side &&\n+\tfor i in $(test_seq 5 9)\n+\tdo\n+\t\techo $i/4 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"side 5-9\" &&\n+\tgit checkout master &&\n+\tfor i in $(test_seq 1 3)\n+\tdo\n+\t\techo $i/4 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"master 1-3 +4hello\" &&\n+\tgit merge side &&\n+\techo \"Hello World\" >4hello.txt &&\n+\tgit add 4hello.txt &&\n+\tgit commit --amend &&\n+\techo 4hello.txt >diffc.expect &&\n+\tdiffc_verify\n+'\n+\n+test_expect_success 'merge removed a file' '\n+\tgit checkout side &&\n+\tfor i in $(test_seq 5 9)\n+\tdo\n+\t\techo $i/5 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"side 5-9\" &&\n+\tgit checkout master &&\n+\tfor i in $(test_seq 1 3)\n+\tdo\n+\t\techo $i/4 >>$i.txt\n+\tdone &&\n+\tgit commit -a -m \"master 1-3\" &&\n+\tgit merge side &&\n+\tgit rm 4.txt &&\n+\tgit commit --amend &&\n+\techo 4.txt >diffc.expect &&\n+\tdiffc_verify\n+'\n+\n+test_done\n-- \n1.9.rc1.181.g641f458\n"},{"id":"234280","messageId":"20140205165119.GA18558@tugrik.mns.mnsspb.ru","threadId":"35786","inReplyTo":"xmqq4n4eafmj.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-05T16:51:19Z","receivedAt":"2014-02-05T16:51:19Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Tue, Feb 04, 2014 at 10:37:24AM -0800, Junio C Hamano wrote:\n> Kirill Smelkov writes:\n> \n> >> if we did not want to reinvent the whole tree walking thing, which\n> >> would add risks for new bugs and burden to maintain this and the\n> >> usual two-tree diff tree walking in sync.\n> >\n> > Junio, I understand it is not good to duplicate code and increase\n> > maintenance risks....\n> > Instead I propose we switch to the new tree walker completely.\n> \n> I am not fundamentally opposed to the idea. We'll see what happens.\n\nThanks. Locally, with draft patches with generalized tree-walker, for\n`git log --raw --no-abbrev --no-renames` I was able to get to as fast as\nwith old two-tree walker for navy.git and 1% faster for linux.git and\nall tests pass.\n\nOnly, before I clean things up, I'd like to ask - would the following\npatch be accepted\n\n---- 8< ---\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 79dba1d..4dc86c7 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -37,7 +37,7 @@ static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned\n \n \t/* Initialize the descriptor entry */\n \tdesc->entry.path = path;\n-\tdesc->entry.mode = mode;\n+\tdesc->entry.mode = canon_mode(mode);\n \tdesc->entry.sha1 = (const unsigned char *)(path + len);\n }\n \ndiff --git a/tree-walk.h b/tree-walk.h\nindex ae04b64..ae7fb3a 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -16,7 +16,7 @@ struct tree_desc {\n static inline const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)\n {\n \t*pathp = desc->entry.path;\n-\t*modep = canon_mode(desc->entry.mode);\n+\t*modep = desc->entry.mode;\n \treturn desc->entry.sha1;\n }\n---- 8< ---\n \n?\n\nThe reason I ask is because it is more handy to work with tree_desc\nstructures, compared to splitting it to sha1/path/mode/pathlen, and\nif canon_mode() is done only once, clients don't have to pay the\nperformance price of canon_mode on each tree_desc \"extract\".\n\nI understand there is fsck, which on invalid tree entry prints the mode,\nbut maybe somehow fsck should be special, and common interface be tuned\nto usual clients?\n\nThanks,\nKirill\n"},{"id":"234292","messageId":"xmqqfvnx5umg.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"20140205165119.GA18558@tugrik.mns.mnsspb.ru","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-05T17:36:55Z","receivedAt":"2014-02-05T17:36:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> Only, before I clean things up, I'd like to ask - would the following\n> patch be accepted\n>\n> ---- 8< ---\n> diff --git a/tree-walk.c b/tree-walk.c\n> index 79dba1d..4dc86c7 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -37,7 +37,7 @@ static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned\n> \n> \t/* Initialize the descriptor entry */\n> \tdesc->entry.path = path;\n> -\tdesc->entry.mode = mode;\n> +\tdesc->entry.mode = canon_mode(mode);\n> \tdesc->entry.sha1 = (const unsigned char *)(path + len);\n> }\n> \n> diff --git a/tree-walk.h b/tree-walk.h\n> index ae04b64..ae7fb3a 100644\n> --- a/tree-walk.h\n> +++ b/tree-walk.h\n> @@ -16,7 +16,7 @@ struct tree_desc {\n> static inline const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)\n> {\n> \t*pathp = desc->entry.path;\n> -\t*modep = canon_mode(desc->entry.mode);\n> +\t*modep = desc->entry.mode;\n> \treturn desc->entry.sha1;\n> }\n> ---- 8< ---\n> \n> ?\n\nDoesn't desc point into and walks over the data we read from the\ntree object directly?\n\nWe try to keep (tree|commit)->buffer intact and that is done pretty\ndeliberately. While you are walking a tree or parsing a commit,\nsomebody else, perhaps called indirectly by a helper function you\ncall, may call lookup_object() for the same object, get the copy\nthat has already been read and start using it. This kind of change\nwill introduce bugs that are hard to debug unless it is done very\ncarefully (e.g. starting from making tree.buffer into a const pointer\nand propagating constness throughout the system), which might not be\nworth the pain.\n"},{"id":"234312","messageId":"20140205191427.GA3923@mini.zxlink","threadId":"35786","inReplyTo":"xmqqfvnx5umg.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Kirill Smelkov","fromEmail":"kirr@navytux.spb.ru","sentAt":"2014-02-05T19:14:27Z","receivedAt":"2014-02-05T19:14:27Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Wed, Feb 05, 2014 at 09:36:55AM -0800, Junio C Hamano wrote:\n> Kirill Smelkov writes:\n> \n> > Only, before I clean things up, I'd like to ask - would the following\n> > patch be accepted\n> >\n> > ---- 8< ---\n> > diff --git a/tree-walk.c b/tree-walk.c\n> > index 79dba1d..4dc86c7 100644\n> > --- a/tree-walk.c\n> > +++ b/tree-walk.c\n> > @@ -37,7 +37,7 @@ static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned\n> > \n> > \t/* Initialize the descriptor entry */\n> > \tdesc->entry.path = path;\n> > -\tdesc->entry.mode = mode;\n> > +\tdesc->entry.mode = canon_mode(mode);\n> > \tdesc->entry.sha1 = (const unsigned char *)(path + len);\n> > }\n> > \n> > diff --git a/tree-walk.h b/tree-walk.h\n> > index ae04b64..ae7fb3a 100644\n> > --- a/tree-walk.h\n> > +++ b/tree-walk.h\n> > @@ -16,7 +16,7 @@ struct tree_desc {\n> > static inline const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)\n> > {\n> > \t*pathp = desc->entry.path;\n> > -\t*modep = canon_mode(desc->entry.mode);\n> > +\t*modep = desc->entry.mode;\n> > \treturn desc->entry.sha1;\n> > }\n> > ---- 8< ---\n> > \n> > ?\n> \n> Doesn't desc point into and walks over the data we read from the\n> tree object directly?\n> \n> We try to keep (tree|commit)->buffer intact and that is done pretty\n> deliberately. While you are walking a tree or parsing a commit,\n> somebody else, perhaps called indirectly by a helper function you\n> call, may call lookup_object() for the same object, get the copy\n> that has already been read and start using it. This kind of change\n> will introduce bugs that are hard to debug unless it is done very\n> carefully (e.g. starting from making tree.buffer into a const pointer\n> and propagating constness throughout the system), which might not be\n> worth the pain.\n\nI agree object data should be immutable for good. The only thing I'm talking\nabout here is mode, which is parsed from a tree buffer and is stored in\nseparate field:\n\n ---- 8< ---- tree-walk.h\n struct name_entry {\n const unsigned char *sha1;\n const char *path;\n unsigned int mode; <---\n };\n\n struct tree_desc {\n const void *buffer;\n struct name_entry entry;\n unsigned int size;\n };\n\n ---- 8< ---- tree-walk.c\n const char *get_mode(const char *str, unsigned int *modep)\n { ... } /* parses symbolic mode from tree buffer to uint */\n\n void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)\n {\n const char *path;\n unsigned int mode, len;\n\n ...\n path = get_mode(buf, &mode);\n\n /* Initialize the descriptor entry */\n desc->entry.path = path;\n desc->entry.mode = mode; <---\n desc->entry.sha1 = (const unsigned char *)(path + len);\n\n\nso we are not talking about modifying object buffers here. All I'm\nasking is about canonicalizing _already_ parsed and copied mode on the\nfly.\n\nDoes that change anything?\n\n\nSorry, if I'm maybe misunderstanding something, and thanks,\nKirill\n"},{"id":"234321","messageId":"xmqq61ot4a8e.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"20140205191427.GA3923@mini.zxlink","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-05T19:42:41Z","receivedAt":"2014-02-05T19:42:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> I agree object data should be immutable for good. The only thing I'm talking\n> about here is mode, which is parsed from a tree buffer and is stored in\n> separate field:\n\nAh, I do not see any problem in that case, then.\n\nThanks.\n"},{"id":"234326","messageId":"20140205202248.GB4695@mini.zxlink","threadId":"35786","inReplyTo":"xmqq61ot4a8e.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Kirill Smelkov","fromEmail":"kirr@navytux.spb.ru","sentAt":"2014-02-05T20:22:48Z","receivedAt":"2014-02-05T20:22:48Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Wed, Feb 05, 2014 at 11:42:41AM -0800, Junio C Hamano wrote:\n> Kirill Smelkov writes:\n> \n> > I agree object data should be immutable for good. The only thing I'm talking\n> > about here is mode, which is parsed from a tree buffer and is stored in\n> > separate field:\n> \n> Ah, I do not see any problem in that case, then.\n> \n> Thanks.\n\nThanks, that simplifies things for me.\n"},{"id":"234346","messageId":"xmqqfvnx180z.fsf@gitster.dls.corp.google.com","threadId":"35786","inReplyTo":"20140205202248.GB4695@mini.zxlink","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-02-05T22:58:36Z","receivedAt":"2014-02-05T22:58:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov writes:\n\n> On Wed, Feb 05, 2014 at 11:42:41AM -0800, Junio C Hamano wrote:\n>> Kirill Smelkov writes:\n>> \n>> > I agree object data should be immutable for good. The only thing I'm talking\n>> > about here is mode, which is parsed from a tree buffer and is stored in\n>> > separate field:\n>> \n>> Ah, I do not see any problem in that case, then.\n>> \n>> Thanks.\n>\n> Thanks, that simplifies things for me.\n\nSurely.\n\nBe careful when traversing N-trees in parallel---you may have to\nwatch out for the entry ordering rules that sorts the following\npaths in the order shown:\n\n\ta\n\ta-b\n a/b\n a_b\n\nInside a single tree, you cannot have 'a' and 'a/b' at the same\ntime, but one tree may have 'a' (without 'a/b') while another one\nmay have 'a/b' (without 'a'), and walking them in parallel has\nhistorically been one source of funny bugs.\n"},{"id":"234376","messageId":"20140206162254.GA28889@tugrik.mns.mnsspb.ru","threadId":"35786","inReplyTo":"xmqqfvnx180z.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 7/8] combine-diff: Fast changed-to-all-parents paths scanning","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-02-06T16:22:54Z","receivedAt":"2014-02-06T16:22:54Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Wed, Feb 05, 2014 at 02:58:36PM -0800, Junio C Hamano wrote:\n> Kirill Smelkov writes:\n> \n> > On Wed, Feb 05, 2014 at 11:42:41AM -0800, Junio C Hamano wrote:\n> >> Kirill Smelkov writes:\n> >> \n> >> > I agree object data should be immutable for good. The only thing I'm talking\n> >> > about here is mode, which is parsed from a tree buffer and is stored in\n> >> > separate field:\n> >> \n> >> Ah, I do not see any problem in that case, then.\n> >> \n> >> Thanks.\n> >\n> > Thanks, that simplifies things for me.\n\nBelow is a patch which does it. Please apply, if it is ok.\n\n\n> Surely.\n> \n> Be careful when traversing N-trees in parallel---you may have to\n> watch out for the entry ordering rules that sorts the following\n> paths in the order shown:\n> \n> \ta\n> \ta-b\n> a/b\n> a_b\n> \n> Inside a single tree, you cannot have 'a' and 'a/b' at the same\n> time, but one tree may have 'a' (without 'a/b') while another one\n> may have 'a/b' (without 'a'), and walking them in parallel has\n> historically been one source of funny bugs.\n\nThanks for the warning. I'm relying here on base_name_compare() and\nordering it imposes on entries and how it differentiates directories and\nfiles, so let's hope this should be ok.\n\nActual reworking is still in flux though...\n\nThanks,\nKirill\n\n\n---- 8< ----\nFrom: Kirill Smelkov \nDate: Thu, 6 Feb 2014 15:36:31 +0400\nSubject: [PATCH] Finally switch over tree descriptors to contain a pre-parsed entry\n\nThis continues 4651ece8 (Switch over tree descriptors to contain a\npre-parsed entry) and moves the only rest computational part\n\n mode = canon_mode(mode)\n\nfrom tree_entry_extract() to tree entry decode phase - to\ndecode_tree_entry().\n\nThe reason to do it, is that canon_mode() is at least 2 conditional\njumps for regular files, and that could be noticeable should canon_mode()\nbe invoked several times.\n\nThat does not matter for current Git codebase, where typical tree\ntraversal is\n\n while (t->size) {\n sha1 = tree_entry_extract(t, &path, &mode);\n ...\n update_tree_entry(t);\n }\n\ni.e. we do t -> sha1,path.mode \"extraction\" only once per entry. In such\ncases, it does not matter performance-wise, where that mode\ncanonicalization is done - either once in tree_entry_extract(), or once\nin decode_tree_entry() called by update_tree_entry() - it is\napproximately the same.\n\nBut for future code, which could need to work with several tree_desc's\nin parallel, it could be handy to operate on tree_desc descriptors, and\ndo \"extracts\" only when needed, or at all, access only relevant part of\nit through structure fields directly.\n\nAnd for such situations, having canon_mode() be done once in decode\nphase is better - we won't need to pay the performance price of 2 extra\nconditional jumps on every t->mode access.\n\nSo let's move mode canonicalization to decode_tree_entry(). That was the\nfinal bit. Now after tree entry is decoded, it is fully ready and could\nbe accessed either directly via field, or through tree_entry_extract()\nwhich this time got really \"totally trivial\".\n\nSigned-off-by: Kirill Smelkov \n---\n tree-walk.c | 2 +-\n tree-walk.h | 2 +-\n 2 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 79dba1d..4dc86c7 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -37,7 +37,7 @@ static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned\n \n \t/* Initialize the descriptor entry */\n \tdesc->entry.path = path;\n-\tdesc->entry.mode = mode;\n+\tdesc->entry.mode = canon_mode(mode);\n \tdesc->entry.sha1 = (const unsigned char *)(path + len);\n }\n \ndiff --git a/tree-walk.h b/tree-walk.h\nindex ae04b64..ae7fb3a 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -16,7 +16,7 @@ struct tree_desc {\n static inline const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)\n {\n \t*pathp = desc->entry.path;\n-\t*modep = canon_mode(desc->entry.mode);\n+\t*modep = desc->entry.mode;\n \treturn desc->entry.sha1;\n }\n \n-- \n1.9.rc1.181.g641f458\n"}]}