[PATCH v2 4/4] xdiff: use a faster hash in xdl_hash_record_verbatim
From: Alexander Monakov <hidden>
Date: 2025-09-08 18:49:54
Subsystem:
the rest · Maintainer:
Linus Torvalds
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 <redacted> --- 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