git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH 0/7] RFC: Accelerate xdiff and begin its rustification
@ 2025-07-17 20:32 Ezekiel Newren via GitGitGadget
  2025-07-17 20:32 ` [PATCH 1/7] xdiff: introduce rust Ezekiel Newren via GitGitGadget
                   ` (12 more replies)
  0 siblings, 13 replies; 203+ messages in thread
From: Ezekiel Newren via GitGitGadget @ 2025-07-17 20:32 UTC (permalink / raw)
  To: git; +Cc: Elijah Newren, Ezekiel Newren

This series accelerates xdiff by 5-19%.

It also introduces Rust as a hard dependency.

…and it doesn’t yet pass a couple of the github workflows; hints from
Windows experts, and opinions on ambiguous primitives would be appreciated
(see below).

This is just the beginning of many patches that I have to convert portions
of, maybe eventually all of, xdiff to Rust. While working on that
conversion, I found several ways to clarify the code, along with some
optimizations.

So...

This obviously raises the question of whether we are ready to accept a hard
dependency on Rust. Previous discussions on the mailing list and at Git
Merge 2024 have not answered that question. If not now, will we be willing
to accept such a hard dependency later? And what route do we want to take to
get there?

About the optimizations in this series:

1. xdiff currently uses DJB2a for hashing (even though it is not explicitly named as such). This is an older hashing algorithm, and modern alternatives are superior. I chose xxhash because it’s faster, more collision resistant, and designed to be a standard. Other hash algorithms like aHash, MurMurHash, SipHash, and Fnv1a were considered, but my local testing made me feel like xxhash was the best choice for usage in xdiff.

2. In support of switching to xxhash, parsing and hashing were split into separate steps. And it turns out that memchr() is faster for parsing than character-by-character iteration.


About the workflow builds/tests that aren’t working with this series:

1. Windows fails to build. I don’t know which rust toolchain is even correct for this or if multiple are needed.  Example failed build: https://github.com/git/git/actions/runs/16353209191

2. I386/ubuntu:focal will build, but fails the tests. The kernel reports the bitness as 64 despite the container being 32. I believe the issue is that C uses ambiguous primitives (which differ in size between platforms). The new code should use unambiguous primitives from Rust (u32, u64, etc.) rather than perpetuating ambiguous primitive types.  Since the current xdiff API hardcodes the ambiguous types, though, those places will need to be migrated to unambiguous primitives. Much of the C code needs a slight refactor to be compatible with the Rust FFI and usually requires converting ambiguous to unambiguous types. What does this community think of this approach?


My brother (Elijah, cc’ed) has been guiding and reviewing my work here.

Ezekiel Newren (7):
  xdiff: introduce rust
  xdiff/xprepare: remove superfluous forward declarations
  xdiff: delete unnecessary fields from xrecord_t and xdfile_t
  xdiff: make fields of xrecord_t Rust friendly
  xdiff: separate parsing lines from hashing them
  xdiff: conditionally use Rust's implementation of xxhash
  github_workflows: install rust

 .github/workflows/main.yml |   1 +
 .gitignore                 |   1 +
 Makefile                   |  60 +++++++---
 build_rust.sh              |  59 ++++++++++
 ci/install-dependencies.sh |  14 +--
 ci/install-rust.sh         |  33 ++++++
 ci/lib.sh                  |   8 ++
 ci/make-test-artifacts.sh  |   7 ++
 ci/run-build-and-tests.sh  |  10 ++
 git-compat-util.h          |  17 +++
 meson.build                |  40 +++++--
 rust/Cargo.lock            |  21 ++++
 rust/Cargo.toml            |   6 +
 rust/interop/Cargo.toml    |  14 +++
 rust/interop/src/lib.rs    |   0
 rust/xdiff/Cargo.toml      |  16 +++
 rust/xdiff/src/lib.rs      |   7 ++
 xdiff/xdiffi.c             |   8 +-
 xdiff/xemit.c              |   2 +-
 xdiff/xmerge.c             |  14 +--
 xdiff/xpatience.c          |   2 +-
 xdiff/xprepare.c           | 226 ++++++++++++++++++-------------------
 xdiff/xtypes.h             |   9 +-
 xdiff/xutils.c             |   4 +-
 24 files changed, 414 insertions(+), 165 deletions(-)
 create mode 100755 build_rust.sh
 create mode 100644 ci/install-rust.sh
 create mode 100644 rust/Cargo.lock
 create mode 100644 rust/Cargo.toml
 create mode 100644 rust/interop/Cargo.toml
 create mode 100644 rust/interop/src/lib.rs
 create mode 100644 rust/xdiff/Cargo.toml
 create mode 100644 rust/xdiff/src/lib.rs


