{"thread":{"id":"35695","subject":"[PATCH 0/4] `log -c` speedup","startedAt":"2014-01-20T16:20:37Z","lastAt":"2014-01-29T11:21:06Z","messageCount":8,"participants":["Kirill Smelkov","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"233401","messageId":"cover.1390234183.git.kirr@mns.spb.ru","threadId":"35695","inReplyTo":null,"subject":"[PATCH 0/4] `log -c` speedup","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-01-20T16:20:37Z","receivedAt":"2014-01-20T16:20:37Z","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 using `git log --raw` to reconstruct file dates (readonly filesystem for\ngit archives) and, as it turned out, for --raw to emit diffs for merges we need\nto explicitly activate combine-diff via -c.\n\nThe combined-diff turned out to be slow, I'm trying to optimize it. Please apply.\n\nThanks beforehand,\nKirill\n\n\nKirill Smelkov (4):\n  diffcore-order: Export generic ordering interface\n  diff test: Add tests for combine-diff with orderfile\n  combine-diff: Optimize combine_diff_path sets intersection\n  combine-diff: combine_diff_path.len is not needed anymore\n\n combine-diff.c        | 121 +++++++++++++++++++++++++++++++++-----------------\n diff-lib.c            |   2 -\n diff.h                |   1 -\n diffcore-order.c      |  53 ++++++++++++++--------\n diffcore.h            |  15 +++++++\n t/t4056-diff-order.sh |  21 +++++++++\n 6 files changed, 151 insertions(+), 62 deletions(-)\n\n-- \n1.9.rc0.143.g6fd479e\n"},{"id":"233403","messageId":"0fb4f53ca93de6ec8f6f11e9fbbe6199ea900f2c.1390234183.git.kirr@mns.spb.ru","threadId":"35695","inReplyTo":"cover.1390234183.git.kirr@mns.spb.ru","subject":"[PATCH 1/4] diffcore-order: Export generic ordering interface","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-01-20T16:20:38Z","receivedAt":"2014-01-20T16:20:38Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"At present, diffcore_order() interface is to accept only queue of\n`struct diff_filepair`.\n\nIn the next patches, we'll need to order `struct combine_diff_path` by path,\nso let's first rework diffcore-order to also provide generic low-level\ninterface for ordering arbitrary objects, provided they have path accessors.\n\nThe new interface is:\n\n    - `struct obj_order`    for describing objects to ordering routine, and\n    - order_objects()       for actually doing the ordering work.\n\nSigned-off-by: Kirill Smelkov <kirr@mns.spb.ru>\n---\n diffcore-order.c | 53 +++++++++++++++++++++++++++++++++++------------------\n diffcore.h       | 15 +++++++++++++++\n 2 files changed, 50 insertions(+), 18 deletions(-)\n\ndiff --git a/diffcore-order.c b/diffcore-order.c\nindex fe7f1f4..327a93e 100644\n--- a/diffcore-order.c\n+++ b/diffcore-order.c\n@@ -57,11 +57,7 @@ static void prepare_order(const char *orderfile)\n \t}\n }\n \n-struct pair_order {\n-\tstruct diff_filepair *pair;\n-\tint orig_order;\n-\tint order;\n-};\n+\n \n static int match_order(const char *path)\n {\n@@ -84,35 +80,56 @@ static int match_order(const char *path)\n \treturn order_cnt;\n }\n \n-static int compare_pair_order(const void *a_, const void *b_)\n+static int compare_objs_order(const void *a_, const void *b_)\n {\n-\tstruct pair_order const *a, *b;\n-\ta = (struct pair_order const *)a_;\n-\tb = (struct pair_order const *)b_;\n+\tstruct obj_order const *a, *b;\n+\ta = (struct obj_order const *)a_;\n+\tb = (struct obj_order const *)b_;\n \tif (a->order != b->order)\n \t\treturn a->order - b->order;\n \treturn a->orig_order - b->orig_order;\n }\n \n+\n+void order_objects(const char *orderfile, obj_path_fn_t obj_path,\n+\t\t\tstruct obj_order *objs, int nr)\n+{\n+\tint i;\n+\n+\tif (!nr)\n+\t\treturn;\n+\n+\tprepare_order(orderfile);\n+\tfor (i = 0; i < nr; i++) {\n+\t\tobjs[i].orig_order = i;\n+\t\tobjs[i].order = match_order(obj_path(objs[i].obj));\n+\t}\n+\tqsort(objs, nr, sizeof(*objs), compare_objs_order);\n+}\n+\n+\n+static const char *pair_pathtwo(void *obj)\n+{\n+\tstruct diff_filepair *pair = (struct diff_filepair *)obj;\n+\n+\treturn pair->two->path;\n+}\n+\n void diffcore_order(const char *orderfile)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n-\tstruct pair_order *o;\n+\tstruct obj_order *o;\n \tint i;\n \n \tif (!q->nr)\n \t\treturn;\n \n \to = xmalloc(sizeof(*o) * q->nr);\n-\tprepare_order(orderfile);\n-\tfor (i = 0; i < q->nr; i++) {\n-\t\to[i].pair = q->queue[i];\n-\t\to[i].orig_order = i;\n-\t\to[i].order = match_order(o[i].pair->two->path);\n-\t}\n-\tqsort(o, q->nr, sizeof(*o), compare_pair_order);\n \tfor (i = 0; i < q->nr; i++)\n-\t\tq->queue[i] = o[i].pair;\n+\t\to[i].obj = q->queue[i];\n+\torder_objects(orderfile, pair_pathtwo, o, q->nr);\n+\tfor (i = 0; i < q->nr; i++)\n+\t\tq->queue[i] = o[i].obj;\n \tfree(o);\n \treturn;\n }\ndiff --git a/diffcore.h b/diffcore.h\nindex 1c16c85..1fd00fc 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -111,6 +111,21 @@ extern void diffcore_merge_broken(void);\n extern void diffcore_pickaxe(struct diff_options *);\n extern void diffcore_order(const char *orderfile);\n \n+/* low-level interface to diffcore_order */\n+struct obj_order {\n+\tvoid *obj;\t/* setup by caller */\n+\n+\t/* setup/used by order_objects() */\n+\tint orig_order;\n+\tint order;\n+};\n+\n+typedef const char *(*obj_path_fn_t)(void *obj);\n+\n+void order_objects(const char *orderfile, obj_path_fn_t obj_path,\n+\t\t\tstruct obj_order *objs, int nr);\n+\n+\n #define DIFF_DEBUG 0\n #if DIFF_DEBUG\n void diff_debug_filespec(struct diff_filespec *, int, const char *);\n-- \n1.9.rc0.143.g6fd479e\n"},{"id":"233402","messageId":"0c3e9511a4ff373ecf432fcb4a5d00864e1d8b2a.1390234183.git.kirr@mns.spb.ru","threadId":"35695","inReplyTo":"cover.1390234183.git.kirr@mns.spb.ru","subject":"[PATCH 2/4] diff test: Add tests for combine-diff with orderfile","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-01-20T16:20:39Z","receivedAt":"2014-01-20T16:20:39Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"In the next patch combine-diff will have special code-path for taking\norderfile into account. Prepare for making changes by introducing\ncoverage tests for that case.\n\nSigned-off-by: Kirill Smelkov <kirr@mns.spb.ru>\n---\n t/t4056-diff-order.sh | 21 +++++++++++++++++++++\n 1 file changed, 21 insertions(+)\n\ndiff --git a/t/t4056-diff-order.sh b/t/t4056-diff-order.sh\nindex 9e2b29e..c0460bb 100755\n--- a/t/t4056-diff-order.sh\n+++ b/t/t4056-diff-order.sh\n@@ -97,4 +97,25 @@ do\n \t'\n done\n \n+test_expect_success 'setup for testing combine-diff order' '\n+\tgit checkout -b tmp HEAD~ &&\n+\tcreate_files 3 &&\n+\tgit checkout master &&\n+\tgit merge --no-commit -s ours tmp &&\n+\tcreate_files 5\n+'\n+\n+test_expect_success \"combine-diff: no order (=tree object order)\" '\n+\tgit diff --name-only HEAD HEAD^ HEAD^2 >actual &&\n+\ttest_cmp expect_none actual\n+'\n+\n+for i in 1 2\n+do\n+\ttest_expect_success \"combine-diff: orderfile using option ($i)\" '\n+\t\tgit diff -Oorder_file_$i --name-only HEAD HEAD^ HEAD^2 >actual &&\n+\t\ttest_cmp expect_$i actual\n+\t'\n+done\n+\n test_done\n-- \n1.9.rc0.143.g6fd479e\n"},{"id":"233405","messageId":"b97e63128093f6c5f5cab854b9b9487c4e6b955a.1390234183.git.kirr@mns.spb.ru","threadId":"35695","inReplyTo":"cover.1390234183.git.kirr@mns.spb.ru","subject":"[PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-01-20T16:20:40Z","receivedAt":"2014-01-20T16:20:40Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"Currently, when generating combined diff, for a commit, we intersect\ndiff paths from diff(parent_0,commit) to diff(parent_i,commit) comparing\nall paths pairs, i.e. doing it the quadratic way. That is correct, but\ncould be optimized:\n\nPaths come from trees in sorted (= tree) order, and so does diff_tree()\nemits resulting paths in that order too. Now if we look at diffcore\ntransformations, all of them, except diffcore_order, preserve resulting\npath ordering:\n\n    - skip_stat_unmatch, grep, pickaxe, filter\n                            -- just skip elements -> order stays preserved\n\n    - break                 -- just breaks diff for a path, adding path\n                               dup after the path -> order stays preserved\n\n    - detect rename/copy    -- resulting paths are emitted sorted\n                               (verified empirically)\n\nSo only diffcore_order changes diff paths ordering.\n\nBut diffcore_order meaning affects only presentation - i.e. only how to\nshow the diff, so we could do all the internal computations without\npaths reordering, and order only resultant paths set. This is faster,\nsince, if we know two paths sets are all ordered, their intersection\ncould be done in linear time.\n\nThis patch does just that.\n\nTimings for `git log --raw --no-abbrev --no-renames` without `-c` (\"git log\")\nand with `-c` (\"git log -c\") before and after the patch are as follows:\n\n                linux.git v3.10..v3.11\n\n            log     log -c\n\n    before  1.9s    20.4s\n    after   1.9s    16.6s\n\n                navy.git    (private repo)\n\n            log     log -c\n\n    before  0.83s   15.6s\n    after   0.83s    2.1s\n\nP.S.\n\nI think linux.git case is sped up not so much as the second one, since\nin navy.git, there are more exotic (subtree, etc) merges.\n\nP.P.S.\n\nMy tracing showed that the rest of the time (16.6s vs 1.9s) is usually\nspent in computing huge diffs from commit to second parent. Will try to\ndeal with it, if I'll have time.\n\nP.P.P.S.\n\nFor combine_diff_path, ->len is not needed anymore - will remove it in\nthe next noisy cleanup path, to maintain good signal/noise ratio here.\n\nSigned-off-by: Kirill Smelkov <kirr@mns.spb.ru>\n---\n combine-diff.c | 93 +++++++++++++++++++++++++++++++++++++++++++++-------------\n 1 file changed, 72 insertions(+), 21 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 3b92c448..98c2562 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -15,8 +15,8 @@\n static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n-\tstruct combine_diff_path *p;\n-\tint i;\n+\tstruct combine_diff_path *p, *pprev, *ptmp;\n+\tint i, cmp;\n \n \tif (!n) {\n \t\tstruct combine_diff_path *list = NULL, **tail = &list;\n@@ -47,28 +47,43 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n \t\treturn list;\n \t}\n \n-\tfor (p = curr; p; p = p->next) {\n-\t\tint found = 0;\n-\t\tif (!p->len)\n+\t/*\n+\t * NOTE paths are coming sorted here (= in tree order)\n+\t */\n+\n+\tpprev = NULL;\n+\tp = curr;\n+\ti = 0;\n+\n+\twhile (1) {\n+\t\tif (!p)\n+\t\t\tbreak;\n+\n+\t\tcmp = (i >= q->nr) ? -1\n+\t\t\t\t   : strcmp(p->path, q->queue[i]->two->path);\n+\t\tif (cmp < 0) {\n+\t\t\tif (pprev)\n+\t\t\t\tpprev->next = p->next;\n+\t\t\tptmp = p;\n+\t\t\tp = p->next;\n+\t\t\tfree(ptmp);\n+\t\t\tif (curr == ptmp)\n+\t\t\t\tcurr = p;\n \t\t\tcontinue;\n-\t\tfor (i = 0; i < q->nr; i++) {\n-\t\t\tconst char *path;\n-\t\t\tint len;\n+\t\t}\n \n-\t\t\tif (diff_unmodified_pair(q->queue[i]))\n-\t\t\t\tcontinue;\n-\t\t\tpath = q->queue[i]->two->path;\n-\t\t\tlen = strlen(path);\n-\t\t\tif (len == p->len && !memcmp(path, p->path, len)) {\n-\t\t\t\tfound = 1;\n-\t\t\t\thashcpy(p->parent[n].sha1, q->queue[i]->one->sha1);\n-\t\t\t\tp->parent[n].mode = q->queue[i]->one->mode;\n-\t\t\t\tp->parent[n].status = q->queue[i]->status;\n-\t\t\t\tbreak;\n-\t\t\t}\n+\t\tif (cmp > 0) {\n+\t\t\ti++;\n+\t\t\tcontinue;\n \t\t}\n-\t\tif (!found)\n-\t\t\tp->len = 0;\n+\n+\t\thashcpy(p->parent[n].sha1, q->queue[i]->one->sha1);\n+\t\tp->parent[n].mode = q->queue[i]->one->mode;\n+\t\tp->parent[n].status = q->queue[i]->status;\n+\n+\t\tpprev = p;\n+\t\tp = p->next;\n+\t\ti++;\n \t}\n \treturn curr;\n }\n@@ -1295,6 +1310,13 @@ static void handle_combined_callback(struct diff_options *opt,\n \tfree(q.queue);\n }\n \n+static const char *path_path(void *obj)\n+{\n+\tstruct combine_diff_path *path = (struct combine_diff_path *)obj;\n+\n+\treturn path->path;\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,6 +1332,8 @@ void diff_tree_combined(const unsigned char *sha1,\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 \tshow_log_first = !!rev->loginfo && !rev->no_commit_id;\n \tneedsep = 0;\n@@ -1335,6 +1359,13 @@ void diff_tree_combined(const unsigned char *sha1,\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+\t\t\tdiffcore_order(opt->orderfile);\n+\t\t}\n+\n \t\tdiff_flush(&diffopts);\n \t}\n \n@@ -1343,6 +1374,26 @@ void diff_tree_combined(const unsigned char *sha1,\n \t\tif (p->len)\n \t\t\tnum_paths++;\n \t}\n+\n+\t/* order paths according to diffcore_order */\n+\tif (opt->orderfile && num_paths) {\n+\t\tstruct obj_order *o;\n+\n+\t\to = xmalloc(sizeof(*o) * num_paths);\n+\t\tfor (i = 0, p = paths; p; p = p->next, i++)\n+\t\t\to[i].obj = p;\n+\t\torder_objects(opt->orderfile, path_path, o, num_paths);\n+\t\tfor (i = 0; i < num_paths - 1; i++) {\n+\t\t\tp = o[i].obj;\n+\t\t\tp->next = o[i+1].obj;\n+\t\t}\n+\n+\t\tp = o[num_paths-1].obj;\n+\t\tp->next = NULL;\n+\t\tpaths = o[0].obj;\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-- \n1.9.rc0.143.g6fd479e\n"},{"id":"233404","messageId":"81fdea65268f1d5cfe120ec37ee577f4639f9d74.1390234183.git.kirr@mns.spb.ru","threadId":"35695","inReplyTo":"cover.1390234183.git.kirr@mns.spb.ru","subject":"[PATCH 4/4] combine-diff: combine_diff_path.len is not needed anymore","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-01-20T16:20:41Z","receivedAt":"2014-01-20T16:20:41Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"Brefore previous patch, ->len was used to speedup name compares and also\nto mark removed paths via len=0. Now we do significantly less strcmp and\nalso just remove paths from list and free right after we know a path\nwill not be needed, so ->len is not needed anymore.\n\nSigned-off-by: Kirill Smelkov <kirr@mns.spb.ru>\n---\n combine-diff.c | 30 +++++++++---------------------\n diff-lib.c     |  2 --\n diff.h         |  1 -\n 3 files changed, 9 insertions(+), 24 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 98c2562..07faa96 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -31,7 +31,6 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n \t\t\tp->path = (char *) &(p->parent[num_parent]);\n \t\t\tmemcpy(p->path, path, len);\n \t\t\tp->path[len] = 0;\n-\t\t\tp->len = len;\n \t\t\tp->next = NULL;\n \t\t\tmemset(p->parent, 0,\n \t\t\t       sizeof(p->parent[0]) * num_parent);\n@@ -1234,8 +1233,6 @@ void show_combined_diff(struct combine_diff_path *p,\n {\n \tstruct diff_options *opt = &rev->diffopt;\n \n-\tif (!p->len)\n-\t\treturn;\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@@ -1299,11 +1296,8 @@ static void handle_combined_callback(struct diff_options *opt,\n \tq.queue = xcalloc(num_paths, sizeof(struct diff_filepair *));\n \tq.alloc = num_paths;\n \tq.nr = num_paths;\n-\tfor (i = 0, p = paths; p; p = p->next) {\n-\t\tif (!p->len)\n-\t\t\tcontinue;\n+\tfor (i = 0, p = paths; p; p = p->next)\n \t\tq.queue[i++] = combined_pair(p, num_parent);\n-\t}\n \topt->format_callback(&q, opt, opt->format_callback_data);\n \tfor (i = 0; i < num_paths; i++)\n \t\tfree_combined_pair(q.queue[i]);\n@@ -1369,11 +1363,9 @@ void diff_tree_combined(const unsigned char *sha1,\n \t\tdiff_flush(&diffopts);\n \t}\n \n-\t/* find out surviving paths */\n-\tfor (num_paths = 0, p = paths; p; p = p->next) {\n-\t\tif (p->len)\n-\t\t\tnum_paths++;\n-\t}\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/* order paths according to diffcore_order */\n \tif (opt->orderfile && num_paths) {\n@@ -1398,10 +1390,8 @@ void diff_tree_combined(const unsigned char *sha1,\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\tif (p->len)\n-\t\t\t\t\tshow_raw_diff(p, num_parent, rev);\n-\t\t\t}\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@@ -1414,11 +1404,9 @@ void diff_tree_combined(const unsigned char *sha1,\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\tif (p->len)\n-\t\t\t\t\tshow_patch_diff(p, num_parent, dense,\n-\t\t\t\t\t\t\t0, rev);\n-\t\t\t}\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 \t}\n \ndiff --git a/diff-lib.c b/diff-lib.c\nindex e6d33b3..938869d 100644\n--- a/diff-lib.c\n+++ b/diff-lib.c\n@@ -121,7 +121,6 @@ int run_diff_files(struct rev_info *revs, unsigned int option)\n \t\t\tdpath->path = (char *) &(dpath->parent[5]);\n \n \t\t\tdpath->next = NULL;\n-\t\t\tdpath->len = path_len;\n \t\t\tmemcpy(dpath->path, ce->name, path_len);\n \t\t\tdpath->path[path_len] = '\\0';\n \t\t\thashclr(dpath->sha1);\n@@ -323,7 +322,6 @@ static int show_modified(struct rev_info *revs,\n \t\tp = xmalloc(combine_diff_path_size(2, pathlen));\n \t\tp->path = (char *) &p->parent[2];\n \t\tp->next = NULL;\n-\t\tp->len = pathlen;\n \t\tmemcpy(p->path, new->name, pathlen);\n \t\tp->path[pathlen] = 0;\n \t\tp->mode = mode;\ndiff --git a/diff.h b/diff.h\nindex 0e6898f..a24a767 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -198,7 +198,6 @@ extern int diff_root_tree_sha1(const unsigned char *new, const char *base,\n \n struct combine_diff_path {\n \tstruct combine_diff_path *next;\n-\tint len;\n \tchar *path;\n \tunsigned int mode;\n \tunsigned char sha1[20];\n-- \n1.9.rc0.143.g6fd479e\n"},{"id":"233868","messageId":"20140128154654.GA5925@tugrik.mns.mnsspb.ru","threadId":"35695","inReplyTo":"b97e63128093f6c5f5cab854b9b9487c4e6b955a.1390234183.git.kirr@mns.spb.ru","subject":"Re: [PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-01-28T15:46:55Z","receivedAt":"2014-01-28T15:46:55Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Mon, Jan 20, 2014 at 08:20:40PM +0400, Kirill Smelkov wrote:\n[...]\n\n> @@ -1343,6 +1374,26 @@ void diff_tree_combined(const unsigned char *sha1,\n>  \t\tif (p->len)\n>  \t\t\tnum_paths++;\n>  \t}\n> +\n> +\t/* order paths according to diffcore_order */\n> +\tif (opt->orderfile && num_paths) {\n> +\t\tstruct obj_order *o;\n> +\n> +\t\to = xmalloc(sizeof(*o) * num_paths);\n> +\t\tfor (i = 0, p = paths; p; p = p->next, i++)\n> +\t\t\to[i].obj = p;\n> +\t\torder_objects(opt->orderfile, path_path, o, num_paths);\n> +\t\tfor (i = 0; i < num_paths - 1; i++) {\n> +\t\t\tp = o[i].obj;\n> +\t\t\tp->next = o[i+1].obj;\n> +\t\t}\n> +\n> +\t\tp = o[num_paths-1].obj;\n> +\t\tp->next = NULL;\n> +\t\tpaths = o[0].obj;\n> +\t}\n\nI found I've introduced memory leak here (malloc without free). Please\napply the fix.  Thanks, Kirill.\n\n---- 8< ----\nFrom: Kirill Smelkov <kirr@mns.spb.ru>\nDate: Tue, 28 Jan 2014 19:39:16 +0400\nSubject: [PATCH] fixup! combine-diff: Optimize combine_diff_path sets intersection\n\nPlug a memory leak.\n---\n combine-diff.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 07faa96..2d79312 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1383,6 +1383,7 @@ void diff_tree_combined(const unsigned char *sha1,\n \t\tp = o[num_paths-1].obj;\n \t\tp->next = NULL;\n \t\tpaths = o[0].obj;\n+\t\tfree(o);\n \t}\n \n \n-- \n1.9.rc1.181.g641f458\n"},{"id":"233873","messageId":"xmqqbnyvlqki.fsf@gitster.dls.corp.google.com","threadId":"35695","inReplyTo":"b97e63128093f6c5f5cab854b9b9487c4e6b955a.1390234183.git.kirr@mns.spb.ru","subject":"Re: [PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-28T21:55:09Z","receivedAt":"2014-01-28T21:55:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kirill Smelkov <kirr@mns.spb.ru> writes:\n\n> diff --git a/combine-diff.c b/combine-diff.c\n> index 3b92c448..98c2562 100644\n> --- a/combine-diff.c\n> +++ b/combine-diff.c\n> @@ -15,8 +15,8 @@\n> ...\n> +\twhile (1) {\n> ...\n> +\t\tif (cmp < 0) {\n> +\t\t\tif (pprev)\n> +\t\t\t\tpprev->next = p->next;\n> +\t\t\tptmp = p;\n> +\t\t\tp = p->next;\n> +\t\t\tfree(ptmp);\n> +\t\t\tif (curr == ptmp)\n> +\t\t\t\tcurr = p;\n>  \t\t\tcontinue;\n> ...\n> +\t\tif (cmp > 0) {\n> +\t\t\ti++;\n> +\t\t\tcontinue;\n>  \t\t}\n> ...\n> +\n> +\t\tpprev = p;\n> +\t\tp = p->next;\n> +\t\ti++;\n>  \t}\n>  \treturn curr;\n>  }\n\nThanks. I very much like the approach.\n\nI was staring at the above part of the code, but couldn't help\nrecalling this gem (look for \"understand pointers\" in the article):\n\n  http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions\n\nHow about doing it this way (on top of your patch)?  It reduces 7\nlines even though it adds two comment lines ;-)\n\n combine-diff.c | 37 +++++++++++++++----------------------\n 1 file changed, 15 insertions(+), 22 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 2d79312..0809e79 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -15,11 +15,10 @@\n static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)\n {\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n-\tstruct combine_diff_path *p, *pprev, *ptmp;\n+\tstruct combine_diff_path *p, **tail = &curr;\n \tint i, cmp;\n \n \tif (!n) {\n-\t\tstruct combine_diff_path *list = NULL, **tail = &list;\n \t\tfor (i = 0; i < q->nr; i++) {\n \t\t\tint len;\n \t\t\tconst char *path;\n@@ -43,35 +42,30 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n \t\t\t*tail = p;\n \t\t\ttail = &p->next;\n \t\t}\n-\t\treturn list;\n+\t\treturn curr;\n \t}\n \n \t/*\n-\t * NOTE paths are coming sorted here (= in tree order)\n+\t * paths in curr (linked list) and q->queue[] (array) are\n+\t * both sorted in the tree order.\n \t */\n-\n-\tpprev = NULL;\n-\tp = curr;\n \ti = 0;\n+\twhile ((p = *tail) != NULL) {\n+\t\tcmp = ((i >= q->nr)\n+\t\t       ? -1 : strcmp(p->path, q->queue[i]->two->path));\n \n-\twhile (1) {\n-\t\tif (!p)\n-\t\t\tbreak;\n-\n-\t\tcmp = (i >= q->nr) ? -1\n-\t\t\t\t   : strcmp(p->path, q->queue[i]->two->path);\n \t\tif (cmp < 0) {\n-\t\t\tif (pprev)\n-\t\t\t\tpprev->next = p->next;\n-\t\t\tptmp = p;\n-\t\t\tp = p->next;\n-\t\t\tfree(ptmp);\n-\t\t\tif (curr == ptmp)\n-\t\t\t\tcurr = p;\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\tfree(p);\n \t\t\tcontinue;\n \t\t}\n \n \t\tif (cmp > 0) {\n+\t\t\t/* q->queue[i] not in p->path; skip it */\n \t\t\ti++;\n \t\t\tcontinue;\n \t\t}\n@@ -80,8 +74,7 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n \t\tp->parent[n].mode = q->queue[i]->one->mode;\n \t\tp->parent[n].status = q->queue[i]->status;\n \n-\t\tpprev = p;\n-\t\tp = p->next;\n+\t\ttail = &p->next;\n \t\ti++;\n \t}\n \treturn curr;\n"},{"id":"233884","messageId":"20140129112106.GA3144@tugrik.mns.mnsspb.ru","threadId":"35695","inReplyTo":"xmqqbnyvlqki.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection","fromName":"Kirill Smelkov","fromEmail":"kirr@mns.spb.ru","sentAt":"2014-01-29T11:21:06Z","receivedAt":"2014-01-29T11:21:06Z","isPatch":true,"sender":{"key":"kirr@navytux.spb.ru","avatar":"https://gravatar.com/avatar/cf3445fdad1849941e17ab25bf1ee7c5ea1be2deb444be25ff5f36b0e50a985f?d=mp&s=160"},"body":"On Tue, Jan 28, 2014 at 01:55:09PM -0800, Junio C Hamano wrote:\n> Kirill Smelkov <kirr@mns.spb.ru> writes:\n> \n> > diff --git a/combine-diff.c b/combine-diff.c\n> > index 3b92c448..98c2562 100644\n> > --- a/combine-diff.c\n> > +++ b/combine-diff.c\n> > @@ -15,8 +15,8 @@\n> > ...\n> > +\twhile (1) {\n> > ...\n> > +\t\tif (cmp < 0) {\n> > +\t\t\tif (pprev)\n> > +\t\t\t\tpprev->next = p->next;\n> > +\t\t\tptmp = p;\n> > +\t\t\tp = p->next;\n> > +\t\t\tfree(ptmp);\n> > +\t\t\tif (curr == ptmp)\n> > +\t\t\t\tcurr = p;\n> >  \t\t\tcontinue;\n> > ...\n> > +\t\tif (cmp > 0) {\n> > +\t\t\ti++;\n> > +\t\t\tcontinue;\n> >  \t\t}\n> > ...\n> > +\n> > +\t\tpprev = p;\n> > +\t\tp = p->next;\n> > +\t\ti++;\n> >  \t}\n> >  \treturn curr;\n> >  }\n> \n> Thanks. I very much like the approach.\n> \n> I was staring at the above part of the code, but couldn't help\n> recalling this gem (look for \"understand pointers\" in the article):\n> \n>   http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions\n> \n> How about doing it this way (on top of your patch)?  It reduces 7\n> lines even though it adds two comment lines ;-)\n> \n>  combine-diff.c | 37 +++++++++++++++----------------------\n>  1 file changed, 15 insertions(+), 22 deletions(-)\n\nThanks, this is sound approach and adding guiding comments is good, and\nalso now some of us with self-taught heritage understand (or at least\nthey think so) pointers a bit better :)\n\nNow some nitpicks:\n\n> diff --git a/combine-diff.c b/combine-diff.c\n> index 2d79312..0809e79 100644\n> --- a/combine-diff.c\n> +++ b/combine-diff.c\n> @@ -15,11 +15,10 @@\n>  static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)\n>  {\n>  \tstruct diff_queue_struct *q = &diff_queued_diff;\n> -\tstruct combine_diff_path *p, *pprev, *ptmp;\n> +\tstruct combine_diff_path *p, **tail = &curr;\n>  \tint i, cmp;\n>  \n>  \tif (!n) {\n> -\t\tstruct combine_diff_path *list = NULL, **tail = &list;\n>  \t\tfor (i = 0; i < q->nr; i++) {\n>  \t\t\tint len;\n>  \t\t\tconst char *path;\n> @@ -43,35 +42,30 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n>  \t\t\t*tail = p;\n>  \t\t\ttail = &p->next;\n>  \t\t}\n> -\t\treturn list;\n> +\t\treturn curr;\n>  \t}\n>  \n>  \t/*\n> -\t * NOTE paths are coming sorted here (= in tree order)\n> +\t * paths in curr (linked list) and q->queue[] (array) are\n> +\t * both sorted in the tree order.\n>  \t */\n> -\n> -\tpprev = NULL;\n> -\tp = curr;\n>  \ti = 0;\n> +\twhile ((p = *tail) != NULL) {\n> +\t\tcmp = ((i >= q->nr)\n> +\t\t       ? -1 : strcmp(p->path, q->queue[i]->two->path));\n\nI liked cmp assignment being the original way - when \"-1\" is on one line\nand strcmp is on another - to me it reads better. I'm not insisting on\nit though.\n\n\n> -\twhile (1) {\n> -\t\tif (!p)\n> -\t\t\tbreak;\n> -\n> -\t\tcmp = (i >= q->nr) ? -1\n> -\t\t\t\t   : strcmp(p->path, q->queue[i]->two->path);\n>  \t\tif (cmp < 0) {\n> -\t\t\tif (pprev)\n> -\t\t\t\tpprev->next = p->next;\n> -\t\t\tptmp = p;\n> -\t\t\tp = p->next;\n> -\t\t\tfree(ptmp);\n> -\t\t\tif (curr == ptmp)\n> -\t\t\t\tcurr = p;\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\tfree(p);\n>  \t\t\tcontinue;\n>  \t\t}\n\nA bug crept in here - if we are removing the first element, i.e. when\np=curr, we have to advance curr as well - as we are returning curr back\nas new intersected paths set list start. That's why there was curr\nchange.\n\nNow curr stays the same, and if we'll remove the first element, curr\nwill be pointing to freed memory -> oops. A possible fixup could be:\n\n---- 8< ----\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 0809e79..6a61a25 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -60,6 +60,8 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n \n                        if ((*tail = next) != NULL)\n                                tail = &next->next;\n+                       if (curr == p)\n+                               curr = next;\n                        free(p);\n                        continue;\n                }\n---- 8< ----\n\nbut this is blind code, as I had not tested it.\n\n\n>  \n>  \t\tif (cmp > 0) {\n> +\t\t\t/* q->queue[i] not in p->path; skip it */\n>  \t\t\ti++;\n>  \t\t\tcontinue;\n>  \t\t}\n> @@ -80,8 +74,7 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,\n>  \t\tp->parent[n].mode = q->queue[i]->one->mode;\n>  \t\tp->parent[n].status = q->queue[i]->status;\n>  \n> -\t\tpprev = p;\n> -\t\tp = p->next;\n> +\t\ttail = &p->next;\n>  \t\ti++;\n>  \t}\n>  \treturn curr;\n\n\nP.S. I'm slowly working on to speedup combine-diff further - the same\nway as diff_tree() skips path for two trees, for combine-diff we could\ntraverse a merge tree and n parents simultaneously, even not delving\ninto generating (usually huge) diff(merge,parent_i) for a path, if we\nknow such diff for parent_j will be empty.\n\nI have no numbers yet, but this should give significant speedup, as my\ntracing showed for e.g. linux.git a lot of diffing is done for\ncombine-diff for merges to e.g. second parents (mean value of diff to\nHEAD^2 is ~ 1500 paths) and almost all of them annulate when intersected\nto diff(HEAD, HEAD^1).\n\nOnly this can't work (or at least I don't know how) if rename/copy\ndetection is on, so there will be two codepaths - fast, if we run\nwithout -M/-C, and generic, but slower, where combine-diff paths are\ncomputed as intersections:\n\n    D(A,P1,P2,...Pn) = D(A,P1) ^ D(A,P2) ^ ... ^ D(A,Pn)\n\ni.e. the current way.\n\nDoes this approach sound reasonable? My draft not-working-yet code is here:\n\nhttp://repo.or.cz/w/git/kirr.git/shortlog/refs/heads/x/combinediff-sorted\n(look for diff_tree_combined_X)\n\n\nThanks,\nKirill\n"}]}