Re: [DISCUSS] Introducing Rust into the Git project

On Wed, Jan 10, 2024 at 12:18 PM Taylor Blau <me@ttaylorr.com> wrote:

I'm very happy to see this email.

I think there are other benefits as well; I'll list them at the end of the email to avoid side-tracking too much[6].

I agree with the zero-cost abstraction, but there is a funny caveat with measuring it if anyone is curious[7].

Another alternative (as discussed at Git Merge when we were last talking about Rust[8]), is requiring all Rust code to be optional for now. If we choose to go that route, I think that means that (a) for existing components, we have both a Rust and a C implementation available, and (b) for new components (e.g. new top-level commands like git-replay), they can be Rust-only and those compiling without Rust just don't get them.

If we're happy to allow Rust, I'd like to rewrite git-replay in Rust as a testcase. It's almost certainly not "easiest", but I think it's an interesting testcase because it's a new top-level command that hasn't appeared in any release yet. Further, it is currently only designed for server-side usecases, so would likely not be affected by more limited platform support. (I haven't started on this; my previous experiments were with diffcore-delta.)

:-)

[6] Here are some additional benefits I see:

 - Parallel performance.  We avoid making things parallel in Git because
   debugging/maintaining/reviewing parallel code in C often isn't worth
   the squeeze.  Rust was designed to greatly reduce this effort (the
   whole "fearless concurrency" thing).

 - Single-threaded Performance.  Multiple factors:

   - We had (and might still have) O(N^2) stuff in a lot of places in
     our codebase, because we tend to over-use arrays.  (e.g. with
     string_list, or with insertions and deletions into the index
     during a merge, etc.)

   - Relatedly, using hashes in C is quite onerous, to the point that
     we often simply avoid it.  I know I have, and I also know that
     even after I introduced strmap and tried to use it outside of
     merge-ort, that I got pushback because "string hash-maps are not
     really typical for a C program. I'm sure they are the best choice
     for an advanced merge algorithm but they are not really necessary
     [here; let's use sorted arrays instead]..."  I then had to go
     through multiple rounds of responses and ended up reimplementing
     everything as suggested (before finally convincing others to just
     use the strmap implementation after all).

   - We use QSORT() which basically calls libc's qsort().  Due to the
     design of this function (where the comparator is a separate
     function call), it is slow.  When languages avoid making the
     comparator a separate function call, they can speed sorts up by a
     factor of 2 (or even by 3 when an unstable sort is good enough
     and the platform's qsort() is stable).

   - Difficulty of incorporating other libraries.  For example, our
     hashmap.[ch] make use of FNV, but picking something else is a big
     amount of effort.  Now, while FNV is faster than Rust's default
     of SipHash, cargo makes it easy to pull in alternatives like
     FnvHashMap or FxHashMap, which we can then use where it matters.

I'm also tempted to include bullet points for having a unit testing framework built in, and potentially fewer platform-dependent issues (e.g. forgetting to use STABLE_QSORT when required since qsort is stable in some libc implementations, since rust defines those more carefully to be consistent across platforms), but I'm not sure these additional advantages are big enough to merit a full bullet point.

[7] If you ignore Rust for a moment, and simply divide your files into different libraries (e.g. introducing a new.c file, moving some functions to it, and then compiling new.c into a new library, libnew.a, and linking both libgit.a and libnew.a into git), you can sometimes measure some small performance differences. At least, I did. What this scenario has to do with Rust is that if we start moving some code to Rust, that will naturally likely result in a different division of files into libraries. Thus, for me to verify that Rust did provide zero-cost abstractions with my experiments, in order to compare the performance of my Rust changes, I had to compare to a version of git where I split some functions out into a separate library. When I did that, the performance overhead was actually 0. Otherwise, there was a tiny performance degradation in the particular splitting I employed. However, while splitting did give me a small performance drop, it was completely outweighed by the performance advantages I got elsewhere in the things I converted to Rust.

[8] https://lore.kernel.org/git/ZRrfN2lbg14IOLiK@nand.local/