This is a really core and famous problem in extremal combinatorics and a lot of people think about this problem and many related ones. I think the biggest impediment is that too many people were looking for the upper bound instead of looking for a lower bound. The construction here is still incredibly novel and requires sophisticated mathematics to prove it is correct.
But specifically, the ORT strategy can cache computed renames across multiple commits being rebased, so the performance benefits are even greater for "git rebase".
That history that looks tangled and awful would look a lot better if the commits were sorted by `--topo-order` instead of `--date-order`. That sort “groups” commits that are in a single line of history.
You're right that we used what we learned from Scalar's background maintenance an applied that to Git itself.
Putting background maintenance into Git was actually part of our effort to get Scalar on Linux.
You might be interested in our "Philosophy of Scalar" [1] document, which includes this paragraph:
> Scalar intends to do very little more than the standard Git client. We actively implement new features into Git instead of Scalar, then update Scalar only to configure those new settings. In particular, we are porting features like background maintenance to Git to make Scalar simpler and make Git more powerful.
The delta compression in Git is about storing the file contents of an object as a diff against another object. This changes the literal size on-disk, but it doesn't change the logical unit.
In fact, the delta chains used by Git for space compression have no direct relation to the object model DAG. From the perspective of a user using Git, these deltas are completely invisible.
Edit: perhaps to help this point... If Git stores an object using a delta, that doesn't change the object ID of that object compared to storing it uncompressed.
If I have a 100-line file and on 'main' it changes near the top, but in my 'topic' branch it changes near the bottom, then I can cherry-pick 'topic' onto 'main' and Git will resolve the diff correctly. The resulting diff or patch would only change in the line numbers for the context of the diff.
This is of course a very simple example. You might hit a conflict in your "git cherry-pick" command which gives you an opportunity to resolve the unexpected diff issue in an appropriate way, which ends up with a different diff than before.