[PATCH 2 of 2] bdiff: early pruning of common suffix before doing expensive computations

Mads Kiilerich mads at kiilerich.com
Thu Nov 17 12:16:40 EST 2016


# HG changeset patch
# User Mads Kiilerich <madski at unity3d.com>
# Date 1479322051 -3600
#      Wed Nov 16 19:47:31 2016 +0100
# Node ID 851a14d5b80639efe61bd01ad215479c99106b40
# Parent  7f39bccc1c96bffc83f3c6e774da57ecd38982a7
bdiff: early pruning of common suffix before doing expensive computations

Similar to the previous change, but trimming trailing lines.

On mozilla-unified:
perfbdiff -m 3041e4d59df2
! wall 0.024618 comb 0.020000 user 0.020000 sys 0.000000 (best of 116) to
! wall 0.008259 comb 0.010000 user 0.010000 sys 0.000000 (best of 356) to
perfbdiff 0e9928989e9c --alldata --count 10
! wall 0.579235 comb 0.580000 user 0.580000 sys 0.000000 (best of 18)
! wall 0.469869 comb 0.460000 user 0.460000 sys 0.000000 (best of 22)

diff --git a/mercurial/bdiff_module.c b/mercurial/bdiff_module.c
--- a/mercurial/bdiff_module.c
+++ b/mercurial/bdiff_module.c
@@ -66,7 +66,7 @@ static PyObject *bdiff(PyObject *self, P
 	struct bdiff_line *al, *bl;
 	struct bdiff_hunk l, *h;
 	int an, bn, count;
-	Py_ssize_t len = 0, la, lb, li = 0, lcommon = 0, lmax;
+	Py_ssize_t len = 0, la, lb, li = 0, lcommon = 0, lcommonend = 0, lmax;
 	PyThreadState *_save;
 
 	l.next = NULL;
@@ -88,9 +88,16 @@ static PyObject *bdiff(PyObject *self, P
 		if (*ia == '\n')
 			lcommon = li + 1;
 	/* we can almost add: if (li == lmax) lcommon = li; */
+	lmax -= lcommon;
+	for (li = 0, ia = sa + la - 1, ib = sb + lb - 1;
+	     li <= lmax && *ia == *ib;
+	     ++li, --ia, --ib)
+		if (*ia == '\n')
+			lcommonend = li;
+	/* printf("common %i %i\n", lcommon, lcommonend); */
 
-	an = bdiff_splitlines(sa + lcommon, la - lcommon, &al);
-	bn = bdiff_splitlines(sb + lcommon, lb - lcommon, &bl);
+	an = bdiff_splitlines(sa + lcommon, la - lcommon - lcommonend, &al);
+	bn = bdiff_splitlines(sb + lcommon, lb - lcommon - lcommonend, &bl);
 	if (!al || !bl)
 		goto nomem;
 
diff --git a/tests/test-bdiff.py.out b/tests/test-bdiff.py.out
--- a/tests/test-bdiff.py.out
+++ b/tests/test-bdiff.py.out
@@ -28,9 +28,9 @@ showdiff(
   'x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n'):
  'x\n\nx\n\n'
  6 6 '' -> 'y\n\n'
- 'x\n\n'
- 9 9 '' -> 'y\n\n'
- 'x\n\nz\n'
+ 'x\n'
+ 8 8 '' -> '\ny\n'
+ '\nx\n\nz\n'
 showdiff(
   'a\nb\nb\nb\nc\n.\nd\ne\n.\nf\n',
   'a\nb\nb\na\nb\nb\nb\nc\n.\nb\nc\n.\nd\ne\nf\n'):
diff --git a/tests/test-check-code.t b/tests/test-check-code.t
--- a/tests/test-check-code.t
+++ b/tests/test-check-code.t
@@ -15,10 +15,6 @@ New errors are not allowed. Warnings are
   Skipping hgext/fsmonitor/pywatchman/msc_stdint.h it has no-che?k-code (glob)
   Skipping hgext/fsmonitor/pywatchman/pybser.py it has no-che?k-code (glob)
   Skipping i18n/polib.py it has no-che?k-code (glob)
-  mercurial/bdiff_module.c:89:
-   > 	//printf("common prefix: %i next line: %i\n", li, llf);
-   don't use //-style comments
   Skipping mercurial/httpclient/__init__.py it has no-che?k-code (glob)
   Skipping mercurial/httpclient/_readers.py it has no-che?k-code (glob)
   Skipping mercurial/statprof.py it has no-che?k-code (glob)
-  [1]


More information about the Mercurial-devel mailing list