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

From: Elijah Newren <newren@gmail.com>
Date: Feb 14, 2025, 06:04 UTC
Message-ID: <CABPp-BGq-x9Z98scXRtEnqz7BCmPn9ONHd6wDnnm9jL4YeDHxQ@mail.gmail.com>
In-Reply-To: <CAPhwyn0hz16mZ-UoVAczC4qDLx2i0LwfFhhDjdTahe0=4TO57g@mail.gmail.com>

On Thu, Feb 13, 2025 at 8:28 PM Meet Soni <meetsoni3017@gmail.com> wrote:

>
> On Thu, 13 Feb 2025 at 22:41, Elijah Newren <newren@gmail.com> wrote:
> >
> > On Thu, Feb 13, 2025 at 1:01 AM Meet Soni <meetsoni3017@gmail.com> wrote:

...

Show 26 quoted lines

> > > 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.
>
> I didn't run any tests -- I wanted to, but I wasn’t sure how to do it
> for this change. Since you suggested dropping this patch from the
> series, I’ll do that. But for similar changes in the future, how should I go
> about testing them?

As per Documentation/CodingGuidelines: "After any code change, make
sure that the entire test suite passes."  You can do that by running:
    cd t && make
(You probably want to also run that before making any changes, just to
verify that they all pass for you.  Then, if any test fails after you
make changes, you know it's because of your changes rather than
because you missed something in building or setting up the tests.)

And although it doesn't matter since we're dropping this patch, the issue I noticed was that if there were, say, three unmerged entries with the same path, the original code would create one entry in the string list and modify it 3 times (each with a different ce_stage(ce). Your modification would create three different entries (each with only information from one stage) and drop two of them, meaning we no longer have a single string_list_item that contains information from all 3 unmerged entries for the same path. I'm pretty sure running the existing tests would catch that kind of bug, which is what raised the question.