{"thread":{"id":"15148","subject":"[PATCH 3/5] Always initialize xpparam_t to 0","startedAt":"2008-08-21T23:21:56Z","lastAt":"2008-10-26T22:20:08Z","messageCount":17,"participants":["Brian Downing","René Scharfe","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"88063","messageId":"1219360921-28529-1-git-send-email-bdowning@lavos.net","threadId":"15148","inReplyTo":null,"subject":"[PATCH 0/5] More git blame speed improvements","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-08-21T23:21:56Z","receivedAt":"2008-08-21T23:21:56Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"This patch series contains more git blame speed improvements.  It's\nreally in two parts; patches 1-2 are the first improvement, and patches\n3-5 are the second (which depend on the first, at least textually.)\n\nThere are some things I'm not entirely happy about in here, but overall\nit's not too bad for a first effort.  I'm interested in hearing what\npeople have to say about it, especially since I'm adding new interfaces\nto the xdiff core for some of this.\n\nPerformance summary for my (proprietary, alas) test case:\n:; time git-blame -M -C -C -p --incremental server.c >/dev/null\nBefore (master):\n79.62user 0.10system 1:19.81elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41189minor)pagefaults 0swaps\nAfter:\n29.68user 0.22system 0:29.98elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+37897minor)pagefaults 0swaps\n\nI have an additional patch (not included here) that caches the actual\nentry lines from the blame, but the performance gain was not exciting\n(the entries passed as the second file to the compare_buffer() call in\nfind_copy_in_blob() are generally quite small), and it results in more\npage faults and a fair amount more code:\n:; time git-blame -M -C -C -p --incremental server.c >/dev/null\n28.82user 0.07system 0:28.93elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+40268minor)pagefaults 0swaps\n\n [PATCH 1/5] Allow alternate \"low-level\" emit function from xdl_diff\n [PATCH 2/5] Bypass textual patch generation and parsing in git blame\n [PATCH 3/5] Always initialize xpparam_t to 0\n [PATCH 4/5] Allow xdiff machinery to cache hash results for a file\n [PATCH 5/5] Use xdiff caching to improve git blame performance\n\n builtin-blame.c  |  103 +++++++++++++++++++++--------------------------------\n builtin-rerere.c |    1 +\n combine-diff.c   |    1 +\n diff.c           |    5 +++\n merge-file.c     |    1 +\n xdiff/xdiff.h    |   12 ++++++\n xdiff/xdiffi.c   |    4 ++-\n xdiff/xemit.c    |    3 +-\n xdiff/xemit.h    |    3 ++\n xdiff/xprepare.c |   59 +++++++++++++++++++++++++++----\n xdiff/xtypes.h   |    1 +\n 11 files changed, 121 insertions(+), 72 deletions(-)\n\n-bcd\n"},{"id":"88059","messageId":"1219360921-28529-2-git-send-email-bdowning@lavos.net","threadId":"15148","inReplyTo":"1219360921-28529-1-git-send-email-bdowning@lavos.net","subject":"[PATCH 1/5] Allow alternate \"low-level\" emit function from xdl_diff","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-08-21T23:21:57Z","receivedAt":"2008-08-21T23:21:57Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"For some users (e.g. git blame), getting textual patch output is just\nextra work, as they can get all the information they need from the low-\nlevel diff structures.  Allow for an alternate low-level emit function\nto be defined to allow bypassing the textual patch generation; set\nxemitconf_t's emit_func member to enable this.\n\nThe (void (*)()) type is pretty ugly, but the alternative would be to\ninclude most of the private xdiff headers in xdiff.h to get the types\nrequired for the \"proper\" function prototype.  Also, a (void *) won't\nwork, as ANSI C doesn't allow a function pointer to be cast to an\nobject pointer.\n\nSigned-off-by: Brian Downing <bdowning@lavos.net>\n---\n xdiff/xdiff.h  |    1 +\n xdiff/xdiffi.c |    4 +++-\n xdiff/xemit.c  |    3 +--\n xdiff/xemit.h  |    3 +++\n 4 files changed, 8 insertions(+), 3 deletions(-)\n\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 413082e..281fc0b 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -81,6 +81,7 @@ typedef struct s_xdemitconf {\n \tunsigned long flags;\n \tfind_func_t find_func;\n \tvoid *find_func_priv;\n+\tvoid (*emit_func)();\n } xdemitconf_t;\n \n typedef struct s_bdiffparam {\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 1bad846..9d0324a 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -538,6 +538,8 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t     xdemitconf_t const *xecfg, xdemitcb_t *ecb) {\n \txdchange_t *xscr;\n \txdfenv_t xe;\n+\temit_func_t ef = xecfg->emit_func ?\n+\t\t(emit_func_t)xecfg->emit_func : xdl_emit_diff;\n \n \tif (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) {\n \n@@ -551,7 +553,7 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\treturn -1;\n \t}\n \tif (xscr) {\n-\t\tif (xdl_emit_diff(&xe, xscr, ecb, xecfg) < 0) {\n+\t\tif (ef(&xe, xscr, ecb, xecfg) < 0) {\n \n \t\t\txdl_free_script(xscr);\n \t\t\txdl_free_env(&xe);\ndiff --git a/xdiff/xemit.c b/xdiff/xemit.c\nindex d3d9c84..4625c1b 100644\n--- a/xdiff/xemit.c\n+++ b/xdiff/xemit.c\n@@ -27,7 +27,6 @@\n \n static long xdl_get_rec(xdfile_t *xdf, long ri, char const **rec);\n static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *ecb);\n-static xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg);\n \n \n \n@@ -58,7 +57,7 @@ static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *\n  * Starting at the passed change atom, find the latest change atom to be included\n  * inside the differential hunk according to the specified configuration.\n  */\n-static xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg) {\n+xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg) {\n \txdchange_t *xch, *xchp;\n \n \tfor (xchp = xscr, xch = xscr->next; xch; xchp = xch, xch = xch->next)\ndiff --git a/xdiff/xemit.h b/xdiff/xemit.h\nindex 440a739..c2e2e83 100644\n--- a/xdiff/xemit.h\n+++ b/xdiff/xemit.h\n@@ -24,7 +24,10 @@\n #define XEMIT_H\n \n \n+typedef int (*emit_func_t)(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n+\t\t\t   xdemitconf_t const *xecfg);\n \n+xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg);\n int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t  xdemitconf_t const *xecfg);\n \n-- \n1.5.6.1\n"},{"id":"88060","messageId":"1219360921-28529-3-git-send-email-bdowning@lavos.net","threadId":"15148","inReplyTo":"1219360921-28529-2-git-send-email-bdowning@lavos.net","subject":"[PATCH 2/5] Bypass textual patch generation and parsing in git blame","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-08-21T23:21:58Z","receivedAt":"2008-08-21T23:21:58Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"This uses the new xdiff emit_func feature to directly generate the\npatch/chunk information from the low-level diff output, rather than\ngenerating and parsing a patch.  This improves performance considerably\nfor certain test cases:\n\n:; time git-blame -M -C -C -p --incremental server.c >/dev/null\nBefore:\n79.62user 0.10system 1:19.81elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+41189minor)pagefaults 0swaps\nAfter:\n48.66user 0.08system 0:48.75elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+36961minor)pagefaults 0swaps\n\nSigned-off-by: Brian Downing <bdowning@lavos.net>\n---\n builtin-blame.c |   90 +++++++++++++++++++------------------------------------\n 1 files changed, 31 insertions(+), 59 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex e4d12de..60f70bf 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -19,6 +19,10 @@\n #include \"string-list.h\"\n #include \"mailmap.h\"\n #include \"parse-options.h\"\n+#include \"xdiff/xtypes.h\"\n+#include \"xdiff/xdiffi.h\"\n+#include \"xdiff/xemit.h\"\n+#include \"xdiff/xmacros.h\"\n \n static char blame_usage[] = \"git blame [options] [rev-opts] [rev] [--] file\";\n \n@@ -464,62 +468,36 @@ struct patch {\n \tint num;\n };\n \n-struct blame_diff_state {\n-\tstruct patch *ret;\n-\tunsigned hunk_post_context;\n-\tunsigned hunk_in_pre_context : 1;\n-};\n-\n-static void process_u_diff(void *state_, char *line, unsigned long len)\n+static int process_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n+\t\t\txdemitconf_t const *xecfg)\n {\n-\tstruct blame_diff_state *state = state_;\n+\tstruct patch *patch = ecb->priv;\n+\tlong s1, s2;\n+\txdchange_t *xch, *xche;\n \tstruct chunk *chunk;\n-\tint off1, off2, len1, len2, num;\n \n-\tnum = state->ret->num;\n-\tif (len < 4 || line[0] != '@' || line[1] != '@') {\n-\t\tif (state->hunk_in_pre_context && line[0] == ' ')\n-\t\t\tstate->ret->chunks[num - 1].same++;\n-\t\telse {\n-\t\t\tstate->hunk_in_pre_context = 0;\n-\t\t\tif (line[0] == ' ')\n-\t\t\t\tstate->hunk_post_context++;\n-\t\t\telse\n-\t\t\t\tstate->hunk_post_context = 0;\n-\t\t}\n-\t\treturn;\n-\t}\n+\tfor (xch = xche = xscr; xch; xch = xche->next) {\n+\t\txche = xdl_get_hunk(xch, xecfg);\n \n-\tif (num && state->hunk_post_context) {\n-\t\tchunk = &state->ret->chunks[num - 1];\n-\t\tchunk->p_next -= state->hunk_post_context;\n-\t\tchunk->t_next -= state->hunk_post_context;\n-\t}\n-\tstate->ret->num = ++num;\n-\tstate->ret->chunks = xrealloc(state->ret->chunks,\n-\t\t\t\t      sizeof(struct chunk) * num);\n-\tchunk = &state->ret->chunks[num - 1];\n-\tif (parse_hunk_header(line, len, &off1, &len1, &off2, &len2)) {\n-\t\tstate->ret->num--;\n-\t\treturn;\n-\t}\n-\n-\t/* Line numbers in patch output are one based. */\n-\toff1--;\n-\toff2--;\n+\t\ts1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);\n+\t\ts2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0);\n \n-\tchunk->same = len2 ? off2 : (off2 + 1);\n+\t\t++patch->num;\n+\t\tpatch->chunks = xrealloc(patch->chunks,\n+\t\t\t\t\t sizeof(struct chunk) * patch->num);\n+\t\tchunk = &patch->chunks[patch->num - 1];\n+\t\tchunk->same = s2 + XDL_MAX(xch->i1 - s1, 0);\n+\t\tchunk->p_next = xche->i1 + xche->chg1;\n+\t\tchunk->t_next = xche->i2 + xche->chg2;\n+\t}\n \n-\tchunk->p_next = off1 + (len1 ? len1 : 1);\n-\tchunk->t_next = chunk->same + len2;\n-\tstate->hunk_in_pre_context = 1;\n-\tstate->hunk_post_context = 0;\n+\treturn 0;\n }\n \n static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,\n \t\t\t\t    int context)\n {\n-\tstruct blame_diff_state state;\n+\tstruct patch *patch;\n \txpparam_t xpp;\n \txdemitconf_t xecfg;\n \txdemitcb_t ecb;\n@@ -527,20 +505,14 @@ static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,\n \txpp.flags = xdl_opts;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \txecfg.ctxlen = context;\n-\tmemset(&state, 0, sizeof(state));\n-\tstate.ret = xmalloc(sizeof(struct patch));\n-\tstate.ret->chunks = NULL;\n-\tstate.ret->num = 0;\n-\n-\txdi_diff_outf(file_p, file_o, process_u_diff, &state, &xpp, &xecfg, &ecb);\n+\tpatch = xmalloc(sizeof(struct patch));\n+\tpatch->chunks = NULL;\n+\tpatch->num = 0;\n+\txecfg.emit_func = (void (*)())process_diff;\n+\tecb.priv = patch;\n+\txdi_diff(file_p, file_o, &xpp, &xecfg, &ecb);\n \n-\tif (state.ret->num) {\n-\t\tstruct chunk *chunk;\n-\t\tchunk = &state.ret->chunks[state.ret->num - 1];\n-\t\tchunk->p_next -= state.hunk_post_context;\n-\t\tchunk->t_next -= state.hunk_post_context;\n-\t}\n-\treturn state.ret;\n+\treturn patch;\n }\n \n /*\n-- \n1.5.6.1\n"},{"id":"88058","messageId":"1219360921-28529-4-git-send-email-bdowning@lavos.net","threadId":"15148","inReplyTo":"1219360921-28529-3-git-send-email-bdowning@lavos.net","subject":"[PATCH 3/5] Always initialize xpparam_t to 0","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-08-21T23:21:59Z","receivedAt":"2008-08-21T23:21:59Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"We're going to be adding some parameters to this, so we can't have\nany uninitialized data in it.\n\nSigned-off-by: Brian Downing <bdowning@lavos.net>\n---\n builtin-blame.c  |    1 +\n builtin-rerere.c |    1 +\n combine-diff.c   |    1 +\n diff.c           |    5 +++++\n merge-file.c     |    1 +\n 5 files changed, 9 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex 60f70bf..66b7d15 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -502,6 +502,7 @@ static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,\n \txdemitconf_t xecfg;\n \txdemitcb_t ecb;\n \n+\tmemset(&xpp, 0, sizeof(xpp));\n \txpp.flags = xdl_opts;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \txecfg.ctxlen = context;\ndiff --git a/builtin-rerere.c b/builtin-rerere.c\nindex dd4573f..d4dec6b 100644\n--- a/builtin-rerere.c\n+++ b/builtin-rerere.c\n@@ -98,6 +98,7 @@ static int diff_two(const char *file1, const char *label1,\n \n \tprintf(\"--- a/%s\\n+++ b/%s\\n\", label1, label2);\n \tfflush(stdout);\n+\tmemset(&xpp, 0, sizeof(xpp));\n \txpp.flags = XDF_NEED_MINIMAL;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \txecfg.ctxlen = 3;\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 31ec0c5..70d5aad 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -213,6 +213,7 @@ static void combine_diff(const unsigned char *parent, mmfile_t *result_file,\n \n \tparent_file.ptr = grab_blob(parent, &sz);\n \tparent_file.size = sz;\n+\tmemset(&xpp, 0, sizeof(xpp));\n \txpp.flags = XDF_NEED_MINIMAL;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \tmemset(&state, 0, sizeof(state));\ndiff --git a/diff.c b/diff.c\nindex 5923fe2..52346fe 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -446,6 +446,7 @@ static void diff_words_show(struct diff_words_data *diff_words)\n \tmmfile_t minus, plus;\n \tint i;\n \n+\tmemset(&xpp, 0, sizeof(xpp));\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \tminus.size = diff_words->minus.text.size;\n \tminus.ptr = xmalloc(minus.size);\n@@ -1508,6 +1509,7 @@ static void builtin_diff(const char *name_a,\n \t\tif (!funcname_pattern)\n \t\t\tfuncname_pattern = diff_funcname_pattern(two);\n \n+\t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\tmemset(&ecbdata, 0, sizeof(ecbdata));\n \t\tecbdata.label_path = lbl;\n@@ -1581,6 +1583,7 @@ static void builtin_diffstat(const char *name_a, const char *name_b,\n \t\txdemitconf_t xecfg;\n \t\txdemitcb_t ecb;\n \n+\t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\txpp.flags = XDF_NEED_MINIMAL | o->xdl_opts;\n \t\txdi_diff_outf(&mf1, &mf2, diffstat_consume, diffstat,\n@@ -1627,6 +1630,7 @@ static void builtin_checkdiff(const char *name_a, const char *name_b,\n \t\txdemitconf_t xecfg;\n \t\txdemitcb_t ecb;\n \n+\t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\txecfg.ctxlen = 1; /* at least one context line */\n \t\txpp.flags = XDF_NEED_MINIMAL;\n@@ -3072,6 +3076,7 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)\n \t\tstruct diff_filepair *p = q->queue[i];\n \t\tint len1, len2;\n \n+\t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\tif (p->status == 0)\n \t\t\treturn error(\"internal diff status error\");\ndiff --git a/merge-file.c b/merge-file.c\nindex 2a939c9..3120a95 100644\n--- a/merge-file.c\n+++ b/merge-file.c\n@@ -61,6 +61,7 @@ static int generate_common_file(mmfile_t *res, mmfile_t *f1, mmfile_t *f2)\n \txdemitconf_t xecfg;\n \txdemitcb_t ecb;\n \n+\tmemset(&xpp, 0, sizeof(xpp));\n \txpp.flags = XDF_NEED_MINIMAL;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \txecfg.ctxlen = 3;\n-- \n1.5.6.1\n"},{"id":"88061","messageId":"1219360921-28529-5-git-send-email-bdowning@lavos.net","threadId":"15148","inReplyTo":"1219360921-28529-4-git-send-email-bdowning@lavos.net","subject":"[PATCH 4/5] Allow xdiff machinery to cache hash results for a file","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-08-21T23:22:00Z","receivedAt":"2008-08-21T23:22:00Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"When generating diffs against the same file multiple times, it is a\nwaste of work to regenerate the hash values for each line each time.\nInstead, allow a cache pointer to be passed in xpparam_t; set mf1_cache\nto the cache for the first mmfile_t to xdl_diff, and mf2_cache for the\nsecond.\n\nThis works like:\n\n\txdcache_t cache;\n\tmemset(cache, 0, sizeof(cache));\n\t/* ... */\n\txpp.mf1_cache = &cache;\n\txdl_diff(file1, file2, &xpp, &xecfg, &ecb);\n\t/* ...later... */\n\txpp.mf1_cache = &cache;\n\txdl_diff(file1, file3, &xpp, &xecfg, &ecb);\n\t/* The cache for file1 will be reused. */\n\txdl_cache_free(&cache);\n\nNote that this isn't compatible with xdi_diff as-is, as getting a\ncomplete cache is incompatible with tail trimming.\n\nSigned-off-by: Brian Downing <bdowning@lavos.net>\n---\n xdiff/xdiff.h    |   11 ++++++++++\n xdiff/xprepare.c |   59 +++++++++++++++++++++++++++++++++++++++++++++++------\n xdiff/xtypes.h   |    1 +\n 3 files changed, 64 insertions(+), 7 deletions(-)\n\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 281fc0b..6fd922b 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -65,8 +65,17 @@ typedef struct s_mmbuffer {\n \tlong size;\n } mmbuffer_t;\n \n+typedef struct s_xdcache_int {\n+\tlong nrec;\n+\tunsigned long flags;\n+\tunsigned long *ha;\n+\tlong *size;\n+} xdcache_t;\n+\n typedef struct s_xpparam {\n \tunsigned long flags;\n+\txdcache_t *mf1_cache;\n+\txdcache_t *mf2_cache;\n } xpparam_t;\n \n typedef struct s_xdemitcb {\n@@ -104,6 +113,8 @@ int xdl_merge(mmfile_t *orig, mmfile_t *mf1, const char *name1,\n \t\tmmfile_t *mf2, const char *name2,\n \t\txpparam_t const *xpp, int level, mmbuffer_t *result);\n \n+void xdl_cache_free(xdcache_t *cache);\n+\n #ifdef __cplusplus\n }\n #endif /* #ifdef __cplusplus */\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex e87ab57..291caf9 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -54,7 +54,8 @@ static void xdl_free_classifier(xdlclassifier_t *cf);\n static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,\n \t\t\t       xrecord_t *rec);\n static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n-\t\t\t   xdlclassifier_t *cf, xdfile_t *xdf);\n+\t\t\t   xdlclassifier_t *cf, xdfile_t *xdf,\n+\t\t\t   xdcache_t *cache);\n static void xdl_free_ctx(xdfile_t *xdf);\n static int xdl_clean_mmatch(char const *dis, long i, long s, long e);\n static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2);\n@@ -135,7 +136,8 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned\n \n \n static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n-\t\t\t   xdlclassifier_t *cf, xdfile_t *xdf) {\n+\t\t\t   xdlclassifier_t *cf, xdfile_t *xdf,\n+\t\t\t   xdcache_t *cache) {\n \tunsigned int hbits;\n \tlong i, nrec, hsize, bsize;\n \tunsigned long hav;\n@@ -177,7 +179,12 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\t\ttop = blk + bsize;\n \t\t\t}\n \t\t\tprev = cur;\n-\t\t\thav = xdl_hash_record(&cur, top, xpp->flags);\n+\t\t\tif (cache && cache->ha) {\n+\t\t\t\thav = cache->ha[nrec];\n+\t\t\t\tcur += cache->size[nrec];\n+\t\t\t} else {\n+\t\t\t\thav = xdl_hash_record(&cur, top, xpp->flags);\n+\t\t\t}\n \t\t\tif (nrec >= narec) {\n \t\t\t\tnarec *= 2;\n \t\t\t\tif (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) {\n@@ -199,6 +206,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\tcrec->ptr = prev;\n \t\t\tcrec->size = (long) (cur - prev);\n \t\t\tcrec->ha = hav;\n+\t\t\tcrec->original_ha = hav;\n \t\t\trecs[nrec++] = crec;\n \n \t\t\tif (xdl_classify_record(cf, rhash, hbits, crec) < 0) {\n@@ -249,6 +257,23 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \txdf->dstart = 0;\n \txdf->dend = nrec - 1;\n \n+\tif (cache && !cache->ha) {\n+\t\tcache->nrec = nrec;\n+\t\tcache->ha = xdl_malloc(nrec * sizeof(unsigned long));\n+\t\tif (!cache->ha)\n+\t\t\treturn 0;\n+\t\tcache->size = xdl_malloc(nrec * sizeof(long));\n+\t\tif (!cache->size) {\n+\t\t\txdl_free(cache->ha);\n+\t\t\tcache->ha = NULL;\n+\t\t\treturn 0;\n+\t\t}\n+\t\tfor (i = 0; i < nrec; ++i) {\n+\t\t\tcache->ha[i] = recs[i]->original_ha;\n+\t\t\tcache->size[i] = recs[i]->size;\n+\t\t}\n+\t}\n+\n \treturn 0;\n }\n \n@@ -268,21 +293,34 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\t    xdfenv_t *xe) {\n \tlong enl1, enl2;\n \txdlclassifier_t cf;\n+\txdcache_t *c1 = xpp->mf1_cache;\n+\txdcache_t *c2 = xpp->mf2_cache;\n \n-\tenl1 = xdl_guess_lines(mf1) + 1;\n-\tenl2 = xdl_guess_lines(mf2) + 1;\n+\tif (c1) {\n+\t\tif (c1->flags != xpp->flags)\n+\t\t\txdl_cache_free(c1);\n+\t\tc1->flags = xpp->flags;\n+\t}\n+\tif (c2) {\n+\t\tif (c2->flags != xpp->flags)\n+\t\t\txdl_cache_free(c2);\n+\t\tc2->flags = xpp->flags;\n+\t}\n+\n+\tenl1 = c1 && c1->nrec ? c1->nrec : (xdl_guess_lines(mf1) + 1);\n+\tenl2 = c2 && c2->nrec ? c2->nrec : (xdl_guess_lines(mf2) + 1);\n \n \tif (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {\n \n \t\treturn -1;\n \t}\n \n-\tif (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {\n+\tif (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1, c1) < 0) {\n \n \t\txdl_free_classifier(&cf);\n \t\treturn -1;\n \t}\n-\tif (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {\n+\tif (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2, c2) < 0) {\n \n \t\txdl_free_ctx(&xe->xdf1);\n \t\txdl_free_classifier(&cf);\n@@ -309,6 +347,13 @@ void xdl_free_env(xdfenv_t *xe) {\n }\n \n \n+void xdl_cache_free(xdcache_t *cache) {\n+\txdl_free(cache->ha);\n+\txdl_free(cache->size);\n+\tmemset(cache, 0, sizeof(xdcache_t));\n+}\n+\n+\n static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {\n \tlong r, rdis0, rpdis0, rdis1, rpdis1;\n \ndiff --git a/xdiff/xtypes.h b/xdiff/xtypes.h\nindex 2511aef..e6f6890 100644\n--- a/xdiff/xtypes.h\n+++ b/xdiff/xtypes.h\n@@ -43,6 +43,7 @@ typedef struct s_xrecord {\n \tchar const *ptr;\n \tlong size;\n \tunsigned long ha;\n+\tunsigned long original_ha;\n } xrecord_t;\n \n typedef struct s_xdfile {\n-- \n1.5.6.1\n"},{"id":"88062","messageId":"1219360921-28529-6-git-send-email-bdowning@lavos.net","threadId":"15148","inReplyTo":"1219360921-28529-5-git-send-email-bdowning@lavos.net","subject":"[PATCH 5/5] Use xdiff caching to improve git blame performance","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-08-21T23:22:01Z","receivedAt":"2008-08-21T23:22:01Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"git blame -C -C diffs all entries against the same file.  To avoid having\nto recompute the line hashes for this file over and over again, use the\nxddiff cache feature to store the hashes in struct origin.\n\nNote that because this bypasses the xdi_diff tail trimming, it can\nreturn different (but still valid) blame results for certain cases.\nSee http://article.gmane.org/gmane.comp.version-control.git/93112 for\nmore details.\n\nThis yields another significant speed improvement for some cases:\n\n:; time git-blame -M -C -C -p --incremental server.c >/dev/null\nBefore:\n48.66user 0.08system 0:48.75elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+36961minor)pagefaults 0swaps\nAfter:\n29.68user 0.22system 0:29.98elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+37897minor)pagefaults 0swaps\n\nSigned-off-by: Brian Downing <bdowning@lavos.net>\n---\n builtin-blame.c |   14 ++++++++++----\n 1 files changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex 66b7d15..3e90668 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -80,6 +80,7 @@ struct origin {\n \tint refcnt;\n \tstruct commit *commit;\n \tmmfile_t file;\n+\txdcache_t xdcache;\n \tunsigned char blob_sha1[20];\n \tchar path[FLEX_ARRAY];\n };\n@@ -119,6 +120,7 @@ static inline struct origin *origin_incref(struct origin *o)\n static void origin_decref(struct origin *o)\n {\n \tif (o && --o->refcnt <= 0) {\n+\t        xdl_cache_free(&o->xdcache);\n \t\tfree(o->file.ptr);\n \t\tfree(o);\n \t}\n@@ -494,7 +496,8 @@ static int process_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \treturn 0;\n }\n \n-static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,\n+static struct patch *compare_buffer(mmfile_t *file_p, xdcache_t *cache_p,\n+\t\t\t\t    mmfile_t *file_o, xdcache_t *cache_o,\n \t\t\t\t    int context)\n {\n \tstruct patch *patch;\n@@ -504,6 +507,8 @@ static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,\n \n \tmemset(&xpp, 0, sizeof(xpp));\n \txpp.flags = xdl_opts;\n+\txpp.mf1_cache = cache_p;\n+\txpp.mf2_cache = cache_o;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \txecfg.ctxlen = context;\n \tpatch = xmalloc(sizeof(struct patch));\n@@ -511,7 +516,7 @@ static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,\n \tpatch->num = 0;\n \txecfg.emit_func = (void (*)())process_diff;\n \tecb.priv = patch;\n-\txdi_diff(file_p, file_o, &xpp, &xecfg, &ecb);\n+\txdl_diff(file_p, file_o, &xpp, &xecfg, &ecb);\n \n \treturn patch;\n }\n@@ -530,7 +535,8 @@ static struct patch *get_patch(struct origin *parent, struct origin *origin)\n \tfill_origin_blob(origin, &file_o);\n \tif (!file_p.ptr || !file_o.ptr)\n \t\treturn NULL;\n-\tpatch = compare_buffer(&file_p, &file_o, 0);\n+\tpatch = compare_buffer(&file_p, &parent->xdcache,\n+\t\t\t       &file_o, &origin->xdcache, 0);\n \tnum_get_patch++;\n \treturn patch;\n }\n@@ -937,7 +943,7 @@ static void find_copy_in_blob(struct scoreboard *sb,\n \t}\n \tfile_o.size = cp - file_o.ptr;\n \n-\tpatch = compare_buffer(file_p, &file_o, 1);\n+\tpatch = compare_buffer(file_p, &parent->xdcache, &file_o, NULL, 1);\n \n \t/*\n \t * file_o is a part of final image we are annotating.\n-- \n1.5.6.1\n"},{"id":"88263","messageId":"48AFC73F.2010100@lsrfire.ath.cx","threadId":"15148","inReplyTo":"1219360921-28529-2-git-send-email-bdowning@lavos.net","subject":"Re: [PATCH 1/5] Allow alternate \"low-level\" emit function from xdl_diff","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-08-23T08:15:59Z","receivedAt":"2008-08-23T08:15:59Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Brian Downing schrieb:\n> For some users (e.g. git blame), getting textual patch output is just\n> extra work, as they can get all the information they need from the low-\n> level diff structures.  Allow for an alternate low-level emit function\n> to be defined to allow bypassing the textual patch generation; set\n> xemitconf_t's emit_func member to enable this.\n> \n> The (void (*)()) type is pretty ugly, but the alternative would be to\n> include most of the private xdiff headers in xdiff.h to get the types\n> required for the \"proper\" function prototype.  Also, a (void *) won't\n> work, as ANSI C doesn't allow a function pointer to be cast to an\n> object pointer.\n\nCould we move more code into the library code to avoid that ugliness?\n\nAFAICS, compare_buffer() builds a struct patch with an array of\nstruct chunks, whose members are then fed one by one into either\nblame_chunk() or handle_split().  Could we avoid the allocation\naltogether by using a different interface?\n\nE.g. have a callback like this:\n\n\tstatic void handle_split_cb(long same, long p_next, long t_next,\n\t\t\tvoid *data)\n\t{\n\t\tstruct chunk_cb_data *d = data;\n\t\thandle_split(d->sb, d->ent, d->tlno, d->plno, same,\n\t\t\t\td->parent, d->split);\n\t\td->plno = p_next;\n\t\td->tlno = t_next;\n\t}\n\nAnd use it like this:\n\n\tstruct chunk_cb_data d = {sb, ent, 0, 0, parent, split};\n        xpparam_t xpp;\n        xdemitconf_t xecfg;\n\n        xpp.flags = xdl_opts;\n        memset(&xecfg, 0, sizeof(xecfg));\n        xecfg.ctxlen = context;\n\txdi_diff_chunks(file_p, file_o, &xpp, &xecfg, handle_split_cb, &d);\n        handle_split(sb, ent, d.tlno, d.plno, ent->num_lines,\n\t\t\tparent, split);\n\nMakes sense?\n\nRené\n"},{"id":"88278","messageId":"7vy72o14tw.fsf@gitster.siamese.dyndns.org","threadId":"15148","inReplyTo":"48AFC73F.2010100@lsrfire.ath.cx","subject":"Re: [PATCH 1/5] Allow alternate \"low-level\" emit function from xdl_diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-08-23T09:03:07Z","receivedAt":"2008-08-23T09:03:07Z","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> Could we move more code into the library code to avoid that ugliness?\n>\n> AFAICS, compare_buffer() builds a struct patch with an array of\n> struct chunks, whose members are then fed one by one into either\n> blame_chunk() or handle_split().  Could we avoid the allocation\n> altogether by using a different interface?\n>\n> E.g. have a callback like this:\n>\n> \tstatic void handle_split_cb(long same, long p_next, long t_next,\n> \t\t\tvoid *data)\n> \t{\n> \t\tstruct chunk_cb_data *d = data;\n> \t\thandle_split(d->sb, d->ent, d->tlno, d->plno, same,\n> \t\t\t\td->parent, d->split);\n> \t\td->plno = p_next;\n> \t\td->tlno = t_next;\n> \t}\n>\n> And use it like this:\n>\n> \tstruct chunk_cb_data d = {sb, ent, 0, 0, parent, split};\n>         xpparam_t xpp;\n>         xdemitconf_t xecfg;\n>\n>         xpp.flags = xdl_opts;\n>         memset(&xecfg, 0, sizeof(xecfg));\n>         xecfg.ctxlen = context;\n> \txdi_diff_chunks(file_p, file_o, &xpp, &xecfg, handle_split_cb, &d);\n>         handle_split(sb, ent, d.tlno, d.plno, ent->num_lines,\n> \t\t\tparent, split);\n>\n> Makes sense?\n\nAbsolutely; very well formulated.  Thanks.\n"},{"id":"88352","messageId":"20080824081254.GI31114@lavos.net","threadId":"15148","inReplyTo":"48AFC73F.2010100@lsrfire.ath.cx","subject":"Re: [PATCH 1/5] Allow alternate \"low-level\" emit function from xdl_diff","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-08-24T08:12:54Z","receivedAt":"2008-08-24T08:12:54Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"On Sat, Aug 23, 2008 at 10:15:59AM +0200, René Scharfe wrote:\n> Could we move more code into the library code to avoid that ugliness?\n> \n> AFAICS, compare_buffer() builds a struct patch with an array of\n> struct chunks, whose members are then fed one by one into either\n> blame_chunk() or handle_split().  Could we avoid the allocation\n> altogether by using a different interface?\n\nThanks, I think this is a good idea.  I'll try to work up something like\nthis, but it may be a few days before I have any appreciable hacking\ntime to do so.\n\n-bcd \n"},{"id":"89698","messageId":"48BF0FBF.3010104@lsrfire.ath.cx","threadId":"15148","inReplyTo":"20080824081254.GI31114@lavos.net","subject":"Re: [PATCH 1/5] Allow alternate \"low-level\" emit function from xdl_diff","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-09-03T22:29:19Z","receivedAt":"2008-09-03T22:29:19Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Brian Downing schrieb:\n> On Sat, Aug 23, 2008 at 10:15:59AM +0200, René Scharfe wrote:\n>> Could we move more code into the library code to avoid that ugliness?\n>>\n>> AFAICS, compare_buffer() builds a struct patch with an array of\n>> struct chunks, whose members are then fed one by one into either\n>> blame_chunk() or handle_split().  Could we avoid the allocation\n>> altogether by using a different interface?\n> \n> Thanks, I think this is a good idea.  I'll try to work up something like\n> this, but it may be a few days before I have any appreciable hacking\n> time to do so.\n\nHere's a patch on top of the one I'm replying to, which in turn is\nb3779280ca4881252069fa9d1c7d2069a69c4a52 in pu.  While it removes more\ncode than it adds and has a slightly nicer interface, it doesn't speed\nup blame.  The following test case:\n\n   $ git-blame -M -C -C -p --incremental master -- Makefile >/dev/null\n\nloses a few calls to mmap, munmap and brk, as strace tells me, but any\nspeed up that might result from that is lost in the noise.\n\nI haven't had time to think about how to combine it with the cache you\nintroduced in patches 2-5, though, and I won't get to it before the\nweekend (if at all). :-/\n\nThanks,\nRené\n\n\n builtin-blame.c   |  178 ++++++++++++++++------------------------------------\n xdiff-interface.c |   50 +++++++++++++++-\n xdiff-interface.h |    5 ++\n 3 files changed, 109 insertions(+), 124 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex 60f70bf..c9783dc 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -19,10 +19,6 @@\n #include \"string-list.h\"\n #include \"mailmap.h\"\n #include \"parse-options.h\"\n-#include \"xdiff/xtypes.h\"\n-#include \"xdiff/xdiffi.h\"\n-#include \"xdiff/xemit.h\"\n-#include \"xdiff/xmacros.h\"\n \n static char blame_usage[] = \"git blame [options] [rev-opts] [rev] [--] file\";\n \n@@ -448,99 +444,6 @@ static struct origin *find_rename(struct scoreboard *sb,\n }\n \n /*\n- * Parsing of patch chunks...\n- */\n-struct chunk {\n-\t/* line number in postimage; up to but not including this\n-\t * line is the same as preimage\n-\t */\n-\tint same;\n-\n-\t/* preimage line number after this chunk */\n-\tint p_next;\n-\n-\t/* postimage line number after this chunk */\n-\tint t_next;\n-};\n-\n-struct patch {\n-\tstruct chunk *chunks;\n-\tint num;\n-};\n-\n-static int process_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n-\t\t\txdemitconf_t const *xecfg)\n-{\n-\tstruct patch *patch = ecb->priv;\n-\tlong s1, s2;\n-\txdchange_t *xch, *xche;\n-\tstruct chunk *chunk;\n-\n-\tfor (xch = xche = xscr; xch; xch = xche->next) {\n-\t\txche = xdl_get_hunk(xch, xecfg);\n-\n-\t\ts1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);\n-\t\ts2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0);\n-\n-\t\t++patch->num;\n-\t\tpatch->chunks = xrealloc(patch->chunks,\n-\t\t\t\t\t sizeof(struct chunk) * patch->num);\n-\t\tchunk = &patch->chunks[patch->num - 1];\n-\t\tchunk->same = s2 + XDL_MAX(xch->i1 - s1, 0);\n-\t\tchunk->p_next = xche->i1 + xche->chg1;\n-\t\tchunk->t_next = xche->i2 + xche->chg2;\n-\t}\n-\n-\treturn 0;\n-}\n-\n-static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,\n-\t\t\t\t    int context)\n-{\n-\tstruct patch *patch;\n-\txpparam_t xpp;\n-\txdemitconf_t xecfg;\n-\txdemitcb_t ecb;\n-\n-\txpp.flags = xdl_opts;\n-\tmemset(&xecfg, 0, sizeof(xecfg));\n-\txecfg.ctxlen = context;\n-\tpatch = xmalloc(sizeof(struct patch));\n-\tpatch->chunks = NULL;\n-\tpatch->num = 0;\n-\txecfg.emit_func = (void (*)())process_diff;\n-\tecb.priv = patch;\n-\txdi_diff(file_p, file_o, &xpp, &xecfg, &ecb);\n-\n-\treturn patch;\n-}\n-\n-/*\n- * Run diff between two origins and grab the patch output, so that\n- * we can pass blame for lines origin is currently suspected for\n- * to its parent.\n- */\n-static struct patch *get_patch(struct origin *parent, struct origin *origin)\n-{\n-\tmmfile_t file_p, file_o;\n-\tstruct patch *patch;\n-\n-\tfill_origin_blob(parent, &file_p);\n-\tfill_origin_blob(origin, &file_o);\n-\tif (!file_p.ptr || !file_o.ptr)\n-\t\treturn NULL;\n-\tpatch = compare_buffer(&file_p, &file_o, 0);\n-\tnum_get_patch++;\n-\treturn patch;\n-}\n-\n-static void free_patch(struct patch *p)\n-{\n-\tfree(p->chunks);\n-\tfree(p);\n-}\n-\n-/*\n  * Link in a new blame entry to the scoreboard.  Entries that cover the\n  * same line range have been removed from the scoreboard previously.\n  */\n@@ -786,6 +689,22 @@ static void blame_chunk(struct scoreboard *sb,\n \t}\n }\n \n+struct blame_chunk_cb_data {\n+\tstruct scoreboard *sb;\n+\tstruct origin *target;\n+\tstruct origin *parent;\n+\tlong plno;\n+\tlong tlno;\n+};\n+\n+static void blame_chunk_cb(void *data, long same, long p_next, long t_next)\n+{\n+\tstruct blame_chunk_cb_data *d = data;\n+\tblame_chunk(d->sb, d->tlno, d->plno, same, d->target, d->parent);\n+\td->plno = p_next;\n+\td->tlno = t_next;\n+}\n+\n /*\n  * We are looking at the origin 'target' and aiming to pass blame\n  * for the lines it is suspected to its parent.  Run diff to find\n@@ -795,26 +714,28 @@ static int pass_blame_to_parent(struct scoreboard *sb,\n \t\t\t\tstruct origin *target,\n \t\t\t\tstruct origin *parent)\n {\n-\tint i, last_in_target, plno, tlno;\n-\tstruct patch *patch;\n+\tint last_in_target;\n+\tmmfile_t file_p, file_o;\n+\tstruct blame_chunk_cb_data d = { sb, target, parent, 0, 0 };\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n \n \tlast_in_target = find_last_in_target(sb, target);\n \tif (last_in_target < 0)\n \t\treturn 1; /* nothing remains for this target */\n \n-\tpatch = get_patch(parent, target);\n-\tplno = tlno = 0;\n-\tfor (i = 0; i < patch->num; i++) {\n-\t\tstruct chunk *chunk = &patch->chunks[i];\n+\tfill_origin_blob(parent, &file_p);\n+\tfill_origin_blob(target, &file_o);\n \n-\t\tblame_chunk(sb, tlno, plno, chunk->same, target, parent);\n-\t\tplno = chunk->p_next;\n-\t\ttlno = chunk->t_next;\n-\t}\n+\tnum_get_patch++;\n+\n+\txpp.flags = xdl_opts;\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\txecfg.ctxlen = 0;\n+\txdi_diff_chunks(&file_p, &file_o, blame_chunk_cb, &d, &xpp, &xecfg);\n \t/* The rest (i.e. anything after tlno) are the same as the parent */\n-\tblame_chunk(sb, tlno, plno, last_in_target, target, parent);\n+\tblame_chunk(sb, d.tlno, d.plno, last_in_target, target, parent);\n \n-\tfree_patch(patch);\n \treturn 0;\n }\n \n@@ -906,6 +827,23 @@ static void handle_split(struct scoreboard *sb,\n \t}\n }\n \n+struct handle_split_cb_data {\n+\tstruct scoreboard *sb;\n+\tstruct blame_entry *ent;\n+\tstruct origin *parent;\n+\tstruct blame_entry *split;\n+\tlong plno;\n+\tlong tlno;\n+};\n+\n+static void handle_split_cb(void *data, long same, long p_next, long t_next)\n+{\n+\tstruct handle_split_cb_data *d = data;\n+\thandle_split(d->sb, d->ent, d->tlno, d->plno, same, d->parent, d->split);\n+\td->plno = p_next;\n+\td->tlno = t_next;\n+}\n+\n /*\n  * Find the lines from parent that are the same as ent so that\n  * we can pass blames to it.  file_p has the blob contents for\n@@ -920,8 +858,9 @@ static void find_copy_in_blob(struct scoreboard *sb,\n \tconst char *cp;\n \tint cnt;\n \tmmfile_t file_o;\n-\tstruct patch *patch;\n-\tint i, plno, tlno;\n+\tstruct handle_split_cb_data d = { sb, ent, parent, split, 0, 0 };\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n \n \t/*\n \t * Prepare mmfile that contains only the lines in ent.\n@@ -936,24 +875,17 @@ static void find_copy_in_blob(struct scoreboard *sb,\n \t}\n \tfile_o.size = cp - file_o.ptr;\n \n-\tpatch = compare_buffer(file_p, &file_o, 1);\n-\n \t/*\n \t * file_o is a part of final image we are annotating.\n \t * file_p partially may match that image.\n \t */\n+\txpp.flags = xdl_opts;\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\txecfg.ctxlen = 1;\n \tmemset(split, 0, sizeof(struct blame_entry [3]));\n-\tplno = tlno = 0;\n-\tfor (i = 0; i < patch->num; i++) {\n-\t\tstruct chunk *chunk = &patch->chunks[i];\n-\n-\t\thandle_split(sb, ent, tlno, plno, chunk->same, parent, split);\n-\t\tplno = chunk->p_next;\n-\t\ttlno = chunk->t_next;\n-\t}\n+\txdi_diff_chunks(file_p, &file_o, handle_split_cb, &d, &xpp, &xecfg);\n \t/* remainder, if any, all match the preimage */\n-\thandle_split(sb, ent, tlno, plno, ent->num_lines, parent, split);\n-\tfree_patch(patch);\n+\thandle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);\n }\n \n /*\ndiff --git a/xdiff-interface.c b/xdiff-interface.c\nindex 944ad98..a7cfdab 100644\n--- a/xdiff-interface.c\n+++ b/xdiff-interface.c\n@@ -1,6 +1,9 @@\n #include \"cache.h\"\n #include \"xdiff-interface.h\"\n-#include \"strbuf.h\"\n+#include \"xdiff/xtypes.h\"\n+#include \"xdiff/xdiffi.h\"\n+#include \"xdiff/xemit.h\"\n+#include \"xdiff/xmacros.h\"\n \n struct xdiff_emit_state {\n \txdiff_emit_consume_fn consume;\n@@ -153,6 +156,51 @@ int xdi_diff_outf(mmfile_t *mf1, mmfile_t *mf2,\n \treturn ret;\n }\n \n+struct xdiff_emit_chunk_state {\n+\txdiff_emit_chunk_consume_fn consume;\n+\tvoid *consume_callback_data;\n+};\n+\n+static int process_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n+\t\t\txdemitconf_t const *xecfg)\n+{\n+\tlong s1, s2, same, p_next, t_next;\n+\txdchange_t *xch, *xche;\n+\tstruct xdiff_emit_chunk_state *state = ecb->priv;\n+\txdiff_emit_chunk_consume_fn fn = state->consume;\n+\tvoid *consume_callback_data = state->consume_callback_data;\n+\n+\n+\tfor (xch = xche = xscr; xch; xch = xche->next) {\n+\t\txche = xdl_get_hunk(xch, xecfg);\n+\n+\t\ts1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);\n+\t\ts2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0);\n+\t\tsame = s2 + XDL_MAX(xch->i1 - s1, 0);\n+\t\tp_next = xche->i1 + xche->chg1;\n+\t\tt_next = xche->i2 + xche->chg2;\n+\n+\t\tfn(consume_callback_data, same, p_next, t_next);\n+\t}\n+\treturn 0;\n+}\n+\n+int xdi_diff_chunks(mmfile_t *mf1, mmfile_t *mf2,\n+\t\t    xdiff_emit_chunk_consume_fn fn, void *consume_callback_data,\n+\t\t    xpparam_t const *xpp, xdemitconf_t *xecfg)\n+{\n+\tstruct xdiff_emit_chunk_state state;\n+\txdemitcb_t ecb;\n+\n+\tmemset(&state, 0, sizeof(state));\n+\tmemset(&ecb, 0, sizeof(ecb));\n+\tstate.consume = fn;\n+\tstate.consume_callback_data = consume_callback_data;\n+\txecfg->emit_func = (void (*)())process_diff;\n+\tecb.priv = &state;\n+\treturn xdi_diff(mf1, mf2, xpp, xecfg, &ecb);\n+}\n+\n int read_mmfile(mmfile_t *ptr, const char *filename)\n {\n \tstruct stat st;\ndiff --git a/xdiff-interface.h b/xdiff-interface.h\nindex 558492b..1f7d985 100644\n--- a/xdiff-interface.h\n+++ b/xdiff-interface.h\n@@ -4,12 +4,17 @@\n #include \"xdiff/xdiff.h\"\n \n typedef void (*xdiff_emit_consume_fn)(void *, char *, unsigned long);\n+typedef void (*xdiff_emit_chunk_consume_fn)(void *, long, long, long);\n \n int xdi_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdemitconf_t const *xecfg, xdemitcb_t *ecb);\n int xdi_diff_outf(mmfile_t *mf1, mmfile_t *mf2,\n \t\t  xdiff_emit_consume_fn fn, void *consume_callback_data,\n \t\t  xpparam_t const *xpp,\n \t\t  xdemitconf_t const *xecfg, xdemitcb_t *xecb);\n+int xdi_diff_chunks(mmfile_t *mf1, mmfile_t *mf2,\n+\t\t    xdiff_emit_chunk_consume_fn fn, void *consume_callback_data,\n+\t\t    xpparam_t const *xpp, xdemitconf_t *xecfg);\n+\n int parse_hunk_header(char *line, int len,\n \t\t      int *ob, int *on,\n \t\t      int *nb, int *nn);\n"},{"id":"93926","messageId":"49031F6E.7040402@lsrfire.ath.cx","threadId":"15148","inReplyTo":"48BF0FBF.3010104@lsrfire.ath.cx","subject":"[PATCH 1/5] blame: inline get_patch()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-10-25T13:30:22Z","receivedAt":"2008-10-25T13:30:22Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Inline get_patch() to its only call site as a preparation for getting rid\nof struct patch.  Also we don't need to check the ptr members because\nfill_origin_blob() already did, and the caller didn't check for NULL\nanyway, so drop the test.\n\nSigned-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n---\n builtin-blame.c |   31 +++++++++++--------------------\n 1 files changed, 11 insertions(+), 20 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex 48cc0c1..593b539 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -542,25 +542,6 @@ static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,\n \treturn state.ret;\n }\n \n-/*\n- * Run diff between two origins and grab the patch output, so that\n- * we can pass blame for lines origin is currently suspected for\n- * to its parent.\n- */\n-static struct patch *get_patch(struct origin *parent, struct origin *origin)\n-{\n-\tmmfile_t file_p, file_o;\n-\tstruct patch *patch;\n-\n-\tfill_origin_blob(parent, &file_p);\n-\tfill_origin_blob(origin, &file_o);\n-\tif (!file_p.ptr || !file_o.ptr)\n-\t\treturn NULL;\n-\tpatch = compare_buffer(&file_p, &file_o, 0);\n-\tnum_get_patch++;\n-\treturn patch;\n-}\n-\n static void free_patch(struct patch *p)\n {\n \tfree(p->chunks);\n@@ -824,12 +805,22 @@ static int pass_blame_to_parent(struct scoreboard *sb,\n {\n \tint i, last_in_target, plno, tlno;\n \tstruct patch *patch;\n+\tmmfile_t file_p, file_o;\n \n \tlast_in_target = find_last_in_target(sb, target);\n \tif (last_in_target < 0)\n \t\treturn 1; /* nothing remains for this target */\n \n-\tpatch = get_patch(parent, target);\n+\t/*\n+\t * Run diff between two origins and grab the patch output, so that\n+\t * we can pass blame for lines origin is currently suspected for\n+\t * to its parent.\n+\t */\n+\tfill_origin_blob(parent, &file_p);\n+\tfill_origin_blob(target, &file_o);\n+\tpatch = compare_buffer(&file_p, &file_o, 0);\n+\tnum_get_patch++;\n+\n \tplno = tlno = 0;\n \tfor (i = 0; i < patch->num; i++) {\n \t\tstruct chunk *chunk = &patch->chunks[i];\n-- \n1.6.0.3.514.g2f91b\n"},{"id":"93924","messageId":"49031F7D.2010908@lsrfire.ath.cx","threadId":"15148","inReplyTo":"48BF0FBF.3010104@lsrfire.ath.cx","subject":"[PATCH 2/5] Always initialize xpparam_t to 0","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-10-25T13:30:37Z","receivedAt":"2008-10-25T13:30:37Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"From: Brian Downing <bdowning@lavos.net>\n\nWe're going to be adding some parameters to this, so we can't have\nany uninitialized data in it.\n\nSigned-off-by: Brian Downing <bdowning@lavos.net>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\nTaken from pu.  This patch series doesn't add anything to the struct,\nbut it's a good idea to future-proof its initialization anyway.\n\n builtin-blame.c  |    1 +\n builtin-rerere.c |    1 +\n combine-diff.c   |    1 +\n diff.c           |    5 +++++\n merge-file.c     |    1 +\n 5 files changed, 9 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex 593b539..5ca7065 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -523,6 +523,7 @@ static struct patch *compare_buffer(mmfile_t\n*file_p, mmfile_t *file_o,\n \txdemitconf_t xecfg;\n \txdemitcb_t ecb;\n\n+\tmemset(&xpp, 0, sizeof(xpp));\n \txpp.flags = xdl_opts;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \txecfg.ctxlen = context;\ndiff --git a/builtin-rerere.c b/builtin-rerere.c\nindex dd4573f..d4dec6b 100644\n--- a/builtin-rerere.c\n+++ b/builtin-rerere.c\n@@ -98,6 +98,7 @@ static int diff_two(const char *file1, const char *label1,\n\n \tprintf(\"--- a/%s\\n+++ b/%s\\n\", label1, label2);\n \tfflush(stdout);\n+\tmemset(&xpp, 0, sizeof(xpp));\n \txpp.flags = XDF_NEED_MINIMAL;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \txecfg.ctxlen = 3;\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 5aa1104..ec8df39 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -213,6 +213,7 @@ static void combine_diff(const unsigned char\n*parent, mmfile_t *result_file,\n\n \tparent_file.ptr = grab_blob(parent, &sz);\n \tparent_file.size = sz;\n+\tmemset(&xpp, 0, sizeof(xpp));\n \txpp.flags = XDF_NEED_MINIMAL;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \tmemset(&state, 0, sizeof(state));\ndiff --git a/diff.c b/diff.c\nindex e368fef..1918b73 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -400,6 +400,7 @@ static void diff_words_show(struct diff_words_data\n*diff_words)\n \tmmfile_t minus, plus;\n \tint i;\n\n+\tmemset(&xpp, 0, sizeof(xpp));\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \tminus.size = diff_words->minus.text.size;\n \tminus.ptr = xmalloc(minus.size);\n@@ -1416,6 +1417,7 @@ static void builtin_diff(const char *name_a,\n \t\tif (!pe)\n \t\t\tpe = diff_funcname_pattern(two);\n\n+\t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\tmemset(&ecbdata, 0, sizeof(ecbdata));\n \t\tecbdata.label_path = lbl;\n@@ -1489,6 +1491,7 @@ static void builtin_diffstat(const char *name_a,\nconst char *name_b,\n \t\txdemitconf_t xecfg;\n \t\txdemitcb_t ecb;\n\n+\t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\txpp.flags = XDF_NEED_MINIMAL | o->xdl_opts;\n \t\txdi_diff_outf(&mf1, &mf2, diffstat_consume, diffstat,\n@@ -1535,6 +1538,7 @@ static void builtin_checkdiff(const char *name_a,\nconst char *name_b,\n \t\txdemitconf_t xecfg;\n \t\txdemitcb_t ecb;\n\n+\t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\txecfg.ctxlen = 1; /* at least one context line */\n \t\txpp.flags = XDF_NEED_MINIMAL;\n@@ -2958,6 +2962,7 @@ static int diff_get_patch_id(struct diff_options\n*options, unsigned char *sha1)\n \t\tstruct diff_filepair *p = q->queue[i];\n \t\tint len1, len2;\n\n+\t\tmemset(&xpp, 0, sizeof(xpp));\n \t\tmemset(&xecfg, 0, sizeof(xecfg));\n \t\tif (p->status == 0)\n \t\t\treturn error(\"internal diff status error\");\ndiff --git a/merge-file.c b/merge-file.c\nindex 2a939c9..3120a95 100644\n--- a/merge-file.c\n+++ b/merge-file.c\n@@ -61,6 +61,7 @@ static int generate_common_file(mmfile_t *res,\nmmfile_t *f1, mmfile_t *f2)\n \txdemitconf_t xecfg;\n \txdemitcb_t ecb;\n\n+\tmemset(&xpp, 0, sizeof(xpp));\n \txpp.flags = XDF_NEED_MINIMAL;\n \tmemset(&xecfg, 0, sizeof(xecfg));\n \txecfg.ctxlen = 3;\n-- \n1.6.0.3.514.g2f91b\n"},{"id":"93925","messageId":"49031F8E.8000203@lsrfire.ath.cx","threadId":"15148","inReplyTo":"48BF0FBF.3010104@lsrfire.ath.cx","subject":"[PATCH 3/5] Allow alternate \"low-level\" emit function from xdl_diff","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-10-25T13:30:54Z","receivedAt":"2008-10-25T13:30:54Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"From: Brian Downing <bdowning@lavos.net>\n\nFor some users (e.g. git blame), getting textual patch output is just\nextra work, as they can get all the information they need from the low-\nlevel diff structures.  Allow for an alternate low-level emit function\nto be defined to allow bypassing the textual patch generation; set\nxemitconf_t's emit_func member to enable this.\n\nThe (void (*)()) type is pretty ugly, but the alternative would be to\ninclude most of the private xdiff headers in xdiff.h to get the types\nrequired for the \"proper\" function prototype.  Also, a (void *) won't\nwork, as ANSI C doesn't allow a function pointer to be cast to an\nobject pointer.\n\nSigned-off-by: Brian Downing <bdowning@lavos.net>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\nTaken from pu.\n\n xdiff/xdiff.h  |    1 +\n xdiff/xdiffi.c |    4 +++-\n xdiff/xemit.c  |    3 +--\n xdiff/xemit.h  |    3 +++\n 4 files changed, 8 insertions(+), 3 deletions(-)\n\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex deebe02..84fff58 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -87,6 +87,7 @@ typedef struct s_xdemitconf {\n \tunsigned long flags;\n \tfind_func_t find_func;\n \tvoid *find_func_priv;\n+\tvoid (*emit_func)();\n } xdemitconf_t;\n \n typedef struct s_bdiffparam {\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex 1bad846..9d0324a 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -538,6 +538,8 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t     xdemitconf_t const *xecfg, xdemitcb_t *ecb) {\n \txdchange_t *xscr;\n \txdfenv_t xe;\n+\temit_func_t ef = xecfg->emit_func ?\n+\t\t(emit_func_t)xecfg->emit_func : xdl_emit_diff;\n \n \tif (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) {\n \n@@ -551,7 +553,7 @@ int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\treturn -1;\n \t}\n \tif (xscr) {\n-\t\tif (xdl_emit_diff(&xe, xscr, ecb, xecfg) < 0) {\n+\t\tif (ef(&xe, xscr, ecb, xecfg) < 0) {\n \n \t\t\txdl_free_script(xscr);\n \t\t\txdl_free_env(&xe);\ndiff --git a/xdiff/xemit.c b/xdiff/xemit.c\nindex d3d9c84..4625c1b 100644\n--- a/xdiff/xemit.c\n+++ b/xdiff/xemit.c\n@@ -27,7 +27,6 @@\n \n static long xdl_get_rec(xdfile_t *xdf, long ri, char const **rec);\n static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *ecb);\n-static xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg);\n \n \n \n@@ -58,7 +57,7 @@ static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *\n  * Starting at the passed change atom, find the latest change atom to be included\n  * inside the differential hunk according to the specified configuration.\n  */\n-static xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg) {\n+xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg) {\n \txdchange_t *xch, *xchp;\n \n \tfor (xchp = xscr, xch = xscr->next; xch; xchp = xch, xch = xch->next)\ndiff --git a/xdiff/xemit.h b/xdiff/xemit.h\nindex 440a739..c2e2e83 100644\n--- a/xdiff/xemit.h\n+++ b/xdiff/xemit.h\n@@ -24,7 +24,10 @@\n #define XEMIT_H\n \n \n+typedef int (*emit_func_t)(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n+\t\t\t   xdemitconf_t const *xecfg);\n \n+xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg);\n int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t  xdemitconf_t const *xecfg);\n \n-- \n1.6.0.3.514.g2f91b\n"},{"id":"93927","messageId":"49031FA3.3050803@lsrfire.ath.cx","threadId":"15148","inReplyTo":"48BF0FBF.3010104@lsrfire.ath.cx","subject":"[PATCH 4/5] add xdi_diff_hunks() for callers that only need hunk lengths","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-10-25T13:31:15Z","receivedAt":"2008-10-25T13:31:15Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Based on a patch by Brian Downing, this uses the xdiff emit_func feature\nto implement xdi_diff_hunks().  It's a function that calls a callback for\neach hunk of a diff, passing its lengths.\n\nSigned-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n---\n xdiff-interface.c |   49 ++++++++++++++++++++++++++++++++++++++++++++++++-\n xdiff-interface.h |    4 ++++\n 2 files changed, 52 insertions(+), 1 deletions(-)\n\ndiff --git a/xdiff-interface.c b/xdiff-interface.c\nindex 49e06af..e8ef46d 100644\n--- a/xdiff-interface.c\n+++ b/xdiff-interface.c\n@@ -1,6 +1,9 @@\n #include \"cache.h\"\n #include \"xdiff-interface.h\"\n-#include \"strbuf.h\"\n+#include \"xdiff/xtypes.h\"\n+#include \"xdiff/xdiffi.h\"\n+#include \"xdiff/xemit.h\"\n+#include \"xdiff/xmacros.h\"\n \n struct xdiff_emit_state {\n \txdiff_emit_consume_fn consume;\n@@ -153,6 +156,50 @@ int xdi_diff_outf(mmfile_t *mf1, mmfile_t *mf2,\n \treturn ret;\n }\n \n+struct xdiff_emit_hunk_state {\n+\txdiff_emit_hunk_consume_fn consume;\n+\tvoid *consume_callback_data;\n+};\n+\n+static int process_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n+\t\t\txdemitconf_t const *xecfg)\n+{\n+\tlong s1, s2, same, p_next, t_next;\n+\txdchange_t *xch, *xche;\n+\tstruct xdiff_emit_hunk_state *state = ecb->priv;\n+\txdiff_emit_hunk_consume_fn fn = state->consume;\n+\tvoid *consume_callback_data = state->consume_callback_data;\n+\n+\tfor (xch = xscr; xch; xch = xche->next) {\n+\t\txche = xdl_get_hunk(xch, xecfg);\n+\n+\t\ts1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);\n+\t\ts2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0);\n+\t\tsame = s2 + XDL_MAX(xch->i1 - s1, 0);\n+\t\tp_next = xche->i1 + xche->chg1;\n+\t\tt_next = xche->i2 + xche->chg2;\n+\n+\t\tfn(consume_callback_data, same, p_next, t_next);\n+\t}\n+\treturn 0;\n+}\n+\n+int xdi_diff_hunks(mmfile_t *mf1, mmfile_t *mf2,\n+\t\t   xdiff_emit_hunk_consume_fn fn, void *consume_callback_data,\n+\t\t   xpparam_t const *xpp, xdemitconf_t *xecfg)\n+{\n+\tstruct xdiff_emit_hunk_state state;\n+\txdemitcb_t ecb;\n+\n+\tmemset(&state, 0, sizeof(state));\n+\tmemset(&ecb, 0, sizeof(ecb));\n+\tstate.consume = fn;\n+\tstate.consume_callback_data = consume_callback_data;\n+\txecfg->emit_func = (void (*)())process_diff;\n+\tecb.priv = &state;\n+\treturn xdi_diff(mf1, mf2, xpp, xecfg, &ecb);\n+}\n+\n int read_mmfile(mmfile_t *ptr, const char *filename)\n {\n \tstruct stat st;\ndiff --git a/xdiff-interface.h b/xdiff-interface.h\nindex eaf9cd3..7352b9a 100644\n--- a/xdiff-interface.h\n+++ b/xdiff-interface.h\n@@ -4,12 +4,16 @@\n #include \"xdiff/xdiff.h\"\n \n typedef void (*xdiff_emit_consume_fn)(void *, char *, unsigned long);\n+typedef void (*xdiff_emit_hunk_consume_fn)(void *, long, long, long);\n \n int xdi_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdemitconf_t const *xecfg, xdemitcb_t *ecb);\n int xdi_diff_outf(mmfile_t *mf1, mmfile_t *mf2,\n \t\t  xdiff_emit_consume_fn fn, void *consume_callback_data,\n \t\t  xpparam_t const *xpp,\n \t\t  xdemitconf_t const *xecfg, xdemitcb_t *xecb);\n+int xdi_diff_hunks(mmfile_t *mf1, mmfile_t *mf2,\n+\t\t   xdiff_emit_hunk_consume_fn fn, void *consume_callback_data,\n+\t\t   xpparam_t const *xpp, xdemitconf_t *xecfg);\n int parse_hunk_header(char *line, int len,\n \t\t      int *ob, int *on,\n \t\t      int *nb, int *nn);\n-- \n1.6.0.3.514.g2f91b\n"},{"id":"93928","messageId":"49031FB8.8060003@lsrfire.ath.cx","threadId":"15148","inReplyTo":"48BF0FBF.3010104@lsrfire.ath.cx","subject":"[PATCH 5/5] blame: use xdi_diff_hunks(), get rid of struct patch","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-10-25T13:31:36Z","receivedAt":"2008-10-25T13:31:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Based on a patch by Brian Downing, this replaces the struct patch based\ncode for blame passing with calls to xdi_diff_hunks().  This way we\navoid generating and then parsing patches; we only let the interesting\ninfos be passed to our callbacks instead.  This makes blame a bit faster:\n\n   $ blame=\"./git blame -M -C -C -p --incremental v1.6.0\"\n\n   # master\n   $ /usr/bin/time $blame Makefile >/dev/null\n   1.38user 0.14system 0:01.52elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (0major+12226minor)pagefaults 0swaps\n   $ /usr/bin/time $blame cache.h >/dev/null\n   1.66user 0.13system 0:01.80elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (0major+12262minor)pagefaults 0swaps\n\n   # this patch series\n   $ /usr/bin/time $blame Makefile >/dev/null\n   1.27user 0.12system 0:01.40elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (0major+11836minor)pagefaults 0swaps\n   $ /usr/bin/time $blame cache.h >/dev/null\n   1.52user 0.12system 0:01.70elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (0major+12052minor)pagefaults 0swaps\n\nSigned-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n---\nBrian, your numbers looked much more impressive.  Could you please clock\nthis code with your repository and the file server.c?  I wonder if this\ncallback mechanism is just too complicated or if your case simply benefits\nlots more than the two files from git mentioned above.\n\nThe patch series ends here without adding xdiff caching, for two reasons.\nIt's quite easy to add it; patch 4 from your series applies unchanged and\npatch 5 is just needs a few small changes to account for the absence of\ncompare_buffer().  More importantly, speed actually went down with caching\nfor the test case.  The common tail optimization (xdi_diff() vs. xdl_diff())\nseems to beat caching for cache.h and Makefile..\n\n builtin-blame.c |  191 +++++++++++++++----------------------------------------\n 1 files changed, 52 insertions(+), 139 deletions(-)\n\ndiff --git a/builtin-blame.c b/builtin-blame.c\nindex 5ca7065..b6bc5cf 100644\n--- a/builtin-blame.c\n+++ b/builtin-blame.c\n@@ -443,113 +443,6 @@ static struct origin *find_rename(struct scoreboard *sb,\n }\n \n /*\n- * Parsing of patch chunks...\n- */\n-struct chunk {\n-\t/* line number in postimage; up to but not including this\n-\t * line is the same as preimage\n-\t */\n-\tint same;\n-\n-\t/* preimage line number after this chunk */\n-\tint p_next;\n-\n-\t/* postimage line number after this chunk */\n-\tint t_next;\n-};\n-\n-struct patch {\n-\tstruct chunk *chunks;\n-\tint num;\n-};\n-\n-struct blame_diff_state {\n-\tstruct patch *ret;\n-\tunsigned hunk_post_context;\n-\tunsigned hunk_in_pre_context : 1;\n-};\n-\n-static void process_u_diff(void *state_, char *line, unsigned long len)\n-{\n-\tstruct blame_diff_state *state = state_;\n-\tstruct chunk *chunk;\n-\tint off1, off2, len1, len2, num;\n-\n-\tnum = state->ret->num;\n-\tif (len < 4 || line[0] != '@' || line[1] != '@') {\n-\t\tif (state->hunk_in_pre_context && line[0] == ' ')\n-\t\t\tstate->ret->chunks[num - 1].same++;\n-\t\telse {\n-\t\t\tstate->hunk_in_pre_context = 0;\n-\t\t\tif (line[0] == ' ')\n-\t\t\t\tstate->hunk_post_context++;\n-\t\t\telse\n-\t\t\t\tstate->hunk_post_context = 0;\n-\t\t}\n-\t\treturn;\n-\t}\n-\n-\tif (num && state->hunk_post_context) {\n-\t\tchunk = &state->ret->chunks[num - 1];\n-\t\tchunk->p_next -= state->hunk_post_context;\n-\t\tchunk->t_next -= state->hunk_post_context;\n-\t}\n-\tstate->ret->num = ++num;\n-\tstate->ret->chunks = xrealloc(state->ret->chunks,\n-\t\t\t\t      sizeof(struct chunk) * num);\n-\tchunk = &state->ret->chunks[num - 1];\n-\tif (parse_hunk_header(line, len, &off1, &len1, &off2, &len2)) {\n-\t\tstate->ret->num--;\n-\t\treturn;\n-\t}\n-\n-\t/* Line numbers in patch output are one based. */\n-\toff1--;\n-\toff2--;\n-\n-\tchunk->same = len2 ? off2 : (off2 + 1);\n-\n-\tchunk->p_next = off1 + (len1 ? len1 : 1);\n-\tchunk->t_next = chunk->same + len2;\n-\tstate->hunk_in_pre_context = 1;\n-\tstate->hunk_post_context = 0;\n-}\n-\n-static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,\n-\t\t\t\t    int context)\n-{\n-\tstruct blame_diff_state state;\n-\txpparam_t xpp;\n-\txdemitconf_t xecfg;\n-\txdemitcb_t ecb;\n-\n-\tmemset(&xpp, 0, sizeof(xpp));\n-\txpp.flags = xdl_opts;\n-\tmemset(&xecfg, 0, sizeof(xecfg));\n-\txecfg.ctxlen = context;\n-\tmemset(&state, 0, sizeof(state));\n-\tstate.ret = xmalloc(sizeof(struct patch));\n-\tstate.ret->chunks = NULL;\n-\tstate.ret->num = 0;\n-\n-\txdi_diff_outf(file_p, file_o, process_u_diff, &state, &xpp, &xecfg, &ecb);\n-\n-\tif (state.ret->num) {\n-\t\tstruct chunk *chunk;\n-\t\tchunk = &state.ret->chunks[state.ret->num - 1];\n-\t\tchunk->p_next -= state.hunk_post_context;\n-\t\tchunk->t_next -= state.hunk_post_context;\n-\t}\n-\treturn state.ret;\n-}\n-\n-static void free_patch(struct patch *p)\n-{\n-\tfree(p->chunks);\n-\tfree(p);\n-}\n-\n-/*\n  * Link in a new blame entry to the scoreboard.  Entries that cover the\n  * same line range have been removed from the scoreboard previously.\n  */\n@@ -795,6 +688,22 @@ static void blame_chunk(struct scoreboard *sb,\n \t}\n }\n \n+struct blame_chunk_cb_data {\n+\tstruct scoreboard *sb;\n+\tstruct origin *target;\n+\tstruct origin *parent;\n+\tlong plno;\n+\tlong tlno;\n+};\n+\n+static void blame_chunk_cb(void *data, long same, long p_next, long t_next)\n+{\n+\tstruct blame_chunk_cb_data *d = data;\n+\tblame_chunk(d->sb, d->tlno, d->plno, same, d->target, d->parent);\n+\td->plno = p_next;\n+\td->tlno = t_next;\n+}\n+\n /*\n  * We are looking at the origin 'target' and aiming to pass blame\n  * for the lines it is suspected to its parent.  Run diff to find\n@@ -804,36 +713,28 @@ static int pass_blame_to_parent(struct scoreboard *sb,\n \t\t\t\tstruct origin *target,\n \t\t\t\tstruct origin *parent)\n {\n-\tint i, last_in_target, plno, tlno;\n-\tstruct patch *patch;\n+\tint last_in_target;\n \tmmfile_t file_p, file_o;\n+\tstruct blame_chunk_cb_data d = { sb, target, parent, 0, 0 };\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n \n \tlast_in_target = find_last_in_target(sb, target);\n \tif (last_in_target < 0)\n \t\treturn 1; /* nothing remains for this target */\n \n-\t/*\n-\t * Run diff between two origins and grab the patch output, so that\n-\t * we can pass blame for lines origin is currently suspected for\n-\t * to its parent.\n-\t */\n \tfill_origin_blob(parent, &file_p);\n \tfill_origin_blob(target, &file_o);\n-\tpatch = compare_buffer(&file_p, &file_o, 0);\n \tnum_get_patch++;\n \n-\tplno = tlno = 0;\n-\tfor (i = 0; i < patch->num; i++) {\n-\t\tstruct chunk *chunk = &patch->chunks[i];\n-\n-\t\tblame_chunk(sb, tlno, plno, chunk->same, target, parent);\n-\t\tplno = chunk->p_next;\n-\t\ttlno = chunk->t_next;\n-\t}\n+\tmemset(&xpp, 0, sizeof(xpp));\n+\txpp.flags = xdl_opts;\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\txecfg.ctxlen = 0;\n+\txdi_diff_hunks(&file_p, &file_o, blame_chunk_cb, &d, &xpp, &xecfg);\n \t/* The rest (i.e. anything after tlno) are the same as the parent */\n-\tblame_chunk(sb, tlno, plno, last_in_target, target, parent);\n+\tblame_chunk(sb, d.tlno, d.plno, last_in_target, target, parent);\n \n-\tfree_patch(patch);\n \treturn 0;\n }\n \n@@ -925,6 +826,23 @@ static void handle_split(struct scoreboard *sb,\n \t}\n }\n \n+struct handle_split_cb_data {\n+\tstruct scoreboard *sb;\n+\tstruct blame_entry *ent;\n+\tstruct origin *parent;\n+\tstruct blame_entry *split;\n+\tlong plno;\n+\tlong tlno;\n+};\n+\n+static void handle_split_cb(void *data, long same, long p_next, long t_next)\n+{\n+\tstruct handle_split_cb_data *d = data;\n+\thandle_split(d->sb, d->ent, d->tlno, d->plno, same, d->parent, d->split);\n+\td->plno = p_next;\n+\td->tlno = t_next;\n+}\n+\n /*\n  * Find the lines from parent that are the same as ent so that\n  * we can pass blames to it.  file_p has the blob contents for\n@@ -939,8 +857,9 @@ static void find_copy_in_blob(struct scoreboard *sb,\n \tconst char *cp;\n \tint cnt;\n \tmmfile_t file_o;\n-\tstruct patch *patch;\n-\tint i, plno, tlno;\n+\tstruct handle_split_cb_data d = { sb, ent, parent, split, 0, 0 };\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n \n \t/*\n \t * Prepare mmfile that contains only the lines in ent.\n@@ -955,24 +874,18 @@ static void find_copy_in_blob(struct scoreboard *sb,\n \t}\n \tfile_o.size = cp - file_o.ptr;\n \n-\tpatch = compare_buffer(file_p, &file_o, 1);\n-\n \t/*\n \t * file_o is a part of final image we are annotating.\n \t * file_p partially may match that image.\n \t */\n+\tmemset(&xpp, 0, sizeof(xpp));\n+\txpp.flags = xdl_opts;\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\txecfg.ctxlen = 1;\n \tmemset(split, 0, sizeof(struct blame_entry [3]));\n-\tplno = tlno = 0;\n-\tfor (i = 0; i < patch->num; i++) {\n-\t\tstruct chunk *chunk = &patch->chunks[i];\n-\n-\t\thandle_split(sb, ent, tlno, plno, chunk->same, parent, split);\n-\t\tplno = chunk->p_next;\n-\t\ttlno = chunk->t_next;\n-\t}\n+\txdi_diff_hunks(file_p, &file_o, handle_split_cb, &d, &xpp, &xecfg);\n \t/* remainder, if any, all match the preimage */\n-\thandle_split(sb, ent, tlno, plno, ent->num_lines, parent, split);\n-\tfree_patch(patch);\n+\thandle_split(sb, ent, d.tlno, d.plno, ent->num_lines, parent, split);\n }\n \n /*\n-- \n1.6.0.3.514.g2f91b\n"},{"id":"93939","messageId":"7vhc708o1v.fsf@gitster.siamese.dyndns.org","threadId":"15148","inReplyTo":"49031FB8.8060003@lsrfire.ath.cx","subject":"Re: [PATCH 5/5] blame: use xdi_diff_hunks(), get rid of struct patch","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-10-25T19:36:28Z","receivedAt":"2008-10-25T19:36:28Z","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> Based on a patch by Brian Downing, this replaces the struct patch based\n> code for blame passing with calls to xdi_diff_hunks().  This way we\n> avoid generating and then parsing patches; we only let the interesting\n> infos be passed to our callbacks instead.  This makes blame a bit faster:\n>\n>    $ blame=\"./git blame -M -C -C -p --incremental v1.6.0\"\n>\n>    # master\n>    $ /usr/bin/time $blame Makefile >/dev/null\n>    1.38user 0.14system 0:01.52elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n>    0inputs+0outputs (0major+12226minor)pagefaults 0swaps\n>    $ /usr/bin/time $blame cache.h >/dev/null\n>    1.66user 0.13system 0:01.80elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n>    0inputs+0outputs (0major+12262minor)pagefaults 0swaps\n>\n>    # this patch series\n>    $ /usr/bin/time $blame Makefile >/dev/null\n>    1.27user 0.12system 0:01.40elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n>    0inputs+0outputs (0major+11836minor)pagefaults 0swaps\n>    $ /usr/bin/time $blame cache.h >/dev/null\n>    1.52user 0.12system 0:01.70elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k\n>    0inputs+0outputs (0major+12052minor)pagefaults 0swaps\n>\n> Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n\nThe resulting series reads quite clean.  I like it.\n\n> Brian, your numbers looked much more impressive.  Could you please clock\n> this code with your repository and the file server.c?  I wonder if this\n> callback mechanism is just too complicated or if your case simply benefits\n> lots more than the two files from git mentioned above.\n>\n> The patch series ends here without adding xdiff caching, for two reasons.\n> It's quite easy to add it; patch 4 from your series applies unchanged and\n> patch 5 is just needs a few small changes to account for the absence of\n> compare_buffer().  More importantly, speed actually went down with caching\n> for the test case.  The common tail optimization (xdi_diff() vs. xdl_diff())\n> seems to beat caching for cache.h and Makefile..\n\nPerhaps revision.c in our history would be more interesting than cache.h\nor Makefile, as there are more line migrations from different places to\nthat file.\n"},{"id":"94006","messageId":"4904ED18.3070500@lsrfire.ath.cx","threadId":"15148","inReplyTo":"7vhc708o1v.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 5/5] blame: use xdi_diff_hunks(), get rid of struct patch","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2008-10-26T22:20:08Z","receivedAt":"2008-10-26T22:20:08Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Junio C Hamano schrieb:\n> Perhaps revision.c in our history would be more interesting than cache.h\n> or Makefile, as there are more line migrations from different places to\n> that file.\n\nIndeed:\n\n   # master\n   $ /usr/bin/time $blame revision.c >/dev/null\n   2.15user 0.27system 0:02.58elapsed 94%CPU (0avgtext+0avgdata 0maxresident)k\n   3544inputs+0outputs (29major+13835minor)pagefaults 0swaps\n\n   # this patch series\n   $ /usr/bin/time $blame revision.c >/dev/null\n   1.88user 0.14system 0:02.03elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (0major+14068minor)pagefaults 0swaps\n\nRené\n"}]}