Re: [PATCH v3] sparse-checkout: optimize string_list construction
- From
Amisha Chhajed <amishhhaaaa@gmail.com>
- Date
- Jan 16, 2026, 08:30 UTC
- Message-ID
- <CAPvEtrdQ7LB4p0_yCg+ef6fsWSHwxA8C1uX0SJbfnV3vfQHD_g@mail.gmail.com>
- In-Reply-To
- <fc14e0e5-93bc-4805-a20d-d2aa4eb87ddb@web.de>
It was assumed to be safe under the notion that our entries are not duplicate but as already pointed out, our entries are not unique so we need one of those two ways either insert or remove_duplicates, this can be a trivial question but i wonder how are the tests passing by removing these lines, i was actually researching about it.
On Fri, 16 Jan 2026 at 03:56, René Scharfe <l.s.r@web.de> wrote:
Show 69 quoted lines
>
> On 1/15/26 2:15 PM, Amisha Chhajed wrote:
> > Made the changes for other 2 places as well!
> >
> > I was also very curious about the presence of
> > string_list_remove_duplicates in the original code, from my
> > understanding string_list_insert already removed duplicates and
> > string_list_remove_duplicates was still present with it.
>
> So the string_list_remove_duplicates() calls were unnecessary with
> string_list_insert(), but why is it safe to remove them now that you use
> string_list_append() instead, which doesn't check for duplicates?
>
> >
> > On Thu, 15 Jan 2026 at 18:39, amisha <amishhhaaaa@gmail.com> wrote:
> >>
> >> Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list'
> >> by constructing it unsorted and sorting it afterwards.
> >>
> >> Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>
> >> ---
> >> builtin/sparse-checkout.c | 8 +++-----
> >> 1 file changed, 3 insertions(+), 5 deletions(-)
> >>
> >> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c
> >> index 15d51e60a8..edabe7cbd9 100644
> >> --- a/builtin/sparse-checkout.c
> >> +++ b/builtin/sparse-checkout.c
> >> @@ -91,7 +91,7 @@ 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);
> >> @@ -289,11 +289,10 @@ 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);
> >> - string_list_remove_duplicates(&sl, 0);
> >>
> >> fprintf(fp, "/*\n!/*/\n");
> >>
> >> @@ -311,13 +310,12 @@ 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);
> >>
> >> string_list_sort(&sl);
> >> - string_list_remove_duplicates(&sl, 0);
> >>
> >> for (i = 0; i < sl.nr; i++) {
> >> char *pattern = escaped_pattern(sl.items[i].string);
> >> --
> >> 2.51.0
> >>
>