base-commit: 16bd9f20a403117f2e0d9bcda6c6e621d3763e77
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1980%2Fezekielnewren%2Fxdiff_rust_speedup-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1980/ezekielnewren/xdiff_rust_speedup-v1
Pull-Request: https://github.com/git/git/pull/1980
-- 
gitgitgadget

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

end of thread, other threads:[~2025-10-07  9:12 UTC | newest]

Thread overview: 203+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-07-17 20:32 [PATCH 0/7] RFC: Accelerate xdiff and begin its rustification Ezekiel Newren via GitGitGadget
2025-07-17 20:32 ` [PATCH 1/7] xdiff: introduce rust Ezekiel Newren via GitGitGadget
2025-07-17 21:30   ` brian m. carlson
2025-07-17 21:54     ` Junio C Hamano
2025-07-17 22:39     ` Taylor Blau
2025-07-18 23:15     ` Ezekiel Newren
2025-07-23 21:57       ` brian m. carlson
2025-07-23 22:26         ` Junio C Hamano
2025-07-28 19:11         ` Ezekiel Newren
2025-07-31 22:37           ` brian m. carlson
2025-07-22 22:02     ` Mike Hommey
2025-07-22 23:52       ` brian m. carlson
2025-07-17 22:38   ` Taylor Blau
2025-07-17 20:32 ` [PATCH 2/7] xdiff/xprepare: remove superfluous forward declarations Ezekiel Newren via GitGitGadget
2025-07-17 22:41   ` Taylor Blau
2025-07-17 20:32 ` [PATCH 3/7] xdiff: delete unnecessary fields from xrecord_t and xdfile_t Ezekiel Newren via GitGitGadget
2025-07-17 20:32 ` [PATCH 4/7] xdiff: make fields of xrecord_t Rust friendly Ezekiel Newren via GitGitGadget
2025-07-17 22:46   ` Taylor Blau
2025-07-17 23:13     ` brian m. carlson
2025-07-17 23:37       ` Elijah Newren
2025-07-18  0:23         ` Taylor Blau
2025-07-18  0:21       ` Taylor Blau
2025-07-18 13:35   ` Phillip Wood
2025-07-28 19:34     ` Ezekiel Newren
2025-07-28 19:52       ` Phillip Wood
2025-07-28 20:14         ` Ezekiel Newren
2025-07-31 14:20           ` Phillip Wood
2025-07-31 20:58             ` Ezekiel Newren
2025-08-01  9:14               ` Phillip Wood
2025-07-28 20:53         ` Junio C Hamano
2025-07-28 20:00       ` Collin Funk
2025-07-20  1:39   ` Johannes Schindelin
2025-07-17 20:32 ` [PATCH 5/7] xdiff: separate parsing lines from hashing them Ezekiel Newren via GitGitGadget
2025-07-17 22:59   ` Taylor Blau
2025-07-18 13:34   ` Phillip Wood
2025-07-17 20:32 ` [PATCH 6/7] xdiff: conditionally use Rust's implementation of xxhash Ezekiel Newren via GitGitGadget
2025-07-17 23:29   ` Taylor Blau
2025-07-18 19:00   ` Junio C Hamano
2025-07-31 21:13     ` Ezekiel Newren
2025-08-02  7:53       ` Matthias Aßhauer
2025-07-19 21:53   ` Johannes Schindelin
2025-07-20 10:14     ` Phillip Wood
2025-09-23  9:57       ` gitoxide-compatible licensing of Git's Rust code, was " Johannes Schindelin
2025-09-23 17:48         ` Jeff King
2025-09-24 13:48           ` Phillip Wood
2025-09-25  2:25             ` Jeff King
2025-09-25  5:42               ` Patrick Steinhardt
2025-09-26 10:06               ` Phillip Wood
2025-10-03  3:18                 ` Jeff King
2025-10-03  9:51                   ` Phillip Wood
2025-10-07  9:11                     ` Patrick Steinhardt
2025-10-05  5:32       ` Yee Cheng Chin
2025-07-17 20:32 ` [PATCH 7/7] github_workflows: install rust Ezekiel Newren via GitGitGadget
2025-07-17 21:23   ` brian m. carlson
2025-07-18 23:01     ` Ezekiel Newren
2025-07-25 23:56       ` Ben Knoble
2025-07-19 21:54   ` Johannes Schindelin
2025-07-17 21:51 ` [PATCH 0/7] RFC: Accelerate xdiff and begin its rustification brian m. carlson
2025-07-17 22:25   ` Taylor Blau
2025-07-18  0:29     ` brian m. carlson
2025-07-22 12:21       ` Patrick Steinhardt
2025-07-22 15:56         ` Junio C Hamano
2025-07-22 16:03     ` Sam James
2025-07-22 21:37       ` Elijah Newren
2025-07-22 21:55         ` Sam James
2025-07-22 22:08           ` Collin Funk
2025-07-18  9:23 ` Christian Brabandt
2025-07-18 16:26   ` Junio C Hamano
2025-07-19  0:32     ` Elijah Newren
2025-07-18 13:34 ` Phillip Wood
2025-07-18 21:25   ` Eli Schwartz
2025-07-19  0:48     ` Haelwenn (lanodan) Monnier
2025-07-22 12:21       ` Patrick Steinhardt
2025-07-22 14:24     ` Patrick Steinhardt
2025-07-22 15:14       ` Eli Schwartz
2025-07-22 15:56       ` Sam James
2025-07-23  4:32         ` Patrick Steinhardt
2025-07-24  9:01           ` Pierre-Emmanuel Patry
2025-07-24 10:00             ` Patrick Steinhardt
2025-07-28  9:06               ` Pierre-Emmanuel Patry
2025-07-18 14:38 ` Junio C Hamano
2025-07-18 21:56   ` Ezekiel Newren
2025-07-21 10:14   ` Phillip Wood
2025-07-21 18:33     ` Junio C Hamano
2025-07-19 21:53 ` Johannes Schindelin
2025-07-20  8:45   ` Matthias Aßhauer
2025-08-15  1:22 ` [PATCH v2 00/17] " Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 01/17] doc: add a policy for using Rust brian m. carlson via GitGitGadget
2025-08-15 17:03     ` Matthias Aßhauer
2025-08-15 21:31       ` Junio C Hamano
2025-08-16  8:06         ` Matthias Aßhauer
2025-08-19  2:06       ` Ezekiel Newren
2025-08-15  1:22   ` [PATCH v2 02/17] xdiff: introduce rust Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 03/17] xdiff/xprepare: remove superfluous forward declarations Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 04/17] xdiff: delete unnecessary fields from xrecord_t and xdfile_t Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 05/17] xdiff: make fields of xrecord_t Rust friendly Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 06/17] xdiff: separate parsing lines from hashing them Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 07/17] xdiff: conditionally use Rust's implementation of xxhash Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 08/17] github workflows: install rust Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 09/17] Do support Windows again after requiring Rust Johannes Schindelin via GitGitGadget
2025-08-15 17:12     ` Matthias Aßhauer
2025-08-15 21:48       ` Junio C Hamano
2025-08-15 22:11         ` Johannes Schindelin
2025-08-15 23:37           ` Junio C Hamano
2025-08-15 23:37         ` Junio C Hamano
2025-08-16  8:53         ` Matthias Aßhauer
2025-08-17 15:57           ` Junio C Hamano
2025-08-19  2:22       ` Ezekiel Newren
2025-08-15  1:22   ` [PATCH v2 10/17] win+Meson: allow for xdiff to be compiled with MSVC Johannes Schindelin via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 11/17] win+Meson: do allow linking with the Rust-built xdiff Johannes Schindelin via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 12/17] github workflows: define rust versions and targets in the same place Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 13/17] github workflows: upload Cargo.lock Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 14/17] xdiff: implement a white space iterator in Rust Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 15/17] xdiff: create line_hash() and line_equal() Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 16/17] xdiff: optimize case where --ignore-cr-at-eol is the only whitespace flag Ezekiel Newren via GitGitGadget
2025-08-15  1:22   ` [PATCH v2 17/17] xdiff: use rust's version of whitespace processing Ezekiel Newren via GitGitGadget
2025-08-15 15:07   ` [-SPAM-] [PATCH v2 00/17] RFC: Accelerate xdiff and begin its rustification Ramsay Jones
2025-08-19  2:00     ` Elijah Newren
2025-08-24 16:52       ` Patrick Steinhardt
2025-08-18 22:31   ` Junio C Hamano
2025-08-18 23:52     ` Ben Knoble
2025-08-19  1:52     ` Elijah Newren
2025-08-19  9:47       ` Junio C Hamano
2025-08-23  3:55   ` [PATCH v3 00/15] RFC: Cleanup " Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 01/15] doc: add a policy for using Rust brian m. carlson via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 02/15] xdiff: introduce rust Ezekiel Newren via GitGitGadget
2025-08-23 13:43       ` rsbecker
2025-08-23 14:26         ` Kristoffer Haugsbakk
2025-08-23 15:06           ` rsbecker
2025-08-23 18:30             ` Elijah Newren
2025-08-23 19:24               ` brian m. carlson
2025-08-23 20:04                 ` rsbecker
2025-08-23 20:36                 ` Sam James
2025-08-23 21:17                 ` Haelwenn (lanodan) Monnier
2025-08-27  1:57               ` Taylor Blau
2025-08-27 14:39                 ` rsbecker
2025-08-27 17:06                   ` Junio C Hamano
2025-08-27 17:15                     ` rsbecker
2025-08-27 20:12                     ` Taylor Blau
2025-08-27 20:22                       ` Junio C Hamano
2025-09-02 11:16                         ` Patrick Steinhardt
2025-09-02 11:30                           ` Sam James
2025-09-02 17:27                           ` brian m. carlson
2025-09-02 18:47                             ` Sam James
2025-09-03 18:22                               ` Collin Funk
2025-09-03  5:40                             ` Patrick Steinhardt
2025-09-03 16:22                               ` Ramsay Jones
2025-09-03 22:10                               ` Junio C Hamano
2025-09-03 22:48                                 ` Josh Steadmon
2025-09-04 11:10                                 ` Patrick Steinhardt
2025-09-04 15:45                                   ` Junio C Hamano
2025-09-05  8:23                                     ` Patrick Steinhardt
2025-09-04  0:57                               ` brian m. carlson
2025-09-04 11:39                                 ` Patrick Steinhardt
2025-09-04 13:53                                   ` Sam James
2025-09-05  3:55                                     ` Elijah Newren
2025-09-04 23:17                                   ` Ezekiel Newren
2025-09-05  3:54                                   ` Elijah Newren
2025-09-05  6:50                                     ` Patrick Steinhardt
2025-09-07  4:10                                       ` Elijah Newren
2025-09-07 16:09                                         ` rsbecker
2025-09-08 10:12                                           ` Phillip Wood
2025-09-08 15:32                                             ` rsbecker
2025-09-08 15:10                                           ` Ezekiel Newren
2025-09-08 15:41                                             ` rsbecker
2025-09-08 15:31                                           ` Elijah Newren
2025-09-08 15:36                                             ` rsbecker
2025-09-08 16:13                                               ` Elijah Newren
2025-09-08 17:01                                                 ` rsbecker
2025-09-08  6:40                                         ` Patrick Steinhardt
2025-09-05 10:31                                     ` Phillip Wood
2025-09-05 11:32                                       ` Sam James
2025-09-05 13:14                                       ` Phillip Wood
2025-09-05 13:23                                         ` Patrick Steinhardt
2025-09-05 15:37                                         ` Junio C Hamano
2025-09-08  6:40                                           ` Patrick Steinhardt
2025-08-23 14:29         ` Ezekiel Newren
2025-08-23  3:55     ` [PATCH v3 03/15] github workflows: install rust Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 04/15] win+Meson: do allow linking with the Rust-built xdiff Johannes Schindelin via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 05/15] github workflows: upload Cargo.lock Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 06/15] ivec: create a vector type that is interoperable between C and Rust Ezekiel Newren via GitGitGadget
2025-08-23  8:12       ` Kristoffer Haugsbakk
2025-08-23  9:29         ` Ezekiel Newren
2025-08-23 16:14       ` Junio C Hamano
2025-08-23 16:37         ` Ezekiel Newren
2025-08-23 18:05       ` Junio C Hamano
2025-08-23 20:29         ` Ezekiel Newren
2025-08-25 19:16         ` Elijah Newren
2025-08-26  5:40           ` Junio C Hamano
2025-08-24 13:31       ` Ben Knoble
2025-08-25 20:40         ` Ezekiel Newren
2025-08-26 13:30           ` D. Ben Knoble
2025-08-26 18:47             ` Ezekiel Newren
2025-08-26 22:01               ` brian m. carlson
2025-08-23  3:55     ` [PATCH v3 07/15] xdiff/xprepare: remove superfluous forward declarations Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 08/15] xdiff: delete unnecessary fields from xrecord_t and xdfile_t Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 09/15] xdiff: make fields of xrecord_t Rust friendly Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 10/15] xdiff: use one definition for freeing xdfile_t Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 11/15] xdiff: replace chastore with an ivec in xdfile_t Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 12/15] xdiff: delete nrec field from xdfile_t Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 13/15] xdiff: delete recs " Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 14/15] xdiff: make xdfile_t more rust friendly Ezekiel Newren via GitGitGadget
2025-08-23  3:55     ` [PATCH v3 15/15] xdiff: implement xdl_trim_ends() in Rust Ezekiel Newren via GitGitGadget

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).