Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative

From: Elijah Newren <newren@gmail.com>
Date: May 28, 2021, 18:09 UTC
Message-ID: <CABPp-BHoZTFwcqZvLLdPR0deuBRjzeY9DgPVkCu4GYkt9=gc-Q@mail.gmail.com>
In-Reply-To: <106a5592-4e5e-cf06-16e4-100ca3c3fb5f@web.de>

On Fri, May 28, 2021 at 9:12 AM René Scharfe <l.s.r@web.de> wrote:

Show 5 quoted lines

>
> Am 28.05.21 um 00:47 schrieb Elijah Newren:
> > On Thu, May 27, 2021 at 2:00 PM René Scharfe <l.s.r@web.de> wrote:
> >>
> >> Am 27.05.21 um 10:37 schrieb Elijah Newren via GitGitGadget:

...

Show 16 quoted lines

> >>>  /*** Function Grouping: functions related to process_entries() ***/
> >>>
> >>> -static int string_list_df_name_compare(const char *one, const char *two)
> >>> +static int sort_dirs_next_to_their_children(const void *a, const void *b)
> >>>  {
> >>> -     int onelen = strlen(one);
> >>> -     int twolen = strlen(two);
> >>
> >> The old code scans both strings fully, while the new one stops when it
> >> reaches a difference and doesn't look at any further characters.  How
> >> much does that contribute to the speedup?  (I suspect a lot.)
> >
> > Oh, indeed, good catch.  It appears to be responsible for essentially all of it.
>
> Then you can keep the original function signature (as well as the use of
> string_list_sort) and avoid explicit casts.

Fair enough; though I'll probably still apply the function rename, even if I keep the old signature. The function has a completely different purpose in merge-ort.c than it does in merge-recursive.c.

Show 10 quoted lines

> The same function exists in merge-recursive.c, by the way.  I suspect we
> could avoid sorting entirely there by taking advantage of the index
> order and a mechanism like the one in the second half of
> fsck.c::verify_ordered().  That's a bit tricky, though (for me anyway).
>
> All tests still pass when I replace string_list_df_name_compare() with
> strcmp() in merge-recursive.c, so the first thing needed would be tests
> that highlight the difference between those comparison functions,
> however.  Not sure if it's worth it -- merge-recursive is on its way
> out, right?

Interesting idea (and interesting that the function might not matter anymore in merge-recursive.c and might be replaceable by strcmp), but yeah merge-recursive.c is on its way out. In fact, there are two other reasons to also not modify merge-recursive.c along these lines: (1) We want to keep merge-recursive stable right now as we push people to try out merge-ort, so that we have a good comparison point if they run into problems; if we modify merge-recursive, especially in tricky ways, then our comparison point might get invalidated. (2) This codepath is relatively hot in merge-ort.c because it has optimized all the other stuff, so saving approximately half a second is significant. In merge-recursive.c, saving half a second is a small blip in the overall timing that would be lost in the run-to-run variability. (Saving 0.7s off of 10.127 s ± 0.073 s is huge; but removing that much time from 5964.031 s ± 10.459 is wasted effort.)

> Not sure if d/f conflicts could also be detected in merge-ort.c without
> sorting -- the original order is lost when the paths are thrown into
> a strmap.

While string_list_df_name_compare() in merge-recursive.c is used for the purpose of detecting D/F conflicts, this function in merge-ort.c had nothing to do with detecting D/F conflicts. In fact, D/F conflicts were already detected in collect_merge_info_callback() on this line:

    unsigned df_conflict = (filemask != 0) && (dirmask != 0);

and recorded in setup_path_info(), which was done long before it got to this point in the code. The point of this sorting in merge-ort.c is just to put paths in an order that allows us to write out trees as we process them and record the resulting hash for the next directory up the chain as we go.