Git development
 help / color / mirror / Atom feed
* [PATCH 0/4] faster SHA-1 collision detection
@ 2026-09-29 11:25 Scott Chacon
  2026-09-29 11:25 ` [PATCH 1/4] sha1dc-accel: add a block loop for sha1dc's SHA1_CTX Scott Chacon
                   ` (5 more replies)
  0 siblings, 6 replies; 23+ messages in thread
From: Scott Chacon @ 2026-09-29 11:25 UTC (permalink / raw)
  To: git

So, spoiler alert, the code in this patch series is mainly AI generated.
I would try to fool you, but too many of you are far too aware of my
actual C skills. That being said, I thought maybe someone here (especially
those of you working on server optimization stuff) would be interested
in the speed increases for both the server and client in making sha1dc
quite a bit faster.

This series ports the approach of Sam Reis's sha1dc Rust crate [1], 
which gitoxide recently switched to [2], to C. 

The end result hashes roughly 2.7x faster on the Xeon and 2.85x faster
on the M5 Max. Single-threaded index-pack of git.git goes from 24.3s to
12.7s on the Xeon, and from 16.1s to 8.7s on the M5 Max.

Hashing throughput on the Xeon, in MiB/s:

                                16KiB    1MiB   vs OpenSSL
  OpenSSL SHA-1 (no detection)   1234    1129      1.00x
  sha1dc/ (today)                 435     450      2.67x
  shani+avx2 (default here)      1002     901      1.24x
  shani+sse2                     1075    1008      1.13x
  portable+avx2                   553     654      1.96x
  portable+sse2                   603     681      1.84x
  portable                        466     565      2.29x

In other words, currently collision detection costs about 1.5–2.5x on
top of the hashing itself today, but only about 0.2x with the series. 

The patches are:

  [1/4]: sha1dc-accel: add a block loop for sha1dc's SHA1_CTX

    Just groundwork: our own block loop around sha1dc's context and DV
    table, with the same results and a few percent slower, plus tests
    that compare against sha1dc/ directly, including on real collisions
    in every mode.

  [2/4]: sha1dc-accel: vectorize the unavoidable-bitconditions check

    The UBC filter rewritten as SSE2, AVX2, NEON, and new scalar forms, 
    using the conditions the crate's solver picks for each. They're 
    carried as tables, with a short loop per form to run them. 
    1.29x on the Xeon, 1.27x on the M5 Max.

  [3/4]: sha1dc-accel: compress with SHA-NI on x86-64

    Hardware compression, with the schedule spilled, and recompression
    of flagged blocks in hardware, too. Another 2.07x on the Xeon.

  [4/4]: sha1dc-accel: compress with the ARMv8 SHA-1 instructions

    The same for arm64. Another 2.4x on the M5 Max.

The x86 numbers are from a 4-vCPU Xeon VM with SHA-NI and AVX2 (GCC 13,
Linux), which is unfortunately rather noisy; the per-patch hyperfine
output has the spread. The arm64 numbers are medians of 9 runs on an
Apple M5 Max (Apple clang, macOS). The full test suite passes on both.

[1] https://sam.dev/blog/faster-sha1-collision-detection
[2] https://github.com/GitoxideLabs/gitoxide/pull/3008

Scott Chacon (4):
  sha1dc-accel: add a block loop for sha1dc's SHA1_CTX
  sha1dc-accel: vectorize the unavoidable-bitconditions check
  sha1dc-accel: compress with SHA-NI on x86-64
  sha1dc-accel: compress with the ARMv8 SHA-1 instructions

 Makefile                            |   14 +
 contrib/buildsystems/CMakeLists.txt |    2 +-
 meson.build                         |    4 +
 sha1dc-accel/arm.c                  |  274 ++++
 sha1dc-accel/internal.h             |  126 ++
 sha1dc-accel/sha1.c                 |  498 ++++++++
 sha1dc-accel/sha1.h                 |   31 +
 sha1dc-accel/ubc_check.c            | 1789 +++++++++++++++++++++++++++
 sha1dc-accel/x86.c                  |  260 ++++
 sha1dc_git.c                        |   18 +
 t/.gitattributes                    |    1 +
 t/helper/test-sha1.c                |   95 ++
 t/helper/test-tool.c                |    2 +
 t/helper/test-tool.h                |    2 +
 t/meson.build                       |    1 +
 t/t0013-sha1dc.sh                   |   47 +
 t/t0013/sha-mbles-1.bin             |  Bin 0 -> 640 bytes
 t/t0013/sha1-reduced-round.bin      |  Bin 0 -> 128 bytes
 t/unit-tests/u-sha1dc.c             |  366 ++++++
 19 files changed, 3529 insertions(+), 1 deletion(-)
 create mode 100644 sha1dc-accel/arm.c
 create mode 100644 sha1dc-accel/internal.h
 create mode 100644 sha1dc-accel/sha1.c
 create mode 100644 sha1dc-accel/sha1.h
 create mode 100644 sha1dc-accel/ubc_check.c
 create mode 100644 sha1dc-accel/x86.c
 create mode 100644 t/t0013/sha-mbles-1.bin
 create mode 100644 t/t0013/sha1-reduced-round.bin
 create mode 100644 t/unit-tests/u-sha1dc.c


base-commit: a018953688f1b10bddf91bff8747068f5f4746a4
-- 
2.50.1 (Apple Git-155)



^ permalink raw reply	[flat|nested] 23+ messages in thread

end of thread, other threads:[~2026-10-10 15:37 UTC | newest]

Thread overview: 23+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-09-29 11:25 [PATCH 0/4] faster SHA-1 collision detection Scott Chacon
2026-09-29 11:25 ` [PATCH 1/4] sha1dc-accel: add a block loop for sha1dc's SHA1_CTX Scott Chacon
2026-10-07 12:17   ` Johannes Schindelin
2026-09-29 11:25 ` [PATCH 2/4] sha1dc-accel: vectorize the unavoidable-bitconditions check Scott Chacon
2026-10-07 12:17   ` Johannes Schindelin
2026-10-07 21:32     ` Junio C Hamano
2026-09-29 11:25 ` [PATCH 3/4] sha1dc-accel: compress with SHA-NI on x86-64 Scott Chacon
2026-09-29 11:25 ` [PATCH 4/4] sha1dc-accel: compress with the ARMv8 SHA-1 instructions Scott Chacon
2026-10-07 12:17 ` [PATCH 0/4] faster SHA-1 collision detection Johannes Schindelin
2026-10-07 17:23 ` Junio C Hamano
2026-10-07 18:13   ` Scott Chacon
2026-10-08  6:21     ` Sebastian Thiel
2026-10-08 11:20       ` Sam Reis
2026-10-08 13:25         ` D. Ben Knoble
2026-10-08 13:59           ` Sam Reis
2026-10-08 17:10           ` Junio C Hamano
2026-10-08 17:46             ` D. Ben Knoble
2026-10-08 21:03               ` Junio C Hamano
2026-10-09 20:37           ` Todd Zullinger
2026-10-10 14:10             ` D. Ben Knoble
2026-10-10 15:37               ` Todd Zullinger
2026-10-09 23:41           ` Junio C Hamano
2026-10-08 15:55         ` Junio C Hamano

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox