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

[Taylor Blau <me@ttaylorr.com>]

On Mon, Sep 02, 2024 at 03:41:31PM +0200, Patrick Steinhardt wrote:
> 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.

Yeah, I was similarly surprised as you are.

> 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.

Right, the only case I believe we care about hash collisions is writing
loose objects, and hashing packed objects from within a packfile. The
loose object write path does not use hashfile(), so it is immune from
these changes.

The path where we read the objects packed in a packfile to determine
their OID is also safe, because that happens in index-pack and does not
use the _fast variants of these functions.

> 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?

I think the answer to this is "no", but let's consolidate this
discussion into the sub-thread where brian and I are already chatting
about this to avoid having the discussion in two places.

Thanks,
Taylor