diff options
| author |  René Scharfe <rene.scharfe@lsrfire.ath.cx> | 2011-09-25 21:39:08 +0800 |
|---|---|---|
| committer |  Junio C Hamano <gitster@pobox.com> | 2011-09-26 11:38:14 -0700 |
| commit | c5aa90682f82fe0dabdc0280be93568d52efddfc (patch) | |
| tree | 1aad9b101300368bdbb9c60f84f48f3279ef9ca5 | |
| parent | xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records() (diff) | |
| download | tgif-c5aa90682f82fe0dabdc0280be93568d52efddfc.tar.xz | |
Revert removal of multi-match discard heuristic in 27af01
27af01d (xdiff/xprepare: improve O(n*m) performance in
xdl_cleanup_records(), 2011-08-17) was supposed to be a performance
boost only. However, it unexpectedly changed the behaviour of diff.
Revert a part of 27af01d that removes logic that mark lines as
"multi-match" (ie. dis[i] == 2). This was preventing the multi-match
discard heuristic (performed in xdl_cleanup_records() and
xdl_clean_mmatch()) from executing.
Reported-by: Alexander Pepper <pepper@inf.fu-berlin.de>
Signed-off-by: René Scharfe <rene.scharfe@lsrfire.ath.cx>
Signed-off-by: Tay Ray Chuan <rctay89@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
| -rw-r--r-- | xdiff/xprepare.c | 10 |
1 files changed, 7 insertions, 3 deletions
diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index 05a8f01f38..4c447ca6d2 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -398,7 +398,7 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { * might be potentially discarded if they happear in a run of discardable. */ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { - long i, nm, nreff; + long i, nm, nreff, mlim; xrecord_t **recs; xdlclass_t *rcrec; char *dis, *dis1, *dis2; @@ -411,16 +411,20 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd dis1 = dis; dis2 = dis1 + xdf1->nrec + 1; + if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT) + mlim = XDL_MAX_EQLIMIT; for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { rcrec = cf->rcrecs[(*recs)->ha]; nm = rcrec ? rcrec->len2 : 0; - dis1[i] = (nm == 0) ? 0: 1; + dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1; } + if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT) + mlim = XDL_MAX_EQLIMIT; for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { rcrec = cf->rcrecs[(*recs)->ha]; nm = rcrec ? rcrec->len1 : 0; - dis2[i] = (nm == 0) ? 0: 1; + dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1; } for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; |