All of lore.kernel.org
 help / color / mirror / Atom feed
From: "René Scharfe" <l.s.r@web.de>
To: Elijah Newren <newren@gmail.com>
Cc: Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>,
	Git Mailing List <git@vger.kernel.org>,
	Derrick Stolee <dstolee@microsoft.com>,
	Jonathan Tan <jonathantanmy@google.com>,
	Taylor Blau <me@ttaylorr.com>
Subject: Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative
Date: Fri, 28 May 2021 18:12:29 +0200	[thread overview]
Message-ID: <106a5592-4e5e-cf06-16e4-100ca3c3fb5f@web.de> (raw)
In-Reply-To: <CABPp-BH_nFJ2N6Jf64jZPNKdbwm2Yt=zo6pw-9s6S+fzo7a=pg@mail.gmail.com>

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:
>>> From: Elijah Newren <newren@gmail.com>
>>>
>>> Gathering accumulated times from trace2 output on the mega-renames
>>> testcase, I saw the following timings (where I'm only showing a few
>>> lines to highlight the portions of interest):
>>>
>>>     10.120 : label:incore_nonrecursive
>>>         4.462 : ..label:process_entries
>>>            3.143 : ....label:process_entries setup
>>>               2.988 : ......label:plist special sort
>>>            1.305 : ....label:processing
>>>         2.604 : ..label:collect_merge_info
>>>         2.018 : ..label:merge_start
>>>         1.018 : ..label:renames
>>>
>>> In the above output, note that the 4.462 seconds for process_entries was
>>> split as 3.143 seconds for "process_entries setup" and 1.305 seconds for
>>> "processing" (and a little time for other stuff removed from the
>>> highlight).  Most of the "process_entries setup" time was spent on
>>> "plist special sort" which corresponds to the following code:
>>>
>>>     trace2_region_enter("merge", "plist special sort", opt->repo);
>>>     plist.cmp = string_list_df_name_compare;
>>>     string_list_sort(&plist);
>>>     trace2_region_leave("merge", "plist special sort", opt->repo);
>>>
>>> In other words, in a merge strategy that would be invoked by passing
>>> "-sort" to either rebase or merge, sorting an array takes more time than
>>> anything else.  Serves me right for naming my merge strategy this way.
>>>
>>> Rewrite the comparison function and remove as many levels of indirection
>>> as possible (e.g. the old code had
>>>     cmp_items() ->
>>>       string_list_df_name_compare() ->
>>>         df_name_compare()
>>> now we just have sort_dirs_next_to_their_children()), and tweak it to be
>>> as optimized as possible for our specific case.  These changes reduced
>>> the time spent in "plist special sort" by ~25% in the mega-renames case.
>>>
>>> For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
>>> performance work; instrument with trace2_region_* calls", 2020-10-28),
>>> this change improves the performance as follows:
>>>
>>>                             Before                  After
>>>     no-renames:        5.622 s ±  0.059 s     5.235 s ±  0.042 s
>>>     mega-renames:     10.127 s ±  0.073 s     9.419 s ±  0.107 s
>>>     just-one-mega:   500.3  ms ±  3.8  ms   480.1  ms ±  3.9  ms
>>
>> Interesting.
>>
>>>
>>> Signed-off-by: Elijah Newren <newren@gmail.com>
>>> ---
>>>  merge-ort.c | 64 ++++++++++++++++++++++++++++++++++-------------------
>>>  1 file changed, 41 insertions(+), 23 deletions(-)
>>>
>>> diff --git a/merge-ort.c b/merge-ort.c
>>> index 142d44d74d63..367aec4b7def 100644
>>> --- a/merge-ort.c
>>> +++ b/merge-ort.c
>>> @@ -2746,31 +2746,50 @@ static int detect_and_process_renames(struct merge_options *opt,
>>>
>>>  /*** 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.

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?

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.

>
>>>       /*
>>> -      * Here we only care that entries for D/F conflicts are
>>> -      * adjacent, in particular with the file of the D/F conflict
>>> -      * appearing before files below the corresponding directory.
>>> -      * The order of the rest of the list is irrelevant for us.
>>> +      * Here we only care that entries for directories appear adjacent
>>> +      * to and before files underneath the directory.  In other words,
>>> +      * we do not want the natural sorting of
>>> +      *     foo
>>> +      *     foo.txt
>>> +      *     foo/bar
>>> +      * Instead, we want "foo" to sort as though it were "foo/", so that
>>> +      * we instead get
>>> +      *     foo.txt
>>> +      *     foo
>>> +      *     foo/bar
>>> +      * To achieve this, we basically implement our own strcmp, except that
>>> +      * if we get to the end of either string instead of comparing NUL to
>>> +      * another character, we compare '/' to it.
>>>        *
>>> -      * To achieve this, we sort with df_name_compare and provide
>>> -      * the mode S_IFDIR so that D/F conflicts will sort correctly.
>>> -      * We use the mode S_IFDIR for everything else for simplicity,
>>> -      * since in other cases any changes in their order due to
>>> -      * sorting cause no problems for us.
>>> +      * The reason to not use df_name_compare directly was that it was
>>> +      * just too expensive, so I had to reimplement it.
>>>        */
>>> -     int cmp = df_name_compare(one, onelen, S_IFDIR,
>>> -                               two, twolen, S_IFDIR);
>>> -     /*
>>> -      * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
>>> -      * that 'foo' comes before 'foo/bar'.
>>> -      */
>>> -     if (cmp)
>>> -             return cmp;
>>> -     return onelen - twolen;
>>> +     const char *one = ((struct string_list_item *)a)->string;
>>> +     const char *two = ((struct string_list_item *)b)->string;
>>
>> Casting away const, hmm. :-/  Harmless because no actual write is
>> attempted, but still looks needlessly scary to me.
>
> Right, that should have been
> +     const char *one = ((const struct string_list_item *)a)->string;
> +     const char *two = ((const struct string_list_item *)b)->string;
> but since I was just assigning to a const char * on those lines, I'm
> not sure why it'd qualify as scary.  Regardless, I'm happy to put
> these consts back in.

Explicit casts are a red flag already (anything could be cast to
anything else) and if they remove const their severity increases.  The
resulting object text is fine, but the code yells "TYPE SYSTEM
OVERRRULED!"  And type checks in C are weak to begin with, so a casual
reader has to wonder what kind of black magic is at work.  None in
this case, as an implicit casts would have sufficed:

	const struct string_list_item *item_a = a, *item_b = b;
	const char *one = item_a->string, *two = item_b->string;

Boring.  Calming.  Nice. ;)  The compiler would warn us if the pieces
didn't fit.

