[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