Re: [PATCH 0/4] Add a compile-time option to use the new, very fast sha1dc Rust crate

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Oct 3, 2026, 10:23 UTC
Message-ID: <09b76ee1-2bac-4c33-b09d-d414717d3ced@gmx.de>
In-Reply-To: <xmqqa4p0jz0d.fsf@gitster.g>

Hi Junio,

On Tue, 29 Sep 2026, Junio C Hamano wrote:

Show 26 quoted lines

> "Johannes Schindelin via GitGitGadget" <gitgitgadget@gmail.com>
> writes:
> 
> > I stumbled across this new Rust crate last week. Its performance
> > numbers are quite impressive. Naturally, I want to make use of this
> > and get for Windows, which is used on many monorepos where this makes
> > a real difference: In a pretty fast and loose test, I verified that a
> > git index-pack runs roughly three times faster solely due to using
> > those SIMD-based optimizations!
> >
> > As a safety precaution, because this sha1dc crate is quite new, I
> > wanted to introduce an escape hatch: core.sha1dcBackend=c, but turn it
> > on by default, which is the reason for the three additional patches.
> > Should these patches be undesirable for the Git project? I would not
> > be mad at all if they were simply dropped.
> >
> > Johannes Schindelin (4):
> >   libgitcore: add `sha1dc` as an optional feature
> >   sha1dc: allow selecting the C backend without rebuilding
> >   pthread: provide `pthread_once()` shims for Windows and for
> >     NO_PTHREADS
> >   sha1dc: make `sha1dc_init()` thread-safe
> 
> The feature sha1dc_choose() means that you can between Rust and C
> implementations of sha1dc pick at runtime and I was confused by the
> "compile-time" in the topic title, which is misleading.

Right. I was almost certain that you'd reject the runtime flag, which is really only interesting for binary-first distribution vectors such as Git for Windows but not source-code-only releases such as core Git's.

Show 9 quoted lines

> From the end-user's point of view, being able to choose between the two
> at runtime gives them a lot bigger value, even though from the point of
> view of the developer who added the feature to allow users to do so,
> that feature being a compile-time choice might matter more.
> 
> How close are these two implementations?  Do they implement the same
> idea but the details may differ?  Do they both faithfully implement
> what the same paper wrote and given the same fudged input they will
> always detect the attempted attack the same way?

Those two implementations are quite different. As the author of the Rust crate detailed in https://sam.dev/blog/faster-sha1-collision-detection, they first tried to accelerate the quite faithful Rust port of the library that is used by Git, and while there were some gains to be made, a more fundamental approach proved to offer way bigger wins.

While I would have _loved_ to have the time to dig into this myself, armed with pencil and paper only, and doing maths again for once, I simply could not afford the time to assess the validity of the Rust `sha1dc` implementation without AI assistance. With that disclaimer out of the way (which should actually _increase_ your confidence, because I haven't been in the math business in a very, very long time, so the double-teaming with GPT-5.5 Sol and Opus 5.5 probably increased the soundness of my analysis), here are my findings:

- The Rust implementation chooses a different approach from the C
  implementation. The idea is the same, though: to dismiss as quickly as
  possible as many of the DV vectors (each check can cover several of
  those at once). It's just that with SIMD, the technique differs, and
  that informs about the order and the grouping of those checks.

  (In more technical terms: The UBC filter is different, not the overall
  collision-detection algorithm. Both Rust and C implementation cover the
  same per-DV affine solution space over GF(2), albeit with different
  equations).

- While the approach is different, exploiting SIMD-specific advantages to
  great speed-wise effects, the covered DV vectors are exactly the same,
  and the filtering and recompression checks are equivalent; therefore
  both C and Rust implementation detect the very same class of collisions
  under the paper's assumptions.

- The Rust implementation is robust and correct. I performed a light
  (well, for me, not so much for the AI models) static analysis, and then
  I ran some substantial tests. My plan was to exercise Git's entire test
  suite (with a patched-in mode that would exercise both C and Rust and
  validate that they compute the same SHA-1), but I haven't managed to
  kick off _those_ particular AI-assisted sessions yet (I would want to
  exercise both x86_64 and aarch64, of course).

- The reason why I posted this before I finished _all_ the tests? To allow
  other Git contributors an early look, and to inspire (see e.g. Scott's
  alternative), to invite collaboration on this patch series.

Ciao, Johannes