Re: [PATCH v5 1/2] sparse-checkout: optimize string_list construction
- From
Amisha Chhajed <amishhhaaaa@gmail.com>
- Date
- Jan 20, 2026, 15:47 UTC
- Message-ID
- <CAPvEtrcGYXeXWn-p=EipyE07gqNcP1qx_=V94cSD5XLwk4mdDg@mail.gmail.com>
- In-Reply-To
- <36b50d7d-b9f4-4ff3-b00e-9c98ad690749@gmail.com>
On Mon, 19 Jan 2026 at 22:34, Derrick Stolee <stolee@gmail.com> wrote:
Show 44 quoted lines
>
> 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.I was wondering if the string_list_remove_duplicates here is redundant as if we refer to the code that adds entries in the parent hashmap, refer:
from git/dir.c if (hashmap_get_entry(&pl->parent_hashmap, translated, ent, NULL)) { /* we already included this at the parent level */ warning(_("your sparse-checkout file may have issues: pattern '%s' is repeated"), given->pattern); goto clear_hashmaps; }
It does not add duplicates to it, and we are only iterating on parent_hashmap in this loop, the tests i have added in v6 do fail on removal of other string_list_remove duplicates lines in this file, however here i tried testing but i was not able to find a covering case for this line.
Show 13 quoted lines
> 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
Thank you it was a bit tricky to make the test fail directly on list command, i was able to do it in v6 after this guidance.