[PATCH] xdiff: Do not enable XDL_FAST_HASH by default

[PATCH] xdiff: Do not enable XDL_FAST_HASH by default

[Anders Kaseorg]

Although XDL_FAST_HASH computes hashes slightly faster on some
architectures, its collision characteristics are much worse, resulting
in some pathological diffs running over 100x slower
(http://public-inbox.org/git/20141222041944.GA441@peff.net/).

Furthermore, it was being enabled when ‘uname -m’ returns x86_64, even
if we are cross-compiling for a different architecture.  This mistake
was also causing the Debian build reproducibility test to fail
(https://tests.reproducible-builds.org/debian/index_variations.html).
Future architecture-specific definitions should be based on compiler
macros such as __x86_64__ rather than uname.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
---

On Wed, 30 Nov 2016, Jeff King wrote:
> However, I think this might be the tip of the iceberg. There are lots of
> Makefile knobs whose defaults are tweaked based on uname output. This
> one caught you because you are cross-compiling across architectures, but
> in theory you could cross-compile for FreeBSD from Linux, or whatever.
> 
> So I suspect a better strategy in general is to just override the
> uname_* variables when cross-compiling.

The specific case of an i386 userspace on an x86_64 kernel is important 
independently of the general cross compilation problem (in fact, the words 
“cross compilation” may not even really apply here).  And I don’t think 
one should have to manually tweak the build for this setup, especially 
since the compiler already has the needed information.

> All that being said, I actually think an easier fix for this particular
> case might be to drop XDL_FAST_HASH entirely.

Works for me.

Anders

 Makefile         | 1 -
 config.mak.uname | 5 -----
 2 files changed, 6 deletions(-)

diff --git a/Makefile b/Makefile
index f53fcc90d..c237d4f91 100644
--- a/Makefile
+++ b/Makefile
@@ -341,7 +341,6 @@ all::
 # 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.
 #
 # Define GIT_USER_AGENT if you want to change how git identifies itself during
 # network interactions.  The default is "git/$(GIT_VERSION)".
diff --git a/config.mak.uname b/config.mak.uname
index b232908f8..2831a68c3 100644
--- a/config.mak.uname
+++ b/config.mak.uname
@@ -1,10 +1,8 @@
 # Platform specific Makefile tweaks based on uname detection
 
 uname_S := $(shell sh -c 'uname -s 2>/dev/null || echo not')
-uname_M := $(shell sh -c 'uname -m 2>/dev/null || echo not')
 uname_O := $(shell sh -c 'uname -o 2>/dev/null || echo not')
 uname_R := $(shell sh -c 'uname -r 2>/dev/null || echo not')
-uname_P := $(shell sh -c 'uname -p 2>/dev/null || echo not')
 uname_V := $(shell sh -c 'uname -v 2>/dev/null || echo not')
 
 ifdef MSVC
@@ -17,9 +15,6 @@ endif
 # 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
-- 
2.11.0

Re: [PATCH] xdiff: Do not enable XDL_FAST_HASH by default

[Jeff King]

On Wed, Nov 30, 2016 at 11:26:43PM -0500, Anders Kaseorg wrote:

> > So I suspect a better strategy in general is to just override the
> > uname_* variables when cross-compiling.
> 
> The specific case of an i386 userspace on an x86_64 kernel is important 
> independently of the general cross compilation problem (in fact, the words 
> “cross compilation” may not even really apply here).  And I don’t think 
> one should have to manually tweak the build for this setup, especially 
> since the compiler already has the needed information.

Ah, I mistook that you were really cross-compiling x86-64 from i386, in
which case you'd generally have to set CC, etc for the cross-compile
chain. I agree this is a much more subtle case, and it's nice for it to
work out of the box.

> diff --git a/Makefile b/Makefile
> index f53fcc90d..c237d4f91 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -341,7 +341,6 @@ all::
>  # 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.

This is a nice incremental step in the sense that people can still
enable it if they want to in order to time it, play with it, etc. But
given what we know, I wonder if the help text here should warn people.

Or I guess we could move straight to dropping it entirely.

Here's what that patch might look like (I retimed it just be sure, and
was sad to see that it really _is_ making some cases faster. But I still
think slower-but-predictable is a better default).

I didn't drop uname_M here. If we go this route, I think it would make
sense to do that in a separate patch on top, with your commit message
explaining why it is a bad idea versus using compiler-defined macros.

-- >8 --
Subject: [PATCH] xdiff: drop XDL_FAST_HASH

The xdiff code hashes every line of both sides of a diff,
and then compares those hashes to find duplicates. The
overall performance depends both on how fast we can compute
the hashes, but also on how many hash collisions we see.

The idea of XDL_FAST_HASH is to speed up the hash
computation. But the generated hashes have worse collision
behavior. This means that in some cases it speeds diffs up
(running "git log -p" on git.git improves by ~8% with it),
but in others it can slow things down. One pathological case
saw over a 100x slowdown[1].

There may be a better hash function that covers both
properties, but in the meantime we are better off with the
original hash. It's slightly slower in the common case, but
it has fewer surprising pathological cases.

[1] http://public-inbox.org/git/20141222041944.GA441@peff.net/

Signed-off-by: Jeff King <peff@peff.net>
---
 Makefile         |   9 -----
 config.mak.uname |   3 --
 xdiff/xutils.c   | 106 -------------------------------------------------------
 3 files changed, 118 deletions(-)

diff --git a/Makefile b/Makefile
index f53fcc90d..f61076997 100644
--- a/Makefile
+++ b/Makefile
@@ -338,11 +338,6 @@ all::
 #
 # 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.
-#
 # Define GIT_USER_AGENT if you want to change how git identifies itself during
 # network interactions.  The default is "git/$(GIT_VERSION)".
 #
@@ -1485,10 +1480,6 @@ ifndef NO_MSGFMT_EXTENDED_OPTIONS
 	MSGFMT += --check --statistics
 endif
 
-ifneq (,$(XDL_FAST_HASH))
-	BASIC_CFLAGS += -DXDL_FAST_HASH
-endif
-
 ifdef GMTIME_UNRELIABLE_ERRORS
 	COMPAT_OBJS += compat/gmtime.o
 	BASIC_CFLAGS += -DGMTIME_UNRELIABLE_ERRORS
diff --git a/config.mak.uname b/config.mak.uname
index b232908f8..447f36ac2 100644
--- a/config.mak.uname
+++ b/config.mak.uname
@@ -17,9 +17,6 @@ endif
 # 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
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 027192a1c..04d7b32e4 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -264,110 +264,6 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,
 	return ha;
 }
 