René

  reply	other threads:[~2021-05-28 16:12 UTC|newest]

Thread overview: 39+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-05-27  8:37 [PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
2021-05-27  8:37 ` [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
2021-05-27 21:00   ` René Scharfe
2021-05-27 22:47     ` Elijah Newren
2021-05-28 16:12       ` René Scharfe [this message]
2021-05-28 18:09         ` Elijah Newren
2021-05-28  1:32   ` Taylor Blau
2021-05-28  4:10     ` Elijah Newren
2021-05-27  8:37 ` [PATCH 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
2021-05-27  8:37 ` [PATCH 3/5] diffcore-rename: enable limiting rename detection to relevant destinations Elijah Newren via GitGitGadget
2021-05-27  8:37 ` [PATCH 4/5] Fix various issues found in comments Elijah Newren via GitGitGadget
2021-05-27  8:37 ` [PATCH 5/5] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
2021-06-01 14:58 ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Elijah Newren via GitGitGadget
2021-06-01 14:58   ` [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
2021-06-02 11:29     ` Derrick Stolee
2021-06-01 14:58   ` [PATCH v2 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
2021-06-01 14:58   ` [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations Elijah Newren via GitGitGadget
2021-06-03 12:54     ` Derrick Stolee
2021-06-03 14:13       ` Elijah Newren
2021-06-01 14:58   ` [PATCH v2 4/5] Fix various issues found in comments Elijah Newren via GitGitGadget
2021-06-01 14:58   ` [PATCH v2 5/5] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
2021-06-03 12:55   ` [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff Derrick Stolee
2021-06-04  4:39   ` [PATCH v3 0/4] " Elijah Newren via GitGitGadget
2021-06-04  4:39     ` [PATCH v3 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
2021-06-04  4:39     ` [PATCH v3 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
2021-06-04  4:39     ` [PATCH v3 3/4] Fix various issues found in comments Elijah Newren via GitGitGadget
2021-06-04  4:39     ` [PATCH v3 4/4] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget
2021-06-04 13:11     ` [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff Derrick Stolee
2021-06-04 15:48       ` Elijah Newren
2021-06-04 16:30         ` Elijah Newren
2021-06-04 16:35         ` Jeff King
2021-06-04 18:42           ` Derrick Stolee
2021-06-04 19:43             ` Elijah Newren
2021-06-04 19:53             ` Jeff King
2021-06-08 16:11     ` [PATCH v4 " Elijah Newren via GitGitGadget
2021-06-08 16:11       ` [PATCH v4 1/4] merge-ort: replace string_list_df_name_compare with faster alternative Elijah Newren via GitGitGadget
2021-06-08 16:11       ` [PATCH v4 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx Elijah Newren via GitGitGadget
2021-06-08 16:11       ` [PATCH v4 3/4] Fix various issues found in comments Elijah Newren via GitGitGadget
2021-06-08 16:11       ` [PATCH v4 4/4] merge-ort: miscellaneous touch-ups Elijah Newren via GitGitGadget

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=106a5592-4e5e-cf06-16e4-100ca3c3fb5f@web.de \
    --to=l.s.r@web.de \
    --cc=dstolee@microsoft.com \
    --cc=git@vger.kernel.org \
    --cc=gitgitgadget@gmail.com \
    --cc=jonathantanmy@google.com \
    --cc=me@ttaylorr.com \
    --cc=newren@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.