{"thread":{"id":"47988","subject":"[PATCH] xdiff: improve trimming preprocessing","startedAt":"2018-03-06T11:54:01Z","lastAt":"2018-03-07T14:36:21Z","messageCount":7,"participants":["Jun Wu","Eric Sunshine","Junio C Hamano","René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"341127","messageId":"1520337165-sup-4504@x1c","threadId":"47988","inReplyTo":null,"subject":"[PATCH] xdiff: improve trimming preprocessing","fromName":"Jun Wu","fromEmail":"quark@fb.com","sentAt":"2018-03-06T11:53:46Z","receivedAt":"2018-03-06T11:54:01Z","isPatch":true,"sender":{"key":"quark@fb.com","avatar":null},"body":"xdiff-interface trims common suffix if ctxlen is 0. Teach it to also\ntrim common prefix, and trim less lines if ctxlen > 0. So it can benefit\nthe default diff command, as seen by profiling:\n\n $ GIT_PERF_REPEAT_COUNT=10 ./run origin/master . -- p4000-diff-algorithms.sh\n [...]\n Test origin/master this tree\n ------------------------------------------------------------------------------\n 4000.1: log -3000 (baseline) 0.07(0.06+0.01) 0.06(0.05+0.01) -14.3%\n 4000.2: log --raw -3000 (tree-only) 0.31(0.28+0.02) 0.31(0.27+0.02) +0.0%\n 4000.3: log -p -3000 (Myers) 2.25(2.05+0.17) 1.66(1.52+0.11) -26.2%\n 4000.4: log -p -3000 --histogram 2.51(2.36+0.10) 1.90(1.79+0.09) -24.3%\n 4000.5: log -p -3000 --patience 2.63(2.44+0.16) 1.70(1.56+0.12) -35.4%\n\nDiff shifting behaviors (hunk merging, indent heuristic, shift towards\nthe end for repetitive content) are preserved as a best effort by:\n\n 1. Reserve extra 100 lines to not be trimmed. Leave room for shifting.\n 2. Calculate common prefix first. Disallow suffix overlap with prefix\n in the smaller file. So diff hunk tends to be shifted down.\n\nAdd tests for those. Make sure they fail on the old code.\n\nBackported from a Mercurial patch [1]. Adjusted to git's existing\nxdiff-interface.c (which isn't ported to Mercurial).\n\nNote: xdl_trim_ends does a similar job. But too late - it's after line\nsplitting, hashing, correcting hash values. Those steps have visible\noverhead.\n\n[1]: https://phab.mercurial-scm.org/D2686\n\nSigned-off-by: Jun Wu \n---\n t/t4066-diff-trimming.sh | 49 +++++++++++++++++++++++++++++++++++++++\n xdiff-interface.c | 60 +++++++++++++++++++++++++++++++++---------------\n xdiff/xdiff.h | 3 +++\n xdiff/xdiffi.c | 5 ++--\n xdiff/xemit.c | 3 ++-\n 5 files changed, 98 insertions(+), 22 deletions(-)\n create mode 100755 t/t4066-diff-trimming.sh\n\ndiff --git a/t/t4066-diff-trimming.sh b/t/t4066-diff-trimming.sh\nnew file mode 100755\nindex 000000000..3d90175ac\n--- /dev/null\n+++ b/t/t4066-diff-trimming.sh\n@@ -0,0 +1,49 @@\n+#!/bin/sh\n+\n+test_description='diff trimming optimization'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'setup' '\n+ printf \"x\\n%.0s\" {1..1000} >a &&\n+ printf \"x\\n%.0s\" {1..1001} >b &&\n+ cat >c <d <>c &&\\\n+ printf \"x%.0s\" {1..934} >>d # pad common suffix to 1024 bytes\n+ try:\n+ import foo\n+ except ImportError:\n+ pass\n+ try:\n+ import bar\n+ except ImportError:\n+ pass\n+EOF1\n+ try:\n+ import foo\n+ except ImportError:\n+ pass\n+ try:\n+ import baz\n+ except ImportError:\n+ pass\n+ try:\n+ import bar\n+ except ImportError:\n+ pass\n+EOF2\n+'\n+\n+test_expect_success 'git diff -U0 shifts hunk towards the end' '\n+\ttest_expect_code 1 git diff -U0 --no-index a b |\\\n+ fgrep \"@@ -1000,0 +1001 @@\" &&\n+\ttest_expect_code 1 git diff -U0 --no-index b a |\\\n+ fgrep \"@@ -1001 +1000,0 @@\"\n+'\n+\n+test_expect_success 'git diff -U0 --indent-heuristic' '\n+\ttest_expect_code 1 git diff -U0 --no-index --indent-heuristic c d |\\\n+ fgrep \"@@ -4,0 +5,4 @@\"\n+'\n+\n+test_done\ndiff --git a/xdiff-interface.c b/xdiff-interface.c\nindex 770e1f7f8..a4141e2db 100644\n--- a/xdiff-interface.c\n+++ b/xdiff-interface.c\n@@ -101,42 +101,64 @@ static int xdiff_outf(void *priv_, mmbuffer_t *mb, int nbuf)\n }\n \n /*\n- * Trim down common substring at the end of the buffers,\n- * but end on a complete line.\n+ * Trim down common prefix and suffix, except for reserved lines.\n+ * Align to line boundary.\n */\n-static void trim_common_tail(mmfile_t *a, mmfile_t *b)\n+static void trim_common(mmfile_t *a, mmfile_t *b, long reserved,\n+\t\t\txdemitconf_t *xecfg)\n {\n \tconst int blk = 1024;\n-\tlong trimmed = 0, recovered = 0;\n-\tchar *ap = a->ptr + a->size;\n-\tchar *bp = b->ptr + b->size;\n+\tlong i = 0, lines = 0;\n+\tchar *ap = a->ptr, *ae = a->ptr + a->size - 1;\n+\tchar *bp = b->ptr, *be = b->ptr + b->size - 1;\n \tlong smaller = (a->size < b->size) ? a->size : b->size;\n+\tsize_t prefix = 0, suffix = 0;\n \n-\twhile (blk + trimmed <= smaller && !memcmp(ap - blk, bp - blk, blk)) {\n-\t\ttrimmed += blk;\n-\t\tap -= blk;\n-\t\tbp -= blk;\n+\tif (smaller == 0)\n+\t\treturn;\n+\n+\t/* prefix - need line count for xecfg->ptrimmed */\n+\tfor (i = 0; ++i < smaller && *ap == *bp;) {\n+\t\tlines += (*ap == '\\n');\n+\t\tap++, bp++;\n+\t}\n+\tfor (i = 0; i <= reserved && --ap >= a->ptr;)\n+\t\ti += (*ap == '\\n');\n+\tif (ap > a->ptr) {\n+\t\tprefix = ap + 1 - a->ptr;\n+\t\txecfg->ptrimmed = lines + 1 - i;\n \t}\n \n-\twhile (recovered < trimmed)\n-\t\tif (ap[recovered++] == '\\n')\n-\t\t\tbreak;\n-\ta->size -= trimmed - recovered;\n-\tb->size -= trimmed - recovered;\n-}\n+\t/* suffix - no line count, but do not overlap with prefix */\n+\tfor (i = bp - b->ptr; (i += blk) < smaller && !memcmp(ae - blk, be - blk, blk);)\n+\t\tae -= blk, be -= blk;\n+\tfor (i = 0; i <= reserved && ++ae < a->ptr + a->size;)\n+\t\ti += (*ae == '\\n');\n+\tif (ae < a->ptr + a->size)\n+\t\tsuffix = a->ptr + a->size - 1 - ae;\n+\n+\ta->size -= prefix + suffix;\n+\tb->size -= prefix + suffix;\n+\ta->ptr += prefix;\n+\tb->ptr += prefix;\n+};\n \n int xdi_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdemitconf_t const *xecfg, xdemitcb_t *xecb)\n {\n \tmmfile_t a = *mf1;\n \tmmfile_t b = *mf2;\n+\txdemitconf_t ecfg = *xecfg;\n \n \tif (mf1->size > MAX_XDIFF_SIZE || mf2->size > MAX_XDIFF_SIZE)\n \t\treturn -1;\n \n-\tif (!xecfg->ctxlen && !(xecfg->flags & XDL_EMIT_FUNCCONTEXT))\n-\t\ttrim_common_tail(&a, &b);\n+\tif (!(xecfg->flags & XDL_EMIT_FUNCCONTEXT)) {\n+\t\t/* reserve 100 lines for hunk shifting */\n+\t\tlong reserved = xecfg->ctxlen + 100;\n+\t\ttrim_common(&a, &b, reserved, &ecfg);\n+\t}\n \n-\treturn xdl_diff(&a, &b, xpp, xecfg, xecb);\n+\treturn xdl_diff(&a, &b, xpp, &ecfg, xecb);\n }\n \n int xdi_diff_outf(mmfile_t *mf1, mmfile_t *mf2,\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex c1937a291..737d96607 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -110,6 +110,9 @@ typedef struct s_xdemitconf {\n \tfind_func_t find_func;\n \tvoid *find_func_priv;\n \txdl_emit_hunk_consume_func_t hunk_func;\n+\n+\t/* prefix lines trimmed */\n+\tlong ptrimmed;\n } xdemitconf_t;\n \n typedef struct s_bdiffparam {\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 0de1ef463..d62c5769e 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -981,13 +981,14 @@ static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t\t xdemitconf_t const *xecfg)\n {\n \txdchange_t *xch, *xche;\n+\tlong p = xecfg->ptrimmed;\n \n \tfor (xch = xscr; xch; xch = xche->next) {\n \t\txche = xdl_get_hunk(&xch, xecfg);\n \t\tif (!xch)\n \t\t\tbreak;\n-\t\tif (xecfg->hunk_func(xch->i1, xche->i1 + xche->chg1 - xch->i1,\n-\t\t\t\t xch->i2, xche->i2 + xche->chg2 - xch->i2,\n+\t\tif (xecfg->hunk_func(xch->i1 + p, xche->i1 + xche->chg1 - xch->i1,\n+\t\t\t\t xch->i2 + p, xche->i2 + xche->chg2 - xch->i2,\n \t\t\t\t ecb->priv) < 0)\n \t\t\treturn -1;\n \t}\ndiff --git a/xdiff/xemit.c b/xdiff/xemit.c\nindex 7778dc2b1..45d4ab073 100644\n--- a/xdiff/xemit.c\n+++ b/xdiff/xemit.c\n@@ -167,6 +167,7 @@ static int is_empty_rec(xdfile_t *xdf, long ri)\n int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t xdemitconf_t const *xecfg) {\n \tlong s1, s2, e1, e2, lctx;\n+\tlong p = xecfg->ptrimmed + 1;\n \txdchange_t *xch, *xche;\n \tlong funclineprev = -1;\n \tstruct func_line func_line = { 0 };\n@@ -261,7 +262,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t\t\t s1 - 1, funclineprev);\n \t\t\tfunclineprev = s1 - 1;\n \t\t}\n-\t\tif (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,\n+\t\tif (xdl_emit_hunk_hdr(s1 + p, e1 - s1, s2 + p, e2 - s2,\n \t\t\t\t func_line.buf, func_line.len, ecb) < 0)\n \t\t\treturn -1;\n \n-- \n2.16.2\n\n\n"},{"id":"341141","messageId":"CAPig+cRYsf161-Xomw7daj8XdEBxZAEQQRdOn4krRTpSAFkPOw@mail.gmail.com","threadId":"47988","inReplyTo":"1520337165-sup-4504@x1c","subject":"Re: [PATCH] xdiff: improve trimming preprocessing","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-03-06T19:23:46Z","receivedAt":"2018-03-06T19:23:52Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Mar 6, 2018 at 6:53 AM, Jun Wu wrote:\n> xdiff-interface trims common suffix if ctxlen is 0. Teach it to also\n> trim common prefix, and trim less lines if ctxlen > 0. So it can benefit\n> the default diff command, as seen by profiling: [...]\n\nA few comments (below) based upon a quick scan of the patch...\n\n> Signed-off-by: Jun Wu \n> ---\n> diff --git a/t/t4066-diff-trimming.sh b/t/t4066-diff-trimming.sh\n> @@ -0,0 +1,49 @@\n> +test_expect_success 'setup' '\n> + printf \"x\\n%.0s\" {1..1000} >a &&\n> + printf \"x\\n%.0s\" {1..1001} >b &&\n> + cat >c <d < + printf \"x%.0s\" {1..934} >>c &&\\\n> + printf \"x%.0s\" {1..934} >>d # pad common suffix to 1024 bytes\n\nThe expression {x..y} is not portable to non-POSIX shells.\n\n> +test_expect_success 'git diff -U0 shifts hunk towards the end' '\n> + test_expect_code 1 git diff -U0 --no-index a b |\\\n> + fgrep \"@@ -1000,0 +1001 @@\" &&\n> + test_expect_code 1 git diff -U0 --no-index b a |\\\n> + fgrep \"@@ -1001 +1000,0 @@\"\n> +'\n\nStyle: Mix of tabs and spaces for indentation. Please indent only with\ntabs throughout the patch.\n\n> diff --git a/xdiff-interface.c b/xdiff-interface.c\n> @@ -101,42 +101,64 @@ static int xdiff_outf(void *priv_, mmbuffer_t *mb, int nbuf)\n> +static void trim_common(mmfile_t *a, mmfile_t *b, long reserved,\n> + xdemitconf_t *xecfg)\n> {\n> + /* prefix - need line count for xecfg->ptrimmed */\n> + for (i = 0; ++i < smaller && *ap == *bp;) {\n> + lines += (*ap == '\\n');\n> + ap++, bp++;\n\nIs there a good reason for not placing 'ap++, bp++' directly in the 'for'?\n\n for (i = 0; ++i < smaller && *ap == *bp; ap++, bp++)\n"},{"id":"341144","messageId":"xmqq7eqp3suv.fsf@gitster-ct.c.googlers.com","threadId":"47988","inReplyTo":"CAPig+cRYsf161-Xomw7daj8XdEBxZAEQQRdOn4krRTpSAFkPOw@mail.gmail.com","subject":"Re: [PATCH] xdiff: improve trimming preprocessing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-03-06T19:29:44Z","receivedAt":"2018-03-06T19:30:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Eric Sunshine writes:\n\n> On Tue, Mar 6, 2018 at 6:53 AM, Jun Wu wrote:\n>> xdiff-interface trims common suffix if ctxlen is 0. Teach it to also\n>> trim common prefix, and trim less lines if ctxlen > 0. So it can benefit\n>> the default diff command, as seen by profiling: [...]\n\nI vaguely recall that we have tried this in the distant past, found\nthat it produced incorrect result, and that is why we limit the\noptimization for no-context case.\n\nDoes anybody have an archive reference?\n"},{"id":"341171","messageId":"1520370729-sup-3241@x1c","threadId":"47988","inReplyTo":"CAPig+cRYsf161-Xomw7daj8XdEBxZAEQQRdOn4krRTpSAFkPOw@mail.gmail.com","subject":"Re: [PATCH] xdiff: improve trimming preprocessing","fromName":"Jun Wu","fromEmail":"quark@fb.com","sentAt":"2018-03-06T23:05:18Z","receivedAt":"2018-03-06T23:05:42Z","isPatch":true,"sender":{"key":"quark@fb.com","avatar":null},"body":"Excerpts from Eric Sunshine's message of 2018-03-06 14:23:46 -0500:\n> On Tue, Mar 6, 2018 at 6:53 AM, Jun Wu wrote:\n> > + printf \"x%.0s\" {1..934} >>d # pad common suffix to 1024 bytes\n> \n> The expression {x..y} is not portable to non-POSIX shells.\n\nIs there a recommended way to generate a repetitive string?\nMaybe `seq 1000 | sed 's/.*/x/'` ?\n\n> > + fgrep \"@@ -1001 +1000,0 @@\"\n> > +'\n> \n> Style: Mix of tabs and spaces for indentation. Please indent only with\n> tabs throughout the patch.\n\nSorry. Will fix in V2.\n \n> > + /* prefix - need line count for xecfg->ptrimmed */\n> > + for (i = 0; ++i < smaller && *ap == *bp;) {\n> > + lines += (*ap == '\\n');\n> > + ap++, bp++;\n> \n> Is there a good reason for not placing 'ap++, bp++' directly in the 'for'?\n\n\"lines += (*ap == '\\n');\" needs the \"ap\" before adding. Alternatives are\n\n for (i = 0; ++i < smaller && *ap == *bp; ) /* 1 */\n lines += (*ap++, *bp++) == '\\n';\n\n for (i = 0; ++i < smaller && *ap == *bp; ap++, bp++) /* 2 */\n lines += (*(ap - 1) == '\\n');\n\nMaybe will pick /* 1 */ to make the code shorter.\n"},{"id":"341179","messageId":"1520378039-sup-4143@x1c","threadId":"47988","inReplyTo":"xmqq7eqp3suv.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] xdiff: improve trimming preprocessing","fromName":"Jun Wu","fromEmail":"quark@fb.com","sentAt":"2018-03-06T23:59:21Z","receivedAt":"2018-03-07T00:00:40Z","isPatch":true,"sender":{"key":"quark@fb.com","avatar":null},"body":"Excerpts from Junio C Hamano's message of 2018-03-06 11:29:44 -0800:\n> Eric Sunshine writes:\n> \n> > On Tue, Mar 6, 2018 at 6:53 AM, Jun Wu wrote:\n> >> xdiff-interface trims common suffix if ctxlen is 0. Teach it to also\n> >> trim common prefix, and trim less lines if ctxlen > 0. So it can benefit\n> >> the default diff command, as seen by profiling: [...]\n> \n> I vaguely recall that we have tried this in the distant past, found\n> that it produced incorrect result, and that is why we limit the\n> optimization for no-context case.\n> \n> Does anybody have an archive reference?\n\nI think it's d2f8295 (\"Re(-re)*fix trim_common_tail()\", 2007-12-20).\n\nYeah, this is more complex than I thought. In Mercurial's use-case, ctxlen\nis 0 and context are added in a higher layer so it's fine.\n\nIt's clearly hunk shifting causing problems. I'll send a V2 to forbid hunk\nshifting if it can possibly lose context lines. That implies counting suffix\nlines, which adds some overhead but the overall perf win still seems\nworthwhile.\n"},{"id":"341192","messageId":"CAPig+cToTv063z-HB=8Y9LkpbqQaKCVJG_nU0Qd7O9ZdJY-p6g@mail.gmail.com","threadId":"47988","inReplyTo":"1520370729-sup-3241@x1c","subject":"Re: [PATCH] xdiff: improve trimming preprocessing","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2018-03-07T09:36:08Z","receivedAt":"2018-03-07T09:36:15Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Mar 6, 2018 at 6:05 PM, Jun Wu wrote:\n> Excerpts from Eric Sunshine's message of 2018-03-06 14:23:46 -0500:\n>> On Tue, Mar 6, 2018 at 6:53 AM, Jun Wu wrote:\n>> > + printf \"x%.0s\" {1..934} >>d # pad common suffix to 1024 bytes\n>>\n>> The expression {x..y} is not portable to non-POSIX shells.\n>\n> Is there a recommended way to generate a repetitive string?\n> Maybe `seq 1000 | sed 's/.*/x/'` ?\n\nThat seems reasonable, although you'd want to use the test suite's\nmore portable test_seq rather than seq.\n\n>> > + /* prefix - need line count for xecfg->ptrimmed */\n>> > + for (i = 0; ++i < smaller && *ap == *bp;) {\n>> > + lines += (*ap == '\\n');\n>> > + ap++, bp++;\n>>\n>> Is there a good reason for not placing 'ap++, bp++' directly in the 'for'?\n>\n> \"lines += (*ap == '\\n');\" needs the \"ap\" before adding. Alternatives are\n>\n> for (i = 0; ++i < smaller && *ap == *bp; ) /* 1 */\n> lines += (*ap++, *bp++) == '\\n';\n>\n> for (i = 0; ++i < smaller && *ap == *bp; ap++, bp++) /* 2 */\n> lines += (*(ap - 1) == '\\n');\n>\n> Maybe will pick /* 1 */ to make the code shorter.\n\nI was thinking specifically about #2 when asking the question. The\nreason I asked is that, as one reading the code, the\nnot-quite-idiomatic loop made me stop and wonder if something special\nwas going on which wasn't obvious at a glance.\n\nAnd, apparently, I'm still wondering since I'm not groking what you mean by:\n\n \"lines += (*ap == '\\n');\" needs the \"ap\" before adding\n\nIt's quite possible that I'm being dense and overlooking something\nblindingly obvious.\n"},{"id":"341207","messageId":"35faf81e-b604-d5b5-be51-bfe5cb9ec4cc@web.de","threadId":"47988","inReplyTo":"CAPig+cToTv063z-HB=8Y9LkpbqQaKCVJG_nU0Qd7O9ZdJY-p6g@mail.gmail.com","subject":"Re: [PATCH] xdiff: improve trimming preprocessing","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-03-07T14:36:06Z","receivedAt":"2018-03-07T14:36:21Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 07.03.2018 um 10:36 schrieb Eric Sunshine:\n> On Tue, Mar 6, 2018 at 6:05 PM, Jun Wu wrote:\n>> Excerpts from Eric Sunshine's message of 2018-03-06 14:23:46 -0500:\n>>> On Tue, Mar 6, 2018 at 6:53 AM, Jun Wu wrote:\n>>>> + printf \"x%.0s\" {1..934} >>d # pad common suffix to 1024 bytes\n>>>\n>>> The expression {x..y} is not portable to non-POSIX shells.\n>>\n>> Is there a recommended way to generate a repetitive string?\n>> Maybe `seq 1000 | sed 's/.*/x/'` ?\n> \n> That seems reasonable, although you'd want to use the test suite's\n> more portable test_seq rather than seq.\n\nYou could also use Perl's repetition operator (x):\n\n\tperl -e \"print \\\"x\\\" x 934\" >>d\n\nIt is a single command (only one fork()/exec()), simple, produces no\nextra newline characters and it's already used e.g. in\nt5300-pack-object.sh.\n\nRené\n"}]}