Re: [PATCH v3 0/5] Optimization batch 13: partial clone optimizations for merge-ort

[Elijah Newren <newren@gmail.com>]

On Tue, Jun 22, 2021 at 9:10 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 6/22/2021 4:04 AM, Elijah Newren via GitGitGadget wrote:
> > This series optimizes blob downloading in merges for partial clones. It can
> > apply on master. It's independent of ort-perf-batch-12.
>
> As promised, I completed a performance evaluation of this series as well
> as ort-perf-batch-12 (and all earlier batches) against our microsoft/git
> fork and running in one of our large monorepos that has over 2 million
> files at HEAD. Here are my findings.

Nice, thanks for the investigation and the detailed report!

> In my comparisons, I compare the recursive merge strategy with renames
> disabled against the ORT strategy (which always has renames enabled). When
> I enabled renames for the recursive merge I saw the partial clone logic
> kick in and start downloading many files in every case, so I dropped that
> from consideration.

I understand it'd take way too long to do an exhaustive testing, but
just doing a couple example comparisons against recursive with rename
detection turned on (and merge.renameLimit set to e.g. 0, or to some
high number if needed) would still be interesting.

> Experiment #1: Large RI/FI merges
> ---------------------------------
>
...
>      Recursive     ORT
> -----------------------
> MAX     34.97s    4.74s
> P90     30.04s    4.50s
> P75     15.35s    3.74s
> P50      7.22s    3.39s
> P10      3.61s    3.08s
>
> (I'm not testing ORT with the sparse-index yet. A significant portion of
> this 3 second lower bound is due to reading and writing the index file
> with 2 million entries. I _am_ using sparse-checkout with only the files
> at root, which minimizes the time required to update the working directory
> with any changed files.)
>
> For these merges, ORT is a clear win.

Wahoo!

I suspect I know what you're seeing from recursive as well; recursive
had some quadratic behaviors found within it, separate from the calls
into diffcore-rename.  It was much less likely to be triggered with
rename detection turned off, but could still be triggered.  I suspect
you just had enough testcases that some of them were affected.  (I
particularly suspect the item described at (5a) of
https://lore.kernel.org/git/pull.842.git.1612331345.gitgitgadget@gmail.com/)

Given the 2 million entries, I'm curious if ort-perf-batch-14 (not yet
submitted; I've been waiting a few weeks for ort-perf-batch-12 to hit
next) will provide further significant benefits.  If it really does
take 3s or so to do index reading and writing, then it'd only be able
to help with the slower cases, but I'm still curious.  It helped
rather dramatically on my linux kernel testcase with lots of renames.


> Experiment #2: User-created merges
> ----------------------------------
>
> To find merges that might be created by actual user cases, I ran
> 'git rev-list --grep="^Merge branch"' to get merges that had default
> messages from 'git merge' runs. (The merges from Experiment #1 had other
> automated names that did not appear in this search.)
>
> Here, the differences are less striking, but still valuable:
>
>      Recursive     ORT
> -----------------------
> MAX     10.61s   6.27s
> P75      8.81s   3.92s
> P50      4.32s   3.21s
> P10      3.53s   2.95s
>
> The ORT strategy had more variance in these examples, though still not as
> much as the recursive strategy. Here the variance is due to conflicting
> files needing content merges, which usually were automatically resolved.

Is the max case on the ort side related to item #2 below, where
perhaps there was a case where there was no automatic resolution of
some file?

> This version of the experiment provided interesting observations in a few
> cases:
>
> 1. One case had the recursive merge strategy result in a root tree that
>    disagreed with what the user committed, but the ORT strategy _did_ the
>    correct resolution. Likely, this is due to the rename detection and
>    resolution. The user probably had to manually resolve the merge to
>    match their expected renames since we turn off merge.renames in their
>    config.

I agree that seems like the likely explanation.

> 2. I watched for the partial clone logic to kick in and download blobs.
>    Some of these were inevitable: we need the blobs to resolve edit/edit
>    conflicts. Most cases none were downloaded at all, so this series is
>    working as advertised. There _was_ a case where the inexact rename
>    detection requested a large list of files (~2900 in three batches) but
>    _then_ said "inexact rename detection was skipped due to too many
>    files". This is a case that would be nice to resolve in this series. I
>    will try to find exactly where in the code this is being triggered and
>    report back.

This suggests perhaps that EITHER there was a real modify/delete
conflict (because you have to do full rename detection to rule out
that the modify/delete was part of some rename), OR that there was a
renamed file modified on both sides that did not keep its original
basename (because that combination is needed to bypass the various
optimizations and make it fall back to full inexact rename detection).
Further, in either case, there were enough adds/deletes that full
inexact detection is still a bit expensive.  It'd be interesting to
know which case it was.  What happens if you set merge.renameLimit to
something higher (the default is surprisingly small)?

> 3. As I mentioned, I was using sparse-checkout to limit the size of the
>    working directory. In one case of a conflict that could not be
>    automatically resolved, the ORT strategy output this error:
>
>    error: could not open '<X>': No such file or directory
>
>    It seems we are looking for a file on disk without considering if it
>    might have the SKIP_WORKTREE bit on in the index. I don't think this is
>    an issue for this series, but might require a follow-up on top of the
>    other ORT work.

I suspect either checkout() or record_conflicted_index_entries() are
to blame, and yeah, it'd be an issue from a previous series.  If you
have any further details or even hints about reproducing (doesn't have
to be a complete set of steps or minimal testcase), I would love to
hear it.  (Incidentally, of all the reviews on merge-ort, those two
functions were left out; look for "17" and "19" in
https://lore.kernel.org/git/pull.923.git.git.1606635803.gitgitgadget@gmail.com/
)


> Conclusions
> -----------
>
> I continue to be excited about the ORT strategy and will likely be
> focusing on it in a month or so to integrate it with the sparse-index. I
> think we would be interested in making the ORT strategy a new default for
> Scalar, but we might really want it to respect merge.renames=false if only
> so we can deploy the settings in stages (first, change the strategy, then
> enable renames as an independent step) so we can isolate concerns.

Given that my ort performance work concentrated on rename detection,
it's encouraging to see that ort-WITH-renames is generally faster for
you than recursive-WITHOUT-renames.  That means not only that rename
detection can be done in reasonable time now, but that the
improvements outside of rename detection show some real benefits as
well.  It'll be interesting to see how the final two performance
series for merge-ort, which will concentrate on performance on areas
other than rename detection, will affect these above results.


And by the way, thanks for the herculean review effort you've put in.
You've reviewed nearly every merge-ort and diffcore-rename patch
(which included many big, tricky patches)...and a quick search says
there's been at least 128 patches so far in the last 8 months.  And
the code is better (cleaner, clearer, and faster) for all your
reviews.