[PATCH 3/4] xdiff/xhistogram: rely on xdl_trim_ends()
- From
Tay Ray Chuan <rctay89@gmail.com>
- Date
- Aug 1, 2011, 04:20 UTC
- Message-ID
- <1312172410-4380-4-git-send-email-rctay89@gmail.com>
- In-Reply-To
- <1312172410-4380-3-git-send-email-rctay89@gmail.com>
Do away with reduce_common_start_end() and use xdf->dstart and xdf->dend set by xdl_trim_ends() that similarly tells us where the first unmatched line from the start and end occurs.
Signed-off-by: Tay Ray Chuan <rctay89@gmail.com> ---
On Wed, Jul 13, 2011 at 3:56 AM, Junio C Hamano <gitster@pobox.com> wrote:
Show 11 quoted lines
>[snip] >> + reduce_common_start_end(xpp, env, &line1, &count1, &line2, &count2); > > What this does is logically not specific to histogram algorithm but can be > applied to other backends, no? And I vaguely recall that Linus did try > something like this once, found some issues with it when context is set to > non zero, and stopped doing it (sorry, I do not have any more details). > > I am not suggesting you to remove this call or hoist the call to one level > up to xdl_do_diff(), but I do have to wonder how much of the performance > improvement you reported is due to this common head/tail reduction.
In a way, this patch is a response to Junio's email. It just made sense to use existing functionality in xdiff (xdl_trim_ends() and xdf->dstart and dend) over writing a new one (reduce_common_start_end()).
I believe Junio was referring to this patch by Linus:
https://lkml.org/lkml/2007/12/20/692
That is an optimization on a more aggressive level - cutting out content so that it doesn't get hashed in the first place. The optimization used here (reduce_common_start_end()/xdl_trim_ends()) depends on the hashed result and simply reduces the "area" on which the algorithm is applied to.
(Actually, I do have a working patch that does content trimming that is context-length safe. But it's not specific to histogram so I'll keep it with me till this series gets merged, lest it holds up the series.)
xdiff/xhistogram.c | 31 ++++--------------------------- 1 files changed, 4 insertions(+), 27 deletions(-)
diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index 9cb69ea..804e19b 100644 --- a/xdiff/xhistogram.c +++ b/xdiff/xhistogram.c @@ -102,7 +102,7 @@ static int cmp_recs(xpparam_t const *xpp, (cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2))) #define CMP(i, s1, l1, s2, l2) \ - (CMP_ENV(i->xpp, i->env, s1, l1, s2, l2)) + (cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2))) #define TABLE_HASH(index, side, line) \ XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits) @@ -248,23 +248,6 @@ static int find_lcs(struct histindex *index, struct region *lcs, return index->has_common && index->max_chain_length < index->cnt; } -static void reduce_common_start_end(xpparam_t const *xpp, xdfenv_t *env, - int *line1, int *count1, int *line2, int *count2) -{ - if (*count1 <= 1 || *count2 <= 1) - return; - while (*count1 > 1 && *count2 > 1 && CMP_ENV(xpp, env, 1, *line1, 2, *line2)) { - (*line1)++; - (*count1)--; - (*line2)++; - (*count2)--; - } - while (*count1 > 1 && *count2 > 1 && CMP_ENV(xpp, env, 1, LINE_END_PTR(1), 2, LINE_END_PTR(2))) { - (*count1)--; - (*count2)--; - } -} - static int fall_back_to_classic_diff(struct histindex *index, int line1, int count1, int line2, int count2) { @@ -370,16 +353,10 @@ cleanup: int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2, xpparam_t const *xpp, xdfenv_t *env) { - int line1, line2, count1, count2; - if (xdl_prepare_env(file1, file2, xpp, env) < 0) return -1; - line1 = line2 = 1; - count1 = env->xdf1.nrec; - count2 = env->xdf2.nrec; - - reduce_common_start_end(xpp, env, &line1, &count1, &line2, &count2); - - return histogram_diff(xpp, env, line1, count1, line2, count2); + return histogram_diff(xpp, env, + env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1, + env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1); }
-- 1.7.3.4.730.g67af1.dirty