Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged

>
> On Thu, Feb 13, 2025 at 1:01 AM Meet Soni <meetsoni3017@gmail.com> wrote:
> >
> > Previously, `get_unmerged()` used `string_list_insert()`, which has an
> > O(n^2) complexity due to shifting elements on each insertion. It also
> > called `string_list_lookup()` before insertion, which performs a binary
> > search in O(log n).
>
> Okay.
>
> > This combination made insertion costly, especially
> > for large index states, as each new entry required both a search and
> > potentially shifting many elements.
>
> Why does the combination make it costly?  O(log n) + O(n^2) is still
> O(n^2), so I don't see why it matters to mention the combination.
> Could you clarify?
>
> Also, does it actually make it costly, or do you only suspect that it
> does?  O(n^2) worst case sometimes behaves O(n) or O(n log n) in some
> cases.  Since your commit message says "made insertion costly" instead
> of "might make insertion costly", I think that would suggest you have
> some performance numbers to back this up on some interesting real
> world repository.  Do you?  Can you share them?
>

> > Replace `string_list_insert()` with `string_list_append()` to achieve
> > O(n) insertion. After all entries are added, sort the list in O(n log n)
> > and remove duplicates in O(n), reducing the overall complexity to
> > O(n log n).
>
> Okay.
>
> > This improves performance significantly for large datasets
>
> That's a big claim; it may be true, but without evidence I don't
> believe it for three reasons : (1) n here is the number of conflicts,
> not the number of files in the repo or the number of lines being
> merged.  Thus, n is typically small.  (2) Other O(n^2) behavior in
> merge-recursive likely drowns this particular codepath out, so any
> gains here just aren't going to be noticed, (3) After looking at the
> code and knowing the specialized structure of the index, I think that
> while string_list_insert() for n items in general is going to be
> O(n^2), it will likely functionally be O(n log n) for this particular
> code path, meaning you haven't actually improved the performance.
>
> > while maintaining correctness.
>
> More on that below.
>
>
> > Signed-off-by: Meet Soni <meetsoni3017@gmail.com>
> > ---
> >  merge-recursive.c | 10 +++++-----
> >  1 file changed, 5 insertions(+), 5 deletions(-)
> >
> > diff --git a/merge-recursive.c b/merge-recursive.c
> > index 884ccf99a5..6165993429 100644
> > --- a/merge-recursive.c
> > +++ b/merge-recursive.c
> > @@ -547,15 +547,15 @@ static struct string_list *get_unmerged(struct index_state *istate)
> >                 if (!ce_stage(ce))
> >                         continue;
> >
> > -               item = string_list_lookup(unmerged, ce->name);
> > -               if (!item) {
> > -                       item = string_list_insert(unmerged, ce->name);
> > -                       item->util = xcalloc(1, sizeof(struct stage_data));
> > -               }
> > +               item = string_list_append(unmerged, ce->name);
> > +               item->util = xcalloc(1, sizeof(struct stage_data));
> > +
> >                 e = item->util;
> >                 e->stages[ce_stage(ce)].mode = ce->ce_mode;
> >                 oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid);
>
> Did you run any tests?  I'm not sure you maintained correctness here.

>
> >         }
> > +       string_list_sort(unmerged);
> > +       string_list_remove_duplicates(unmerged, 1);
> >
> >         return unmerged;
> >  }
> > --
> > 2.34.1
>
> (As a side note, due to the specialized structure of the input, I
> suspect this code could be modified to run in O(n), i.e. we could skip
> the string_list_lookup and the string_list_sort and the
> string_list_remove_duplicates...  But, it'd make the code trickier, so
> it'd need to be carefully commented, the change would need to be
> justified, and it'd need to be carefully tested.  Even if we weren't
> planning to delete this entire file, I suspect it's not possible to
> find a case justifying such a change without optimizing several other
> things in merge-recursive first, but optimizing those things probably
> results in a significant rewrite...which we've already done with
> merge-ort.)