From: Phillip Wood Date: Mon, 04 Aug 2025 13:49:41 GMT Subject: Re: [PATCH 2/2] xdiff: optimize xdl_hash_record_verbatim Message-ID: In-Reply-To: <20250728190520.10962-3-amonakov@ispras.ru> 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 > --- > 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; > } >