| Submitter | Gregory Szorc |
|---|---|
| Date | Nov. 6, 2016, 7:42 a.m. |
| Message ID | <430a4c8f9fa6992afa47.1478418148@ubuntu-vm-main> |
| Download | mbox | patch |
| Permalink | /patch/17374/ |
| State | Accepted |
| Headers | show |
Comments
These two are pushed thanks. On 11/06/2016 08:42 AM, Gregory Szorc wrote: > # HG changeset patch > # User Gregory Szorc <gregory.szorc@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@mercurial-scm.org > https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel >
Patch
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)