diff --git a/mercurial/bdiff.c b/mercurial/bdiff.c
--- a/mercurial/bdiff.c
+++ b/mercurial/bdiff.c
@@ -148,7 +148,7 @@ static int equatelines(struct line *a, i
 static int longest_match(struct line *a, struct line *b, struct pos *pos,
 			 int a1, int a2, int b1, int b2, int *omi, int *omj)
 {
-	int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k;
+	int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k, half = (a1 + a2) / 2;
 
 	for (i = a1; i < a2; i++) {
 		/* skip all lines in b after the current block */
@@ -165,8 +165,9 @@ static int longest_match(struct line *a,
 			pos[j].pos = i;
 			pos[j].len = k;
 
-			/* best match so far? */
-			if (k > mk || (k == mk && i <= mi)) {
+			/* best match so far? we prefer matches closer
+			   to the middle to balance recursion */
+			if (k > mk || (k == mk && (i <= mi || i < half))) {
 				mi = i;
 				mj = j;
 				mk = k;
diff --git a/tests/test-issue4074.t b/tests/test-issue4074.t
new file mode 100644
--- /dev/null
+++ b/tests/test-issue4074.t
@@ -0,0 +1,29 @@
+#require no-pure
+
+A script to generate nasty diff worst-case scenarios:
+
+  $ cat > s.py <<EOF
+  > import random
+  > for x in xrange(100000):
+  >     print
+  >     if random.randint(0, 100) >= 50:
+  >         x += 1
+  >     print hex(x)
+  > EOF
+
+  $ hg init a
+  $ cd a
+
+Check in a big file:
+
+  $ python ../s.py > a
+  $ hg ci -qAm0
+
+Modify it:
+
+  $ python ../s.py > a
+
+Time a check-in, should never take more than 10 seconds user time:
+
+  $ hg ci --time -m1
+  time: real .* secs .user [0-9][.].* sys .* (re)