Subject: Re: [PATCH 4/4] csum-file.c: use fast SHA-1 implementation when available

From: Patrick Steinhardt <[email-masked]>
Date: Mon, 2 Sep 2024 15:41:31 +0200

On Sun, Sep 01, 2024 at 12:03:32PM -0400, Taylor Blau wrote:
> Update hashwrite() and friends to use the fast_-variants of hashing
> functions, calling for e.g., "the_hash_algo->fast_update_fn()" instead
> of "the_hash_algo->update_fn()".
> 
> These callers only use the_hash_algo to produce a checksum, which we
> depend on for data integrity, but not for cryptographic purposes, so
> these callers are safe to use the fast (and potentially non-collision
> detecting) SHA-1 implementation.
> 
> To time this, I took a freshly packed copy of linux.git, and ran the
> following with and without the OPENSSL_SHA1_FAST=1 build-knob. Both
> versions were compiled with -O3:
> 
>     $ git for-each-ref --format='%(objectname)' refs/heads refs/tags >in
>     $ valgrind --tool=callgrind ~/src/git/git-pack-objects \
>         --revs --stdout --all-progress --use-bitmap-index <in >/dev/null
> 
> Without OPENSSL_SHA1_FAST=1 (that is, using the collision-detecting
> SHA-1 implementation for both cryptographic and non-cryptographic
> purposes), we spend a significant amount of our instruction count in
> hashwrite():
> 
>     $ callgrind_annotate --inclusive=yes | grep hashwrite | head -n1
>     159,998,868,413 (79.42%)  /home/ttaylorr/src/git/csum-file.c:hashwrite [/home/ttaylorr/src/git/git-pack-objects]
> 
> , and the resulting "clone" takes 19.219 seconds of wall clock time,
> 18.94 seconds of user time and 0.28 seconds of system time.
> 
> Compiling with OPENSSL_SHA1_FAST=1, we spend ~60% fewer instructions in
> hashwrite():
> 
>     $ callgrind_annotate --inclusive=yes | grep hashwrite | head -n1
>      59,164,001,176 (58.79%)  /home/ttaylorr/src/git/csum-file.c:hashwrite [/home/ttaylorr/src/git/git-pack-objects]
> 
> , and generate the resulting "clone" much faster, in only 11.597 seconds
> of wall time, 11.37 seconds of user time, and 0.23 seconds of system
> time, for a ~40% speed-up.

Neat. I knew that SHA1DC was slower, but I certainly didn't expect it to
make such a huge difference.

I of course wish that we just moved on and switched the default to
SHA256, which should provide similar speedups. But that of course
wouldn't help all the projects out there that will use SHA1 for the next
couple decades.

One thing I'm missing is an analysis of users of "csum-file.c" so that
we can assess whether it is safe to switch over this subsystem to use
the fast variant. As far as I can see it's used for packfiles, commit
graphs, the index, packfile reverse indices, MIDXs. None of them strike
me as particularly critical, also because almost all of them would be
created locally by the user anyway.

The only exception are of course packfiles, which get generated by the
remote. Is it possible to generate packfiles with colliding trailer
hashes? And if so, how would the client behave if it was served a
packfile with such a collision?

Patrick