bdiff: further restrain potential quadratic performance stable
authorMatt Mackall <mpm@selenic.com>
Fri, 22 Apr 2016 13:38:02 -0500
branchstable
changeset 29015 87d4a6c5567e
parent 29014 f1ca249696ed
child 29016 94451300f3ec
bdiff: further restrain potential quadratic performance This causes the longest_match search to limit itself to a window of 30000 lines during search (roughly 1MB), thus avoiding a full O(N*M) search that might occur in repetitive structured inputs. For a particular class of many MB pathological test cases, this generated the following timings: size before after 10x 1.25s 1.24s 100x 57s 33s 1000x >8400s 400s The times on the right quickly become much faster and appear more linear. While windowing means deltas are no longer "optimal", the resulting deltas were within a couple percent of expected size. While we've yet to have a report of a file with the level of repetition necessary to hit this case, some JSON/XML database dump scenario is fairly likely to hit it. This may also slightly improve the average-case performance for deltas of large binaries.
mercurial/bdiff.c
--- a/mercurial/bdiff.c	Thu Apr 21 22:04:11 2016 -0500
+++ b/mercurial/bdiff.c	Fri Apr 22 13:38:02 2016 -0500
@@ -148,7 +148,15 @@
 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, half = (a1 + a2) / 2;
+	int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k, half;
+
+	/* window our search on large regions to better bound
+	   worst-case performance. by choosing a window at the end, we
+	   reduce skipping overhead on the b chains. */
+	if (a2 - a1 > 30000)
+		a1 = a2 - 30000;
+
+	half = (a1 + a2) / 2;
 
 	for (i = a1; i < a2; i++) {
 		/* skip all lines in b after the current block */