Patchwork [6,of,6,STABLE,V2] bdiff: further restrain potential quadratic performance

login
register
mail settings
Submitter Matt Mackall
Date April 25, 2016, 10:10 p.m.
Message ID <9b1dc9fcff5fffbc18be.1461622222@ruin.waste.org>
Download mbox | patch
Permalink /patch/14788/
State Accepted
Commit 87d4a6c5567e81386b8c2209d95060d5bf72e064
Headers show

Comments

Matt Mackall - April 25, 2016, 10:10 p.m.
# HG changeset patch
# User Matt Mackall <mpm@selenic.com>
# Date 1461350282 18000
#      Fri Apr 22 13:38:02 2016 -0500
# Branch stable
# Node ID 9b1dc9fcff5fffbc18be186d7c3ecc5f4247f121
# Parent  8ac62bff6df06bedd86e560a734c4328616e745d
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.
Augie Fackler - April 26, 2016, 1:42 p.m.
On Mon, Apr 25, 2016 at 05:10:22PM -0500, Matt Mackall wrote:
> # HG changeset patch
> # User Matt Mackall <mpm@selenic.com>
> # Date 1461350282 18000
> #      Fri Apr 22 13:38:02 2016 -0500
> # Branch stable
> # Node ID 9b1dc9fcff5fffbc18be186d7c3ecc5f4247f121
> # Parent  8ac62bff6df06bedd86e560a734c4328616e745d
> bdiff: further restrain potential quadratic performance

Queueing these, very nice.

>
> 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.
>
> diff -r 8ac62bff6df0 -r 9b1dc9fcff5f 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 */
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel

Patch

diff -r 8ac62bff6df0 -r 9b1dc9fcff5f 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 */