{"thread":{"id":"27792","subject":"[RFC/PATCH 0/3] teach --histogram to diff","startedAt":"2011-07-12T06:10:24Z","lastAt":"2011-08-01T04:20:10Z","messageCount":24,"participants":["Tay Ray Chuan","Shawn Pearce","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"171130","messageId":"1310451027-15148-1-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":null,"subject":"[RFC/PATCH 0/3] teach --histogram to diff","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-07-12T06:10:24Z","receivedAt":"2011-07-12T06:10:24Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"(Shawn, I was held up with the patch messages, sorry for the delay.)\n\nPort JGit's HistogramDiff(Index) over to C. This algorithm extends the\npatience algorithm to \"support low-occurrence common elements\" [1].\n\nRough numbers show that it is a faster alternative to its --patience\ncousin, as well as to the default Meyers algorithm:\n\n $ time ./git log --histogram -p v1.0.0 >/dev/null\n \n real 0m12.998s\n user 0m11.506s\n sys 0m1.487s\n $ time ./git log -p v1.0.0 >/dev/null\n \n real 0m13.575s\n user 0m12.101s\n sys 0m1.468s\n $ time ./git log --patience -p v1.0.0 >/dev/null\n \n real 0m14.978s\n user 0m13.508s\n sys 0m1.464s\n\nThe first patch implements JGit's HistogramDiff(Index) proper. The\nsecond and third patches aren't essential but yield performance gains.\n\nNote: these patches must be applied on top of rc/histogram-diff in pu.\n\nContents:\n[RFC/PATCH 1/3] teach --histogram to diff\n[RFC/PATCH 2/3] xdiff/xprepare: skip classification\n[RFC/PATCH 3/3] xdiff/xprepare: use a smaller sample size for histogram\n\n Makefile | 2 +-\n diff.c | 2 +\n merge-recursive.c | 2 +\n t/t4048-diff-histogram.sh | 12 ++\n xdiff/xdiff.h | 1 +\n xdiff/xdiffi.c | 3 +\n xdiff/xdiffi.h | 2 +\n xdiff/xhistogram.c | 384 +++++++++++++++++++++++++++++++++++++++++++++\n xdiff/xprepare.c | 41 ++++--\n xdiff/xutils.c | 8 +-\n xdiff/xutils.h | 2 +-\n 11 files changed, 440 insertions(+), 19 deletions(-)\n create mode 100755 t/t4048-diff-histogram.sh\n create mode 100644 xdiff/xhistogram.c\n\n--\nFootnotes:\n[1] http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java;hb=HEAD\n\n-- \n1.7.3.4.681.gb718e\n"},{"id":"171133","messageId":"1310451027-15148-2-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1310451027-15148-1-git-send-email-rctay89@gmail.com","subject":"[RFC/PATCH 1/3] teach --histogram to diff","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-07-12T06:10:25Z","receivedAt":"2011-07-12T06:10:25Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Port JGit's HistogramDiff algorithm over to C. Rough numbers (TODO) show\nthat it is faster than its --patience cousin, as well as the default\nMeyers algorithm.\n\nThe implementation has been reworked to use structs and pointers,\ninstead of bitmasks, thus doing away with JGit's 2^28 line limit.\n\nWe also use xdiff's default hash table implementation (xdl_hash_bits()\nwith XDL_HASHLONG()) for convenience.\n\nSigned-off-by: Tay Ray Chuan \n---\n Makefile | 2 +-\n diff.c | 2 +\n merge-recursive.c | 2 +\n t/t4048-diff-histogram.sh | 12 ++\n xdiff/xdiff.h | 1 +\n xdiff/xdiffi.c | 3 +\n xdiff/xdiffi.h | 2 +\n xdiff/xhistogram.c | 384 +++++++++++++++++++++++++++++++++++++++++++++\n 8 files changed, 407 insertions(+), 1 deletions(-)\n create mode 100755 t/t4048-diff-histogram.sh\n create mode 100644 xdiff/xhistogram.c\n\ndiff --git a/Makefile b/Makefile\nindex 775ee83..9930e6b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1836,7 +1836,7 @@ ifndef NO_CURL\n \tGIT_OBJS += http.o http-walker.o remote-curl.o\n endif\n XDIFF_OBJS = xdiff/xdiffi.o xdiff/xprepare.o xdiff/xutils.o xdiff/xemit.o \\\n-\txdiff/xmerge.o xdiff/xpatience.o\n+\txdiff/xmerge.o xdiff/xpatience.o xdiff/xhistogram.o\n VCSSVN_OBJS = vcs-svn/string_pool.o vcs-svn/line_buffer.o \\\n \tvcs-svn/repo_tree.o vcs-svn/fast_export.o vcs-svn/svndump.o\n VCSSVN_TEST_OBJS = test-obj-pool.o test-string-pool.o \\\ndiff --git a/diff.c b/diff.c\nindex 5422c43..a113294 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3186,6 +3186,8 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\tDIFF_XDL_SET(options, IGNORE_WHITESPACE_AT_EOL);\n \telse if (!strcmp(arg, \"--patience\"))\n \t\tDIFF_XDL_SET(options, PATIENCE_DIFF);\n+\telse if (!strcmp(arg, \"--histogram\"))\n+\t\tDIFF_XDL_SET(options, HISTOGRAM_DIFF);\n \n \t/* flags options */\n \telse if (!strcmp(arg, \"--binary\")) {\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 16c2dbe..3e8267b 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -1773,6 +1773,8 @@ int parse_merge_opt(struct merge_options *o, const char *s)\n \t\to->subtree_shift = s + strlen(\"subtree=\");\n \telse if (!strcmp(s, \"patience\"))\n \t\to->xdl_opts |= XDF_PATIENCE_DIFF;\n+\telse if (!strcmp(s, \"histogram\"))\n+\t\to->xdl_opts |= XDF_HISTOGRAM_DIFF;\n \telse if (!strcmp(s, \"ignore-space-change\"))\n \t\to->xdl_opts |= XDF_IGNORE_WHITESPACE_CHANGE;\n \telse if (!strcmp(s, \"ignore-all-space\"))\ndiff --git a/t/t4048-diff-histogram.sh b/t/t4048-diff-histogram.sh\nnew file mode 100755\nindex 0000000..fd3e86a\n--- /dev/null\n+++ b/t/t4048-diff-histogram.sh\n@@ -0,0 +1,12 @@\n+#!/bin/sh\n+\n+test_description='histogram diff algorithm'\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-diff-alternative.sh\n+\n+test_diff_frobnitz \"histogram\"\n+\n+test_diff_unique \"histogram\"\n+\n+test_done\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 711048e..c26170c 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -33,6 +33,7 @@ extern \"C\" {\n #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)\n #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4)\n #define XDF_PATIENCE_DIFF (1 << 5)\n+#define XDF_HISTOGRAM_DIFF (1 << 6)\n #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)\n \n #define XDL_PATCH_NORMAL '-'\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex da67c04..75a3922 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -331,6 +331,9 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \tif (xpp->flags & XDF_PATIENCE_DIFF)\n \t\treturn xdl_do_patience_diff(mf1, mf2, xpp, xe);\n \n+\tif (xpp->flags & XDF_HISTOGRAM_DIFF)\n+\t\treturn xdl_do_histogram_diff(mf1, mf2, xpp, xe);\n+\n \tif (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {\n \n \t\treturn -1;\ndiff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h\nindex ad033a8..7a92ea9 100644\n--- a/xdiff/xdiffi.h\n+++ b/xdiff/xdiffi.h\n@@ -57,5 +57,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t xdemitconf_t const *xecfg);\n int xdl_do_patience_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\txdfenv_t *env);\n+int xdl_do_histogram_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t\txdfenv_t *env);\n \n #endif /* #if !defined(XDIFFI_H) */\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nnew file mode 100644\nindex 0000000..391333a\n--- /dev/null\n+++ b/xdiff/xhistogram.c\n@@ -0,0 +1,384 @@\n+/*\n+ * Copyright (C) 2010, Google Inc.\n+ * and other copyright owners as documented in JGit's IP log.\n+ *\n+ * This program and the accompanying materials are made available\n+ * under the terms of the Eclipse Distribution License v1.0 which\n+ * accompanies this distribution, is reproduced below, and is\n+ * available at http://www.eclipse.org/org/documents/edl-v10.php\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Eclipse Foundation, Inc. nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+#include \"xinclude.h\"\n+#include \"xtypes.h\"\n+#include \"xdiff.h\"\n+\n+#define MAX_PTR\tUINT_MAX\n+#define MAX_CNT\tUINT_MAX\n+\n+#define LINE_END(n) (line##n + count##n - 1)\n+#define LINE_END_PTR(n) (*line##n + *count##n - 1)\n+\n+struct histindex {\n+\tstruct record {\n+\t\tunsigned int ptr, cnt;\n+\t\tstruct record *next;\n+\t} **records, /* an ocurrence */\n+\t **line_map; /* map of line to record chain */\n+\tchastore_t rcha;\n+\tunsigned int *next_ptrs;\n+\tunsigned int table_bits,\n+\t\t records_size,\n+\t\t line_map_size;\n+\n+\tunsigned int max_chain_length,\n+\t\t key_shift,\n+\t\t ptr_shift;\n+\n+\tunsigned int cnt,\n+\t\t has_common;\n+\n+\txdfenv_t *env;\n+\txpparam_t const *xpp;\n+};\n+\n+struct region {\n+\tunsigned int begin1, end1;\n+\tunsigned int begin2, end2;\n+};\n+\n+#define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift])\n+\n+#define NEXT_PTR(index, ptr) \\\n+\t(index->next_ptrs[(ptr) - index->ptr_shift])\n+\n+#define CNT(index, ptr) \\\n+\t((LINE_MAP(index, ptr))->cnt)\n+\n+#define REC(env, s, l) \\\n+\t(env->xdf##s.recs[l - 1])\n+\n+static int cmp_recs(xpparam_t const *xpp,\n+\txrecord_t *r1, xrecord_t *r2)\n+{\n+\treturn r1->ha == r2->ha &&\n+\t\txdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,\n+\t\t\t xpp->flags);\n+}\n+\n+#define CMP_ENV(xpp, env, s1, l1, s2, l2) \\\n+\t(cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2)))\n+\n+#define CMP(i, s1, l1, s2, l2) \\\n+\t(CMP_ENV(i->xpp, i->env, s1, l1, s2, l2))\n+\n+#define TABLE_HASH(index, side, line) \\\n+\tXDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)\n+\n+static int scanA(struct histindex *index, int line1, int count1)\n+{\n+\tunsigned int ptr, tbl_idx;\n+\tunsigned int chain_len;\n+\tstruct record **rec_chain, *rec;\n+\n+\tfor (ptr = LINE_END(1); line1 <= ptr; ptr--) {\n+\t\ttbl_idx = TABLE_HASH(index, 1, ptr);\n+\t\trec_chain = index->records + tbl_idx;\n+\t\trec = *rec_chain;\n+\n+\t\tchain_len = 0;\n+\t\twhile (rec) {\n+\t\t\tif (CMP(index, 1, rec->ptr, 1, ptr)) {\n+\t\t\t\t/*\n+\t\t\t\t * ptr is identical to another element. Insert\n+\t\t\t\t * it onto the front of the existing element\n+\t\t\t\t * chain.\n+\t\t\t\t */\n+\t\t\t\tNEXT_PTR(index, ptr) = rec->ptr;\n+\t\t\t\trec->ptr = ptr;\n+\t\t\t\t/* cap rec->cnt at MAX_CNT */\n+\t\t\t\trec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1);\n+\t\t\t\tLINE_MAP(index, ptr) = rec;\n+\t\t\t\tgoto continue_scan;\n+\t\t\t}\n+\n+\t\t\trec = rec->next;\n+\t\t\tchain_len++;\n+\t\t}\n+\n+\t\tif (chain_len == index->max_chain_length)\n+\t\t\treturn -1;\n+\n+\t\t/*\n+\t\t * This is the first time we have ever seen this particular\n+\t\t * element in the sequence. Construct a new chain for it.\n+\t\t */\n+\t\tif (!(rec = xdl_cha_alloc(&index->rcha)))\n+\t\t\treturn -1;\n+\t\trec->ptr = ptr;\n+\t\trec->cnt = 1;\n+\t\trec->next = *rec_chain;\n+\t\t*rec_chain = rec;\n+\t\tLINE_MAP(index, ptr) = rec;\n+\n+continue_scan:\n+\t\t; /* no op */\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr,\n+\tint line1, int count1, int line2, int count2)\n+{\n+\tunsigned int b_next = b_ptr + 1;\n+\tstruct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)];\n+\tunsigned int as, ae, bs, be, np, rc;\n+\tint should_break;\n+\n+\tfor (; rec; rec = rec->next) {\n+\t\tif (rec->cnt > index->cnt) {\n+\t\t\tif (!index->has_common)\n+\t\t\t\tindex->has_common = CMP(index, 1, rec->ptr, 2, b_ptr);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tas = rec->ptr;\n+\t\tif (!CMP(index, 1, as, 2, b_ptr))\n+\t\t\tcontinue;\n+\n+\t\tindex->has_common = 1;\n+\t\tfor (;;) {\n+\t\t\tshould_break = 0;\n+\t\t\tnp = NEXT_PTR(index, as);\n+\t\t\tbs = b_ptr;\n+\t\t\tae = as;\n+\t\t\tbe = bs;\n+\t\t\trc = rec->cnt;\n+\n+\t\t\twhile (line1 < as && line2 < bs\n+\t\t\t\t&& CMP(index, 1, as - 1, 2, bs - 1)) {\n+\t\t\t\tas--;\n+\t\t\t\tbs--;\n+\t\t\t\tif (1 < rc)\n+\t\t\t\t\trc = XDL_MIN(rc, CNT(index, as));\n+\t\t\t}\n+\t\t\twhile (ae < LINE_END(1) && be < LINE_END(2)\n+\t\t\t\t&& CMP(index, 1, ae + 1, 2, be + 1)) {\n+\t\t\t\tae++;\n+\t\t\t\tbe++;\n+\t\t\t\tif (1 < rc)\n+\t\t\t\t\trc = XDL_MIN(rc, CNT(index, ae));\n+\t\t\t}\n+\n+\t\t\tif (b_next <= be)\n+\t\t\t\tb_next = be + 1;\n+\t\t\tif (lcs->end1 - lcs->begin1 < ae - as || rc < index->cnt) {\n+\t\t\t\tlcs->begin1 = as;\n+\t\t\t\tlcs->begin2 = bs;\n+\t\t\t\tlcs->end1 = ae;\n+\t\t\t\tlcs->end2 = be;\n+\t\t\t\tindex->cnt = rc;\n+\t\t\t}\n+\n+\t\t\tif (np == 0)\n+\t\t\t\tbreak;\n+\n+\t\t\twhile (np <= ae) {\n+\t\t\t\tnp = NEXT_PTR(index, np);\n+\t\t\t\tif (np == 0) {\n+\t\t\t\t\tshould_break = 1;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif (should_break)\n+\t\t\t\tbreak;\n+\n+\t\t\tas = np;\n+\t\t}\n+\t}\n+\treturn b_next;\n+}\n+\n+static int find_lcs(struct histindex *index, struct region *lcs,\n+\tint line1, int count1, int line2, int count2) {\n+\tint b_ptr;\n+\n+\tif (scanA(index, line1, count1))\n+\t\treturn -1;\n+\n+\tindex->cnt = index->max_chain_length + 1;\n+\n+\tfor (b_ptr = line2; b_ptr <= LINE_END(2); )\n+\t\tb_ptr = try_lcs(index, lcs, b_ptr, line1, count1, line2, count2);\n+\n+\treturn index->has_common && index->max_chain_length < index->cnt;\n+}\n+\n+static void reduce_common_start_end(xpparam_t const *xpp, xdfenv_t *env,\n+\tint *line1, int *count1, int *line2, int *count2)\n+{\n+\tif (*count1 <= 1 || *count2 <= 1)\n+\t\treturn;\n+\twhile (*count1 > 1 && *count2 > 1 && CMP_ENV(xpp, env, 1, *line1, 2, *line2)) {\n+\t\t(*line1)++;\n+\t\t(*count1)--;\n+\t\t(*line2)++;\n+\t\t(*count2)--;\n+\t}\n+\twhile (*count1 > 1 && *count2 > 1 && CMP_ENV(xpp, env, 1, LINE_END_PTR(1), 2, LINE_END_PTR(2))) {\n+\t\t(*count1)--;\n+\t\t(*count2)--;\n+\t}\n+}\n+\n+static int fall_back_to_classic_diff(struct histindex *index,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\txpparam_t xpp;\n+\txpp.flags = index->xpp->flags & ~XDF_HISTOGRAM_DIFF;\n+\n+\treturn xdl_fall_back_diff(index->env, &xpp,\n+\t\t\t\t line1, count1, line2, count2);\n+}\n+\n+static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n+\tint line1, int count1, int line2, int count2)\n+{\n+\tstruct histindex index;\n+\tstruct region lcs;\n+\tint sz;\n+\tint result = -1;\n+\n+\tif (count1 <= 0 && count2 <= 0)\n+\t\treturn 0;\n+\n+\tif (LINE_END(1) >= MAX_PTR)\n+\t\treturn -1;\n+\n+\tif (!count1) {\n+\t\twhile(count2--)\n+\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\treturn 0;\n+\t} else if (!count2) {\n+\t\twhile(count1--)\n+\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\treturn 0;\n+\t}\n+\n+\tmemset(&index, 0, sizeof(index));\n+\n+\tindex.env = env;\n+\tindex.xpp = xpp;\n+\n+\tindex.records = NULL;\n+\tindex.line_map = NULL;\n+\t/* in case of early xdl_cha_free() */\n+\tindex.rcha.head = NULL;\n+\n+\tindex.table_bits = xdl_hashbits(count1);\n+\tsz = index.records_size = 1 << index.table_bits;\n+\tsz *= sizeof(struct record *);\n+\tif (!(index.records = (struct record **) xdl_malloc(sz)))\n+\t\tgoto cleanup;\n+\tmemset(index.records, 0, sz);\n+\n+\tsz = index.line_map_size = count1;\n+\tsz *= sizeof(struct record *);\n+\tif (!(index.line_map = (struct record **) xdl_malloc(sz)))\n+\t\tgoto cleanup;\n+\tmemset(index.line_map, 0, sz);\n+\n+\tsz = index.line_map_size;\n+\tsz *= sizeof(unsigned int);\n+\tif (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz)))\n+\t\tgoto cleanup;\n+\tmemset(index.next_ptrs, 0, sz);\n+\n+\t/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */\n+\tif (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)\n+\t\tgoto cleanup;\n+\n+\tindex.ptr_shift = line1;\n+\tindex.max_chain_length = 64;\n+\n+\tmemset(&lcs, 0, sizeof(lcs));\n+\tif (find_lcs(&index, &lcs, line1, count1, line2, count2))\n+\t\tresult = fall_back_to_classic_diff(&index, line1, count1, line2, count2);\n+\telse {\n+\t\tresult = 0;\n+\t\tif (lcs.begin1 == 0 && lcs.begin2 == 0) {\n+\t\t\tint ptr;\n+\t\t\tfor (ptr = 0; ptr < count1; ptr++)\n+\t\t\t\tenv->xdf1.rchg[line1 + ptr - 1] = 1;\n+\t\t\tfor (ptr = 0; ptr < count2; ptr++)\n+\t\t\t\tenv->xdf2.rchg[line2 + ptr - 1] = 1;\n+\t\t} else {\n+\t\t\tresult = histogram_diff(xpp, env,\n+\t\t\t\tline1, lcs.begin1 - line1,\n+\t\t\t\tline2, lcs.begin2 - line2);\n+\t\t\tresult = histogram_diff(xpp, env,\n+\t\t\t\tlcs.end1 + 1, LINE_END(1) - lcs.end1,\n+\t\t\t\tlcs.end2 + 1, LINE_END(2) - lcs.end2);\n+\t\t\tresult *= -1;\n+\t\t}\n+\t}\n+\n+cleanup:\n+\txdl_free(index.records);\n+\txdl_free(index.line_map);\n+\txdl_free(index.next_ptrs);\n+\txdl_cha_free(&index.rcha);\n+\n+\treturn result;\n+}\n+\n+int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2,\n+\txpparam_t const *xpp, xdfenv_t *env)\n+{\n+\tint line1, line2, count1, count2;\n+\n+\tif (xdl_prepare_env(file1, file2, xpp, env) < 0)\n+\t\treturn -1;\n+\n+\tline1 = line2 = 1;\n+\tcount1 = env->xdf1.nrec;\n+\tcount2 = env->xdf2.nrec;\n+\n+\treduce_common_start_end(xpp, env, &line1, &count1, &line2, &count2);\n+\n+\treturn histogram_diff(xpp, env, line1, count1, line2, count2);\n+}\n-- \n1.7.3.4.681.gb718e\n"},{"id":"171131","messageId":"1310451027-15148-3-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1310451027-15148-2-git-send-email-rctay89@gmail.com","subject":"[RFC/PATCH 2/3] xdiff/xprepare: skip classification","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-07-12T06:10:26Z","receivedAt":"2011-07-12T06:10:26Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"xdiff performs \"classification\" of records (xdl_classify_record()),\nreplacing hashes (xrecord_t.ha) with a unique identifier of the\nrecord/line and building a hash table (xrecord_t.rhash) of records. This\nis then used to \"cleanup\" records (xdl_cleanup_records()).\n\nWe don't need any of that in histogram diff, so we omit calls to these\nfunctions. We also skip allocating memory to the hash table, rhash, as\nit is no longer used.\n\nThis gives us a small boost in performance.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xprepare.c | 24 ++++++++++++++++--------\n 1 files changed, 16 insertions(+), 8 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 0f571db..7556538 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -154,11 +154,15 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \tif (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))\n \t\tgoto abort;\n \n-\thbits = xdl_hashbits((unsigned int) narec);\n-\thsize = 1 << hbits;\n-\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n-\t\tgoto abort;\n-\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n+\tif (xpp->flags & XDF_HISTOGRAM_DIFF)\n+\t\thbits = hsize = 0;\n+\telse {\n+\t\thbits = xdl_hashbits((unsigned int) narec);\n+\t\thsize = 1 << hbits;\n+\t\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n+\t\t\tgoto abort;\n+\t\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n+\t}\n \n \tnrec = 0;\n \tif ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {\n@@ -183,7 +187,8 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\tcrec->ha = hav;\n \t\t\trecs[nrec++] = crec;\n \n-\t\t\tif (xdl_classify_record(cf, rhash, hbits, crec) < 0)\n+\t\t\tif (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&\n+\t\t\t\txdl_classify_record(cf, rhash, hbits, crec) < 0)\n \t\t\t\tgoto abort;\n \t\t}\n \t}\n@@ -240,7 +245,8 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \tenl1 = xdl_guess_lines(mf1) + 1;\n \tenl2 = xdl_guess_lines(mf2) + 1;\n \n-\tif (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {\n+\tif (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&\n+\t\txdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {\n \n \t\treturn -1;\n \t}\n@@ -257,9 +263,11 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\treturn -1;\n \t}\n \n-\txdl_free_classifier(&cf);\n+\tif (!(xpp->flags & XDF_HISTOGRAM_DIFF))\n+\t\txdl_free_classifier(&cf);\n \n \tif (!(xpp->flags & XDF_PATIENCE_DIFF) &&\n+\t\t\t!(xpp->flags & XDF_HISTOGRAM_DIFF) &&\n \t\t\txdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {\n \n \t\txdl_free_ctx(&xe->xdf2);\n-- \n1.7.3.4.681.gb718e\n"},{"id":"171132","messageId":"1310451027-15148-4-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1310451027-15148-3-git-send-email-rctay89@gmail.com","subject":"[RFC/PATCH 3/3] xdiff/xprepare: use a smaller sample size for histogram diff","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-07-12T06:10:27Z","receivedAt":"2011-07-12T06:10:27Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"For histogram diff, we can afford a smaller sample size and thus a\npoorer estimate of the number of lines, as the hash table (rhash) won't\nbe filled up/grown. This is safe as the final count of lines (xdf.nrecs)\nwill be updated correctly anyway by xdl_prepare_ctx().\n\nThis gives us a small boost in performance.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xprepare.c | 17 ++++++++++++++---\n xdiff/xutils.c | 8 ++------\n xdiff/xutils.h | 2 +-\n 3 files changed, 17 insertions(+), 10 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 7556538..dfbb0de 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -26,6 +26,8 @@\n #define XDL_KPDIS_RUN 4\n #define XDL_MAX_EQLIMIT 1024\n #define XDL_SIMSCAN_WINDOW 100\n+#define XDL_GUESS_NLINES1 256\n+#define XDL_GUESS_NLINES2 20\n \n \n typedef struct s_xdlclass {\n@@ -239,11 +241,20 @@ static void xdl_free_ctx(xdfile_t *xdf) {\n \n 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+\tlong enl1, enl2, sample;\n \txdlclassifier_t cf;\n \n-\tenl1 = xdl_guess_lines(mf1) + 1;\n-\tenl2 = xdl_guess_lines(mf2) + 1;\n+\t/*\n+\t * For histogram diff, we can afford a smaller sample size and\n+\t * thus a poorer estimate of the number of lines, as the hash\n+\t * table (rhash) won't be filled up/grown. The number of lines\n+\t * (nrecs) will be updated correctly anyway by\n+\t * xdl_prepare_ctx().\n+\t */\n+\tsample = xpp->flags & XDF_HISTOGRAM_DIFF ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1;\n+\n+\tenl1 = xdl_guess_lines(mf1, sample) + 1;\n+\tenl2 = xdl_guess_lines(mf2, sample) + 1;\n \n \tif (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&\n \t\txdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex ded7c32..a45e89b 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -24,10 +24,6 @@\n \n \n \n-#define XDL_GUESS_NLINES 256\n-\n-\n-\n \n long xdl_bogosqrt(long n) {\n \tlong i;\n@@ -159,12 +155,12 @@ void *xdl_cha_next(chastore_t *cha) {\n }\n \n \n-long xdl_guess_lines(mmfile_t *mf) {\n+long xdl_guess_lines(mmfile_t *mf, long sample) {\n \tlong nl = 0, size, tsize = 0;\n \tchar const *data, *cur, *top;\n \n \tif ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {\n-\t\tfor (top = data + size; nl < XDL_GUESS_NLINES;) {\n+\t\tfor (top = data + size; nl < sample;) {\n \t\t\tif (cur >= top) {\n \t\t\t\ttsize += (long) (cur - data);\n \t\t\t\tif (!(cur = data = xdl_mmfile_next(mf, &size)))\ndiff --git a/xdiff/xutils.h b/xdiff/xutils.h\nindex 674a657..714719a 100644\n--- a/xdiff/xutils.h\n+++ b/xdiff/xutils.h\n@@ -33,7 +33,7 @@ void xdl_cha_free(chastore_t *cha);\n void *xdl_cha_alloc(chastore_t *cha);\n void *xdl_cha_first(chastore_t *cha);\n void *xdl_cha_next(chastore_t *cha);\n-long xdl_guess_lines(mmfile_t *mf);\n+long xdl_guess_lines(mmfile_t *mf, long sample);\n int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);\n unsigned long xdl_hash_record(char const **data, char const *top, long flags);\n unsigned int xdl_hashbits(unsigned int size);\n-- \n1.7.3.4.681.gb718e\n"},{"id":"171149","messageId":"CAJo=hJu5ubkzUyyPM0nqP+J9CU3hBtAHfuzaLSuN214Hux4qTA@mail.gmail.com","threadId":"27792","inReplyTo":"1310451027-15148-1-git-send-email-rctay89@gmail.com","subject":"Re: [RFC/PATCH 0/3] teach --histogram to diff","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-07-12T14:19:47Z","receivedAt":"2011-07-12T14:19:47Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jul 11, 2011 at 23:10, Tay Ray Chuan wrote:\n> (Shawn, I was held up with the patch messages, sorry for the delay.)\n>\n> Port JGit's HistogramDiff(Index) over to C. This algorithm extends the\n> patience algorithm to \"support low-occurrence common elements\" [1].\n>\n> Rough numbers show that it is a faster alternative to its --patience\n> cousin, as well as to the default Meyers algorithm:\n>\n>  $ time ./git log --histogram -p v1.0.0 >/dev/null\n>\n>  real    0m12.998s\n>  user    0m11.506s\n>  sys     0m1.487s\n>  $ time ./git log -p v1.0.0 >/dev/null\n>\n>  real    0m13.575s\n>  user    0m12.101s\n>  sys     0m1.468s\n>  $ time ./git log --patience -p v1.0.0 >/dev/null\n>\n>  real    0m14.978s\n>  user    0m13.508s\n>  sys     0m1.464s\n\nNice!\n\nNot the big difference that it is for us in JGit (between histogram\nand Myers), but its nice to see an improvement here, even if it is\nonly 0.5s for the entire 1.0.0 history. How do the diffs come out? One\nof the arguments for patience diff is the formatting can sometimes be\nmore readable for certain changes, but its slower. Histogram tries to\napply a similar algorithm as patience in order to get the formatting\nbenefits, but also some performance improvements.\n\nHave you looked at a patch that differs in output between Myers and\npatience, and then compared those to the histogram version?\n\n> The first patch implements JGit's HistogramDiff(Index) proper. The\n> second and third patches aren't essential but yield performance gains.\n...\n> [RFC/PATCH 1/3] teach --histogram to diff\n> [RFC/PATCH 2/3] xdiff/xprepare: skip classification\n> [RFC/PATCH 3/3] xdiff/xprepare: use a smaller sample size for histogram\n\nDo we need sampling at all for histogram? Can you skip it?\n\n-- \nShawn.\n"},{"id":"171165","messageId":"7vfwmb8ken.fsf@alter.siamese.dyndns.org","threadId":"27792","inReplyTo":"CAJo=hJu5ubkzUyyPM0nqP+J9CU3hBtAHfuzaLSuN214Hux4qTA@mail.gmail.com","subject":"Re: [RFC/PATCH 0/3] teach --histogram to diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-12T17:43:12Z","receivedAt":"2011-07-12T17:43:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Have you looked at a patch that differs in output between Myers and\n> patience, and then compared those to the histogram version?\n\n$ git log -p v1.6.6..v1.7.6 | git patch-id >/var/tmp/md\n$ git log --histogram -p v1.6.6..v1.7.6 | git patch-id >/var/tmp/hd\n$ diff -u0 /var/tmp/md /var/tmp/hd |\n sed -ne '/^+/s/^+[0-9a-f][0-9a-f][0-9a-f]* //p' |\n while read commit\n do\n \tgit show \"$commit\" >/var/tmp/1\n git show --histogram \"$commit\" >/var/tmp/2\n interdiff /var/tmp/1 /var/tmp/2\n done\n\nshows there is one that gives vastly different appearance, but it all\nboils down to which lines to take as common, and for this particular\nexample neither is more readable over the other (9560808f2ef5a34d2a).\n\nRunning the above \"show\" with larger -U$n value shows there don't seem to\nbe any discrepancies between the two.\n"},{"id":"171184","messageId":"7vy6036zon.fsf@alter.siamese.dyndns.org","threadId":"27792","inReplyTo":"1310451027-15148-2-git-send-email-rctay89@gmail.com","subject":"Re: [RFC/PATCH 1/3] teach --histogram to diff","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-12T19:56:08Z","receivedAt":"2011-07-12T19:56:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is just half-a-review (bottom half of the file).\n\n> +static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n> +\tint line1, int count1, int line2, int count2)\n> +{\n\nWhat does this function return?\n\n> +\tstruct histindex index;\n> +\tstruct region lcs;\n> +\tint sz;\n> +\tint result = -1;\n> +\n> +\tif (count1 <= 0 && count2 <= 0)\n> +\t\treturn 0;\n> +\n> +\tif (LINE_END(1) >= MAX_PTR)\n> +\t\treturn -1;\n> +\n> +\tif (!count1) {\n> +\t\twhile(count2--)\n> +\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n> +\t\treturn 0;\n> +\t} else if (!count2) {\n> +\t\twhile(count1--)\n> +\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n> +\t\treturn 0;\n> +\t}\n> +\n> +\tmemset(&index, 0, sizeof(index));\n> +\n> +\tindex.env = env;\n> +\tindex.xpp = xpp;\n> +\n> +\tindex.records = NULL;\n> +\tindex.line_map = NULL;\n> +\t/* in case of early xdl_cha_free() */\n> +\tindex.rcha.head = NULL;\n> +\n> +\tindex.table_bits = xdl_hashbits(count1);\n> +\tsz = index.records_size = 1 << index.table_bits;\n> +\tsz *= sizeof(struct record *);\n> +\tif (!(index.records = (struct record **) xdl_malloc(sz)))\n> +\t\tgoto cleanup;\n> +\tmemset(index.records, 0, sz);\n> +\n> +\tsz = index.line_map_size = count1;\n> +\tsz *= sizeof(struct record *);\n> +\tif (!(index.line_map = (struct record **) xdl_malloc(sz)))\n> +\t\tgoto cleanup;\n> +\tmemset(index.line_map, 0, sz);\n> +\n> +\tsz = index.line_map_size;\n> +\tsz *= sizeof(unsigned int);\n> +\tif (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz)))\n> +\t\tgoto cleanup;\n> +\tmemset(index.next_ptrs, 0, sz);\n> +\n> +\t/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */\n> +\tif (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)\n> +\t\tgoto cleanup;\n> +\n> +\tindex.ptr_shift = line1;\n> +\tindex.max_chain_length = 64;\n> +\n> +\tmemset(&lcs, 0, sizeof(lcs));\n> +\tif (find_lcs(&index, &lcs, line1, count1, line2, count2))\n> +\t\tresult = fall_back_to_classic_diff(&index, line1, count1, line2, count2);\n> +\telse {\n> +\t\tresult = 0;\n> +\t\tif (lcs.begin1 == 0 && lcs.begin2 == 0) {\n> +\t\t\tint ptr;\n> +\t\t\tfor (ptr = 0; ptr < count1; ptr++)\n> +\t\t\t\tenv->xdf1.rchg[line1 + ptr - 1] = 1;\n> +\t\t\tfor (ptr = 0; ptr < count2; ptr++)\n> +\t\t\t\tenv->xdf2.rchg[line2 + ptr - 1] = 1;\n> +\t\t} else {\n> +\t\t\tresult = histogram_diff(xpp, env,\n> +\t\t\t\tline1, lcs.begin1 - line1,\n> +\t\t\t\tline2, lcs.begin2 - line2);\n> +\t\t\tresult = histogram_diff(xpp, env,\n> +\t\t\t\tlcs.end1 + 1, LINE_END(1) - lcs.end1,\n> +\t\t\t\tlcs.end2 + 1, LINE_END(2) - lcs.end2);\n\nThe result from the first half before lcs is discarded?\n\n> +\t\t\tresult *= -1;\n\nAgain, what does this function (called recursively) return, and what does\nflipping the sign of it do?\n\n> +\t\t}\n> +\t}\n> +\n> +cleanup:\n> +\txdl_free(index.records);\n> +\txdl_free(index.line_map);\n> +\txdl_free(index.next_ptrs);\n> +\txdl_cha_free(&index.rcha);\n> +\n> +\treturn result;\n> +}\n> +\n> +int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2,\n> +\txpparam_t const *xpp, xdfenv_t *env)\n> +{\n> +\tint line1, line2, count1, count2;\n> +\n> +\tif (xdl_prepare_env(file1, file2, xpp, env) < 0)\n> +\t\treturn -1;\n> +\n> +\tline1 = line2 = 1;\n> +\tcount1 = env->xdf1.nrec;\n> +\tcount2 = env->xdf2.nrec;\n> +\n> +\treduce_common_start_end(xpp, env, &line1, &count1, &line2, &count2);\n\nWhat this does is logically not specific to histogram algorithm but can be\napplied to other backends, no? And I vaguely recall that Linus did try\nsomething like this once, found some issues with it when context is set to\nnon zero, and stopped doing it (sorry, I do not have any more details).\n\nI am not suggesting you to remove this call or hoist the call to one level\nup to xdl_do_diff(), but I do have to wonder how much of the performance\nimprovement you reported is due to this common head/tail reduction.\n\n> +\treturn histogram_diff(xpp, env, line1, count1, line2, count2);\n> +}\n"},{"id":"171264","messageId":"CALUzUxqS8y4HH44t2CuSvfQiLP-Y7hFtbi5x2rtAwPBKSJ+3Bw@mail.gmail.com","threadId":"27792","inReplyTo":"CAJo=hJu5ubkzUyyPM0nqP+J9CU3hBtAHfuzaLSuN214Hux4qTA@mail.gmail.com","subject":"Re: [RFC/PATCH 0/3] teach --histogram to diff","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-07-13T16:34:14Z","receivedAt":"2011-07-13T16:34:14Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"On Tue, Jul 12, 2011 at 10:19 PM, Shawn Pearce wrote:\n> On Mon, Jul 11, 2011 at 23:10, Tay Ray Chuan wrote:\n>> [RFC/PATCH 3/3] xdiff/xprepare: use a smaller sample size for histogram\n>\n> Do we need sampling at all for histogram? Can you skip it?\n\nSampling is done to get a guess of lines in the file. This guess is\nthen used to preallocated memory for the list of records. (This is\njust a guess; if we find more records we allocate more memory.) By\ndoing this preallocation, we can save on malloc()'s, giving a\nperformance boost.\n\nBut then sampling has its costs - previously, we ran up to 256\nmemchr('\\n')s within a mmfile \"block\". For histogram diff, we cut the\ncap down to 20. (But not for the other diff algorithms - see the\nrelevant patch text for more.) I think this gives us a good balance -\ntime spent in guessing lines, and time gained from preallocating\nmemory.\n\n-- \nCheers,\nRay Chuan\n"},{"id":"171265","messageId":"CALUzUxo1tBDjmN_Xu9OnQn3OFqzuDovU48d+nmkokm6mVOVWwg@mail.gmail.com","threadId":"27792","inReplyTo":"7vfwmb8ken.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 0/3] teach --histogram to diff","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-07-13T16:35:37Z","receivedAt":"2011-07-13T16:35:37Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"On Wed, Jul 13, 2011 at 1:43 AM, Junio C Hamano wrote:\n> Shawn Pearce writes:\n>\n>> Have you looked at a patch that differs in output between Myers and\n>> patience, and then compared those to the histogram version?\n>\n> $ git log -p v1.6.6..v1.7.6 | git patch-id >/var/tmp/md\n> $ git log --histogram -p v1.6.6..v1.7.6 | git patch-id >/var/tmp/hd\n> $ diff -u0 /var/tmp/md /var/tmp/hd |\n>  sed -ne '/^+/s/^+[0-9a-f][0-9a-f][0-9a-f]* //p' |\n>  while read commit\n>  do\n>        git show \"$commit\" >/var/tmp/1\n>        git show --histogram \"$commit\" >/var/tmp/2\n>        interdiff /var/tmp/1 /var/tmp/2\n>  done\n\nThanks for taking the time to run this.\n\n> shows there is one that gives vastly different appearance, but it all\n> boils down to which lines to take as common, and for this particular\n> example neither is more readable over the other (9560808f2ef5a34d2a).\n>\n> Running the above \"show\" with larger -U$n value shows there don't seem to\n> be any discrepancies between the two.\n\nI suspect it's due to that change being mostly a lot of additions on\nthe right side, without much deletions on the left.\n\n-- \nCheers,\nRay Chuan\n"},{"id":"171266","messageId":"CALUzUxqv5PTche5-fG5CPVg+hrO1a0R73gF23gcJbWM3wO_wbA@mail.gmail.com","threadId":"27792","inReplyTo":"7vy6036zon.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 1/3] teach --histogram to diff","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-07-13T16:36:18Z","receivedAt":"2011-07-13T16:36:18Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"On Wed, Jul 13, 2011 at 3:56 AM, Junio C Hamano wrote:\n> This is just half-a-review (bottom half of the file).\n> [snip]\n>> +                     result = histogram_diff(xpp, env,\n>> +                             line1, lcs.begin1 - line1,\n>> +                             line2, lcs.begin2 - line2);\n>> +                     result = histogram_diff(xpp, env,\n>> +                             lcs.end1 + 1, LINE_END(1) - lcs.end1,\n>> +                             lcs.end2 + 1, LINE_END(2) - lcs.end2);\n>\n> The result from the first half before lcs is discarded?\n>\n>> +                     result *= -1;\n>\n> Again, what does this function (called recursively) return, and what does\n> flipping the sign of it do?\n\nOops, my bad.\n\n>[snip]\n>> +     reduce_common_start_end(xpp, env, &line1, &count1, &line2, &count2);\n>\n> What this does is logically not specific to histogram algorithm but can be\n> applied to other backends, no? And I vaguely recall that Linus did try\n> something like this once, found some issues with it when context is set to\n> non zero, and stopped doing it (sorry, I do not have any more details).\n>\n> I am not suggesting you to remove this call or hoist the call to one level\n> up to xdl_do_diff(), but I do have to wonder how much of the performance\n> improvement you reported is due to this common head/tail reduction.\n\nI believe xdiff already performs this for the Meyers algorithm (in\nxprepare.c:xdl_trim_ends()), but the Meyers code doesn't look like it\nuses this information at all. If this is the case, then I do think\nthat a large part of the performance improvement is due to this common\nreduction - for git log -p, one would expect a pretty large number of\ncommon head/tail lines in files within a commit.\n\n-- \nCheers,\nRay Chuan\n"},{"id":"172486","messageId":"1312168608-10828-1-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1310451027-15148-1-git-send-email-rctay89@gmail.com","subject":"[PATCH v2 0/8] teach --histogram to diff","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T03:16:40Z","receivedAt":"2011-08-01T03:16:40Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Port JGit's HistogramDiff(Index) over to C. This algorithm extends the\npatience algorithm to \"support low-occurrence common elements\" [1].\nRough numbers show that it is a faster alternative to its --patience\ncousin, as well as to the default Meyers algorithm.\n\nChanged from v1/RFC:\n - patch #2 is new\n - patch #6 been changed\n - all other patches are unchanged\n\nContents:\n[PATCH v2 1/8] xdiff/xprepare: use memset()\n[PATCH v2 2/8] do away with xdl_mmfile_next()\n[PATCH v2 3/8] xdiff/xprepare: refactor abort cleanups\n[PATCH v2 4/8] xdiff/xpatience: factor out fall-back-diff function\n[PATCH v2 5/8] t4033-diff-patience: factor out tests\n[PATCH v2 6/8] teach --histogram to diff\n[PATCH v2 7/8] xdiff/xprepare: skip classification\n[PATCH v2 8/8] xdiff/xprepare: use a smaller sample size for histogram diff\n\n--\nFootnotes:\n[1]\nhttp://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java;hb=HEAD\n\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172487","messageId":"1312168608-10828-2-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312168608-10828-1-git-send-email-rctay89@gmail.com","subject":"[PATCH v2 1/8] xdiff/xprepare: use memset()","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T03:16:41Z","receivedAt":"2011-08-01T03:16:41Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Use memset() instead of a for loop to initialize. This could give a\nperformance advantage.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xprepare.c | 10 +++-------\n 1 files changed, 3 insertions(+), 7 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 1689085..783631a 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -64,8 +64,6 @@ static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);\n \n \n static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {\n-\tlong i;\n-\n \tcf->flags = flags;\n \n \tcf->hbits = xdl_hashbits((unsigned int) size);\n@@ -80,8 +78,7 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {\n \t\txdl_cha_free(&cf->ncha);\n \t\treturn -1;\n \t}\n-\tfor (i = 0; i < cf->hsize; i++)\n-\t\tcf->rchash[i] = NULL;\n+\tmemset(cf->rchash, 0, cf->hsize * sizeof(xdlclass_t *));\n \n \tcf->count = 0;\n \n@@ -136,7 +133,7 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned\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 \tunsigned int hbits;\n-\tlong i, nrec, hsize, bsize;\n+\tlong nrec, hsize, bsize;\n \tunsigned long hav;\n \tchar const *blk, *cur, *top, *prev;\n \txrecord_t *crec;\n@@ -164,8 +161,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\txdl_cha_free(&xdf->rcha);\n \t\treturn -1;\n \t}\n-\tfor (i = 0; i < hsize; i++)\n-\t\trhash[i] = NULL;\n+\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n \n \tnrec = 0;\n \tif ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172488","messageId":"1312168608-10828-3-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312168608-10828-2-git-send-email-rctay89@gmail.com","subject":"[PATCH v2 2/8] do away with xdl_mmfile_next()","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T03:16:42Z","receivedAt":"2011-08-01T03:16:42Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Given our simple mmfile structure, xdl_mmfile_next() calls are\nredundant. Do away with calls to them.\n\nSigned-off-by: Tay Ray Chuan \n---\n\nNew in v2.\n\n xdiff/xdiff.h | 1 -\n xdiff/xprepare.c | 7 +------\n xdiff/xutils.c | 14 +-------------\n 3 files changed, 2 insertions(+), 20 deletions(-)\n\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 711048e..6ea1d0e 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -105,7 +105,6 @@ typedef struct s_bdiffparam {\n #define xdl_realloc(ptr,x) realloc(ptr,x)\n \n void *xdl_mmfile_first(mmfile_t *mmf, long *size);\n-void *xdl_mmfile_next(mmfile_t *mmf, long *size);\n long xdl_mmfile_size(mmfile_t *mmf);\n \n int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 783631a..49c7e8a 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -165,12 +165,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \n \tnrec = 0;\n \tif ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {\n-\t\tfor (top = blk + bsize;;) {\n-\t\t\tif (cur >= top) {\n-\t\t\t\tif (!(cur = blk = xdl_mmfile_next(mf, &bsize)))\n-\t\t\t\t\tbreak;\n-\t\t\t\ttop = blk + bsize;\n-\t\t\t}\n+\t\tfor (top = blk + bsize; cur < top; ) {\n \t\t\tprev = cur;\n \t\t\thav = xdl_hash_record(&cur, top, xpp->flags);\n \t\t\tif (nrec >= narec) {\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex ab65034..ea1357d 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -71,12 +71,6 @@ void *xdl_mmfile_first(mmfile_t *mmf, long *size)\n }\n \n \n-void *xdl_mmfile_next(mmfile_t *mmf, long *size)\n-{\n-\treturn NULL;\n-}\n-\n-\n long xdl_mmfile_size(mmfile_t *mmf)\n {\n \treturn mmf->size;\n@@ -164,13 +158,7 @@ long xdl_guess_lines(mmfile_t *mf) {\n \tchar const *data, *cur, *top;\n \n \tif ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {\n-\t\tfor (top = data + size; nl < XDL_GUESS_NLINES;) {\n-\t\t\tif (cur >= top) {\n-\t\t\t\ttsize += (long) (cur - data);\n-\t\t\t\tif (!(cur = data = xdl_mmfile_next(mf, &size)))\n-\t\t\t\t\tbreak;\n-\t\t\t\ttop = data + size;\n-\t\t\t}\n+\t\tfor (top = data + size; nl < XDL_GUESS_NLINES && cur < top; ) {\n \t\t\tnl++;\n \t\t\tif (!(cur = memchr(cur, '\\n', top - cur)))\n \t\t\t\tcur = top;\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172490","messageId":"1312168608-10828-4-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312168608-10828-3-git-send-email-rctay89@gmail.com","subject":"[PATCH v2 3/8] xdiff/xprepare: refactor abort cleanups","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T03:16:43Z","receivedAt":"2011-08-01T03:16:43Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Group free()'s that are called when a malloc() fails in\nxdl_prepare_ctx(), making for more readable code.\n\nAlso add a free() on ha, in case future git hackers add allocs after the\nha malloc.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xprepare.c | 91 +++++++++++++++++++-----------------------------------\n 1 files changed, 32 insertions(+), 59 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 49c7e8a..3ebad0f 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -143,24 +143,21 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \tchar *rchg;\n \tlong *rindex;\n \n-\tif (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) {\n+\tha = NULL;\n+\trindex = NULL;\n+\trchg = NULL;\n+\trhash = NULL;\n+\trecs = NULL;\n \n-\t\treturn -1;\n-\t}\n-\tif (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) {\n-\n-\t\txdl_cha_free(&xdf->rcha);\n-\t\treturn -1;\n-\t}\n+\tif (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0)\n+\t\tgoto abort;\n+\tif (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))\n+\t\tgoto abort;\n \n \thbits = xdl_hashbits((unsigned int) narec);\n \thsize = 1 << hbits;\n-\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *)))) {\n-\n-\t\txdl_free(recs);\n-\t\txdl_cha_free(&xdf->rcha);\n-\t\treturn -1;\n-\t}\n+\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n+\t\tgoto abort;\n \tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n \n \tnrec = 0;\n@@ -170,63 +167,30 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\thav = xdl_hash_record(&cur, top, xpp->flags);\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-\n-\t\t\t\t\txdl_free(rhash);\n-\t\t\t\t\txdl_free(recs);\n-\t\t\t\t\txdl_cha_free(&xdf->rcha);\n-\t\t\t\t\treturn -1;\n-\t\t\t\t}\n+\t\t\t\tif (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *))))\n+\t\t\t\t\tgoto abort;\n \t\t\t\trecs = rrecs;\n \t\t\t}\n-\t\t\tif (!(crec = xdl_cha_alloc(&xdf->rcha))) {\n-\n-\t\t\t\txdl_free(rhash);\n-\t\t\t\txdl_free(recs);\n-\t\t\t\txdl_cha_free(&xdf->rcha);\n-\t\t\t\treturn -1;\n-\t\t\t}\n+\t\t\tif (!(crec = xdl_cha_alloc(&xdf->rcha)))\n+\t\t\t\tgoto abort;\n \t\t\tcrec->ptr = prev;\n \t\t\tcrec->size = (long) (cur - prev);\n \t\t\tcrec->ha = hav;\n \t\t\trecs[nrec++] = crec;\n \n-\t\t\tif (xdl_classify_record(cf, rhash, hbits, crec) < 0) {\n-\n-\t\t\t\txdl_free(rhash);\n-\t\t\t\txdl_free(recs);\n-\t\t\t\txdl_cha_free(&xdf->rcha);\n-\t\t\t\treturn -1;\n-\t\t\t}\n+\t\t\tif (xdl_classify_record(cf, rhash, hbits, crec) < 0)\n+\t\t\t\tgoto abort;\n \t\t}\n \t}\n \n-\tif (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) {\n-\n-\t\txdl_free(rhash);\n-\t\txdl_free(recs);\n-\t\txdl_cha_free(&xdf->rcha);\n-\t\treturn -1;\n-\t}\n+\tif (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char))))\n+\t\tgoto abort;\n \tmemset(rchg, 0, (nrec + 2) * sizeof(char));\n \n-\tif (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long)))) {\n-\n-\t\txdl_free(rchg);\n-\t\txdl_free(rhash);\n-\t\txdl_free(recs);\n-\t\txdl_cha_free(&xdf->rcha);\n-\t\treturn -1;\n-\t}\n-\tif (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long)))) {\n-\n-\t\txdl_free(rindex);\n-\t\txdl_free(rchg);\n-\t\txdl_free(rhash);\n-\t\txdl_free(recs);\n-\t\txdl_cha_free(&xdf->rcha);\n-\t\treturn -1;\n-\t}\n+\tif (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long))))\n+\t\tgoto abort;\n+\tif (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long))))\n+\t\tgoto abort;\n \n \txdf->nrec = nrec;\n \txdf->recs = recs;\n@@ -240,6 +204,15 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \txdf->dend = nrec - 1;\n \n \treturn 0;\n+\n+abort:\n+\txdl_free(ha);\n+\txdl_free(rindex);\n+\txdl_free(rchg);\n+\txdl_free(rhash);\n+\txdl_free(recs);\n+\txdl_cha_free(&xdf->rcha);\n+\treturn -1;\n }\n \n \n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172489","messageId":"1312168608-10828-5-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312168608-10828-4-git-send-email-rctay89@gmail.com","subject":"[PATCH v2 4/8] xdiff/xpatience: factor out fall-back-diff function","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T03:16:44Z","receivedAt":"2011-08-01T03:16:44Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"This is in preparation for the histogram diff algorithm, which will also\nre-use much of the code to call the default Meyers diff algorithm.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xpatience.c | 27 ++-------------------------\n xdiff/xutils.c | 31 +++++++++++++++++++++++++++++++\n xdiff/xutils.h | 2 ++\n 3 files changed, 35 insertions(+), 25 deletions(-)\n\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex e42c16a..fdd7d02 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -287,34 +287,11 @@ static int walk_common_sequence(struct hashmap *map, struct entry *first,\n static int fall_back_to_classic_diff(struct hashmap *map,\n \t\tint line1, int count1, int line2, int count2)\n {\n-\t/*\n-\t * This probably does not work outside Git, since\n-\t * we have a very simple mmfile structure.\n-\t *\n-\t * Note: ideally, we would reuse the prepared environment, but\n-\t * the libxdiff interface does not (yet) allow for diffing only\n-\t * ranges of lines instead of the whole files.\n-\t */\n-\tmmfile_t subfile1, subfile2;\n \txpparam_t xpp;\n-\txdfenv_t env;\n-\n-\tsubfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr;\n-\tsubfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr +\n-\t\tmap->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;\n-\tsubfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr;\n-\tsubfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr +\n-\t\tmap->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;\n \txpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;\n-\tif (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0)\n-\t\treturn -1;\n-\n-\tmemcpy(map->env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);\n-\tmemcpy(map->env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);\n-\n-\txdl_free_env(&env);\n \n-\treturn 0;\n+\treturn xdl_fall_back_diff(map->env, &xpp,\n+\t\t\t\t line1, count1, line2, count2);\n }\n \n /*\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex ea1357d..890cc4f 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -390,3 +390,34 @@ int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,\n \n \treturn 0;\n }\n+\n+int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\t/*\n+\t * This probably does not work outside Git, since\n+\t * we have a very simple mmfile structure.\n+\t *\n+\t * Note: ideally, we would reuse the prepared environment, but\n+\t * the libxdiff interface does not (yet) allow for diffing only\n+\t * ranges of lines instead of the whole files.\n+\t */\n+\tmmfile_t subfile1, subfile2;\n+\txdfenv_t env;\n+\n+\tsubfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr;\n+\tsubfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr +\n+\t\tdiff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;\n+\tsubfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr;\n+\tsubfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr +\n+\t\tdiff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;\n+\tif (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0)\n+\t\treturn -1;\n+\n+\tmemcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);\n+\tmemcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);\n+\n+\txdl_free_env(&env);\n+\n+\treturn 0;\n+}\ndiff --git a/xdiff/xutils.h b/xdiff/xutils.h\nindex d5de829..674a657 100644\n--- a/xdiff/xutils.h\n+++ b/xdiff/xutils.h\n@@ -41,6 +41,8 @@ int xdl_num_out(char *out, long val);\n long xdl_atol(char const *str, char const **next);\n int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,\n \t\t const char *func, long funclen, xdemitcb_t *ecb);\n+int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,\n+\t\t int line1, int count1, int line2, int count2);\n \n \n \n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172491","messageId":"1312168608-10828-6-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312168608-10828-5-git-send-email-rctay89@gmail.com","subject":"[PATCH v2 5/8] t4033-diff-patience: factor out tests","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T03:16:45Z","receivedAt":"2011-08-01T03:16:45Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Group the test cases into two functions, test_diff_(frobnitz|unique).\nThis in preparation for the histogram diff algorithm, which would also\nre-use these test cases.\n\nSigned-off-by: Tay Ray Chuan \n---\n t/lib-diff-alternative.sh | 165 +++++++++++++++++++++++++++++++++++++++++++++\n t/t4033-diff-patience.sh | 162 +-------------------------------------------\n 2 files changed, 168 insertions(+), 159 deletions(-)\n create mode 100644 t/lib-diff-alternative.sh\n\ndiff --git a/t/lib-diff-alternative.sh b/t/lib-diff-alternative.sh\nnew file mode 100644\nindex 0000000..75ffd91\n--- /dev/null\n+++ b/t/lib-diff-alternative.sh\n@@ -0,0 +1,165 @@\n+#!/bin/sh\n+\n+test_diff_frobnitz() {\n+\tcat >file1 <<\\EOF\n+#include \n+\n+// Frobs foo heartily\n+int frobnitz(int foo)\n+{\n+ int i;\n+ for(i = 0; i < 10; i++)\n+ {\n+ printf(\"Your answer is: \");\n+ printf(\"%d\\n\", foo);\n+ }\n+}\n+\n+int fact(int n)\n+{\n+ if(n > 1)\n+ {\n+ return fact(n-1) * n;\n+ }\n+ return 1;\n+}\n+\n+int main(int argc, char **argv)\n+{\n+ frobnitz(fact(10));\n+}\n+EOF\n+\n+\tcat >file2 <<\\EOF\n+#include \n+\n+int fib(int n)\n+{\n+ if(n > 2)\n+ {\n+ return fib(n-1) + fib(n-2);\n+ }\n+ return 1;\n+}\n+\n+// Frobs foo heartily\n+int frobnitz(int foo)\n+{\n+ int i;\n+ for(i = 0; i < 10; i++)\n+ {\n+ printf(\"%d\\n\", foo);\n+ }\n+}\n+\n+int main(int argc, char **argv)\n+{\n+ frobnitz(fib(10));\n+}\n+EOF\n+\n+\tcat >expect <<\\EOF\n+diff --git a/file1 b/file2\n+index 6faa5a3..e3af329 100644\n+--- a/file1\n++++ b/file2\n+@@ -1,26 +1,25 @@\n+ #include \n+ \n++int fib(int n)\n++{\n++ if(n > 2)\n++ {\n++ return fib(n-1) + fib(n-2);\n++ }\n++ return 1;\n++}\n++\n+ // Frobs foo heartily\n+ int frobnitz(int foo)\n+ {\n+ int i;\n+ for(i = 0; i < 10; i++)\n+ {\n+- printf(\"Your answer is: \");\n+ printf(\"%d\\n\", foo);\n+ }\n+ }\n+ \n+-int fact(int n)\n+-{\n+- if(n > 1)\n+- {\n+- return fact(n-1) * n;\n+- }\n+- return 1;\n+-}\n+-\n+ int main(int argc, char **argv)\n+ {\n+- frobnitz(fact(10));\n++ frobnitz(fib(10));\n+ }\n+EOF\n+\n+\tSTRATEGY=$1\n+\n+\ttest_expect_success \"$STRATEGY diff\" '\n+\t\ttest_must_fail git diff --no-index \"--$STRATEGY\" file1 file2 > output &&\n+\t\ttest_cmp expect output\n+\t'\n+\n+\ttest_expect_success \"$STRATEGY diff output is valid\" '\n+\t\tmv file2 expect &&\n+\t\tgit apply < output &&\n+\t\ttest_cmp expect file2\n+\t'\n+}\n+\n+test_diff_unique() {\n+\tcat >uniq1 <<\\EOF\n+1\n+2\n+3\n+4\n+5\n+6\n+EOF\n+\n+\tcat >uniq2 <<\\EOF\n+a\n+b\n+c\n+d\n+e\n+f\n+EOF\n+\n+\tcat >expect <<\\EOF\n+diff --git a/uniq1 b/uniq2\n+index b414108..0fdf397 100644\n+--- a/uniq1\n++++ b/uniq2\n+@@ -1,6 +1,6 @@\n+-1\n+-2\n+-3\n+-4\n+-5\n+-6\n++a\n++b\n++c\n++d\n++e\n++f\n+EOF\n+\n+\tSTRATEGY=$1\n+\n+\ttest_expect_success 'completely different files' '\n+\t\ttest_must_fail git diff --no-index \"--$STRATEGY\" uniq1 uniq2 > output &&\n+\t\ttest_cmp expect output\n+\t'\n+}\n+\ndiff --git a/t/t4033-diff-patience.sh b/t/t4033-diff-patience.sh\nindex 1eb1498..3c9932e 100755\n--- a/t/t4033-diff-patience.sh\n+++ b/t/t4033-diff-patience.sh\n@@ -3,166 +3,10 @@\n test_description='patience diff algorithm'\n \n . ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-diff-alternative.sh\n \n-cat >file1 <<\\EOF\n-#include \n+test_diff_frobnitz \"patience\"\n \n-// Frobs foo heartily\n-int frobnitz(int foo)\n-{\n- int i;\n- for(i = 0; i < 10; i++)\n- {\n- printf(\"Your answer is: \");\n- printf(\"%d\\n\", foo);\n- }\n-}\n-\n-int fact(int n)\n-{\n- if(n > 1)\n- {\n- return fact(n-1) * n;\n- }\n- return 1;\n-}\n-\n-int main(int argc, char **argv)\n-{\n- frobnitz(fact(10));\n-}\n-EOF\n-\n-cat >file2 <<\\EOF\n-#include \n-\n-int fib(int n)\n-{\n- if(n > 2)\n- {\n- return fib(n-1) + fib(n-2);\n- }\n- return 1;\n-}\n-\n-// Frobs foo heartily\n-int frobnitz(int foo)\n-{\n- int i;\n- for(i = 0; i < 10; i++)\n- {\n- printf(\"%d\\n\", foo);\n- }\n-}\n-\n-int main(int argc, char **argv)\n-{\n- frobnitz(fib(10));\n-}\n-EOF\n-\n-cat >expect <<\\EOF\n-diff --git a/file1 b/file2\n-index 6faa5a3..e3af329 100644\n---- a/file1\n-+++ b/file2\n-@@ -1,26 +1,25 @@\n- #include \n- \n-+int fib(int n)\n-+{\n-+ if(n > 2)\n-+ {\n-+ return fib(n-1) + fib(n-2);\n-+ }\n-+ return 1;\n-+}\n-+\n- // Frobs foo heartily\n- int frobnitz(int foo)\n- {\n- int i;\n- for(i = 0; i < 10; i++)\n- {\n-- printf(\"Your answer is: \");\n- printf(\"%d\\n\", foo);\n- }\n- }\n- \n--int fact(int n)\n--{\n-- if(n > 1)\n-- {\n-- return fact(n-1) * n;\n-- }\n-- return 1;\n--}\n--\n- int main(int argc, char **argv)\n- {\n-- frobnitz(fact(10));\n-+ frobnitz(fib(10));\n- }\n-EOF\n-\n-test_expect_success 'patience diff' '\n-\n-\ttest_must_fail git diff --no-index --patience file1 file2 > output &&\n-\ttest_cmp expect output\n-\n-'\n-\n-test_expect_success 'patience diff output is valid' '\n-\n-\tmv file2 expect &&\n-\tgit apply < output &&\n-\ttest_cmp expect file2\n-\n-'\n-\n-cat >uniq1 <<\\EOF\n-1\n-2\n-3\n-4\n-5\n-6\n-EOF\n-\n-cat >uniq2 <<\\EOF\n-a\n-b\n-c\n-d\n-e\n-f\n-EOF\n-\n-cat >expect <<\\EOF\n-diff --git a/uniq1 b/uniq2\n-index b414108..0fdf397 100644\n---- a/uniq1\n-+++ b/uniq2\n-@@ -1,6 +1,6 @@\n--1\n--2\n--3\n--4\n--5\n--6\n-+a\n-+b\n-+c\n-+d\n-+e\n-+f\n-EOF\n-\n-test_expect_success 'completely different files' '\n-\n-\ttest_must_fail git diff --no-index --patience uniq1 uniq2 > output &&\n-\ttest_cmp expect output\n-\n-'\n+test_diff_unique \"patience\"\n \n test_done\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172492","messageId":"1312168608-10828-7-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312168608-10828-6-git-send-email-rctay89@gmail.com","subject":"[PATCH v2 6/8] teach --histogram to diff","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T03:16:46Z","receivedAt":"2011-08-01T03:16:46Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Port JGit's HistogramDiff algorithm over to C. Rough numbers (TODO) show\nthat it is faster than its --patience cousin, as well as the default\nMeyers algorithm.\n\nThe implementation has been reworked to use structs and pointers,\ninstead of bitmasks, thus doing away with JGit's 2^28 line limit.\n\nWe also use xdiff's default hash table implementation (xdl_hash_bits()\nwith XDL_HASHLONG()) for convenience.\n\nSigned-off-by: Tay Ray Chuan \n---\n\nChanges in v2:\n - changed handling of recursed results\n - do away with reduce_common_start_end(), as use xdiff's\n xdl_trim_ends()\n\nOn Wed, Jul 13, 2011 at 3:56 AM, Junio C Hamano wrote:\n>[snip]\n>> + reduce_common_start_end(xpp, env, &line1, &count1, &line2, &count2);\n>\n> What this does is logically not specific to histogram algorithm but can be\n> applied to other backends, no? And I vaguely recall that Linus did try\n> something like this once, found some issues with it when context is set to\n> non zero, and stopped doing it (sorry, I do not have any more details).\n>\n> I am not suggesting you to remove this call or hoist the call to one level\n> up to xdl_do_diff(), but I do have to wonder how much of the performance\n> improvement you reported is due to this common head/tail reduction.\n\nI believe this was the patch by Linus you were referring to:\n\n https://lkml.org/lkml/2007/12/20/692\n\nThat is an optimization on a more aggressive level - cutting out\ncontent so that it doesn't get hashed in the first place. The\noptimization used here (reduce_common_start_end()/xdl_trim_ends())\ndepends on the hashed result and simply reduces the \"area\" on which the\nalgorithm is applied to.\n\n(Actually, I do have a working patch that does content trimming that is\ncontext-length safe. But it's not specific to histogram so I'll keep it\nwith me till this series gets merged.)\n\n Makefile | 2 +-\n diff.c | 2 +\n merge-recursive.c | 2 +\n t/t4048-diff-histogram.sh | 12 ++\n xdiff/xdiff.h | 1 +\n xdiff/xdiffi.c | 3 +\n xdiff/xdiffi.h | 2 +\n xdiff/xhistogram.c | 360 +++++++++++++++++++++++++++++++++++++++++++++\n 8 files changed, 383 insertions(+), 1 deletions(-)\n create mode 100755 t/t4048-diff-histogram.sh\n create mode 100644 xdiff/xhistogram.c\n\ndiff --git a/Makefile b/Makefile\nindex 775ee83..9930e6b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1836,7 +1836,7 @@ ifndef NO_CURL\n \tGIT_OBJS += http.o http-walker.o remote-curl.o\n endif\n XDIFF_OBJS = xdiff/xdiffi.o xdiff/xprepare.o xdiff/xutils.o xdiff/xemit.o \\\n-\txdiff/xmerge.o xdiff/xpatience.o\n+\txdiff/xmerge.o xdiff/xpatience.o xdiff/xhistogram.o\n VCSSVN_OBJS = vcs-svn/string_pool.o vcs-svn/line_buffer.o \\\n \tvcs-svn/repo_tree.o vcs-svn/fast_export.o vcs-svn/svndump.o\n VCSSVN_TEST_OBJS = test-obj-pool.o test-string-pool.o \\\ndiff --git a/diff.c b/diff.c\nindex 5422c43..a113294 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -3186,6 +3186,8 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac)\n \t\tDIFF_XDL_SET(options, IGNORE_WHITESPACE_AT_EOL);\n \telse if (!strcmp(arg, \"--patience\"))\n \t\tDIFF_XDL_SET(options, PATIENCE_DIFF);\n+\telse if (!strcmp(arg, \"--histogram\"))\n+\t\tDIFF_XDL_SET(options, HISTOGRAM_DIFF);\n \n \t/* flags options */\n \telse if (!strcmp(arg, \"--binary\")) {\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 16c2dbe..3e8267b 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -1773,6 +1773,8 @@ int parse_merge_opt(struct merge_options *o, const char *s)\n \t\to->subtree_shift = s + strlen(\"subtree=\");\n \telse if (!strcmp(s, \"patience\"))\n \t\to->xdl_opts |= XDF_PATIENCE_DIFF;\n+\telse if (!strcmp(s, \"histogram\"))\n+\t\to->xdl_opts |= XDF_HISTOGRAM_DIFF;\n \telse if (!strcmp(s, \"ignore-space-change\"))\n \t\to->xdl_opts |= XDF_IGNORE_WHITESPACE_CHANGE;\n \telse if (!strcmp(s, \"ignore-all-space\"))\ndiff --git a/t/t4048-diff-histogram.sh b/t/t4048-diff-histogram.sh\nnew file mode 100755\nindex 0000000..fd3e86a\n--- /dev/null\n+++ b/t/t4048-diff-histogram.sh\n@@ -0,0 +1,12 @@\n+#!/bin/sh\n+\n+test_description='histogram diff algorithm'\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/lib-diff-alternative.sh\n+\n+test_diff_frobnitz \"histogram\"\n+\n+test_diff_unique \"histogram\"\n+\n+test_done\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex 6ea1d0e..4beb10c 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -33,6 +33,7 @@ extern \"C\" {\n #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)\n #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4)\n #define XDF_PATIENCE_DIFF (1 << 5)\n+#define XDF_HISTOGRAM_DIFF (1 << 6)\n #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL)\n \n #define XDL_PATCH_NORMAL '-'\ndiff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c\nindex da67c04..75a3922 100644\n--- a/xdiff/xdiffi.c\n+++ b/xdiff/xdiffi.c\n@@ -331,6 +331,9 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \tif (xpp->flags & XDF_PATIENCE_DIFF)\n \t\treturn xdl_do_patience_diff(mf1, mf2, xpp, xe);\n \n+\tif (xpp->flags & XDF_HISTOGRAM_DIFF)\n+\t\treturn xdl_do_histogram_diff(mf1, mf2, xpp, xe);\n+\n \tif (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {\n \n \t\treturn -1;\ndiff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h\nindex ad033a8..7a92ea9 100644\n--- a/xdiff/xdiffi.h\n+++ b/xdiff/xdiffi.h\n@@ -57,5 +57,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,\n \t\t xdemitconf_t const *xecfg);\n int xdl_do_patience_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\txdfenv_t *env);\n+int xdl_do_histogram_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n+\t\txdfenv_t *env);\n \n #endif /* #if !defined(XDIFFI_H) */\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nnew file mode 100644\nindex 0000000..4af99f0\n--- /dev/null\n+++ b/xdiff/xhistogram.c\n@@ -0,0 +1,360 @@\n+/*\n+ * Copyright (C) 2010, Google Inc.\n+ * and other copyright owners as documented in JGit's IP log.\n+ *\n+ * This program and the accompanying materials are made available\n+ * under the terms of the Eclipse Distribution License v1.0 which\n+ * accompanies this distribution, is reproduced below, and is\n+ * available at http://www.eclipse.org/org/documents/edl-v10.php\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Eclipse Foundation, Inc. nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+#include \"xinclude.h\"\n+#include \"xtypes.h\"\n+#include \"xdiff.h\"\n+\n+#define MAX_PTR\tUINT_MAX\n+#define MAX_CNT\tUINT_MAX\n+\n+#define LINE_END(n) (line##n + count##n - 1)\n+#define LINE_END_PTR(n) (*line##n + *count##n - 1)\n+\n+struct histindex {\n+\tstruct record {\n+\t\tunsigned int ptr, cnt;\n+\t\tstruct record *next;\n+\t} **records, /* an ocurrence */\n+\t **line_map; /* map of line to record chain */\n+\tchastore_t rcha;\n+\tunsigned int *next_ptrs;\n+\tunsigned int table_bits,\n+\t\t records_size,\n+\t\t line_map_size;\n+\n+\tunsigned int max_chain_length,\n+\t\t key_shift,\n+\t\t ptr_shift;\n+\n+\tunsigned int cnt,\n+\t\t has_common;\n+\n+\txdfenv_t *env;\n+\txpparam_t const *xpp;\n+};\n+\n+struct region {\n+\tunsigned int begin1, end1;\n+\tunsigned int begin2, end2;\n+};\n+\n+#define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift])\n+\n+#define NEXT_PTR(index, ptr) \\\n+\t(index->next_ptrs[(ptr) - index->ptr_shift])\n+\n+#define CNT(index, ptr) \\\n+\t((LINE_MAP(index, ptr))->cnt)\n+\n+#define REC(env, s, l) \\\n+\t(env->xdf##s.recs[l - 1])\n+\n+static int cmp_recs(xpparam_t const *xpp,\n+\txrecord_t *r1, xrecord_t *r2)\n+{\n+\treturn r1->ha == r2->ha &&\n+\t\txdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,\n+\t\t\t xpp->flags);\n+}\n+\n+#define CMP_ENV(xpp, env, s1, l1, s2, l2) \\\n+\t(cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2)))\n+\n+#define CMP(i, s1, l1, s2, l2) \\\n+\t(cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2)))\n+\n+#define TABLE_HASH(index, side, line) \\\n+\tXDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)\n+\n+static int scanA(struct histindex *index, int line1, int count1)\n+{\n+\tunsigned int ptr, tbl_idx;\n+\tunsigned int chain_len;\n+\tstruct record **rec_chain, *rec;\n+\n+\tfor (ptr = LINE_END(1); line1 <= ptr; ptr--) {\n+\t\ttbl_idx = TABLE_HASH(index, 1, ptr);\n+\t\trec_chain = index->records + tbl_idx;\n+\t\trec = *rec_chain;\n+\n+\t\tchain_len = 0;\n+\t\twhile (rec) {\n+\t\t\tif (CMP(index, 1, rec->ptr, 1, ptr)) {\n+\t\t\t\t/*\n+\t\t\t\t * ptr is identical to another element. Insert\n+\t\t\t\t * it onto the front of the existing element\n+\t\t\t\t * chain.\n+\t\t\t\t */\n+\t\t\t\tNEXT_PTR(index, ptr) = rec->ptr;\n+\t\t\t\trec->ptr = ptr;\n+\t\t\t\t/* cap rec->cnt at MAX_CNT */\n+\t\t\t\trec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1);\n+\t\t\t\tLINE_MAP(index, ptr) = rec;\n+\t\t\t\tgoto continue_scan;\n+\t\t\t}\n+\n+\t\t\trec = rec->next;\n+\t\t\tchain_len++;\n+\t\t}\n+\n+\t\tif (chain_len == index->max_chain_length)\n+\t\t\treturn -1;\n+\n+\t\t/*\n+\t\t * This is the first time we have ever seen this particular\n+\t\t * element in the sequence. Construct a new chain for it.\n+\t\t */\n+\t\tif (!(rec = xdl_cha_alloc(&index->rcha)))\n+\t\t\treturn -1;\n+\t\trec->ptr = ptr;\n+\t\trec->cnt = 1;\n+\t\trec->next = *rec_chain;\n+\t\t*rec_chain = rec;\n+\t\tLINE_MAP(index, ptr) = rec;\n+\n+continue_scan:\n+\t\t; /* no op */\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr,\n+\tint line1, int count1, int line2, int count2)\n+{\n+\tunsigned int b_next = b_ptr + 1;\n+\tstruct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)];\n+\tunsigned int as, ae, bs, be, np, rc;\n+\tint should_break;\n+\n+\tfor (; rec; rec = rec->next) {\n+\t\tif (rec->cnt > index->cnt) {\n+\t\t\tif (!index->has_common)\n+\t\t\t\tindex->has_common = CMP(index, 1, rec->ptr, 2, b_ptr);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tas = rec->ptr;\n+\t\tif (!CMP(index, 1, as, 2, b_ptr))\n+\t\t\tcontinue;\n+\n+\t\tindex->has_common = 1;\n+\t\tfor (;;) {\n+\t\t\tshould_break = 0;\n+\t\t\tnp = NEXT_PTR(index, as);\n+\t\t\tbs = b_ptr;\n+\t\t\tae = as;\n+\t\t\tbe = bs;\n+\t\t\trc = rec->cnt;\n+\n+\t\t\twhile (line1 < as && line2 < bs\n+\t\t\t\t&& CMP(index, 1, as - 1, 2, bs - 1)) {\n+\t\t\t\tas--;\n+\t\t\t\tbs--;\n+\t\t\t\tif (1 < rc)\n+\t\t\t\t\trc = XDL_MIN(rc, CNT(index, as));\n+\t\t\t}\n+\t\t\twhile (ae < LINE_END(1) && be < LINE_END(2)\n+\t\t\t\t&& CMP(index, 1, ae + 1, 2, be + 1)) {\n+\t\t\t\tae++;\n+\t\t\t\tbe++;\n+\t\t\t\tif (1 < rc)\n+\t\t\t\t\trc = XDL_MIN(rc, CNT(index, ae));\n+\t\t\t}\n+\n+\t\t\tif (b_next <= be)\n+\t\t\t\tb_next = be + 1;\n+\t\t\tif (lcs->end1 - lcs->begin1 < ae - as || rc < index->cnt) {\n+\t\t\t\tlcs->begin1 = as;\n+\t\t\t\tlcs->begin2 = bs;\n+\t\t\t\tlcs->end1 = ae;\n+\t\t\t\tlcs->end2 = be;\n+\t\t\t\tindex->cnt = rc;\n+\t\t\t}\n+\n+\t\t\tif (np == 0)\n+\t\t\t\tbreak;\n+\n+\t\t\twhile (np <= ae) {\n+\t\t\t\tnp = NEXT_PTR(index, np);\n+\t\t\t\tif (np == 0) {\n+\t\t\t\t\tshould_break = 1;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif (should_break)\n+\t\t\t\tbreak;\n+\n+\t\t\tas = np;\n+\t\t}\n+\t}\n+\treturn b_next;\n+}\n+\n+static int find_lcs(struct histindex *index, struct region *lcs,\n+\tint line1, int count1, int line2, int count2) {\n+\tint b_ptr;\n+\n+\tif (scanA(index, line1, count1))\n+\t\treturn -1;\n+\n+\tindex->cnt = index->max_chain_length + 1;\n+\n+\tfor (b_ptr = line2; b_ptr <= LINE_END(2); )\n+\t\tb_ptr = try_lcs(index, lcs, b_ptr, line1, count1, line2, count2);\n+\n+\treturn index->has_common && index->max_chain_length < index->cnt;\n+}\n+\n+static int fall_back_to_classic_diff(struct histindex *index,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\txpparam_t xpp;\n+\txpp.flags = index->xpp->flags & ~XDF_HISTOGRAM_DIFF;\n+\n+\treturn xdl_fall_back_diff(index->env, &xpp,\n+\t\t\t\t line1, count1, line2, count2);\n+}\n+\n+static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n+\tint line1, int count1, int line2, int count2)\n+{\n+\tstruct histindex index;\n+\tstruct region lcs;\n+\tint sz;\n+\tint result = -1;\n+\n+\tif (count1 <= 0 && count2 <= 0)\n+\t\treturn 0;\n+\n+\tif (LINE_END(1) >= MAX_PTR)\n+\t\treturn -1;\n+\n+\tif (!count1) {\n+\t\twhile(count2--)\n+\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\treturn 0;\n+\t} else if (!count2) {\n+\t\twhile(count1--)\n+\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\treturn 0;\n+\t}\n+\n+\tmemset(&index, 0, sizeof(index));\n+\n+\tindex.env = env;\n+\tindex.xpp = xpp;\n+\n+\tindex.records = NULL;\n+\tindex.line_map = NULL;\n+\t/* in case of early xdl_cha_free() */\n+\tindex.rcha.head = NULL;\n+\n+\tindex.table_bits = xdl_hashbits(count1);\n+\tsz = index.records_size = 1 << index.table_bits;\n+\tsz *= sizeof(struct record *);\n+\tif (!(index.records = (struct record **) xdl_malloc(sz)))\n+\t\tgoto cleanup;\n+\tmemset(index.records, 0, sz);\n+\n+\tsz = index.line_map_size = count1;\n+\tsz *= sizeof(struct record *);\n+\tif (!(index.line_map = (struct record **) xdl_malloc(sz)))\n+\t\tgoto cleanup;\n+\tmemset(index.line_map, 0, sz);\n+\n+\tsz = index.line_map_size;\n+\tsz *= sizeof(unsigned int);\n+\tif (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz)))\n+\t\tgoto cleanup;\n+\tmemset(index.next_ptrs, 0, sz);\n+\n+\t/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */\n+\tif (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)\n+\t\tgoto cleanup;\n+\n+\tindex.ptr_shift = line1;\n+\tindex.max_chain_length = 64;\n+\n+\tmemset(&lcs, 0, sizeof(lcs));\n+\tif (find_lcs(&index, &lcs, line1, count1, line2, count2))\n+\t\tresult = fall_back_to_classic_diff(&index, line1, count1, line2, count2);\n+\telse {\n+\t\tresult = 0;\n+\t\tif (lcs.begin1 == 0 && lcs.begin2 == 0) {\n+\t\t\tint ptr;\n+\t\t\tfor (ptr = 0; ptr < count1; ptr++)\n+\t\t\t\tenv->xdf1.rchg[line1 + ptr - 1] = 1;\n+\t\t\tfor (ptr = 0; ptr < count2; ptr++)\n+\t\t\t\tenv->xdf2.rchg[line2 + ptr - 1] = 1;\n+\t\t} else {\n+\t\t\tresult += histogram_diff(xpp, env,\n+\t\t\t\tline1, lcs.begin1 - line1,\n+\t\t\t\tline2, lcs.begin2 - line2);\n+\t\t\tresult += histogram_diff(xpp, env,\n+\t\t\t\tlcs.end1 + 1, LINE_END(1) - lcs.end1,\n+\t\t\t\tlcs.end2 + 1, LINE_END(2) - lcs.end2);\n+\t\t}\n+\t}\n+\n+cleanup:\n+\txdl_free(index.records);\n+\txdl_free(index.line_map);\n+\txdl_free(index.next_ptrs);\n+\txdl_cha_free(&index.rcha);\n+\n+\treturn result;\n+}\n+\n+int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2,\n+\txpparam_t const *xpp, xdfenv_t *env)\n+{\n+\tif (xdl_prepare_env(file1, file2, xpp, env) < 0)\n+\t\treturn -1;\n+\n+\treturn histogram_diff(xpp, env,\n+\t\tenv->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,\n+\t\tenv->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);\n+}\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172493","messageId":"1312168608-10828-8-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312168608-10828-7-git-send-email-rctay89@gmail.com","subject":"[PATCH v2 7/8] xdiff/xprepare: skip classification","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T03:16:47Z","receivedAt":"2011-08-01T03:16:47Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"xdiff performs \"classification\" of records (xdl_classify_record()),\nreplacing hashes (xrecord_t.ha) with a unique identifier of the\nrecord/line and building a hash table (xrecord_t.rhash) of records. This\nis then used to \"cleanup\" records (xdl_cleanup_records()).\n\nWe don't need any of that in histogram diff, so we omit calls to these\nfunctions. We also skip allocating memory to the hash table, rhash, as\nit is no longer used.\n\nThis gives us a small boost in performance.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xprepare.c | 28 ++++++++++++++++++----------\n 1 files changed, 18 insertions(+), 10 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex 3ebad0f..c139ba8 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -154,11 +154,15 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \tif (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))\n \t\tgoto abort;\n \n-\thbits = xdl_hashbits((unsigned int) narec);\n-\thsize = 1 << hbits;\n-\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n-\t\tgoto abort;\n-\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n+\tif (xpp->flags & XDF_HISTOGRAM_DIFF)\n+\t\thbits = hsize = 0;\n+\telse {\n+\t\thbits = xdl_hashbits((unsigned int) narec);\n+\t\thsize = 1 << hbits;\n+\t\tif (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))\n+\t\t\tgoto abort;\n+\t\tmemset(rhash, 0, hsize * sizeof(xrecord_t *));\n+\t}\n \n \tnrec = 0;\n \tif ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {\n@@ -178,7 +182,8 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \t\t\tcrec->ha = hav;\n \t\t\trecs[nrec++] = crec;\n \n-\t\t\tif (xdl_classify_record(cf, rhash, hbits, crec) < 0)\n+\t\t\tif (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&\n+\t\t\t\txdl_classify_record(cf, rhash, hbits, crec) < 0)\n \t\t\t\tgoto abort;\n \t\t}\n \t}\n@@ -235,7 +240,8 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \tenl1 = xdl_guess_lines(mf1) + 1;\n \tenl2 = xdl_guess_lines(mf2) + 1;\n \n-\tif (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {\n+\tif (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&\n+\t\txdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {\n \n \t\treturn -1;\n \t}\n@@ -252,10 +258,12 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\n \t\treturn -1;\n \t}\n \n-\txdl_free_classifier(&cf);\n+\tif (!(xpp->flags & XDF_HISTOGRAM_DIFF))\n+\t\txdl_free_classifier(&cf);\n \n-\tif (!(xpp->flags & XDF_PATIENCE_DIFF) &&\n-\t\t\txdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {\n+\tif ((xpp->flags & XDF_HISTOGRAM_DIFF) ?\n+\t\txdl_trim_ends(&xe->xdf1, &xe->xdf2) < 0\n+\t\t: (!(xpp->flags & XDF_PATIENCE_DIFF) && xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0)) {\n \n \t\txdl_free_ctx(&xe->xdf2);\n \t\txdl_free_ctx(&xe->xdf1);\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172494","messageId":"1312168608-10828-9-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312168608-10828-8-git-send-email-rctay89@gmail.com","subject":"[PATCH v2 8/8] xdiff/xprepare: use a smaller sample size for histogram diff","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T03:16:48Z","receivedAt":"2011-08-01T03:16:48Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"For histogram diff, we can afford a smaller sample size and thus a\npoorer estimate of the number of lines, as the hash table (rhash) won't\nbe filled up/grown. This is safe as the final count of lines (xdf.nrecs)\nwill be updated correctly anyway by xdl_prepare_ctx().\n\nThis gives us a small boost in performance.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xprepare.c | 17 ++++++++++++++---\n xdiff/xutils.c | 8 ++------\n xdiff/xutils.h | 2 +-\n 3 files changed, 17 insertions(+), 10 deletions(-)\n\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex c139ba8..b4d8402 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -26,6 +26,8 @@\n #define XDL_KPDIS_RUN 4\n #define XDL_MAX_EQLIMIT 1024\n #define XDL_SIMSCAN_WINDOW 100\n+#define XDL_GUESS_NLINES1 256\n+#define XDL_GUESS_NLINES2 20\n \n \n typedef struct s_xdlclass {\n@@ -234,11 +236,20 @@ static void xdl_free_ctx(xdfile_t *xdf) {\n \n 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+\tlong enl1, enl2, sample;\n \txdlclassifier_t cf;\n \n-\tenl1 = xdl_guess_lines(mf1) + 1;\n-\tenl2 = xdl_guess_lines(mf2) + 1;\n+\t/*\n+\t * For histogram diff, we can afford a smaller sample size and\n+\t * thus a poorer estimate of the number of lines, as the hash\n+\t * table (rhash) won't be filled up/grown. The number of lines\n+\t * (nrecs) will be updated correctly anyway by\n+\t * xdl_prepare_ctx().\n+\t */\n+\tsample = xpp->flags & XDF_HISTOGRAM_DIFF ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1;\n+\n+\tenl1 = xdl_guess_lines(mf1, sample) + 1;\n+\tenl2 = xdl_guess_lines(mf2, sample) + 1;\n \n \tif (!(xpp->flags & XDF_HISTOGRAM_DIFF) &&\n \t\txdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex 890cc4f..0de084e 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -24,10 +24,6 @@\n \n \n \n-#define XDL_GUESS_NLINES 256\n-\n-\n-\n \n long xdl_bogosqrt(long n) {\n \tlong i;\n@@ -153,12 +149,12 @@ void *xdl_cha_next(chastore_t *cha) {\n }\n \n \n-long xdl_guess_lines(mmfile_t *mf) {\n+long xdl_guess_lines(mmfile_t *mf, long sample) {\n \tlong nl = 0, size, tsize = 0;\n \tchar const *data, *cur, *top;\n \n \tif ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {\n-\t\tfor (top = data + size; nl < XDL_GUESS_NLINES && cur < top; ) {\n+\t\tfor (top = data + size; nl < sample && cur < top; ) {\n \t\t\tnl++;\n \t\t\tif (!(cur = memchr(cur, '\\n', top - cur)))\n \t\t\t\tcur = top;\ndiff --git a/xdiff/xutils.h b/xdiff/xutils.h\nindex 674a657..714719a 100644\n--- a/xdiff/xutils.h\n+++ b/xdiff/xutils.h\n@@ -33,7 +33,7 @@ void xdl_cha_free(chastore_t *cha);\n void *xdl_cha_alloc(chastore_t *cha);\n void *xdl_cha_first(chastore_t *cha);\n void *xdl_cha_next(chastore_t *cha);\n-long xdl_guess_lines(mmfile_t *mf);\n+long xdl_guess_lines(mmfile_t *mf, long sample);\n int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);\n unsigned long xdl_hash_record(char const **data, char const *top, long flags);\n unsigned int xdl_hashbits(unsigned int size);\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172500","messageId":"1312172410-4380-1-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312168608-10828-1-git-send-email-rctay89@gmail.com","subject":"[PATCH 0/4] changes for rc/histogram-diff in 'next'","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T04:20:06Z","receivedAt":"2011-08-01T04:20:06Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"This is a rebased version of this series:\n\n [PATCH v2 0/8] teach --histogram to diff\n <1312168608-10828-1-git-send-email-rctay89@gmail.com>\n\nI had overlooked that the previous iteration of the series has been\nadded to 'next'.\n\nContents:\n[PATCH 1/4] xdiff: do away with xdl_mmfile_next()\n[PATCH 2/4] xdiff/xhistogram: rework handling of recursed results\n[PATCH 3/4] xdiff/xhistogram: rely on xdl_trim_ends()\n[PATCH 4/4] xdiff/xhistogram: drop need for additional variable\n\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172502","messageId":"1312172410-4380-2-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312172410-4380-1-git-send-email-rctay89@gmail.com","subject":"[PATCH 1/4] xdiff: do away with xdl_mmfile_next()","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T04:20:07Z","receivedAt":"2011-08-01T04:20:07Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Given our simple mmfile structure, xdl_mmfile_next() calls are\nredundant. Do away with calls to them.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xdiff.h | 1 -\n xdiff/xprepare.c | 7 +------\n xdiff/xutils.c | 14 +-------------\n 3 files changed, 2 insertions(+), 20 deletions(-)\n\ndiff --git a/xdiff/xdiff.h b/xdiff/xdiff.h\nindex c26170c..4beb10c 100644\n--- a/xdiff/xdiff.h\n+++ b/xdiff/xdiff.h\n@@ -106,7 +106,6 @@ typedef struct s_bdiffparam {\n #define xdl_realloc(ptr,x) realloc(ptr,x)\n \n void *xdl_mmfile_first(mmfile_t *mmf, long *size);\n-void *xdl_mmfile_next(mmfile_t *mmf, long *size);\n long xdl_mmfile_size(mmfile_t *mmf);\n \n int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,\ndiff --git a/xdiff/xprepare.c b/xdiff/xprepare.c\nindex dfbb0de..620fc9a 100644\n--- a/xdiff/xprepare.c\n+++ b/xdiff/xprepare.c\n@@ -168,12 +168,7 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,\n \n \tnrec = 0;\n \tif ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {\n-\t\tfor (top = blk + bsize;;) {\n-\t\t\tif (cur >= top) {\n-\t\t\t\tif (!(cur = blk = xdl_mmfile_next(mf, &bsize)))\n-\t\t\t\t\tbreak;\n-\t\t\t\ttop = blk + bsize;\n-\t\t\t}\n+\t\tfor (top = blk + bsize; cur < top; ) {\n \t\t\tprev = cur;\n \t\t\thav = xdl_hash_record(&cur, top, xpp->flags);\n \t\t\tif (nrec >= narec) {\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex a45e89b..0de084e 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -67,12 +67,6 @@ void *xdl_mmfile_first(mmfile_t *mmf, long *size)\n }\n \n \n-void *xdl_mmfile_next(mmfile_t *mmf, long *size)\n-{\n-\treturn NULL;\n-}\n-\n-\n long xdl_mmfile_size(mmfile_t *mmf)\n {\n \treturn mmf->size;\n@@ -160,13 +154,7 @@ long xdl_guess_lines(mmfile_t *mf, long sample) {\n \tchar const *data, *cur, *top;\n \n \tif ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {\n-\t\tfor (top = data + size; nl < sample;) {\n-\t\t\tif (cur >= top) {\n-\t\t\t\ttsize += (long) (cur - data);\n-\t\t\t\tif (!(cur = data = xdl_mmfile_next(mf, &size)))\n-\t\t\t\t\tbreak;\n-\t\t\t\ttop = data + size;\n-\t\t\t}\n+\t\tfor (top = data + size; nl < sample && cur < top; ) {\n \t\t\tnl++;\n \t\t\tif (!(cur = memchr(cur, '\\n', top - cur)))\n \t\t\t\tcur = top;\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172501","messageId":"1312172410-4380-3-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312172410-4380-2-git-send-email-rctay89@gmail.com","subject":"[PATCH 2/4] xdiff/xhistogram: rework handling of recursed results","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T04:20:08Z","receivedAt":"2011-08-01T04:20:08Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Previously we were over-complicating matters by trying to combine the\nrecursed results. Now, terminate immediately if a recursive call failed\nand return its result.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xhistogram.c | 13 +++++++------\n 1 files changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nindex 391333a..9cb69ea 100644\n--- a/xdiff/xhistogram.c\n+++ b/xdiff/xhistogram.c\n@@ -339,21 +339,22 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n \tif (find_lcs(&index, &lcs, line1, count1, line2, count2))\n \t\tresult = fall_back_to_classic_diff(&index, line1, count1, line2, count2);\n \telse {\n-\t\tresult = 0;\n \t\tif (lcs.begin1 == 0 && lcs.begin2 == 0) {\n \t\t\tint ptr;\n \t\t\tfor (ptr = 0; ptr < count1; ptr++)\n \t\t\t\tenv->xdf1.rchg[line1 + ptr - 1] = 1;\n \t\t\tfor (ptr = 0; ptr < count2; ptr++)\n \t\t\t\tenv->xdf2.rchg[line2 + ptr - 1] = 1;\n+\t\t\tresult = 0;\n \t\t} else {\n-\t\t\tresult = histogram_diff(xpp, env,\n+\t\t\tif (result = histogram_diff(xpp, env,\n \t\t\t\tline1, lcs.begin1 - line1,\n-\t\t\t\tline2, lcs.begin2 - line2);\n-\t\t\tresult = histogram_diff(xpp, env,\n+\t\t\t\tline2, lcs.begin2 - line2))\n+\t\t\t\tgoto cleanup;\n+\t\t\tif (result = histogram_diff(xpp, env,\n \t\t\t\tlcs.end1 + 1, LINE_END(1) - lcs.end1,\n-\t\t\t\tlcs.end2 + 1, LINE_END(2) - lcs.end2);\n-\t\t\tresult *= -1;\n+\t\t\t\tlcs.end2 + 1, LINE_END(2) - lcs.end2))\n+\t\t\t\tgoto cleanup;\n \t\t}\n \t}\n \n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172503","messageId":"1312172410-4380-4-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312172410-4380-3-git-send-email-rctay89@gmail.com","subject":"[PATCH 3/4] xdiff/xhistogram: rely on xdl_trim_ends()","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T04:20:09Z","receivedAt":"2011-08-01T04:20:09Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Do away with reduce_common_start_end() and use xdf->dstart and xdf->dend\nset by xdl_trim_ends() that similarly tells us where the first unmatched\nline from the start and end occurs.\n\nSigned-off-by: Tay Ray Chuan \n---\n\nOn Wed, Jul 13, 2011 at 3:56 AM, Junio C Hamano wrote:\n>[snip]\n>> + reduce_common_start_end(xpp, env, &line1, &count1, &line2, &count2);\n>\n> What this does is logically not specific to histogram algorithm but can be\n> applied to other backends, no? And I vaguely recall that Linus did try\n> something like this once, found some issues with it when context is set to\n> non zero, and stopped doing it (sorry, I do not have any more details).\n>\n> I am not suggesting you to remove this call or hoist the call to one level\n> up to xdl_do_diff(), but I do have to wonder how much of the performance\n> improvement you reported is due to this common head/tail reduction.\n\nIn a way, this patch is a response to Junio's email. It just made sense\nto use existing functionality in xdiff (xdl_trim_ends() and xdf->dstart\nand dend) over writing a new one (reduce_common_start_end()).\n\nI believe Junio was referring to this patch by Linus:\n\n https://lkml.org/lkml/2007/12/20/692\n\nThat is an optimization on a more aggressive level - cutting out\ncontent so that it doesn't get hashed in the first place. The\noptimization used here (reduce_common_start_end()/xdl_trim_ends())\ndepends on the hashed result and simply reduces the \"area\" on which the\nalgorithm is applied to.\n\n(Actually, I do have a working patch that does content trimming that is\ncontext-length safe. But it's not specific to histogram so I'll keep it\nwith me till this series gets merged, lest it holds up the series.)\n\n xdiff/xhistogram.c | 31 ++++---------------------------\n 1 files changed, 4 insertions(+), 27 deletions(-)\n\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nindex 9cb69ea..804e19b 100644\n--- a/xdiff/xhistogram.c\n+++ b/xdiff/xhistogram.c\n@@ -102,7 +102,7 @@ static int cmp_recs(xpparam_t const *xpp,\n \t(cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2)))\n \n #define CMP(i, s1, l1, s2, l2) \\\n-\t(CMP_ENV(i->xpp, i->env, s1, l1, s2, l2))\n+\t(cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2)))\n \n #define TABLE_HASH(index, side, line) \\\n \tXDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)\n@@ -248,23 +248,6 @@ static int find_lcs(struct histindex *index, struct region *lcs,\n \treturn index->has_common && index->max_chain_length < index->cnt;\n }\n \n-static void reduce_common_start_end(xpparam_t const *xpp, xdfenv_t *env,\n-\tint *line1, int *count1, int *line2, int *count2)\n-{\n-\tif (*count1 <= 1 || *count2 <= 1)\n-\t\treturn;\n-\twhile (*count1 > 1 && *count2 > 1 && CMP_ENV(xpp, env, 1, *line1, 2, *line2)) {\n-\t\t(*line1)++;\n-\t\t(*count1)--;\n-\t\t(*line2)++;\n-\t\t(*count2)--;\n-\t}\n-\twhile (*count1 > 1 && *count2 > 1 && CMP_ENV(xpp, env, 1, LINE_END_PTR(1), 2, LINE_END_PTR(2))) {\n-\t\t(*count1)--;\n-\t\t(*count2)--;\n-\t}\n-}\n-\n static int fall_back_to_classic_diff(struct histindex *index,\n \t\tint line1, int count1, int line2, int count2)\n {\n@@ -370,16 +353,10 @@ cleanup:\n int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2,\n \txpparam_t const *xpp, xdfenv_t *env)\n {\n-\tint line1, line2, count1, count2;\n-\n \tif (xdl_prepare_env(file1, file2, xpp, env) < 0)\n \t\treturn -1;\n \n-\tline1 = line2 = 1;\n-\tcount1 = env->xdf1.nrec;\n-\tcount2 = env->xdf2.nrec;\n-\n-\treduce_common_start_end(xpp, env, &line1, &count1, &line2, &count2);\n-\n-\treturn histogram_diff(xpp, env, line1, count1, line2, count2);\n+\treturn histogram_diff(xpp, env,\n+\t\tenv->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,\n+\t\tenv->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);\n }\n-- \n1.7.3.4.730.g67af1.dirty\n"},{"id":"172504","messageId":"1312172410-4380-5-git-send-email-rctay89@gmail.com","threadId":"27792","inReplyTo":"1312172410-4380-4-git-send-email-rctay89@gmail.com","subject":"[PATCH 4/4] xdiff/xhistogram: drop need for additional variable","fromName":"Tay Ray Chuan","fromEmail":"rctay89@gmail.com","sentAt":"2011-08-01T04:20:10Z","receivedAt":"2011-08-01T04:20:10Z","isPatch":true,"sender":{"key":"rctay89@gmail.com","avatar":"https://avatars.githubusercontent.com/u/61553?v=4"},"body":"Having an additional variable (ptr) instead of changing line(1|2) and\ncount(1|2) was for debugging purposes.\n\nSigned-off-by: Tay Ray Chuan \n---\n xdiff/xhistogram.c | 9 ++++-----\n 1 files changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nindex 804e19b..3201fc5 100644\n--- a/xdiff/xhistogram.c\n+++ b/xdiff/xhistogram.c\n@@ -323,11 +323,10 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n \t\tresult = fall_back_to_classic_diff(&index, line1, count1, line2, count2);\n \telse {\n \t\tif (lcs.begin1 == 0 && lcs.begin2 == 0) {\n-\t\t\tint ptr;\n-\t\t\tfor (ptr = 0; ptr < count1; ptr++)\n-\t\t\t\tenv->xdf1.rchg[line1 + ptr - 1] = 1;\n-\t\t\tfor (ptr = 0; ptr < count2; ptr++)\n-\t\t\t\tenv->xdf2.rchg[line2 + ptr - 1] = 1;\n+\t\t\twhile (count1--)\n+\t\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\t\twhile (count2--)\n+\t\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n \t\t\tresult = 0;\n \t\t} else {\n \t\t\tif (result = histogram_diff(xpp, env,\n-- \n1.7.3.4.730.g67af1.dirty\n"}]}