From: Amisha Chhajed <amishhhaaaa@gmail.com>
Date: Thu, 15 Jan 2026 13:15:35 GMT
Subject: Re: [PATCH v3] sparse-checkout: optimize string_list construction
Message-ID: <CAPvEtreX9sGHUn7+Y0kLo_VnK7Y=OYLq-kz-+np3bu1QtoEpnA@mail.gmail.com>
In-Reply-To: <20260115130935.93526-1-amishhhaaaa@gmail.com>

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.


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
>