Re: [PATCH] sparse-checkout: optimize string_list construction

[Jeff King <peff@peff.net>]

On Thu, Jan 15, 2026 at 12:58:03AM +0530, amisha 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 <amishhhaaaa@gmail.com>

Thanks, I think the patch is an obvious improvement. In general, please
wrap your lines to something more reasonable (usually 70 or so is
common). And make sure your sign-off identity matches the DCO section of
Documentation/SubmittingPatches, in particular this part:

  Please use a known identity in the `Signed-off-by` trailer, since we cannot
  accept anonymous contributions. It is common, but not required, to use some form
  of your real name. We realize that some contributors are not comfortable doing
  so or prefer to contribute under a pseudonym or preferred name and we can accept
  your patch either way, as long as the name and email you use are distinctive,
  identifying, and not misleading.
  
  The goal of this policy is to allow us to have sufficient information to contact
  you if questions arise about your contribution.

I think what you have is probably sufficient, but if you are not opposed
to giving more identity information, we do usually prefer more full
names.

> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c
> index 15d51e60a8..0a44808ed2 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);

Since we already sort here, I was quite curious how this came about.  It
looks like the _insert() call and the _sort() were both added together
in de11951b03 (sparse-checkout: list directories in cone mode,
2019-12-30).

I'd guess it was just a typo/brain-o to mix up append and insert.

Doesn't the same issue exist in write_cone_to_file(), too (in two
separate spots)?

-Peff