[PATCH 2 of 2] bdiff: don't check border condition in loop

Pierre-Yves David pierre-yves.david at ens-lyon.org
Sun Nov 6 11:40:19 EST 2016


These two are pushed thanks.

On 11/06/2016 08:42 AM, Gregory Szorc wrote:
> # HG changeset patch
> # User Gregory Szorc <gregory.szorc at gmail.com>
> # Date 1478417870 25200
> #      Sun Nov 06 00:37:50 2016 -0700
> # Node ID 430a4c8f9fa6992afa47d459d592f6c58e686be2
> # Parent  e65ef545a3dcb46fe0f1798e76ea17f9f9323452
> bdiff: don't check border condition in loop
>
> `plast = a + len - 1`. So, this "for" loop iterates from "a" to "plast",
> inclusive. So, `p == plast` can only be true on the final iteration
> of the loop. So checking for it on every loop iteration is wasteful.
>
> This patch simply decreases the upper bound of the loop by 1 and
> adds an explicit check after iteration for the `p == plast` case.
> We can't simply add 1 to the initial value for "i" because that
> doesn't do the correct thing on empty input strings.
>
> `perfbdiff -m 3041e4d59df2` on the Firefox repo becomes significantly
> faster:
>
> ! wall 0.072763 comb 0.070000 user 0.070000 sys 0.000000 (best of 100)
> ! wall 0.053221 comb 0.060000 user 0.060000 sys 0.000000 (best of 100)
>
> For the curious, this code has its origins in 8b067bde6679, which is
> the changeset that introduced bdiff.c in 2005.
>
> Also, GNU diffutils is able to perform a similar line-based diff in
> under 20ms. So there's likely more perf wins to be found in this code.
> One of them is the hashing algorithm. But it looks like mpm spent
> some time testing hash collisions in d0c48891dd4a. I'd like to do the
> same before switching away from lyhash, just to be on the safe side.
>
> diff --git a/mercurial/bdiff.c b/mercurial/bdiff.c
> --- a/mercurial/bdiff.c
> +++ b/mercurial/bdiff.c
> @@ -31,9 +31,11 @@ int bdiff_splitlines(const char *a, ssiz
>
>  	/* count the lines */
>  	i = 1; /* extra line for sentinel */
> -	for (p = a; p < a + len; p++)
> -		if (*p == '\n' || p == plast)
> +	for (p = a; p < plast; p++)
> +		if (*p == '\n')
>  			i++;
> +	if (p == plast)
> +		i++;
>
>  	*lr = l = (struct bdiff_line *)malloc(sizeof(struct bdiff_line) * i);
>  	if (!l)
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>

-- 
Pierre-Yves David


More information about the Mercurial-devel mailing list