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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Thu, Feb 13, 2025 at 8:28 PM Meet Soni <meetsoni3017@xxxxxxxxx> wrote:
>
> On Thu, 13 Feb 2025 at 22:41, Elijah Newren <newren@xxxxxxxxx> wrote:
> >
> > On Thu, Feb 13, 2025 at 1:01 AM Meet Soni <meetsoni3017@xxxxxxxxx> wrote:
...
> > > 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.





[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]

  Powered by Linux