Merge branch 'tr/xdiff-fast-hash'

Use word-at-a-time comparison to find end of line or NUL (end of buffer),
borrowed from the linux-kernel discussion.

By Thomas Rast
* tr/xdiff-fast-hash:
xdiff: choose XDL_FAST_HASH code on sizeof(long) instead of __WORDSIZE
xdiff: load full words in the inner loop of xdl_hash_record

diff --git a/Makefile b/Makefile
index 7e243085da4c3f50e4fbef10eb247e0d150a5907..bdf2a578df684224c640332861f7093a38cbe8f3 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -288,6 +288,11 @@ all::
 # dependency rules.
 #
 # Define NATIVE_CRLF if your platform uses CRLF for line endings.
+#
+# Define XDL_FAST_HASH to use an alternative line-hashing method in
+# the diff algorithm.  It gives a nice speedup if your processor has
+# fast unaligned word loads.  Does NOT work on big-endian systems!
+# Enabled by default on x86_64.
 
 GIT-VERSION-FILE: FORCE
        @$(SHELL_PATH) ./GIT-VERSION-GEN
@@ -902,6 +907,9 @@ EXTLIBS =
 # because maintaining the nesting to match is a pain.  If
 # we had "elif" things would have been much nicer...
 
+ifeq ($(uname_M),x86_64)
+       XDL_FAST_HASH = YesPlease
+endif
 ifeq ($(uname_S),OSF1)
        # Need this for u_short definitions et al
        BASIC_CFLAGS += -D_OSF_SOURCE
@@ -1775,6 +1783,10 @@ ifndef NO_MSGFMT_EXTENDED_OPTIONS
        MSGFMT += --check --statistics
 endif
 
+ifneq (,$(XDL_FAST_HASH))
+       BASIC_CFLAGS += -DXDL_FAST_HASH
+endif
+
 ifeq ($(TCLTK_PATH),)
 NO_TCLTK=NoThanks
 endif

diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 0de084e53f5144153373cc66cae7b523b4ae2812..1b3b471ac86a30474e3acabea3d2df3b6da072d8 100644 (file)
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -20,6 +20,8 @@
  *
  */
 
+#include <limits.h>
+#include <assert.h>
 #include "xinclude.h"
 
 
@@ -276,6 +278,109 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,
        return ha;
 }
 
+#ifdef XDL_FAST_HASH
+
+#define ONEBYTES       0x0101010101010101ul
+#define NEWLINEBYTES   0x0a0a0a0a0a0a0a0aul
+#define HIGHBITS       0x8080808080808080ul
+
+/* Return the high bit set in the first byte that is a zero */
+static inline unsigned long has_zero(unsigned long a)
+{
+       return ((a - ONEBYTES) & ~a) & HIGHBITS;
+}
+
+static inline long count_masked_bytes(unsigned long mask)
+{
+       if (sizeof(long) == 8) {
+               /*
+                * Jan Achrenius on G+: microoptimized version of
+                * the simpler "(mask & ONEBYTES) * ONEBYTES >> 56"
+                * that works for the bytemasks without having to
+                * mask them first.
+                */
+               return mask * 0x0001020304050608 >> 56;
+       } else {
+               /*
+                * Modified Carl Chatfield G+ version for 32-bit *
+                *
+                * (a) gives us
+                *   -1 (0, ff), 0 (ffff) or 1 (ffffff)
+                * (b) gives us
+                *   0 for 0, 1 for (ff ffff ffffff)
+                * (a+b+1) gives us
+                *   correct 0-3 bytemask count result
+                */
+               long a = (mask - 256) >> 23;
+               long b = mask & 1;
+               return a + b + 1;
+       }
+}
+
+unsigned long xdl_hash_record(char const **data, char const *top, long flags)
+{
+       unsigned long hash = 5381;
+       unsigned long a = 0, mask = 0;
+       char const *ptr = *data;
+       char const *end = top - sizeof(unsigned long) + 1;
+
+       if (flags & XDF_WHITESPACE_FLAGS)
+               return xdl_hash_record_with_whitespace(data, top, flags);
+
+       ptr -= sizeof(unsigned long);
+       do {
+               hash += hash << 5;
+               hash ^= a;
+               ptr += sizeof(unsigned long);
+               if (ptr >= end)
+                       break;
+               a = *(unsigned long *)ptr;
+               /* Do we have any '\n' bytes in this word? */
+               mask = has_zero(a ^ NEWLINEBYTES);
+       } while (!mask);
+
+       if (ptr >= end) {
+               /*
+                * There is only a partial word left at the end of the
+                * buffer. Because we may work with a memory mapping,
+                * we have to grab the rest byte by byte instead of
+                * blindly reading it.
+                *
+                * To avoid problems with masking in a signed value,
+                * we use an unsigned char here.
+                */
+               const char *p;
+               for (p = top - 1; p >= ptr; p--)
+                       a = (a << 8) + *((const unsigned char *)p);
+               mask = has_zero(a ^ NEWLINEBYTES);
+               if (!mask)
+                       /*
+                        * No '\n' found in the partial word.  Make a
+                        * mask that matches what we read.
+                        */
+                       mask = 1UL << (8 * (top - ptr) + 7);
+       }
+
+       /* The mask *below* the first high bit set */
+       mask = (mask - 1) & ~mask;
+       mask >>= 7;
+       hash += hash << 5;
+       hash ^= a & mask;
+
+       /* Advance past the last (possibly partial) word */
+       ptr += count_masked_bytes(mask);
+
+       if (ptr < top) {
+               assert(*ptr == '\n');
+               ptr++;
+       }
+
+       *data = ptr;
+
+       return hash;
+}
+
+#else /* XDL_FAST_HASH */
 
 unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
        unsigned long ha = 5381;
@@ -293,6 +398,7 @@ unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
        return ha;
 }
 
+#endif /* XDL_FAST_HASH */
 
 unsigned int xdl_hashbits(unsigned int size) {
        unsigned int val = 1, bits = 0;