-#ifdef XDL_FAST_HASH
-
-#define REPEAT_BYTE(x)  ((~0ul / 0xff) * (x))
-
-#define ONEBYTES	REPEAT_BYTE(0x01)
-#define NEWLINEBYTES	REPEAT_BYTE(0x0a)
-#define HIGHBITS	REPEAT_BYTE(0x80)
-
-/* 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;
-		 *
-		 * Doing it like this avoids warnings on 32-bit machines.
-		 */
-		long a = (REPEAT_BYTE(0x01) / 0xff + 1);
-		return mask * a >> (sizeof(long) * 7);
-	} else {
-		/* Carl Chatfield / Jan Achrenius G+ version for 32-bit */
-		/* (000000 0000ff 00ffff ffffff) -> ( 1 1 2 3 ) */
-		long a = (0x0ff0001 + mask) >> 23;
-		/* Fix the 1 for 00 case */
-		return a & mask;
-	}
-}
-
-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;
 	char const *ptr = *data;
@@ -384,8 +280,6 @@ 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;
 
-- 
2.11.0.319.gd1e73eb

Re: [PATCH] xdiff: Do not enable XDL_FAST_HASH by default

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> This is a nice incremental step in the sense that people can still
> enable it if they want to in order to time it, play with it, etc. But
> given what we know, I wonder if the help text here should warn people.
>
> Or I guess we could move straight to dropping it entirely.
>
> Here's what that patch might look like (I retimed it just be sure, and
> was sad to see that it really _is_ making some cases faster. But I still
> think slower-but-predictable is a better default).

