Re: [PATCH 0/2] optimize string hashing in xdiff

From: Alexander Monakov <amonakov@ispras.ru>
Date: Jul 28, 2025, 20:25 UTC
Message-ID: <43459416-ced2-d551-40e3-6db594ca4520@ispras.ru>
In-Reply-To: <xmqqa54oun5w.fsf@gitster.g>

On Mon, 28 Jul 2025, Junio C Hamano wrote:

Show 9 quoted lines

> Alexander Monakov <amonakov@ispras.ru> writes:
> 
> > I've noticed the work by Phillip Wood regarding hash optimization for xdiff.
> > I want to point out that it is possible to speed up the existing hash by 1.5x
> > matching the peformance of xxhash (but without introducing a dependendency).
> 
> Using xxhash() was merely a sample code path for technology
> demonstration, so the Rust adoption topic may want to pick a
> different code path to do its thing.

My interest here is just speeding up xdiff in C, is that a welcome topic?

Show 6 quoted lines

> > The additive variant of the djb2 hash is used in ELF symbol lookup, and
> > Noah Goldstein contributed a well-optimized implementation to Glibc.
> 
> What is the licensing terms for that code you are proposing us to
> borrow?  If it is anything recent in GNU, I'd expect that it would
> be GPLv3, which would be incompatible with our code base?

Noah's code is not usable in xdiff due to different context (mainly the need to limit iteration by length — ELF hashing iterates until the NUL character).

I have participated in review of Noah's patches and he kindly listed me as a co-author in the final revision of his patchset. So while I'm aware of how his code is structured, I had to write a new implementation in order to meet the contract of xdl_hash_record_verbatim. Therefore I think I can contribute this code on GPLv2 terms with my sign-off.

Maybe someone would be willing to look at patch 2 and compare against Noah's patch (linked in the commit message)?

Thank you. Alexander