{"thread":{"id":"25149","subject":"Patch id tests and diff performance optimization","startedAt":"2010-09-19T09:59:26Z","lastAt":"2010-09-30T18:33:20Z","messageCount":13,"participants":["Clemens Buchacher","Sverre Rabbelier","René Scharfe","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"150983","messageId":"1284890369-4136-1-git-send-email-drizzd@aon.at","threadId":"25149","inReplyTo":null,"subject":"Patch id tests and diff performance optimization","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-09-19T09:59:26Z","receivedAt":"2010-09-19T09:59:26Z","isPatch":false,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"Hi,\n\nI finally came around to de-bashify my patch ID test script. Here we go.\n\n[PATCH 1/3] add rebase patch id tests\n[PATCH 2/3] do not search functions for patch ID\n[PATCH 3/3] use cache for function names in hunk headers\n\nThe first patch adds correctness and (optional) performance tests for the patch\n\"hash binary sha1 into patch id\"\nhttp://thread.gmane.org/gmane.comp.version-control.git/153468/focus=155919 .\n\nThe test reveals a performance problem with the search for function names for\nthe hunk headers. This is fixed for patch ID computation by the second patch\nand for diff in general by the third patch.\n\nClemens\n---\n\n diff.c                     |    2 +-\n t/t3419-rebase-patch-id.sh |  109 ++++++++++++++++++++++++++++++++++++++++++++\n xdiff/xemit.c              |   44 +++++++++++++-----\n 3 files changed, 142 insertions(+), 13 deletions(-)\n"},{"id":"150985","messageId":"1284890369-4136-2-git-send-email-drizzd@aon.at","threadId":"25149","inReplyTo":"1284890369-4136-1-git-send-email-drizzd@aon.at","subject":"[PATCH 1/3] add rebase patch id tests","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-09-19T09:59:27Z","receivedAt":"2010-09-19T09:59:27Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"\nSigned-off-by: Clemens Buchacher <drizzd@aon.at>\n---\n t/t3419-rebase-patch-id.sh |  109 ++++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 109 insertions(+), 0 deletions(-)\n create mode 100755 t/t3419-rebase-patch-id.sh\n\ndiff --git a/t/t3419-rebase-patch-id.sh b/t/t3419-rebase-patch-id.sh\nnew file mode 100755\nindex 0000000..1aee483\n--- /dev/null\n+++ b/t/t3419-rebase-patch-id.sh\n@@ -0,0 +1,109 @@\n+#!/bin/bash\n+\n+test_description='git rebase - test patch id computation'\n+\n+. ./test-lib.sh\n+\n+test_set_prereq NOT_EXPENSIVE\n+test -n \"$GIT_PATCHID_TIMING_TESTS\" && test_set_prereq EXPENSIVE\n+test -x /usr/bin/time && test_set_prereq USR_BIN_TIME\n+\n+count()\n+{\n+\ti=0\n+\twhile test $i -lt $1\n+\tdo\n+\t\techo \"$i\"\n+\t\ti=$(($i+1))\n+\tdone\n+}\n+\n+scramble()\n+{\n+\ti=0\n+\twhile read x\n+\tdo\n+\t\tif test $i -ne 0\n+\t\tthen\n+\t\t\techo \"$x\"\n+\t\tfi\n+\t\ti=$(((i+1) % 10))\n+\tdone < \"$1\" > \"$1.new\"\n+\tmv -f \"$1.new\" \"$1\"\n+}\n+\n+run()\n+{\n+\techo \\$ \"$@\"\n+\t/usr/bin/time \"$@\" >/dev/null\n+}\n+\n+test_expect_success 'setup' '\n+\tgit commit --allow-empty -m initial\n+\tgit tag root\n+'\n+\n+do_tests()\n+{\n+\tpr=$1\n+\tnlines=$2\n+\n+\ttest_expect_success $pr \"setup: $nlines lines\" \"\n+\t\trm -f .gitattributes &&\n+\t\tgit checkout -q -f master &&\n+\t\tgit reset --hard root &&\n+\t\tcount $nlines >file &&\n+\t\tgit add file &&\n+\t\tgit commit -q -m initial &&\n+\t\tgit branch -f other &&\n+\n+\t\tscramble file &&\n+\t\tgit add file &&\n+\t\tgit commit -q -m 'change big file' &&\n+\n+\t\tgit checkout -q other &&\n+\t\t: >newfile &&\n+\t\tgit add newfile &&\n+\t\tgit commit -q -m 'add small file' &&\n+\n+\t\tgit cherry-pick master >/dev/null 2>&1\n+\t\"\n+\n+\ttest_debug \"\n+\t\trun git diff master^\\!\n+\t\"\n+\n+\ttest_expect_success $pr 'setup attributes' \"\n+\t\techo 'file binary' >.gitattributes\n+\t\"\n+\n+\ttest_debug \"\n+\t\trun git format-patch --stdout master &&\n+\t\trun git format-patch --stdout --ignore-if-in-upstream master\n+\t\"\n+\n+\ttest_expect_success $pr 'detect upstream patch' \"\n+\t\tgit checkout -q master &&\n+\t\tscramble file &&\n+\t\tgit add file &&\n+\t\tgit commit -q -m 'change big file again' &&\n+\t\tgit checkout -q other^{} &&\n+\t\tgit rebase master &&\n+\t\ttest_must_fail test -n \\\"\\$(git rev-list master...HEAD~)\\\"\n+\t\"\n+\n+\ttest_expect_success $pr 'do not drop patch' \"\n+\t\tgit branch -f squashed master &&\n+\t\tgit checkout -q -f squashed &&\n+\t\tgit reset -q --soft HEAD~2 &&\n+\t\tgit commit -q -m squashed &&\n+\t\tgit checkout -q other^{} &&\n+\t\ttest_must_fail git rebase squashed &&\n+\t\trm -rf .git/rebase-apply\n+\t\"\n+}\n+\n+do_tests NOT_EXPENSIVE 500\n+do_tests EXPENSIVE 50000\n+\n+test_done\n-- \n1.7.1.571.gba4d01\n"},{"id":"150984","messageId":"1284890369-4136-3-git-send-email-drizzd@aon.at","threadId":"25149","inReplyTo":"1284890369-4136-1-git-send-email-drizzd@aon.at","subject":"[PATCH 2/3] do not search functions for patch ID","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-09-19T09:59:28Z","receivedAt":"2010-09-19T09:59:28Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"Visual aids, such as the function name in the hunk\nheader, are not necessary for the purposes of\ncomputing a patch ID.\n\nThis is a performance optimization.\n\nSigned-off-by: Clemens Buchacher <drizzd@aon.at>\n---\n diff.c |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 9a5c77c..454b9c9 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3865,7 +3865,7 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n \n \t\txpp.flags = 0;\n \t\txecfg.ctxlen = 3;\n-\t\txecfg.flags = XDL_EMIT_FUNCNAMES;\n+\t\txecfg.flags = 0;\n \t\txdi_diff_outf(&mf1, &mf2, patch_id_consume, &data,\n \t\t\t      &xpp, &xecfg);\n \t}\n-- \n1.7.1.571.gba4d01\n"},{"id":"150986","messageId":"1284890369-4136-4-git-send-email-drizzd@aon.at","threadId":"25149","inReplyTo":"1284890369-4136-1-git-send-email-drizzd@aon.at","subject":"[PATCH 3/3] use cache for function names in hunk headers","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-09-19T09:59:29Z","receivedAt":"2010-09-19T09:59:29Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"For each hunk, xdl_find_func searches the preimage\nfor a function name until the beginning of the\nfile. If the file does not contain any function\nnames, this search has complexity O(n^2) in the\nnumber of hunks n.\n\nInstead of searching the entire file for each hunk\nindividually, cache and reuse the search result\nfrom previous hunks.\n\nDiff performance for the 50000 line test in t3419\nbefore and after this patch:\n\n2.78user 0.01system 0:02.82elapsed 99%CPU\n0.05user 0.01system 0:00.06elapsed 96%CPU\n\nSigned-off-by: Clemens Buchacher <drizzd@aon.at>\n---\n xdiff/xemit.c |   44 ++++++++++++++++++++++++++++++++------------\n 1 files changed, 32 insertions(+), 12 deletions(-)\n\ndiff --git a/xdiff/xemit.c b/xdiff/xemit.c\nindex c4bedf0..349bd6b 100644\n--- a/xdiff/xemit.c\n+++ b/xdiff/xemit.c\n@@ -85,8 +85,15 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)\n \treturn -1;\n }\n \n-static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,\n-\t\tfind_func_t ff, void *ff_priv) {\n+struct xdl_find_func_cache {\n+\tchar buf[80];\n+\tlong len;\n+\txdfile_t *xf;\n+\tint line;\n+};\n+\n+static void xdl_find_func(xdfile_t *xf, long line, find_func_t ff,\n+\t\t          void *ff_priv, struct xdl_find_func_cache *cache) {\n \n \t/*\n \t * Be quite stupid about this for now.  Find a line in the old file\n@@ -96,13 +103,28 @@ static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,\n \n \tconst char *rec;\n \tlong len;\n+\tint i, l;\n \n-\twhile (i-- > 0) {\n-\t\tlen = xdl_get_rec(xf, i, &rec);\n-\t\tif ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)\n+\tif (line < cache->line)\n+\t\tcache->xf = 0;\n+\n+\ti = line;\n+\tl = -1;\n+\twhile (--i >= 0 && l < 0) {\n+\t\tif (xf == cache->xf && i < cache->line) {\n+\t\t\tcache->line = line;\n \t\t\treturn;\n+\t\t}\n+\n+\t\tlen = xdl_get_rec(xf, i, &rec);\n+\t\tl = ff(rec, len, cache->buf, sizeof(cache->buf), ff_priv);\n \t}\n-\t*ll = 0;\n+\tif (l < 0)\n+\t\tl = 0;\n+\n+\tcache->xf = xf;\n+\tcache->len = l;\n+\tcache->line = line;\n }\n \n \n@@ -125,8 +147,7 @@ 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 \txdchange_t *xch, *xche;\n-\tchar funcbuf[80];\n-\tlong funclen = 0;\n+\tstruct xdl_find_func_cache func_cache = { \"\", 0, NULL, -1 };\n \tfind_func_t ff = xecfg->find_func ?  xecfg->find_func : def_ff;\n \n \tif (xecfg->flags & XDL_EMIT_COMMON)\n@@ -150,12 +171,11 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t */\n \n \t\tif (xecfg->flags & XDL_EMIT_FUNCNAMES) {\n-\t\t\txdl_find_func(&xe->xdf1, s1, funcbuf,\n-\t\t\t\t      sizeof(funcbuf), &funclen,\n-\t\t\t\t      ff, xecfg->find_func_priv);\n+\t\t\txdl_find_func(&xe->xdf1, s1, ff, xecfg->find_func_priv,\n+\t\t\t\t\t&func_cache);\n \t\t}\n \t\tif (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,\n-\t\t\t\t      funcbuf, funclen, ecb) < 0)\n+\t\t\t\t      func_cache.buf, func_cache.len, ecb) < 0)\n \t\t\treturn -1;\n \n \t\t/*\n-- \n1.7.1.571.gba4d01\n"},{"id":"151009","messageId":"AANLkTikArADX8XviB99VtkkmKmVbs9jHPHw9PNSmiOc3@mail.gmail.com","threadId":"25149","inReplyTo":"1284890369-4136-4-git-send-email-drizzd@aon.at","subject":"Re: [PATCH 3/3] use cache for function names in hunk headers","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2010-09-19T20:24:52Z","receivedAt":"2010-09-19T20:24:52Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Sun, Sep 19, 2010 at 11:59, Clemens Buchacher <drizzd@aon.at> wrote:\n> 2.78user 0.01system 0:02.82elapsed 99%CPU\n> 0.05user 0.01system 0:00.06elapsed 96%CPU\n\nVery nice. It would improve the commit message if you could explain\nwhat exactly it is this optimizes though, saving the reader from\nhaving to read through t3419 to find out.\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"151134","messageId":"20100920173605.GA13057@localhost","threadId":"25149","inReplyTo":"AANLkTikArADX8XviB99VtkkmKmVbs9jHPHw9PNSmiOc3@mail.gmail.com","subject":"Re: [PATCH 3/3] use cache for function names in hunk headers","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-09-20T17:36:05Z","receivedAt":"2010-09-20T17:36:05Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Sun, Sep 19, 2010 at 10:24:52PM +0200, Sverre Rabbelier wrote:\n> \n> On Sun, Sep 19, 2010 at 11:59, Clemens Buchacher <drizzd@aon.at> wrote:\n> > 2.78user 0.01system 0:02.82elapsed 99%CPU\n> > 0.05user 0.01system 0:00.06elapsed 96%CPU\n> \n> Very nice. It would improve the commit message if you could explain\n> what exactly it is this optimizes though, saving the reader from\n> having to read through t3419 to find out.\n\nOk.\n\nThe test creates a file with 50000 lines and a one-line change\nevery 10 lines, i.e., about 5000 hunks. Since none of the lines\nmatches a function definition, previous to this optimization, the\nfile was searched 5000 times.\n\nClemens\n"},{"id":"151144","messageId":"AANLkTi==Bcc8kkCXX1qN1QnpMF7U7DRhUkdwaStmkQ66@mail.gmail.com","threadId":"25149","inReplyTo":"20100920173605.GA13057@localhost","subject":"Re: [PATCH 3/3] use cache for function names in hunk headers","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2010-09-20T19:15:29Z","receivedAt":"2010-09-20T19:15:29Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Mon, Sep 20, 2010 at 19:36, Clemens Buchacher <drizzd@aon.at> wrote:\n> The test creates a file with 50000 lines and a one-line change\n> every 10 lines, i.e., about 5000 hunks. Since none of the lines\n> matches a function definition, previous to this optimization, the\n> file was searched 5000 times.\n\nAh, that makes sense, please add (something like) that to the commit message :).\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"151344","messageId":"20100923070439.GA29764@localhost","threadId":"25149","inReplyTo":"1284890369-4136-1-git-send-email-drizzd@aon.at","subject":"[PATCH 3/3 v2] use cache for function names in hunk headers","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-09-23T07:04:39Z","receivedAt":"2010-09-23T07:04:39Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"For each hunk, xdl_find_func searches the preimage\nfor a function name until the beginning of the\nfile. If the file does not contain any function\nnames, this search has complexity O(n^2) in the\nnumber of hunks n.\n\nThe timing test in t3419 creates a file with 50000\nlines and a one-line change every 10 lines, i.e.,\nabout 5000 hunks. Since none of the lines matches\na function definition the file is searched 5000\ntimes.\n\nInstead of searching the entire file for each hunk\nindividually, cache and reuse the search result\nfrom previous hunks.\n\nDiff performance for the test described above\nbefore and after this optimization:\n\n2.78user 0.01system 0:02.82elapsed 99%CPU\n0.05user 0.01system 0:00.06elapsed 96%CPU\n\nSigned-off-by: Clemens Buchacher <drizzd@aon.at>\n---\n\nI have added the test description as requested by\nSverre. There are no code changes with respect to\nthe previous version of the patch.\n\nThe test scenario might seem quite obscure.  But I\nhave this case in some text files which are not\nedited directly by humans.\n\nClemens\n\n xdiff/xemit.c |   44 ++++++++++++++++++++++++++++++++------------\n 1 files changed, 32 insertions(+), 12 deletions(-)\n\ndiff --git a/xdiff/xemit.c b/xdiff/xemit.c\nindex c4bedf0..349bd6b 100644\n--- a/xdiff/xemit.c\n+++ b/xdiff/xemit.c\n@@ -85,8 +85,15 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)\n \treturn -1;\n }\n \n-static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,\n-\t\tfind_func_t ff, void *ff_priv) {\n+struct xdl_find_func_cache {\n+\tchar buf[80];\n+\tlong len;\n+\txdfile_t *xf;\n+\tint line;\n+};\n+\n+static void xdl_find_func(xdfile_t *xf, long line, find_func_t ff,\n+\t\t          void *ff_priv, struct xdl_find_func_cache *cache) {\n \n \t/*\n \t * Be quite stupid about this for now.  Find a line in the old file\n@@ -96,13 +103,28 @@ static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,\n \n \tconst char *rec;\n \tlong len;\n+\tint i, l;\n \n-\twhile (i-- > 0) {\n-\t\tlen = xdl_get_rec(xf, i, &rec);\n-\t\tif ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)\n+\tif (line < cache->line)\n+\t\tcache->xf = 0;\n+\n+\ti = line;\n+\tl = -1;\n+\twhile (--i >= 0 && l < 0) {\n+\t\tif (xf == cache->xf && i < cache->line) {\n+\t\t\tcache->line = line;\n \t\t\treturn;\n+\t\t}\n+\n+\t\tlen = xdl_get_rec(xf, i, &rec);\n+\t\tl = ff(rec, len, cache->buf, sizeof(cache->buf), ff_priv);\n \t}\n-\t*ll = 0;\n+\tif (l < 0)\n+\t\tl = 0;\n+\n+\tcache->xf = xf;\n+\tcache->len = l;\n+\tcache->line = line;\n }\n \n \n@@ -125,8 +147,7 @@ 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 \txdchange_t *xch, *xche;\n-\tchar funcbuf[80];\n-\tlong funclen = 0;\n+\tstruct xdl_find_func_cache func_cache = { \"\", 0, NULL, -1 };\n \tfind_func_t ff = xecfg->find_func ?  xecfg->find_func : def_ff;\n \n \tif (xecfg->flags & XDL_EMIT_COMMON)\n@@ -150,12 +171,11 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t */\n \n \t\tif (xecfg->flags & XDL_EMIT_FUNCNAMES) {\n-\t\t\txdl_find_func(&xe->xdf1, s1, funcbuf,\n-\t\t\t\t      sizeof(funcbuf), &funclen,\n-\t\t\t\t      ff, xecfg->find_func_priv);\n+\t\t\txdl_find_func(&xe->xdf1, s1, ff, xecfg->find_func_priv,\n+\t\t\t\t\t&func_cache);\n \t\t}\n \t\tif (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,\n-\t\t\t\t      funcbuf, funclen, ecb) < 0)\n+\t\t\t\t      func_cache.buf, func_cache.len, ecb) < 0)\n \t\t\treturn -1;\n \n \t\t/*\n-- \n1.7.1.571.gba4d01\n\n"},{"id":"151727","messageId":"4C9F7450.9060208@lsrfire.ath.cx","threadId":"25149","inReplyTo":"20100923070439.GA29764@localhost","subject":"Re: [PATCH 3/3 v2] use cache for function names in hunk headers","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2010-09-26T16:26:56Z","receivedAt":"2010-09-26T16:26:56Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 23.09.2010 09:04, schrieb Clemens Buchacher:\n> For each hunk, xdl_find_func searches the preimage\n> for a function name until the beginning of the\n> file. If the file does not contain any function\n> names, this search has complexity O(n2) in the\n> number of hunks n.\n> \n> The timing test in t3419 creates a file with 50000\n> lines and a one-line change every 10 lines, i.e.,\n> about 5000 hunks. Since none of the lines matches\n> a function definition the file is searched 5000\n> times.\n> \n> Instead of searching the entire file for each hunk\n> individually, cache and reuse the search result\n> from previous hunks.\n> \n> Diff performance for the test described above\n> before and after this optimization:\n> \n> 2.78user 0.01system 0:02.82elapsed 99%CPU\n> 0.05user 0.01system 0:00.06elapsed 96%CPU\n> \n> Signed-off-by: Clemens Buchacher <drizzd@aon.at>\n> ---\n> \n> I have added the test description as requested by\n> Sverre. There are no code changes with respect to\n> the previous version of the patch.\n> \n> The test scenario might seem quite obscure.  But I\n> have this case in some text files which are not\n> edited directly by humans.\n> \n> Clemens\n> \n>  xdiff/xemit.c |   44 ++++++++++++++++++++++++++++++++------------\n>  1 files changed, 32 insertions(+), 12 deletions(-)\n> \n> diff --git a/xdiff/xemit.c b/xdiff/xemit.c\n> index c4bedf0..349bd6b 100644\n> --- a/xdiff/xemit.c\n> +++ b/xdiff/xemit.c\n> @@ -85,8 +85,15 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)\n>  \treturn -1;\n>  }\n>  \n> -static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,\n> -\t\tfind_func_t ff, void *ff_priv) {\n> +struct xdl_find_func_cache {\n> +\tchar buf[80];\n> +\tlong len;\n> +\txdfile_t *xf;\n> +\tint line;\n> +};\n\nIs xf needed?  Does xdl_emit_diff() handle multiple files in one go?\n\nIf you inline xdl_find_func() the struct isn't needed anymore.\n\n> +\n> +static void xdl_find_func(xdfile_t *xf, long line, find_func_t ff,\n> +\t\t          void *ff_priv, struct xdl_find_func_cache *cache) {\n>  \n>  \t/*\n>  \t * Be quite stupid about this for now.  Find a line in the old file\n> @@ -96,13 +103,28 @@ static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,\n>  \n>  \tconst char *rec;\n>  \tlong len;\n> +\tint i, l;\n>  \n> -\twhile (i-- > 0) {\n> -\t\tlen = xdl_get_rec(xf, i, &rec);\n> -\t\tif ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)\n> +\tif (line < cache->line)\n> +\t\tcache->xf = 0;\n\nNULL is preferred.\n\n> +\n> +\ti = line;\n> +\tl = -1;\n> +\twhile (--i >= 0 && l < 0) {\n> +\t\tif (xf == cache->xf && i < cache->line) {\n> +\t\t\tcache->line = line;\n>  \t\t\treturn;\n> +\t\t}\n> +\n> +\t\tlen = xdl_get_rec(xf, i, &rec);\n> +\t\tl = ff(rec, len, cache->buf, sizeof(cache->buf), ff_priv);\n>  \t}\n> -\t*ll = 0;\n> +\tif (l < 0)\n> +\t\tl = 0;\n> +\n> +\tcache->xf = xf;\n> +\tcache->len = l;\n> +\tcache->line = line;\n>  }\n>  \n>  \n> @@ -125,8 +147,7 @@ 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>  \txdchange_t *xch, *xche;\n> -\tchar funcbuf[80];\n> -\tlong funclen = 0;\n> +\tstruct xdl_find_func_cache func_cache = { \"\", 0, NULL, -1 };\n>  \tfind_func_t ff = xecfg->find_func ?  xecfg->find_func : def_ff;\n>  \n>  \tif (xecfg->flags & XDL_EMIT_COMMON)\n> @@ -150,12 +171,11 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n>  \t\t */\n>  \n>  \t\tif (xecfg->flags & XDL_EMIT_FUNCNAMES) {\n> -\t\t\txdl_find_func(&xe->xdf1, s1, funcbuf,\n> -\t\t\t\t      sizeof(funcbuf), &funclen,\n> -\t\t\t\t      ff, xecfg->find_func_priv);\n> +\t\t\txdl_find_func(&xe->xdf1, s1, ff, xecfg->find_func_priv,\n> +\t\t\t\t\t&func_cache);\n>  \t\t}\n>  \t\tif (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,\n> -\t\t\t\t      funcbuf, funclen, ecb) < 0)\n> +\t\t\t\t      func_cache.buf, func_cache.len, ecb) < 0)\n>  \t\t\treturn -1;\n>  \n>  \t\t/*\n\nHow about something like this?  It also removes an outdated comment.  The\ninlining part should probably split out in its own patch..\n\n xdiff/xemit.c |   38 ++++++++++++++------------------------\n 1 files changed, 14 insertions(+), 24 deletions(-)\n\ndiff --git a/xdiff/xemit.c b/xdiff/xemit.c\nindex c4bedf0..a663f21 100644\n--- a/xdiff/xemit.c\n+++ b/xdiff/xemit.c\n@@ -85,27 +85,6 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)\n \treturn -1;\n }\n \n-static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,\n-\t\tfind_func_t ff, void *ff_priv) {\n-\n-\t/*\n-\t * Be quite stupid about this for now.  Find a line in the old file\n-\t * before the start of the hunk (and context) which starts with a\n-\t * plausible character.\n-\t */\n-\n-\tconst char *rec;\n-\tlong len;\n-\n-\twhile (i-- > 0) {\n-\t\tlen = xdl_get_rec(xf, i, &rec);\n-\t\tif ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)\n-\t\t\treturn;\n-\t}\n-\t*ll = 0;\n-}\n-\n-\n static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n                            xdemitconf_t const *xecfg) {\n \txdfile_t *xdf = &xe->xdf1;\n@@ -127,6 +106,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \txdchange_t *xch, *xche;\n \tchar funcbuf[80];\n \tlong funclen = 0;\n+\tlong funclineprev = -1;\n \tfind_func_t ff = xecfg->find_func ?  xecfg->find_func : def_ff;\n \n \tif (xecfg->flags & XDL_EMIT_COMMON)\n@@ -150,9 +130,19 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t */\n \n \t\tif (xecfg->flags & XDL_EMIT_FUNCNAMES) {\n-\t\t\txdl_find_func(&xe->xdf1, s1, funcbuf,\n-\t\t\t\t      sizeof(funcbuf), &funclen,\n-\t\t\t\t      ff, xecfg->find_func_priv);\n+\t\t\tlong l;\n+\t\t\tfor (l = s1 - 1; l >= 0 && l > funclineprev; l--) {\n+\t\t\t\tconst char *rec;\n+\t\t\t\tlong reclen = xdl_get_rec(&xe->xdf1, l, &rec);\n+\t\t\t\tlong newfunclen = ff(rec, reclen, funcbuf,\n+\t\t\t\t\t\t     sizeof(funcbuf),\n+\t\t\t\t\t\t     xecfg->find_func_priv);\n+\t\t\t\tif (newfunclen >= 0) {\n+\t\t\t\t\tfunclen = newfunclen;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t}\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\t\t\t      funcbuf, funclen, ecb) < 0)\n"},{"id":"151748","messageId":"20100926204318.GA19588@localhost","threadId":"25149","inReplyTo":"4C9F7450.9060208@lsrfire.ath.cx","subject":"Re: [PATCH 3/3 v2] use cache for function names in hunk headers","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-09-26T20:43:18Z","receivedAt":"2010-09-26T20:43:18Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Sun, Sep 26, 2010 at 06:26:56PM +0200, René Scharfe wrote:\n> \n> Is xf needed?  Does xdl_emit_diff() handle multiple files in one go?\n\nRight now it does not.\n\n> If you inline xdl_find_func() the struct isn't needed anymore.\n[...]\n>\n> How about something like this?\n\nYes, that's better. Thanks.\n\n> -\t/*\n> -\t * Be quite stupid about this for now.  Find a line in the old file\n> -\t * before the start of the hunk (and context) which starts with a\n> -\t * plausible character.\n> -\t */\n>\n> It also removes an outdated comment.\n\nActually, in the default case, the comment is still correct and\nhelpful IMO.\n\n> The inlining part should probably split out in its own patch..\n\nI am not sure what you mean here. Do you want to add the parameter\nfunclineprev to the function and remove the function in the next\npage, or do you want to refactor the below into an inline function?\n\nClemens\n"},{"id":"151753","messageId":"4C9FC668.8070701@lsrfire.ath.cx","threadId":"25149","inReplyTo":"20100926204318.GA19588@localhost","subject":"Re: [PATCH 3/3 v2] use cache for function names in hunk headers","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2010-09-26T22:17:12Z","receivedAt":"2010-09-26T22:17:12Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 26.09.2010 22:43, schrieb Clemens Buchacher:\n> On Sun, Sep 26, 2010 at 06:26:56PM +0200, René Scharfe wrote:\n>> -\t/*\n>> -\t * Be quite stupid about this for now.  Find a line in the old file\n>> -\t * before the start of the hunk (and context) which starts with a\n>> -\t * plausible character.\n>> -\t */\n>>\n>> It also removes an outdated comment.\n> \n> Actually, in the default case, the comment is still correct and\n> helpful IMO.\n\nThe first sentence was probably written before the match function became\nconfigurable.  The second one could be moved to def_ff().\n\n>> The inlining part should probably split out in its own patch..\n> \n> I am not sure what you mean here. Do you want to add the parameter\n> funclineprev to the function and remove the function in the next\n> page, or do you want to refactor the below into an inline function?\n\nI'd suggest having a first patch for folding xdl_find_func() into\nxdl_emit_diff() without any functional change (manually inlining it) and\na second one for adding funclineprev etc..\n\nRené\n"},{"id":"151847","messageId":"7v39sv13c9.fsf@alter.siamese.dyndns.org","threadId":"25149","inReplyTo":"4C9F7450.9060208@lsrfire.ath.cx","subject":"Re: [PATCH 3/3 v2] use cache for function names in hunk headers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-09-27T17:52:22Z","receivedAt":"2010-09-27T17:52:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n\n> How about something like this?  It also removes an outdated comment.  The\n> inlining part should probably split out in its own patch..\n>\n>  xdiff/xemit.c |   38 ++++++++++++++------------------------\n>  1 files changed, 14 insertions(+), 24 deletions(-)\n>\n> diff --git a/xdiff/xemit.c b/xdiff/xemit.c\n> index c4bedf0..a663f21 100644\n> --- a/xdiff/xemit.c\n> +++ b/xdiff/xemit.c\n> @@ -85,27 +85,6 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)\n>  \treturn -1;\n>  }\n>  \n> -static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,\n> -\t\tfind_func_t ff, void *ff_priv) {\n> -\n> -\t/*\n> -\t * Be quite stupid about this for now.  Find a line in the old file\n> -\t * before the start of the hunk (and context) which starts with a\n> -\t * plausible character.\n> -\t */\n> -\n> -\tconst char *rec;\n> -\tlong len;\n> -\n> -\twhile (i-- > 0) {\n> -\t\tlen = xdl_get_rec(xf, i, &rec);\n> -\t\tif ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)\n> -\t\t\treturn;\n> -\t}\n> -\t*ll = 0;\n> -}\n> -\n> -\n>  static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n>                             xdemitconf_t const *xecfg) {\n>  \txdfile_t *xdf = &xe->xdf1;\n> @@ -127,6 +106,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n>  \txdchange_t *xch, *xche;\n>  \tchar funcbuf[80];\n>  \tlong funclen = 0;\n> +\tlong funclineprev = -1;\n>  \tfind_func_t ff = xecfg->find_func ?  xecfg->find_func : def_ff;\n>  \n>  \tif (xecfg->flags & XDL_EMIT_COMMON)\n> @@ -150,9 +130,19 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n>  \t\t */\n>  \n>  \t\tif (xecfg->flags & XDL_EMIT_FUNCNAMES) {\n> -\t\t\txdl_find_func(&xe->xdf1, s1, funcbuf,\n> -\t\t\t\t      sizeof(funcbuf), &funclen,\n> -\t\t\t\t      ff, xecfg->find_func_priv);\n> +\t\t\tlong l;\n> +\t\t\tfor (l = s1 - 1; l >= 0 && l > funclineprev; l--) {\n> +\t\t\t\tconst char *rec;\n> +\t\t\t\tlong reclen = xdl_get_rec(&xe->xdf1, l, &rec);\n> +\t\t\t\tlong newfunclen = ff(rec, reclen, funcbuf,\n> +\t\t\t\t\t\t     sizeof(funcbuf),\n> +\t\t\t\t\t\t     xecfg->find_func_priv);\n> +\t\t\t\tif (newfunclen >= 0) {\n> +\t\t\t\t\tfunclen = newfunclen;\n> +\t\t\t\t\tbreak;\n> +\t\t\t\t}\n> +\t\t\t}\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\t\t\t      funcbuf, funclen, ecb) < 0)\n\nLooks much more straightforward ;-)\n"},{"id":"152183","messageId":"7v62xnjd3j.fsf@alter.siamese.dyndns.org","threadId":"25149","inReplyTo":"4C9F7450.9060208@lsrfire.ath.cx","subject":"Re: [PATCH 3/3 v2] use cache for function names in hunk headers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-09-30T18:33:20Z","receivedAt":"2010-09-30T18:33:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:\n\n> Am 23.09.2010 09:04, schrieb Clemens Buchacher:\n>> For each hunk, xdl_find_func searches the preimage\n>> for a function name until the beginning of the\n>> file. If the file does not contain any function\n>> names, this search has complexity O(n2) in the\n>> number of hunks n.\n> ...\n> How about something like this?  It also removes an outdated comment.  The\n> inlining part should probably split out in its own patch..\n>\n>  xdiff/xemit.c |   38 ++++++++++++++------------------------\n>  1 files changed, 14 insertions(+), 24 deletions(-)\n\nI had to wonder if this optimization closes a door for us to extend the\nfunction header patterns to allow inspecting multiple lines.\n\nSuppose that a rule says that a header line is a first non-blank line that\nfollows two or more blank lines.  E.g.\n\n    ... the end of a paragraph that is not followed by two blank lines.\n    (blank line)\n    This is not a header, but is part of the previous paragraph group.\n    ... body of the paragraph here ...\n    and this is the tail of the paragraph group.\n    (blank line)\n    (blank line)\n    This begins a new paragraph group.\n    And this is the second line of it.\n\nUnder such a rule, \"This begins a new paragraph group.\" is a header line.\nIf the first hunk begins at the second blank line before that header, we\nwill scan down to the beginning of the file and will find a header that\ncomes before that header line, and remember it in funclen/funcbuf[].  The\nnext scan will stop after looking at one blank line before \"This begins a\nnew paragraph group.\", instead of going down to the beginning, and would\nnot to have a chance to notice that \"This begins a new paragraph group.\"\nindeed has two blank lines before it.  It would instead keep returning the\nheader we found before this header.\n\nI do not think this is such a big issue, though.  In order to allow such a\nmulti-line matching, the loop in xdl_find_func(), now inlined, needs to be\nrestructured anyway, and whoever is doing such an enhancement hopefully\nwill notice that s/he needs to look behind beyond (s1-1) at that point.\n\nSo an Ack from me.\n\nThanks.\n\n> diff --git a/xdiff/xemit.c b/xdiff/xemit.c\n> index c4bedf0..a663f21 100644\n> --- a/xdiff/xemit.c\n> +++ b/xdiff/xemit.c\n> @@ -85,27 +85,6 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv)\n>  \treturn -1;\n>  }\n>  \n> -static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,\n> -\t\tfind_func_t ff, void *ff_priv) {\n> -\n> -\t/*\n> -\t * Be quite stupid about this for now.  Find a line in the old file\n> -\t * before the start of the hunk (and context) which starts with a\n> -\t * plausible character.\n> -\t */\n> -\n> -\tconst char *rec;\n> -\tlong len;\n> -\n> -\twhile (i-- > 0) {\n> -\t\tlen = xdl_get_rec(xf, i, &rec);\n> -\t\tif ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)\n> -\t\t\treturn;\n> -\t}\n> -\t*ll = 0;\n> -}\n> -\n> -\n>  static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n>                             xdemitconf_t const *xecfg) {\n>  \txdfile_t *xdf = &xe->xdf1;\n> @@ -127,6 +106,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n>  \txdchange_t *xch, *xche;\n>  \tchar funcbuf[80];\n>  \tlong funclen = 0;\n> +\tlong funclineprev = -1;\n>  \tfind_func_t ff = xecfg->find_func ?  xecfg->find_func : def_ff;\n>  \n>  \tif (xecfg->flags & XDL_EMIT_COMMON)\n> @@ -150,9 +130,19 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n>  \t\t */\n>  \n>  \t\tif (xecfg->flags & XDL_EMIT_FUNCNAMES) {\n> -\t\t\txdl_find_func(&xe->xdf1, s1, funcbuf,\n> -\t\t\t\t      sizeof(funcbuf), &funclen,\n> -\t\t\t\t      ff, xecfg->find_func_priv);\n> +\t\t\tlong l;\n> +\t\t\tfor (l = s1 - 1; l >= 0 && l > funclineprev; l--) {\n> +\t\t\t\tconst char *rec;\n> +\t\t\t\tlong reclen = xdl_get_rec(&xe->xdf1, l, &rec);\n> +\t\t\t\tlong newfunclen = ff(rec, reclen, funcbuf,\n> +\t\t\t\t\t\t     sizeof(funcbuf),\n> +\t\t\t\t\t\t     xecfg->find_func_priv);\n> +\t\t\t\tif (newfunclen >= 0) {\n> +\t\t\t\t\tfunclen = newfunclen;\n> +\t\t\t\t\tbreak;\n> +\t\t\t\t}\n> +\t\t\t}\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\t\t\t      funcbuf, funclen, ecb) < 0)\n"}]}