I like this version that drops quite a lot of code ;-)

> Subject: [PATCH] xdiff: drop XDL_FAST_HASH
> ...
> The idea of XDL_FAST_HASH is to speed up the hash
> computation. But the generated hashes have worse collision
> behavior. This means that in some cases it speeds diffs up
> (running "git log -p" on git.git improves by ~8% with it),
> but in others it can slow things down. One pathological case
> saw over a 100x slowdown[1].
>
> There may be a better hash function that covers both
> properties, but in the meantime we are better off with the
> original hash. It's slightly slower in the common case, but
> it has fewer surprising pathological cases.
>
> [1] http://public-inbox.org/git/20141222041944.GA441@peff.net/

[PATCH] Define XDL_FAST_HASH when building *for* (not *on*) x86_64

[Anders Kaseorg]

Previously, XDL_FAST_HASH was defined when ‘uname -m’ returns x86_64,
even if we are cross-compiling for a different architecture.  Check
the __x86_64__ compiler macro instead.

In addition to fixing the cross compilation bug, this is needed to
pass the Debian build reproducibility test
(https://tests.reproducible-builds.org/debian/index_variations.html).

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
---
 config.mak.uname | 5 -----
 xdiff/xutils.c   | 4 ++++
 2 files changed, 4 insertions(+), 5 deletions(-)

diff --git a/config.mak.uname b/config.mak.uname
index b232908f8..2831a68c3 100644
--- a/config.mak.uname
+++ b/config.mak.uname
@@ -1,10 +1,8 @@
 # Platform specific Makefile tweaks based on uname detection
 
 uname_S := $(shell sh -c 'uname -s 2>/dev/null || echo not')
-uname_M := $(shell sh -c 'uname -m 2>/dev/null || echo not')
 uname_O := $(shell sh -c 'uname -o 2>/dev/null || echo not')
 uname_R := $(shell sh -c 'uname -r 2>/dev/null || echo not')
-uname_P := $(shell sh -c 'uname -p 2>/dev/null || echo not')
 uname_V := $(shell sh -c 'uname -v 2>/dev/null || echo not')
 
 ifdef MSVC
@@ -17,9 +15,6 @@ endif
 # 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
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 027192a1c..f46351fe4 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -264,6 +264,10 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,
 	return ha;
 }
 
+#ifdef __x86_64__
+#define XDL_FAST_HASH
+#endif
+
 #ifdef XDL_FAST_HASH
 
 #define REPEAT_BYTE(x)  ((~0ul / 0xff) * (x))
-- 
2.11.0

Re: [PATCH] Define XDL_FAST_HASH when building *for* (not *on*) x86_64

[Jeff King]

[resend; the original had an outdated address for Thomas, and I would
 definitely like his blessing before removing XDL_FAST_HASH].

On Wed, Nov 30, 2016 at 10:04:07PM -0500, Anders Kaseorg wrote:

