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

From: Phillip Wood <phillip.wood123@gmail.com>
Date: Aug 11, 2025, 13:13 UTC
Message-ID: <5cf47722-7073-4761-8698-090af840d0c4@gmail.com>
In-Reply-To: <353c7865-d9b5-2a1c-4d71-cd1136581f01@ispras.ru>

On 04/08/2025 15:39, Alexander Monakov wrote:

Show 24 quoted lines

> On Mon, 4 Aug 2025, Phillip Wood wrote:
> 
>>> 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.
> 
> Ok, reworded locally, will appear in v2.

Thanks

Show 6 quoted lines

>>> 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.
> 
> That's what the 'cycles' column in the table gives (6.21/5.8 = 1.070...)

It would be helpful to add a column with those calculations in it rather than forcing the reader to calculate the speed up for themselves. Also what is the cycles column measuring? What is it that takes 6.21 cycles for B and only 5.8 cycles for C?

Show 6 quoted lines

>> 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.
> 
> Then you get 9% from the inlining patch and only 2% from the faster hash
> function? That's a bit surprising, which compiler and CPU you used? Is it
> with default optimization (-O2)?

I used gcc with -O2 -march=native on an i5-8500. I saw a similar improvement from the inlining when I was playing with xxhash.

Show 7 quoted lines

>> 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?
> 
> I'd say under reasonable assumptions (e.g. a not too ancient CPU with 3-cycle
> integer multiplication) the new scheme is generally faster even without asm.

Thanks, fwiw I don't see a measurable difference in the timings with and without the asm on my machine - sometimes one is faster, sometimes the other, any difference is within the noise.

Show 8 quoted lines

> But Git can certainly follow Glibc's choice and employ this only on x86_64
> (and only with GCC or Clang).
> 
>> 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?
> 
> No, what we need to do here is outside of the abstract machine's view, standard
> functions are not going to help.

That's a shame. I'd hoped that stopping the compiler reorder the code would do the same thing - what is the asm doing that's different?

Thanks

Phillip