Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim

[Phillip Wood <phillip.wood123@gmail.com>]

Hi Alexander

On 28/07/2025 20:05, Alexander Monakov wrote:
> xdl_hash_record_verbatim uses modified djb2 hash with XOR instead of ADD
> for combining. The ADD-based variant is used as the basis of the modern
> ("GNU") symbol lookup scheme in ELF. Glibc dynamic loader received an
> optimized version of this hash function thanks to Noah Goldstein [1].

Interesting

> Switch xdl_hash_record_verbatim to additive hashing and implement
> an optimized loop following the scheme suggested by Noah.
> 
> Timing 'git log --oneline --shortstat v2.0.0..v2.5.0' under perf, I got
> 
> version | cycles, bn | instructions, bn
> ---------------------------------------
> A         6.38         11.3
> B         6.21         10.89
> C         5.80          9.95
> D         5.83          8.74
> ---------------------------------------
> 
> A: baseline (git master at e4ef0485fd78)
> B: plus 'xdiff: refactor xdl_hash_record()'
> C: and plus this patch
> D: with 'xdiff: use xxhash' by Phillip Wood

I think it would be helpful to say that B is the previous patch and 
provide a link for D.
> The resulting speedup for xdl_hash_record_verbatim itself is about 1.5x.

While that's interesting it does not tell us how much this speeds up 
diff generation. Running the command above under hyperfine it is 1.02 ± 
0.01 times faster than the previous patch and 1.11 ± 0.01 times faster 
than master. Using xxhash (D above) is 1.03 ± 0.01 times faster than 
this patch. How do the changes below affect compilers other than gcc and 
clang than do not see the re-association barrier? We'd want to make sure 
that it does not result in slower diffs. Can we use 
atomic_signal_fence() on compilers that support C11? (we don't require 
C11 so we'd have to make it optional but it is supported by things like 
MSVC)

Thanks

Phillip
> 
> [1] https://inbox.sourceware.org/libc-alpha/20220519221803.57957-6-goldstein.w.n@gmail.com/
> 
> Signed-off-by: Alexander Monakov <amonakov@ispras.ru>
> ---
>   xdiff/xutils.c | 59 ++++++++++++++++++++++++++++++++++++++++++++++----
>   1 file changed, 55 insertions(+), 4 deletions(-)
> 
> diff --git a/xdiff/xutils.c b/xdiff/xutils.c
> index e070ed649f..b1f8273f0f 100644
> --- a/xdiff/xutils.c
> +++ b/xdiff/xutils.c
> @@ -294,16 +294,67 @@ unsigned long xdl_hash_record_with_whitespace(char const **data,
>   	return ha;
>   }
>   
> +/*
> + * Compiler reassociation barrier: pretend to modify X and Y to disallow
> + * changing evaluation order with respect to following uses of X and Y.
> + */
> +#ifdef __GNUC__
> +#define REASSOC_FENCE(x, y) asm("" : "+r"(x), "+r"(y))
> +#else
> +#define REASSOC_FENCE(x, y)
> +#endif
> +
>   unsigned long xdl_hash_record_verbatim(char const **data, char const *top) {
> -	unsigned long ha = 5381;
> +	unsigned long ha = 5381, c0, c1;
>   	char const *ptr = *data;
> -
> +#if 0
> +	/*
> +	 * The baseline form of the optimized loop below. This is the djb2
> +	 * hash (the above function uses a variant with XOR instead of ADD).
> +	 */
>   	for (; ptr < top && *ptr != '\n'; ptr++) {
>   		ha += (ha << 5);
> -		ha ^= (unsigned long) *ptr;
> +		ha += (unsigned long) *ptr;
>   	}
>   	*data = ptr < top ? ptr + 1: ptr;
> -
> +#else
> +	/* Process two characters per iteration. */
> +	if (top - ptr >= 2) do {
> +		if ((c0 = ptr[0]) == '\n') {
> +			*data = ptr + 1;
> +			return ha;
> +		}
> +		if ((c1 = ptr[1]) == '\n') {
> +			*data = ptr + 2;
> +			c0 += ha;
> +			REASSOC_FENCE(c0, ha);
> +			ha = ha * 32 + c0;
> +			return ha;
> +		}
> +		/*
> +		 * Combine characters C0 and C1 into the hash HA. We have
> +		 * HA = (HA * 33 + C0) * 33 + C1, and we want to ensure
> +		 * that dependency chain over HA is just one multiplication
> +		 * and one addition, i.e. we want to evaluate this as
> +		 * HA = HA * 33 * 33 + (C0 * 33 + C1), and likewise prefer
> +		 * (C0 * 32 + (C0 + C1)) for the expression in parenthesis.
> +		 */
> +		ha *= 33 * 33;
> +		c1 += c0;
> +		REASSOC_FENCE(c1, c0);
> +		c1 += c0 * 32;
> +		REASSOC_FENCE(c1, ha);
> +		ha += c1;
> +
> +		ptr += 2;
> +	} while (ptr < top - 1);
> +	*data = top;
> +	if (ptr < top && (c0 = ptr[0]) != '\n') {
> +		c0 += ha;
> +		REASSOC_FENCE(c0, ha);
> +		ha = ha * 32 + c0;
> +	}
> +#endif
>   	return ha;
>   }
>