D2627: xdiff: use memchr instead of character scanning
indygreg (Gregory Szorc)
phabricator at mercurial-scm.org
Sun Mar 4 01:38:01 UTC 2018
indygreg created this revision.
Herald added a subscriber: mercurial-devel.
Herald added a reviewer: hg-reviewers.
REVISION SUMMARY
Compilers (at least in the configuration used to build Mercurial)
don't seem to be able to optimize a loop to look for a byte in a
buffer very well.
After removing hashing from the loop in our previous commit, we
no longer have a good reason to use a loop at all: we can instead
use memchr() to find a byte value in a memory range. memchr() will
often be backed by platform-optimal, hand-written assembly that will
perform better than anything a compiler can emit.
Using memchr() to scan for newlines makes xdiff a bit faster. On
the mozilla-central repository:
$ hg perfbdiff --alldata -c --count 10 --blocks --xdiff 400000
! wall 0.796796 comb 0.790000 user 0.790000 sys 0.000000 (best of 13)
! wall 0.589753 comb 0.590000 user 0.590000 sys 0.000000 (best of 17)
$ hg perfbdiff -m --count 100 --blocks --xdiff 400000
! wall 9.450092 comb 9.460000 user 8.470000 sys 0.990000 (best of 3)
! wall 7.364899 comb 7.360000 user 6.430000 sys 0.930000 (best of 3)
REPOSITORY
rHG Mercurial
REVISION DETAIL
https://phab.mercurial-scm.org/D2627
AFFECTED FILES
mercurial/thirdparty/xdiff/xutils.c
CHANGE DETAILS
diff --git a/mercurial/thirdparty/xdiff/xutils.c b/mercurial/thirdparty/xdiff/xutils.c
--- a/mercurial/thirdparty/xdiff/xutils.c
+++ b/mercurial/thirdparty/xdiff/xutils.c
@@ -303,12 +303,16 @@
unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
XXH32_hash_t h;
- char const *ptr = *data;
+ char const *ptr;
if (flags & XDF_WHITESPACE_FLAGS)
return xdl_hash_record_with_whitespace(data, top, flags);
- for (; ptr < top && *ptr != '\n'; ptr++) { }
+ ptr = memchr(*data, '\n', top - *data + 1);
+ if (!ptr) {
+ ptr = top;
+ }
+
h = XDIFF_XXH32(*data, ptr - *data + 1, 0);
*data = ptr < top ? ptr + 1: ptr;
return h;
To: indygreg, #hg-reviewers
Cc: mercurial-devel
More information about the Mercurial-devel
mailing list