Subject: [PATCH v2 4/4] xdiff: use a faster hash in xdl_hash_record_verbatim

From: Alexander Monakov <[email-masked]>
Date: Mon, 8 Sep 2025 21:49:39 +0300

Reimplement xdl_hash_record_verbatim such that it computes two djb2
hashes for even and odd characters independently, each at latency two
per character. The new loop is expected to be issue and execution
port throughput bound at three cycles per a pair of characters. The
more efficient ways to evaluate such hashes involve use of
multiplication and higher interleaving factors. The scheme used here
is expected to be a reasonable compromise for lines of source code
(i.e. not very long strings).

Due to interleaving, the new function does not produce the same hash
values as the original. Given values H0 for even characters and H1
for odd characters, we combine them to produce the final hash value
as 'H1 * 257 + H0'. The factor 257 is chosen to approximately match
the original in quality (collision count in xdiff hashtable).

Signed-off-by: Alexander Monakov <[email-masked]>
---
 xdiff/xhash.h | 62 +++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 55 insertions(+), 7 deletions(-)

diff --git a/xdiff/xhash.h b/xdiff/xhash.h
index 27da4288c8..1e9e13cc45 100644
--- a/xdiff/xhash.h
+++ b/xdiff/xhash.h
@@ -29,16 +29,64 @@ unsigned long xdl_hash_record_with_whitespace(char const **data, char const *top
 
 static inline unsigned long xdl_hash_record_verbatim(char const **data, char const *top)
 {
-	unsigned long ha = 5381;
 	char const *ptr = *data;
-
-	for (; ptr < top && *ptr != '\n'; ptr++) {
-		ha += (ha << 5);
-		ha ^= (unsigned long) *ptr;
+#if 0
+	/*
+	 * djb2 hash (below) is latency-bound; on x86, this baseline form cannot
+	 * run faster than two cycles per iteration, and to achieve that it is
+	 * neccessary to arrange for 'ha * 32' to be computed in parallel with
+	 * 'ha + ch'. To avoid being latency-bound, we run two independent djb2
+	 * hashes over even and odd characters, then combine them in the end.
+	 * The resulting hash is not equivalent to the original djb2.
+	 */
+	unsigned long ha = 5381, ch;
+	while (ptr < top) {
+		if ((ch = *ptr++) == '\n')
+			break;
+		ha = ha * 33 + ch;
 	}
-	*data = ptr < top ? ptr + 1: ptr;
-
+	*data = ptr;
 	return ha;
+#else
+#ifdef __GNUC__
+/*
+ * Compiler reassociation barrier: pretend to modify X and Y to disallow
+ * changing evaluation order with respect to following uses of X or Y.
+ */
+#define REASSOC_FENCE(x, y) __asm__("" : "+r"(x), "+r"(y))
+#else
+#define REASSOC_FENCE(x, y)
+#endif
+	unsigned long h0 = 5381, h1 = 0, ch;
+	/* Process two characters per iteration. */
+	if (top - ptr >= 2) do {
+		if ((ch = *ptr++) == '\n') {
+			*data = ptr;
+			h0 += h1;
+			REASSOC_FENCE(h0, h1);
+			return h1 * 256 + h0;
+		}
+		ch += h0;
+		REASSOC_FENCE(ch, h0);
+		h0 = h0 * 32 + ch;
+
+		if ((ch = *ptr++) == '\n') {
+			*data = ptr;
+			h0 += h1;
+			REASSOC_FENCE(h0, h1);
+			return h1 * 256 + h0;
+		}
+		ch += h1;
+		REASSOC_FENCE(ch, h1);
+		h1 = h1 * 32 + ch;
+
+	} while (ptr < top - 1);
+	*data = top;
+	if (ptr < top && (ch = *ptr++) != '\n')
+		h0 = h0 * 33 + ch;
+	return h1 * 257 + h0;
+#undef REASSOC_FENCE
+#endif
 }
 
 static inline unsigned long xdl_hash_record(char const **data, char const *top, long flags)
-- 
2.49.1