Re: [PATCH v5 1/2] sparse-checkout: optimize string_list construction

>
> On 1/19/2026 7:33 AM, amisha wrote:
> > From: Amisha Chhajed <amishhhaaaa@gmail.com>
> >
> > Improve O(n^2) complexity to O(n log n) while building a sorted
> > 'string_list' by constructing it unsorted then sorting it
> > followed by removing duplicates.
> >
> > Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>
> > ---
> >  builtin/sparse-checkout.c | 7 ++++---
> >  1 file changed, 4 insertions(+), 3 deletions(-)
> >
> > diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c
> > index 15d51e60a8..7dfb276bf0 100644
> > --- a/builtin/sparse-checkout.c
> > +++ b/builtin/sparse-checkout.c
> > @@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,
> >
> >               hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {
> >                       /* pe->pattern starts with "/", skip it */
> > -                     string_list_insert(&sl, pe->pattern + 1);
> > +                     string_list_append(&sl, pe->pattern + 1);
> >               }
> >
> >               string_list_sort(&sl);
> > +             string_list_remove_duplicates(&sl, 0);
>
> Shouldn't this line be added in the other uses of string_list_append()?
>
> >
> >               for (i = 0; i < sl.nr; i++) {
> >                       quote_c_style(sl.items[i].string, NULL, stdout, 0);
> > @@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)
> >               if (!hashmap_contains_parent(&pl->recursive_hashmap,
> >                                            pe->pattern,
> >                                            &parent_pattern))
> > -                     string_list_insert(&sl, pe->pattern);
> > +                     string_list_append(&sl, pe->pattern);
> >       }
> >
> >       string_list_sort(&sl);
> Actually, there is a string_list_remove_duplicates() just
> outside of the context of this diff.
>
> > @@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)
> >               if (!hashmap_contains_parent(&pl->recursive_hashmap,
> >                                            pe->pattern,
> >                                            &parent_pattern))
> > -                     string_list_insert(&sl, pe->pattern);
> > +                     string_list_append(&sl, pe->pattern);
> >       }
> >
> >       strbuf_release(&parent_pattern);
>
> Same here.
>
> This diff looks good, but I do believe it would be good to include your
> duplicate test here instead of in a second patch.
>
> Also, the way your second patch appeared as a trailer of your first patch,
> so it didn't appear properly as a thread in my email client. Here it is
> for review:
>
> > From b20a99f0773bab063a31eea6fead730e18200ca7 Mon Sep 17 00:00:00 2001
> > From: Amisha Chhajed <amishhhaaaa@gmail.com>
> > Date: Mon, 19 Jan 2026 00:20:47 +0530
> > Subject: [PATCH v5 2/2] t1091: Add tests for deduplication of cone-mode sparse
> >  patterns
>
> nit: this title is a little long and has incorrect capitalization. Take
> note for later, since I expect this diff to be squashed into the previous
> patch.
>
> > +test_expect_success 'sparse-checkout deduplicates repeated cone patterns' '
> > +    rm -f repo/.git/info/sparse-checkout &&
> > +    git -C repo sparse-checkout init --cone &&
> > +    git -C repo sparse-checkout add --stdin <<-\EOF &&
> > +     /foo/
> > +     /bar/
> > +     /foo/
> > +     EOF
>
> This slashes are redundant for cone-mode patterns. I recommend a more
> interesting case, such as
>
>         foo/bar/baz
>         a/b/c
>         foo/bar/baz
>         a/b
>
> This should remove the duplicates foo/bar/baz during the run, but also it
> should notice that a/b/c is contained within the recursive set defined by
> a/b.
>
> The resulting sparse-checkout file should have lines such as
>
>         /*
>         !/*/
>         /a/
>         !/a/*/
>         /a/b
>         /foo
>         !/foo/*/
>         /foo/bar
>         !/foo/bar/*/
>         /foo/bar/baz
>
> The order might be different, but this is what I recall from how nested
> directories work in cone mode.
>
> > +    cat >expect <<-\EOF &&
> > +     /*
> > +     !/*/
> > +     /bar/
> > +     /foo/
> > +     EOF
> > +    test_cmp expect repo/.git/info/sparse-checkout
> > +'
>
> > +test_expect_success 'sparse-checkout list deduplicates repeated cone patterns' '
> > +    rm -f repo/.git/info/sparse-checkout &&
> > +    git -C repo sparse-checkout init --cone &&
> > +    git -C repo sparse-checkout add --stdin <<-\EOF &&
> > +     /foo/
> > +     /bar/
> > +     /foo/
> > +     EOF
> > +    git -C repo sparse-checkout list >actual &&
> > +    cat >expect <<-\EOF &&
> > +     bar
> > +     foo
> > +     EOF
> > +    test_cmp expect actual
> > +'
>
> This does lead to an interesting case where the 'list' command was only
> interacting with the sparse-checkout file, which wouldn't have duplicates
> if it was modified by the user in cone mode.
>
> Keep in mind that you're not actually testing the 'list' command, because
> the 'add' command already deduplicated. You'll need to modify the
> sparse-checkout file itself to get an interesting test of the 'list'
> command.
>
> When not in cone mode, we should not be removing duplicates because the
> order of the patterns matters and we should not be reordering them. I'm
> not sure if that's relevant but it's something to keep in mind while you're
> testing, since the command will revert to non-cone mode if the
> sparse-checkout file doesn't match the cone mode pattern expectations.
>
> Thanks,
> -Stolee
>