Re: [PATCH v3] sparse-checkout: optimize string_list construction
- From
Amisha Chhajed <amishhhaaaa@gmail.com>
- Date
- Jan 15, 2026, 13:15 UTC
- 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:
Show 53 quoted lines
>
> 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
>