> Previously, XDL_FAST_HASH was defined when ‘uname -m’ returns x86_64,
> even if we are cross-compiling for a different architecture.  Check
> the __x86_64__ compiler macro instead.
> 
> In addition to fixing the cross compilation bug, this is needed to
> pass the Debian build reproducibility test
> (https://tests.reproducible-builds.org/debian/index_variations.html).

I don't think this is a good approach to fix it. Right now XDL_FAST_HASH
is a Makefile knob that can be turned by the user, and can be used
either to explicitly enable or explicitly disable the feature.

With your patch, building with "make XDL_FAST_HASH=Yes" will still
explicitly enable it, but "make XDL_FAST_HASH=" would no longer disable
it (because even if unset, the compiler would turn it on when it sees
__x86_64__).

And being able to turn it off is important; more on that in a second.

So I think if we wanted to auto-detect based on __x86_64__, we'd
probably need to be able to set it to "auto" or something, and then

  #if defined(XDL_FAST_HASH_AUTO) && __x86_64__
  #define XDL_FAST_HASH
  #endif

or something.

However, I think this might be the tip of the iceberg. There are lots of
Makefile knobs whose defaults are tweaked based on uname output. This
one caught you because you are cross-compiling across architectures, but
in theory you could cross-compile for FreeBSD from Linux, or whatever.

So I suspect a better strategy in general is to just override the
uname_* variables when cross-compiling.


All that being said, I actually think an easier fix for this particular
case might be to drop XDL_FAST_HASH entirely. It computes the hashes
slightly faster, but its collision characteristics are much worse. About
2 years ago I ran across a pathological diff that ran over 100x slower
with XDL_FAST_HASH:

  http://public-inbox.org/git/20141222041944.GA441@peff.net/

The discussion veered into whether we should have a randomized hash
secured against DoS attacks. I played around with some alternatives, but
never found anything quite as fast for the "normal" case. And having
disabled XDL_FAST_HASH on GitHub's servers, it wasn't a big priority for
me.

I'd be happy if somebody wanted to investigate other hash functions
further. But barring that, I think we should drop XDL_FAST_HASH (or at
the very least stop turning it on by default) in the meantime. It's just
not a good tradeoff.

-Peff

[PATCH] xdiff: Do not enable XDL_FAST_HASH by default

[Anders Kaseorg]

Although XDL_FAST_HASH computes hashes slightly faster on some
architectures, its collision characteristics are much worse, resulting
in some pathological diffs running over 100x slower
(http://public-inbox.org/git/20141222041944.GA441@peff.net/).

Furthermore, it was being enabled when ‘uname -m’ returns x86_64, even
if we are cross-compiling for a different architecture.  This mistake
was also causing the Debian build reproducibility test to fail
(https://tests.reproducible-builds.org/debian/index_variations.html).
Future architecture-specific definitions should be based on compiler
macros such as __x86_64__ rather than uname.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
---

[Oops, also resending for Thomas’s new email address.  Sorry for the 
spam.]

On Wed, 30 Nov 2016, Jeff King wrote:
> However, I think this might be the tip of the iceberg. There are lots of
> Makefile knobs whose defaults are tweaked based on uname output. This
> one caught you because you are cross-compiling across architectures, but
> in theory you could cross-compile for FreeBSD from Linux, or whatever.
> 
> So I suspect a better strategy in general is to just override the
> uname_* variables when cross-compiling.

The specific case of an i386 userspace on an x86_64 kernel is important 
independently of the general cross compilation problem (in fact, the words 
“cross compilation” may not even really apply here).  And I don’t think 
one should have to manually tweak the build for this setup, especially 
since the compiler already has the needed information.

> All that being said, I actually think an easier fix for this particular
> case might be to drop XDL_FAST_HASH entirely.

Works for me.

Anders

 Makefile         | 1 -
 config.mak.uname | 5 -----
 2 files changed, 6 deletions(-)

diff --git a/Makefile b/Makefile
index f53fcc90d..c237d4f91 100644
--- a/Makefile
+++ b/Makefile
@@ -341,7 +341,6 @@ all::
 # 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.
 #
 # Define GIT_USER_AGENT if you want to change how git identifies itself during
 # network interactions.  The default is "git/$(GIT_VERSION)".
diff --git a/config.mak.uname b/config.mak.uname
index b232908f8..2831a68c3 100644
--- a/config.mak.uname
+++ b/config.mak.uname
@@ -1,10 +1,8 @@
 # Platform specific Makefile tweaks based on uname detection
 
 uname_S := $(shell sh -c 'uname -s 2>/dev/null || echo not')
-uname_M := $(shell sh -c 'uname -m 2>/dev/null || echo not')
 uname_O := $(shell sh -c 'uname -o 2>/dev/null || echo not')
 uname_R := $(shell sh -c 'uname -r 2>/dev/null || echo not')
-uname_P := $(shell sh -c 'uname -p 2>/dev/null || echo not')
 uname_V := $(shell sh -c 'uname -v 2>/dev/null || echo not')
 
 ifdef MSVC
@@ -17,9 +15,6 @@ endif
 # 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
-- 
2.11.0